OS structure — monolithic, microkernel, hybrid: Exercises

Level 1 — Recognition

Exercise 1.1 (L1)

Classify each kernel as Monolithic, Microkernel, or Hybrid: (a) Linux (b) MINIX 3 (c) Windows NT (d) QNX (e) macOS / XNU (f) classic UNIX.

Recall Solution 1.1

(a) Linux → Monolithic — services share kernel space, communicate by function calls. (b) MINIX 3 → Microkernel — FS/drivers are user-mode servers. (c) Windows NT → Hybrid — microkernel design but hot-path services pulled into kernel space. (d) QNX → Microkernel. (e) macOS / XNU → Hybrid — Mach microkernel core + BSD monolithic chunk. (f) classic UNIX → Monolithic. See Linux kernel modules, Windows NT architecture, XNU macOS kernel for how (a),(c),(e) are actually built.

Exercise 1.2 (L1)

In which mode does each run in a monolithic kernel: (a) the CPU scheduler, (b) a network device driver, (c) a text editor?

Recall Solution 1.2

(a) Kernel mode. (b) Kernel mode — this is the whole reason a driver bug can crash a monolithic system. (c) User mode — ordinary application.

Level 2 — Application

Exercise 2.1 (L2)

One boundary crossing costs $s = 1.0 μ s$ . A read() on a monolithic kernel takes $n = 2$ crossings; on a microkernel it takes $n = 6$ . Compute the communication overhead $C$ for each, and the ratio microkernel/monolithic.

Recall Solution 2.1

Apply $C = n \cdot s$ .

Monolithic: $C = 2 \times 1.0 = 2.0 μ s$ .
Microkernel: $C = 6 \times 1.0 = 6.0 μ s$ .
Ratio $= 6.0/2.0 = 3.0$ — the microkernel spends 3× the boundary overhead here. That single number is the classic speed criticism made concrete.

Exercise 2.2 (L2)

A microkernel read() chains through two user-mode servers: app → FS server → disk-driver server, and the answer flows back the same path. Using the convention "one boundary arrow = one crossing", enumerate every crossing (forward sweep and reply sweep) and total them.

Recall Solution 2.2

We walk the request literally, arrow by arrow. Each arrow that crosses the user/kernel wall is one crossing. Look at the chain diagram (figure below) as you count.

Forward sweep (request travelling outward):

app → kernel — the app traps in. (crossing 1)
kernel → FS server — kernel delivers the message out to FS. (crossing 2)
FS → kernel — FS forwards the request toward the driver, trapping back in. (crossing 3)
kernel → disk-driver server — kernel delivers it out to the driver. (crossing 4)

At this point the driver has the data. Now the answer comes home. Crucially the reply is forwarded straight back — the driver hands the data to the kernel, and the kernel returns it to the waiting app in a single reply sweep (we do NOT re-visit the FS server, because in this model the FS is blocked waiting and the kernel routes the completed reply to the original caller):

Reply sweep (answer travelling home): 5. driver → kernel — driver returns the data, trapping in. (crossing 5) 6. kernel → app — kernel delivers the finished data out to the app. (crossing 6)

Total $n = 6$ . This is the concrete $k = 2$ case of the general formula $n (k) = 2 k + 2$ derived in Exercise 4.1, and it matches Exercise 2.1's $n = 6$ .

Reconciling with "round-trip = 4 crossings": that 4-crossing figure is for a single leaf server you bounce off (2 out + 2 back). Here the two servers are chained, not bounced independently — the forward arrows are shared by the whole chain and the reply is one sweep, so a 2-server chain is 6, not $2 \times 4 = 8$ .

Level 3 — Analysis

Exercise 3.1 (L3)

Designer A claims: "Halving $s$ (faster traps) closes the gap between microkernel and monolithic." Using $C = n \cdot s$ with monolithic $n = 2$ , microkernel $n = 6$ , show what halving $s$ does to the ratio and refute or support the claim.

Recall Solution 3.1

Ratio $= \frac{n _{micro} \cdot s}{n _{mono} \cdot s} = \frac{n _{micro}}{n _{mono}} = \frac{6}{2} = 3.$ The $s$ cancels. Halving $s$ makes both faster but leaves the ratio at 3×. So faster traps help absolute latency but do not close the structural gap — that gap is set purely by the crossing count $n$ , which is a property of the structure, not of hardware speed. Claim refuted as stated.

Exercise 3.2 (L3)

A hybrid pulls the FS server back into kernel space. In the chained microkernel of Exercise 2.2 the FS server sat at crossings 2 and 3 (kernel→FS, then FS→kernel). Co-locating FS means those two hand-offs vanish (FS is now just a kernel function call). Starting from $n = 6$ , find the hybrid's $n$ , its $C$ at $s = 1.0 μ s$ , and its speedup over the microkernel.

Recall Solution 3.2

Which crossings disappear: in the Exercise 2.2 enumeration, crossing 2 (kernel→FS) and crossing 3 (FS→kernel) exist only because FS is a separate user process. Pull FS into the kernel and those two arrows become an in-kernel function call — 0 crossings. The remaining path is app→kernel→driver→kernel→app. Remove exactly those 2 crossings: $n_{hybrid} = 6 - 2 = 4$ . $C = 4 \times 1.0 = 4.0 μ s$ . Speedup over microkernel $= 6.0/4.0 = 1.5 \times$ . The hybrid "cheats" by co-locating the hot-path service, buying $1.5 \times$ here while keeping the driver isolated. Note it is still slower than monolithic ( $4.0$ vs $2.0 μ s$ ) — hybrids sit between, exactly as the reliability/speed ordering predicts.

(This is consistent with the convention: we removed the two boundary arrows that flanked the co-located server, not a whole 4-crossing leaf round-trip, because FS was a chained middle server contributing 2 arrows.)

Level 4 — Synthesis

Exercise 4.1 (L4)

Build the crossing count from scratch for a request that touches $k$ separate user-mode servers chained app → server $_{1}$ → server $_{2}$ → … → server $_{k}$ , with the answer forwarded back in a single reply sweep. Each boundary arrow is one crossing. Derive $n (k)$ , then evaluate for $k = 1, 2, 3$ .

Recall Solution 4.1

WHAT we count: every arrow that crosses the user/kernel wall, once. Trace the chain diagram (figure below).

Forward sweep — count the boundary arrows going out:

app → kernel → server $_{1}$ : that is 2 crossings (trap in, deliver out).
For each additional server the request is forwarded server $_{i}$ → kernel → server $_{i + 1}$ : that is 2 crossings per extra server. There are $k - 1$ such forwarding steps ⇒ $2 (k - 1)$ crossings.
So the forward sweep alone = $2 + 2 (k - 1) = 2 k$ crossings.

WHY the reply is only ONE sweep (not one per server): once server $_{k}$ has the answer, it does not walk the chain backwards visiting every intermediate server again. The intermediate servers are blocked waiting on their forwarded call; the completed answer is returned up the call stack, and the microkernel routes the final finished result to the original app. Concretely, the reply is: server $_{k}$ → kernel → app = 2 crossings, independent of $k$ . (Each intermediate server's "return" is an in-process resume, not a boundary arrow — it simply unblocks; the only boundary arrows on the reply are the last hand-off in and the final delivery out.)

Total: $n (k) = forward sweep 2 k + single reply sweep 2 = 2 k + 2.$ Check: $k = 1 \Rightarrow n = 4$ ; $k = 2 \Rightarrow n = 6$ (matches the FS+driver chain of Exercise 2.2!); $k = 3 \Rightarrow n = 8$ . The formula is linear in $k$ — every extra isolated server on the forward path adds a fixed $2$ , while the reply cost stays constant. That linear growth is the microkernel's structural tax, and it's why designers minimise the number of servers on any hot path.

Exercise 4.2 (L4)

Given $n (k) = 2 k + 2$ and monolithic constant $n_{mono} = 2$ , at what $k$ does the microkernel become 4× the monolithic overhead?

Recall Solution 4.2

Ratio $= \frac{2 k + 2}{2} = k + 1$ . Set $k + 1 = 4 \Rightarrow k = 3$ . So touching 3 servers yields a 4× overhead ratio. This gives a designer a hard rule: keep hot-path server chains to $k \leq 1$ if you want to stay within 2× of monolithic.

Level 5 — Mastery

Exercise 5.1 (L5)

You are designing an OS for a medical ventilator (must never crash) that also streams high-rate sensor data (needs low latency). Using $C = n \cdot s$ and $n (k) = 2 k + 2$ , argue for a hybrid design: which one service do you pull into kernel space and what is the quantified benefit? Assume the reliability-critical part is the FS and the latency-critical part is the sensor-driver, and pure microkernel touches both ( $k = 2$ , $n = 6$ ).

Recall Solution 5.1

Reliability constraint says: keep as much as possible isolated (microkernel-like), so a driver bug can't kill the ventilator — the whole point of a medical device. Latency constraint says: the sensor-driver is on the hot path; pulling it into kernel space removes its round-trip. Pull only the sensor-driver into kernel space → $k$ drops from 2 to 1 → $n (1) = 2 (1) + 2 = 4$ . Quantified benefit: at $s = 1.0 μ s$ , $C$ goes $6.0 \to 4.0 μ s$ , a $6/4 = 1.5 \times$ speedup on the sensor path, while the FS stays isolated for safety. This is textbook hybrid reasoning: isolate the risky, co-locate the hot. Windows NT and XNU made exactly this class of choice.

Exercise 5.2 (L5)

Prove the speed ordering Monolithic $\geq$ Hybrid $\geq$ Microkernel for any request, using $n_{mono} = 2$ , $n_{hybrid} = 2 k_{h} + 2$ , $n_{micro} = 2 k + 2$ with $0 \leq k_{h} \leq k$ (hybrid co-locates some servers, so it touches fewer isolated servers $k_{h}$ ).

Recall Solution 5.2

Since $C = n \cdot s$ and $s > 0$ is common, compare the $n$ 's.

$n_{mono} = 2 = 2 (0) + 2$ , i.e. $k = 0$ (nothing isolated).
Because $0 \leq k_{h} \leq k$ and $n (k) = 2 k + 2$ is increasing in $k$ : $n (0) \leq n (k_{h}) \leq n (k) \Rightarrow 2 \leq 2 k_{h} + 2 \leq 2 k + 2.$ Multiplying by $s > 0$ preserves order: $C_{mono} \leq C_{hybrid} \leq C_{micro} .$ Lower $C$ = faster, so Monolithic $\geq$ Hybrid $\geq$ Microkernel in speed — matching the mnemonic MONO > HYBRID > MICRO, now proved rather than memorised. Reliability is the reverse because isolated servers ( $hi g h er k$ ) contain crashes.

The picture behind the counting

The figure below is the chain we enumerated in Exercises 2.2 and 4.1. Read it left-to-right for the forward sweep (orange arrows: app traps in, kernel forwards to each server) and right-to-left for the single reply sweep (plum arrows: the finished answer returns straight to the app). Count the arrows crossing the dashed user/kernel wall and you get exactly $n (k) = 2 k + 2$ — here $k = 2$ gives $6$ crossings. This is the visual that makes Exercise 2.2's "6, not 8" and Exercise 3.2's "remove the 2 FS arrows" obvious at a glance.

Figure — OS structure — monolithic, microkernel, hybrid

Recall One-line self-test

Why can't faster CPUs make a microkernel beat a monolithic kernel? ::: Because the speed ratio equals $n_{micro} / n_{mono}$ and $s$ cancels — the gap is structural (crossing count), not hardware-bound.