CEUC301 · UNIT 8 OF 9

I/O Subsystem
& Storage
System Design

Chapter 7 treated "a disk access" as a given — something that simply cost accesses, full stop. This chapter opens that box. An access is a CPU that has to notice a device is ready, a controller that may or may not need the CPU's help moving the bytes, and — if the device is a spinning disk — an arm that has to physically travel somewhere before any byte moves at all. How the OS handles all three of those decides whether T_save's autosave costs microseconds or seconds.

Colour contract Linux — primary OS Windows — secondary OS process-level — a whole process, allocated resource, or the request/buffer currently active thread-level — a request issued by one of WriteWell's own threads (T_ui or T_save)

The spine, one layer down. Every I/O request in this chapter still traces back to WriteWell: T_save's autosave writes (two data blocks, the inode, the freemap — the same four-block transaction from 7.2), T_ui's rereads for redisplay, and the 340 KiB embedded image that made DMA worth inventing in the first place. New this chapter: WriteWell doesn't have the disk to itself. A second process, MailSync, is quietly reading its own files in the background — every scheduling decision from 8.3 onward has to arbitrate between the two. 8.1 asks how a byte gets from the disk controller into memory at all; 8.2 asks what happens to it once it's there; 8.3 through 8.5 ask what order the disk should service everyone's requests in, and what that choice costs in practice.

8.1 · INTERRUPT HANDLING & DMA DESIGN

Getting Bytes Off the Disk Without Asking the CPU to Carry Each One

T_save is about to hand the disk 340 KiB of image data. Something has to notice when the disk is ready for the next chunk, and something has to actually move the bytes. Who does that job changes the cost by five orders of magnitude.

Every I/O device is slower than the CPU waiting on it — a disk controller measures its own readiness in milliseconds, the CPU measures a clock cycle in nanoseconds. The OS has three fundamentally different ways to bridge that gap, and they differ in exactly one thing: how often the CPU has to stop what it's doing and personally handle a chunk of the transfer.

Three ways to move the same bytes

Picture filling a water tank from a well. Programmed I/O is carrying every bucket yourself, standing at the well the whole time, checking "is it full yet? is it full yet?" — you do nothing else until the tank is full. Interrupt-driven I/O is going back to your other chores, but the well rings a bell every single time a bucket fills, and you have to walk over and carry that one bucket before returning to what you were doing. DMA (Direct Memory Access) is hiring a pipe: you tell it where the water starts, where it should end up, and how much to move, then you leave entirely — the pipe rings the bell exactly once, when the whole tank is full.

What changes between them
  • Programmed I/O: CPU polls a status register in a tight loop, 100% busy, zero interrupts, one register-check per unit transferred.
  • Interrupt-driven I/O: CPU is free between units, but pays a full context-save → ISR → context-restore cycle for every single unit transferred.
  • DMA: CPU is free for the entire transfer and pays that same interrupt cost exactly once, regardless of how large the transfer is.
The one thing people get backwards
  • DMA still uses an interrupt. It hasn't eliminated interrupts — it's collapsed thousands of them into one.
  • Programmed I/O isn't "interrupt-driven done badly." It uses no interrupts at all; the CPU is pinned at 100% the entire time, which is worse in a different way.

The mechanics: interrupt vector, ISR, and the DMA controller's four registers

An interrupt is a signal a device sends on a dedicated line that makes the CPU stop the instruction stream, save enough state to resume later (program counter, key registers), and jump to an interrupt service routine (ISR) looked up by device number in the interrupt vector table — a fixed array of ISR addresses set up at boot. When the ISR finishes, the saved state is restored and the interrupted program resumes exactly where it left off, unaware anything happened. That save/restore round trip is not free: real systems spend roughly 50–200 CPU cycles on it per interrupt, on top of whatever work the ISR itself does.

A DMA controller is a small piece of hardware the CPU programs once per transfer, with four pieces of information: the source address, the destination address, the count (how many words), and the direction (read or write). Once programmed, the DMA controller negotiates for the memory bus itself — either taking it for a whole burst (burst mode) or borrowing one bus cycle at a time between CPU accesses (cycle stealing, which slows the CPU slightly but never stalls it completely) — and moves every word directly between the device and memory without routing through a CPU register at all. Only when count reaches zero does it raise the one interrupt that tells the CPU the whole job is done.

interrupt-driven housekeeping cost, per transfer total cycles  =  (words moved) × (cycles per interrupt)  —  scales with the SIZE of the transfer

DMA housekeeping cost, per transfer total cycles  =  (setup cycles) + (one completion-interrupt cost)  —  constant, independent of size
Worked example 8.1
interrupt-driven vs. DMA
T_save writes WriteWell's 340 KiB embedded image (the same image from 7.1's spine) to disk, 4 bytes at a time, on a 2 GHz CPU where each interrupt costs 100 cycles (context-save + ISR + restore). How much CPU time does housekeeping alone cost under interrupt-driven I/O, versus DMA?
Step 1 · words to move

340 KiB = 340 × 1,024 = 348,160 bytes. At 4 bytes/word: 348,160 ÷ 4 = 87,040 words.

Step 2 · interrupt-driven cost

87,040 words × 100 cycles/word = 8,704,000 cycles. At 2 GHz (2×109 cycles/s): 8,704,000 ÷ 2,000,000,000 = 4.352 ms of pure housekeeping — before a single byte's actual transfer instruction is counted.

Step 3 · DMA cost

Setup (loading 4 registers) ≈ 20 cycles. One completion interrupt ≈ 100 cycles (the same per-interrupt cost as above — DMA doesn't get a cheaper interrupt, it just needs one). Total = 120 cycles = 120 ÷ 2,000,000,000 = 0.00006 ms (60 nanoseconds).

Answer — 4.352 ms (interrupt-driven) vs. 60 ns (DMA): a 72,533× reduction in CPU cycles spent on housekeeping, for transferring the exact same bytes. Neither number includes the disk's own seek and rotational delay (8.5) or the transfer instructions themselves — this is purely the cost of the CPU noticing and responding to the device, which DMA nearly erases.
Transfer-cost comparator
interactive
 

It opens on Worked Example 8.1 (340 KiB, word granularity). Switch to byte-at-a-time and watch interrupt-driven cost jump 4× while DMA's bar doesn't move at all — DMA's cost has nothing to do with how finely the transfer is chopped up.

Pitfalls
  • "DMA has no interrupts." It has exactly one, always. What DMA eliminates is the per-word repetition, not interrupts as a concept.
  • "Cycle stealing is a context switch." It isn't. The CPU pauses for a single bus cycle between decode and operand fetch and resumes with all its registers exactly as they were — no state is saved anywhere, which is precisely why it's so much cheaper than an interrupt.
  • "Faster granularity always helps." It helps interrupt-driven I/O enormously (fewer, bigger interrupts) and does nothing at all for DMA, whose cost is already independent of granularity. Confusing the two leads to "optimizations" that speed up code that was never the bottleneck.

Practice

  1. WriteWell's spell-checker loads a 64 KiB dictionary file at startup, 4 bytes at a time, on the same 2 GHz / 100-cycles-per-interrupt system. Compute the interrupt-driven housekeeping cost in milliseconds.
    Show solution

    64 KiB = 65,536 bytes ÷ 4 = 16,384 words. 16,384 × 100 = 1,638,400 cycles ÷ 2×109 = 0.819 ms.

  2. The same dictionary load, but the interrupt controller on this particular board is slower — 220 cycles per interrupt instead of 100. Recompute, and say in one sentence why DMA's advantage over interrupt-driven I/O only grows on slower hardware.
    Show solution

    16,384 × 220 = 3,604,480 cycles ÷ 2×109 = 1.802 ms (more than double). DMA's completion interrupt also costs more on this board (220 instead of 100 cycles), but it only pays that cost once; interrupt-driven I/O pays the increase 16,384 times over. Any per-interrupt slowdown is multiplied by the transfer size for interrupt-driven I/O and barely felt by DMA.

  3. A vendor claims their new controller "uses DMA, so it never bothers the CPU." A colleague objects that this can't be literally true. Who's right, and what's the one moment the CPU is still involved?
    Show solution

    The colleague. DMA still requires the CPU to program the transfer up front (source, destination, count, direction) and still delivers exactly one completion interrupt at the end. "Never bothers the CPU" is marketing shorthand for "doesn't bother it per word" — the two unavoidable touches (setup, completion) are the entire reason DMA needs an interrupt vector entry at all.

  4. Chapter 7.1 found that reaching a block in WriteWell's document through double-indirection costs 2 extra disk accesses beyond direct access. Does giving the disk controller DMA reduce that count from 2 to something smaller?
    Show solution

    No. DMA makes each of those disk accesses cheaper for the CPU to service (near-zero housekeeping instead of hundreds of interrupts' worth), but it does not change how many accesses the indirection scheme requires — that count is a property of the file system's addressing structure (7.1), not of how bytes travel once the disk has found them. DMA and indexed allocation solve two completely different layers of the same access; fixing one doesn't touch the other.

8.2 · BUFFER CACHE & I/O SCHEDULING

The Waiting Room Between Memory and Disk

T_save's autosave rewrites the same inode and freemap blocks every few seconds. T_ui re-reads blocks it displayed moments ago every time the user scrolls. Going to disk for either is often unnecessary — if the block is still sitting in memory from last time.

Between "the OS wants a block" and "the disk actually spins to find it" sits a layer of memory called the buffer cache: a pool of frames, each able to hold one disk block, populated on demand as blocks are read or written. The next request for that same block checks the cache first. Find it there, and the request finishes in the time it takes to copy memory to memory — no seek, no rotational wait, nothing that touches the disk at all.

Hits, misses, and what happens to a write

A cache hit means the requested block is already resident; a cache miss means the OS has to actually read it from disk first (and evict some other block to make room, if the cache is full — using the same kind of replacement policy 6.2 used for page frames; a buffer cache is a memory hierarchy exactly the way a TLB or a page table is, just one level further from the CPU). Reads are the easy case: a hit returns a copy, done. Writes are where a real design decision appears.

write-through
  • Every write to a cached block is immediately mirrored to disk.
  • The cache and the disk are never out of sync for more than one write's duration.
  • Cost: every write pays full disk-access latency, cache or not — the cache only helps reads.
write-back
  • A write only touches the cached copy, marks it dirty, and returns immediately.
  • The dirty block is flushed to disk later — on eviction, at a periodic sync, or at shutdown.
  • Cost: a block written N times before its one flush pays for exactly one physical write, not N — but anything still dirty when the system crashes is lost.
This is not a substitute for 7.2's journal

Write-back caching and crash-consistency journaling solve adjacent but different problems. The buffer cache decides when a write reaches disk at all, purely for performance. The journal (7.2) guarantees that when a multi-block transaction's writes do reach disk, they land as an all-or-nothing unit. A dirty, not-yet-flushed block sitting in the buffer cache is in fact exactly the kind of unrecorded change a journal's commit record is designed to make recoverable — the two mechanisms cooperate; neither replaces the other.

Worked example 8.2a
write-back savings, 3 autosaves
T_save autosaves three times in a row. Each autosave rewrites 2 fresh data blocks plus the (shared) inode and freemap blocks — 7.2's four-block transaction, repeated three times. Under write-through, how many physical disk writes happen? Under write-back with no flush until the session ends, how many?
Step 1 · the touch sequence

D1, D2, I, F  /  D3, D4, I, F  /  D5, D6, I, F — 12 touches total. Inode (I) and freemap (F) each appear 3 times; the six data blocks appear once each.

Step 2 · write-through

Every touch is a physical write. 12 disk writes.

Step 3 · write-back

Only the final value of each distinct block ever needs to reach disk. Distinct blocks touched: D1–D6, I, F — 8. 8 disk writes.

Answer — 12 vs. 8: 4 writes saved (33% fewer), entirely because I and F's redundant middle writes never had to leave memory. The savings scale with how often the same metadata block gets rewritten before its eventual flush — exactly the inode and freemap, autosave after autosave.
Buffer-cache stepper (LRU, 4 frames)
interactive
step 0 of 15
 

The trace: I, D1, D2, F, D1 (T_ui rereads the block it just helped write), then the same shape twice more with D3/D4 and D5/D6. Step through it and watch which block gets evicted each time capacity-4 runs out.

Pitfalls
  • "A bigger cache always helps proportionally." It only helps the blocks that are actually reused before eviction. WriteWell's freemap is touched exactly as often as its inode (once per autosave) but, in the traced example, never survives long enough between touches to score a hit — frequency of reuse means nothing without closeness of reuse.
  • "Write-back is just a faster write-through." It's faster and weaker: write-through never has data that exists only in memory, so it survives a crash by construction. Write-back's speed is borrowed directly from the durability write-through would have guaranteed.
  • "Caching reads and caching writes are the same mechanism." Caching a read is just "keep a copy." Caching a write requires a policy decision (dirty bit, flush timing) that reads never need — a read never leaves the cache in a state the disk doesn't already match.

Practice

  1. A block is read once, then written four times in a row before the session ends and everything flushes. How many physical disk operations does write-back cost for this one block, and how many would write-through have cost?
    Show solution

    Write-back: 2 — one read (the initial miss) and one write (the final flush); the four intermediate writes only touch the cached, dirty copy. Write-through: 5 — the same one read, plus all four writes hitting disk individually.

  2. Redo 8.2a's write-back count, but this time the buffer cache only has room for 6 frames, and D1 and D2 get evicted (to make room for D3–D6) before the session's final flush. How many physical writes now?
    Show solution

    10. D1 and D2 are each flushed once when evicted (2 writes) plus flushed again... no — once evicted, a clean copy leaves no dirty data behind, so eviction itself triggers exactly one write per evicted dirty block, and that block is done. So: D1 evicted (1 write), D2 evicted (1 write), then D3–D6, I, F flush at session end (6 writes) = 8 total — identical to the unconstrained case, because eviction just moves a block's one necessary write earlier in time rather than adding an extra one. Limited capacity changes when write-back pays its writes, not how many, as long as nothing is written again after being evicted.

  3. In the LRU stepper above, the freemap block F is touched three times (once per autosave) yet scores zero hits, while the inode I is also touched three times and scores two hits. Both are touched equally often — why does one benefit from the cache and the other doesn't?
    Show solution

    Because I's touches are followed almost immediately by another reference to I (the very next autosave's inode update, or a T_ui reread), while F's touches are each followed by enough other distinct block references (4, in this trace) to exceed the 4-frame capacity before F is needed again. Hit ratio depends on the distance between reuses, not just their count — the same fact 6.2 established for page replacement.

  4. 7.2 showed that ordered journaling mode forces data blocks to disk before the metadata transaction referencing them commits. Explain why a write-back buffer cache makes that ordering guarantee something the file system has to actively enforce, rather than something that happens for free.
    Show solution

    Without write-back, "write the data block" already means "it's on disk" by the time the call returns, so any ordering the code expresses in source order is automatically the ordering that reaches disk. With write-back, a written block is only logically durable-later; the buffer cache is free to flush blocks in whatever order is convenient for it (least recently used, cheapest seek, whatever) unless the file system explicitly forces a flush of the data block first. ordered mode's entire job is inserting that forced flush — without it, a write-back cache could flush the inode update before the data it points to, recreating exactly the stale-pointer risk 7.2 built journaling to prevent.

8.3 · DISK SCHEDULING ALGORITHMS

Eight Requests, One Arm, Five Different Orders

T_save's autosave (4 blocks), T_ui's two rereads, and MailSync's two background reads are all waiting at once. The disk can only be in one place at a time — the order it visits these eight cylinders in is a scheduling decision, exactly like 2.2's CPU scheduling, just one layer down.

Moving the read/write head from one cylinder to another — the seek — is, on a mechanical disk, the single most expensive part of an access: milliseconds, versus the microseconds or less that actually reading the data takes once the head arrives. Disk scheduling exists to pick the order of a pending request queue so the arm's total travel is small. Think of the head as an elevator and the requests as floor buttons already pressed: different elevator policies answer "who gets picked up next" very differently.

Five policies

Disk scheduling algorithms, in the order this section covers them
AlgorithmRuleMain weakness
FCFSService requests in arrival order. No reordering at all.Ignores geometry entirely — the arm can crisscross the disk pointlessly.
SSTFAlways service whichever pending request is closest to the head's current position.Greedy: a request far from the current cluster of activity can wait indefinitely if closer ones keep arriving (8.4).
SCANSweep to one physical end of the disk, servicing every request passed along the way, then reverse and sweep to the other end.Wastes motion sweeping past the last real request all the way to an empty boundary.
C-SCANLike SCAN, but after reaching one end, jump back to the start and sweep the same direction again — never reverse.The jump-back is real arm travel that services nothing; higher total movement in exchange for more uniform waits.
LOOKLike SCAN, but reverse at the last real request in each direction — never overshoot to an empty boundary.Still not immune to 8.4's fairness problem the way SSTF is not, though far less severe.
Convention note — where SCAN and LOOK's textbook wording disagrees

Every source agrees SCAN forces a full sweep to the disk's physical end on its first leg, even past the last pending request, and that LOOK never does. Some courses also have SCAN force a full sweep to the opposite end on the return leg; others let it stop once the last request going that way is serviced. This chapter uses the stricter version — SCAN always touches both physical ends (cylinder 0 and the disk's last cylinder), LOOK never travels past the outermost pending request in either direction — because it's the version that keeps every SCAN-vs-LOOK comparison below unambiguous. If your lecture slides do it the other way, only the second leg's total changes; the first leg, and the entire reason LOOK exists, does not.

Worked example 8.3
200-cylinder disk, head at 60
Disk has cylinders 0–199. Head is at 60. Pending queue, in arrival order: 95 (T_save data #1), 173 (T_save data #2), 30 (T_save inode), 145 (T_save freemap), 12 (T_ui read #1), 70 (T_ui read #2), 186 (MailSync read #1), 48 (MailSync read #2). Find the total head movement under each of the five policies.
FCFS

Service in arrival order: 95, 173, 30, 145, 12, 70, 186, 48. Movement = |95−60|+|173−95|+|30−173|+|145−30|+|12−145|+|70−12|+ |186−70|+|48−186| = 35+78+143+115+133+58+116+138 = 816.

SSTF

Nearest-remaining, greedily: 60→70(10)→48(22)→30(18)→12(18)→95(83) →145(50)→173(28)→186(13). Total = 242. Notice the 83-unit jump back across the disk once the near cluster is exhausted — greedy locally, expensive globally, exactly once.

SCAN (upward first)

Up-sweep (≥60, ascending): 70, 95, 145, 173, 186, then on to boundary 199. Down-sweep: reverse all the way to boundary 0, passing 48, 30, 12 along the way. Movement = (126 among the up-set) + 13 (186→199) + 199 (199→0, servicing 48/30/12 en route) = 338.

C-SCAN (upward first)

Up-sweep identical to SCAN: 126 + 13 (to boundary 199) = 139. Jump back to 0: +199. Continue upward again from 0 through 12, 30, 48 (ascending, not reversed): +48. Total = 139+199+48 = 386.

LOOK (upward first)

Up-sweep: 70, 95, 145, 173, 186 (126 units, no boundary overshoot). Reverse directly to the nearest remaining request, 48: +138. Continue down through 30, 12: +18+18. Total = 126+138+18+18 = 300.

Answer — FCFS 816, SSTF 242, SCAN 338, C-SCAN 386, LOOK 300. SSTF wins this particular static snapshot on raw distance; LOOK comes second while never overshooting an empty boundary the way SCAN does; C-SCAN pays the most because its "never reverse" fairness guarantee costs a full extra traverse of the disk on every pass.
Disk-scheduling animator
interactive
step 0 of 8
 

Violet markers are WriteWell's own threads (T_save, T_ui); neutral markers are MailSync's. Step through any algorithm to watch the head's path and running total build up to the worked example's answer above.

Pitfalls
  • "SSTF is just SCAN with extra steps." They can coincide by chance on friendly data (nearby requests happen to sit in sweep order) but SSTF has no concept of a sweep direction at all — it can reverse direction after every single request if the data calls for it, which is exactly what produces both its low totals on easy inputs and its starvation risk on hostile ones (8.4).
  • "LOOK and SCAN always give different totals." Only when the outermost requests don't sit exactly at cylinder 0 or the disk's last cylinder. If a request happens to be sitting right at the boundary, LOOK's "stop at the last request" and SCAN's "go to the boundary" become the same instruction.
  • "Lower total movement is strictly better." It's better for throughput. It says nothing about whether any individual request had to wait an unreasonably long time to be serviced — SSTF's 242 total in the worked example hides exactly that trade-off, unpacked in 8.4.

Practice

  1. Same disk, same head position (60), but the queue is just three requests: 65, 67, 63. Compute FCFS's total movement given arrival order 65, 67, 63.
    Show solution

    |65−60|+|67−65|+|63−67| = 5+2+4 = 11.

  2. Same three requests (65, 67, 63), head at 60, but now compute SSTF instead. Explain why, for a cluster of requests this close together, SSTF, SCAN, and LOOK are all guaranteed to produce the same order regardless of which one you pick.
    Show solution

    SSTF: 60→63(3)→65(2)→67(2) = 7. All three requests lie on the same side of the head (all ≥60) and are close enough together that "nearest remaining" and "next one encountered while sweeping upward" describe the identical sequence (63, 65, 67) — there is no far-side cluster to create a conflict between greedy-nearest and directional-sweep behavior. The algorithms only diverge when requests exist on both sides of the head.

  3. A queue produces a SCAN total of 400 and a LOOK total of 310 on the same disk and head position. Without knowing the actual cylinder numbers, what does the 90-unit gap tell you about where the outermost requests in this queue sit relative to the disk's physical boundaries?
    Show solution

    It tells you the outermost pending requests in at least one direction (likely both) sit well short of cylinders 0 and the disk's last cylinder — SCAN paid for travelling all the way to those empty boundaries and back, which LOOK skipped entirely. A small gap would mean the real requests already sit near the boundaries (little wasted travel either way); a 90-unit gap means there's substantial empty disk beyond the last real request on at least one side.

  4. Chapter 7.2 defined a crash-consistency transaction as data blocks reaching disk before the metadata that references them commits (ordered mode). In the worked example above, T_save's inode write (cylinder 30) is serviced after both of its data writes (95, 173) under LOOK — check the order above and confirm this, then explain why a disk scheduler reordering requests is not, by itself, a threat to that guarantee.
    Show solution

    LOOK's order was 70, 95, 145, 173, 186, 48, 30, 12 — inode (30) at position 7, both data writes (95, 173) at positions 2 and 4, well before it. This is safe precisely because the ordering guarantee is about data-before-commit, and the disk scheduler servicing data first (incidentally) or last doesn't matter as long as the file system never issues the metadata write until it already knows the data write completed — the scheduler is free to reorder the requests it has, but the file system controls when a request enters the queue at all. 7.2's guarantee lives in that submission order, not in whatever order the disk happens to service a batch that's already been submitted.

8.4 · DISK SCHEDULING UNDER MIXED WORKLOADS

What Happens While the Queue Keeps Filling

8.3's queue was a snapshot: eight requests, then nothing. Real disks never get that luxury — new requests keep arriving while old ones are still being serviced. That changes which algorithm is actually "best" in a way a single static total can't show.

Every algorithm in 8.3 was scored on one number: total head movement for one fixed batch. That number answers "how much total work did the arm do," but it says nothing about whether any one request sat waiting an unreasonable amount of time while others kept cutting in front of it. Once requests arrive continuously — the realistic case — that second question, not the first, is usually what actually determines whether the system feels responsive.

Where each algorithm's promise comes from

FCFS and SSTF both make their next decision by looking at whatever is currently pending the moment the head is free. SCAN and LOOK are different: at the instant a sweep begins in a direction, the set of requests it will honor during this pass is already fixed by which side of the head they sit on. A request that arrives behind the head has to wait for the reversal no matter how loudly it asks; a request already ahead of the head is guaranteed service before the sweep turns around, regardless of anything that shows up in the meantime. That guarantee — a request is serviced within one bounded sweep, full stop — is the entire reason SCAN and LOOK exist despite neither minimizing total movement the way SSTF can.

Worked example 8.4
continuous arrival, same base queue
Take 8.3's queue and run SSTF. The moment the head finishes servicing the near cluster (70, 48, 30, 12 — steps 1–4) and sits at cylinder 12, three new nearby requests trickle in one at a time: 18, then 25, then 33. Compare against LOOK on the same original queue.
SSTF under continuous arrival

Steps 1–4: 70, 48, 30, 12 (the near cluster, as in 8.3). At step 4 the head is at 12; 18 arrives and, at distance 6, beats every remaining far-cluster request (nearest far one, 95, is 83 away). Step 5: 18. Then 25 arrives, beats the far cluster again. Step 6: 25. Then 33 arrives, same story. Step 7: 33. Only now, with nothing closer left, does SSTF turn to the far cluster: steps 8–11 service 95, 145, 173, 186.

Where T_save's writes land

T_save's two data writes (95, 173) were requests #1 and #2 in the original arrival order — submitted before every other request in the queue. Under this continuous-arrival SSTF, they are serviced 8th and 10th out of 11. Three requests that didn't even exist yet when T_save asked to save cut in line ahead of it, three separate times.

LOOK on the same base queue

LOOK's up-sweep (fixed the instant the sweep direction is chosen) already contains 95, 145, 173, 186 — they are serviced at sweep positions 2 through 5, before the head ever reaches 12 and before 18/25/33 exist. Nothing that arrives afterward, however close to the head, can insert itself ahead of a request already scheduled for the current sweep.

Answer — under a steady trickle of nearby arrivals, SSTF can defer far-cluster requests indefinitely: each new nearby arrival is, by construction, closer than the wait that's already accumulated. LOOK bounds the wait for any request already ahead of the head to "at most one sweep," regardless of how many new nearby requests show up. This is exactly why production disk schedulers build on SCAN/LOOK-family algorithms rather than pure SSTF, despite SSTF's better raw total in 8.3's snapshot.
Starvation stepper
interactive
step 0
 

New arrivals (18, 25, 33) appear as they trickle in at steps 4–6. Watch T_save's two data writes (95, 173) — amber once serviced, still waiting otherwise — under each policy.

Pitfalls
  • "This requires an adversarial workload to happen." It doesn't — a user actively scrolling or typing generates exactly this pattern: many small requests clustered near wherever attention currently is. SSTF starvation is a normal interactive workload's natural consequence, not an edge case someone has to construct on purpose.
  • "FCFS avoids this problem, so it's underrated." FCFS is indeed immune to starvation — every request's wait is bounded by the queue length at the moment it arrived, since nothing can ever cut in front of it. But 8.3 already showed FCFS pays for that immunity with by far the worst total movement. Immunity to starvation and good average performance are a genuine trade-off, not something either FCFS or SSTF gets for free.
  • "SCAN/LOOK solve fairness completely." They bound the wait to one sweep, which is a real guarantee, but one sweep on a busy disk with hundreds of pending requests can still be a long time. Production schedulers add explicit deadlines or priority boosting on top of a SCAN/LOOK base precisely because "one sweep" isn't always a tight enough bound.

Practice

  1. Using this section's continuous-arrival trace, at what step is MailSync's request at cylinder 186 finally serviced under SSTF?
    Show solution

    Step 11, the very last one — it's the farthest request from the near cluster once the head starts at 60, so every closer request (original or newly-arrived) is serviced first.

  2. Suppose the three new arrivals had instead appeared at 90, 92, and 94 (near the far cluster, not the near one). Would SSTF still defer T_save's data writes (95, 173) the way it did in the worked example? Explain.
    Show solution

    No, or at least not as severely. Arrivals at 90/92/94 sit right next to 95 — once the head is anywhere near that neighborhood, they'd be serviced alongside 95 rather than in place of it, and wouldn't repeatedly out-compete it for "closest pending request" the way arrivals near the head's current (far-away) position did. SSTF's starvation risk is specifically about new arrivals landing near wherever the head currently is, not simply about new arrivals existing.

  3. A monitoring dashboard reports "average seek time: 4ms" for a disk running SSTF under heavy interactive load. A teammate concludes the disk is serving all requests promptly. What question would you ask before agreeing?
    Show solution

    Something like: "what's the worst-case or tail wait, not the average?" A low average is entirely consistent with the 8.4 pattern — most requests (the near cluster) are serviced very quickly, while a small number of far requests wait far longer than average, and their long waits get diluted into an average across many fast ones. SSTF can look excellent on average while still starving specific requests.

  4. 7.2 established that ordered journal mode's data-before-commit guarantee depends on the data write actually reaching disk promptly. If the disk is running SSTF under the kind of continuous nearby arrival this section describes, what real risk does that create for an autosave transaction whose data blocks happen to sit far from the current cluster of activity?
    Show solution

    The data blocks could sit in the queue, unwritten, for an arbitrarily long time while nearby requests keep cutting ahead — and until they're actually on disk, the metadata transaction referencing them cannot safely commit either (7.2's whole point). The autosave isn't just slow in this scenario; it's an open transaction sitting vulnerable for longer than intended, which is precisely the kind of risk that motivates real systems to avoid pure SSTF for anything with durability requirements.

8.5 · STORAGE/RETRIEVAL PERFORMANCE TRADE-OFFS

Does Any of This Matter Without a Moving Arm?

8.1 through 8.4 all assumed a mechanical disk with something worth optimizing: a physical arm that takes time to move. Solid-state storage has no arm. Does that make everything this chapter just covered obsolete, or just differently expensive?

A traditional HDD pays three costs for every access that isn't already under the head: seek time (moving the arm to the right cylinder), rotational latency (waiting for the right sector to spin underneath), and transfer time (actually reading once both are true). An SSD has no arm and nothing spinning — a NAND flash read is a near-constant-time electrical operation regardless of which cell is addressed. That is the entire reason 8.3's scheduling algorithms were built around geometry that simply doesn't apply here.

What SSDs don't have
  • No seek time, no rotational latency — "adjacent" and "far away" cost almost the same.
  • Practical consequence: FCFS (or simple queue-depth batching) is often enough; there's no geometry left for SCAN/LOOK to exploit.
What SSDs have instead
  • Write endurance: each flash cell tolerates a finite number of erase/write cycles before it wears out.
  • Erase-before-write: a cell can't be overwritten directly; it must be erased in a whole block first — the reason SSD controllers run their own background garbage collection and wear leveling, spreading writes evenly so no one cell dies early.
Worked example 8.5
contiguous vs. scattered, HDD vs. SSD
Read all 348 blocks of WriteWell's document (7.1's spine file) two ways — contiguous (7.4's extent case: one seek, then a straight run) and scattered (7.4's worst-case indexed layout: every block needs its own access) — on both an HDD (9 ms average seek, 4.17 ms rotational latency at 7200 RPM, 150 MB/s sustained transfer) and an SSD (0.1 ms access latency, no seek or rotational cost, 500 MB/s sustained transfer).
Step 1 · HDD, contiguous

One seek + one rotational wait, then 348 blocks transferred in one run: 9 + 4.17 + (348 × 0.0068) ≈ 15.4 ms.

Step 2 · HDD, scattered

Every block pays its own seek and rotational wait: 348 × (9 + 4.17 + 0.0068) ≈ 4,585 ms — 4.6 seconds.

Step 3 · SSD, contiguous and scattered

Contiguous: 0.1 + (348 × 0.002) ≈ 0.78 ms. Scattered: 348 × (0.1 + 0.002) ≈ 35.5 ms.

Answer — scattered costs the HDD 297× its own contiguous time, and costs the SSD 46× its own contiguous time. The layout discipline 7.4 measured in metadata bytes (a 96× difference) turns into a far larger real-time gap on a mechanical disk specifically — and doesn't disappear on an SSD, it just shrinks by an order of magnitude. Comparing across devices: HDD-scattered is roughly 129× slower than SSD-scattered, but HDD-contiguous is only about 20× slower than SSD-contiguous — the device choice matters far less once the layout is already good.
Device × layout comparator
interactive
 

Opens on HDD/contiguous, matching the worked example. Flip layout to scattered and watch the bar grow nearly 300× on HDD but "only" 46× on SSD — then flip device to see the SSD bars are simply much shorter throughout.

Pitfalls
  • "SSDs make disk scheduling irrelevant." They make seek-based scheduling irrelevant. SSD controllers still schedule — around write endurance and garbage collection, an entirely different cost model that 8.3's algorithms were never designed for.
  • "Contiguous layout only mattered because of 7.4's metadata bytes." The metadata savings (7.4) and the seek-time savings (this section) are two separate payoffs of the same design choice, and the second is far larger in absolute terms — 96× in bytes versus nearly 300× in HDD time for the identical file.
  • "Since SSDs are so much faster, layout doesn't matter there." The worked example's own SSD numbers contradict this — scattered access still costs the SSD 46× its contiguous time. Smaller than HDD's penalty, but "smaller" isn't "gone."

Practice

  1. Using this section's HDD parameters, compute the time to read a single 1 KiB block in isolation (one seek, one rotational wait, one transfer).
    Show solution

    9 + 4.17 + 0.0068 ≈ 13.2 ms — almost entirely seek and rotational cost; the actual data transfer is a rounding error by comparison.

  2. An HDD vendor releases a drive with the same seek time and transfer rate but a faster 15,000 RPM spindle (rotational latency 2 ms instead of 4.17 ms). Recompute the scattered-read time for WriteWell's 348-block document and say whether this upgrade helps contiguous or scattered access more, in relative terms.
    Show solution

    Scattered: 348 × (9 + 2 + 0.0068) ≈ 3,829 ms (down from 4,585 ms). In relative terms this helps scattered access more: scattered access pays the rotational-latency cost 348 separate times, so shaving it helps 348× over, while contiguous access only pays it once and barely notices. Faster spindles help exactly the access pattern that was already paying the most for rotation.

  3. A colleague says "our new SSD-only storage tier means we can finally stop worrying about file fragmentation." Using this section's numbers, what would you say back?
    Show solution

    Fragmentation's worst-case penalty shrinks a lot (297× on HDD versus 46× on this section's SSD numbers) but doesn't vanish — a 46× slowdown for scattered access is still large enough to matter for latency-sensitive workloads. "Stop worrying entirely" overstates it; "worry proportionally less" is the defensible version.

  4. Chapter 7's whole premise was that indexed allocation costs extra disk accesses for indirection (0, 1, or 2 extra, by block range) while extent-based allocation costs at most one access per contiguous run. Using this section's HDD numbers, express 7.1's "2 extra accesses" for a double-indirect block in milliseconds, and say what that implies about the real cost of indirection specifically on a mechanical disk.
    Show solution

    Each extra access is a full seek + rotational wait (the block holding the pointer isn't necessarily anywhere near the data block it points to): roughly 9 + 4.17 ≈ 13.2 ms per extra access, so 2 extra accesses ≈ 26.3 ms on top of the data block's own access. On an HDD, "2 extra accesses" isn't an abstract count — it's over 26 milliseconds of real, mechanical delay per double-indirect block reached from a cold cache, which is exactly the kind of cost 8.2's buffer cache exists to help amortize across repeated reads.

▣ · REVISION

Cheat Sheet

Everything computed in this chapter, in one place.

8.1 · Interrupts & DMA

interrupt-driven: (words) × (cycles/interrupt) — scales with size

DMA: (setup) + (1 completion interrupt) — constant, size-independent

340 KiB image, word granularity: 4.352 ms vs 60 ns — 72,533×

8.2 · Buffer cache

write-through: every touch = 1 disk write · write-back: 1 write per distinct block, ever

3 autosaves (12 touches, 8 distinct blocks): 12 vs 8 writes — 33% fewer

hit ratio depends on reuse distance, not reuse count (same lesson as 6.2)

8.3 · Disk scheduling

SSTF: greedy-nearest · SCAN: sweep to both ends · LOOK: sweep to last real request

this chapter's queue: FCFS 816, SSTF 242, SCAN 338, C-SCAN 386, LOOK 300

C-SCAN's "never reverse" fairness costs a full extra disk traverse per pass

8.4 · Mixed workloads

SSTF: unbounded wait under continuous nearby arrival — a real starvation risk, not adversarial

SCAN/LOOK: a request already ahead of the head is serviced this sweep, guaranteed

FCFS is starvation-free too — at the cost of 8.3's worst raw total

8.5 · Storage trade-offs

HDD: seek + rotational + transfer · SSD: near-constant access, no seek/rotation

348-block doc, scattered vs contiguous: 297× (HDD) vs 46× (SSD)

SSD's own trade-off: write endurance, erase-before-write, wear leveling

▣ · SELF-TEST

Mixed Self-Test

Not grouped by section — figure out which idea applies before you answer, the way an exam will make you.

  1. A disk with cylinders 0–99 has head at 40 and a pending queue of 55, 20, 35. Compute SSTF's service order and total movement.
    Show solution

    Nearest to 40 is 35 (5), then nearest to 35 is 20 (15), then 55 (35). Order: 35, 20, 55. Total = 5+15+35 = 55. (8.3)

  2. True or false: a DMA transfer of 10 MB and a DMA transfer of 10 KB cost the CPU roughly the same number of housekeeping cycles.
    Show solution

    True. DMA's CPU-side cost is setup + one completion interrupt, independent of transfer size — the DMA controller, not the CPU, absorbs the size difference. (8.1)

  3. A block is read, then re-read four more times in quick succession, all within a 4-frame LRU cache that never evicts it in between. How many physical disk reads does this cost?
    Show solution

    One. The first reference is the only miss; all four re-reads are hits against the same cached copy. (8.2)

  4. Which of this chapter's five disk-scheduling algorithms is the only one guaranteed to never leave a request waiting longer than the length of the queue at the moment that request arrived?
    Show solution

    FCFS. Nothing can ever be inserted ahead of an already-queued request, so its wait is bounded by exactly how many requests were ahead of it at arrival — the trade-off being 8.3's worst total movement of the five. (8.3, 8.4)

  5. WriteWell's document (7.1's spine, 348 blocks) is stored as one contiguous extent on an SSD. Using 8.5's parameters, roughly how long does reading the whole thing take, and is this closer to the HDD contiguous time or the HDD scattered time?
    Show solution

    ≈0.78 ms (8.5's SSD-contiguous figure) — over 19× faster than the HDD's own contiguous time (15.4 ms), and utterly incomparable to the HDD's scattered time (4,585 ms). Device and layout are separate levers; this question isolates the device one. (8.5)

  6. A background process's I/O requests keep arriving right next to wherever the disk head currently sits, while a different process's request waits at a far cylinder. Under which algorithm from this chapter is the far request most at risk of an effectively unbounded wait, and which algorithm from 8.3 was purpose-built to prevent exactly that?
    Show solution

    SSTF is at risk; LOOK (or SCAN) bounds the wait by fixing which requests belong to the current sweep before any new arrival can compete for priority. (8.4)

  7. 7.2's ordered journal mode and 8.2's write-back buffer cache both delay when a write physically reaches disk. Explain why the file system still needs to force a flush at the right moment even though the buffer cache will eventually write everything out on its own.
    Show solution

    The buffer cache's own flush timing (on eviction, at a periodic sync, or at shutdown) has no awareness of which block needs to precede which other block for crash-consistency purposes — left alone, it could just as easily flush the inode before the data it points to. ordered mode's forced flush is the file system stepping in to guarantee a specific sequencing the cache's own policy doesn't promise on its own. (7.2, 8.2)

  8. Chapter 7.4 measured indexed-vs-extent allocation's difference as 3,072 vs 32 bytes of metadata (96×) for WriteWell's document. Chapter 8.5 measured the same contiguous-vs-scattered contrast in HDD time as roughly 297×. Are these two numbers measuring the same underlying trade-off, and if not, what does each one actually capture?
    Show solution

    Same underlying design choice (contiguous vs. scattered block layout), two different costs of it. 7.4's 96× is purely about how many bytes of pointer/extent metadata the allocation scheme itself needs to store — it says nothing about disk mechanics. 8.5's 297× is about how long it physically takes an HDD's arm to visit those blocks given how scattered they are — it would be a different number on a different device (8.5's SSD case: 46×) even though the underlying layout choice is identical. Metadata size and access time are two separate consequences of the same layout decision, not two measurements of the same thing. (7.4, 8.5)

Further reading

  • Stallings, Operating Systems: Internals and Design Principles, 9th ed., Ch. 11, "I/O Management and Disk Scheduling." This course's primary text; covers I/O buffering, disk scheduling, and disk caching in the same chapter this chapter's 8.1–8.4 draw from.
  • Silberschatz, Galvin & Gagne, Operating System Concepts, 10th ed., Ch. 11 ("Mass-Storage Systems") and Ch. 12 ("I/O Systems"). The standard reference treatment, split across two chapters: disk structure and scheduling in the first, interrupt/DMA hardware and the kernel I/O subsystem in the second.
  • Teorey & Pinkerton, "A Comparative Analysis of Disk Scheduling Policies," Communications of the ACM, 1972. The original paper behind 8.3's five-policy comparison — and the first to formally separate "expected seek time" from "expected individual waiting time," which is exactly the distinction 8.4 unpacks between throughput and starvation.

Before this chapter — Chapter 7 (every "disk access" that chapter counted — direct, single-indirect, double-indirect — is exactly the unit of work this chapter finally prices out in real interrupts, cache hits, and milliseconds) and Chapter 6 (6.2's page-replacement lesson, that hit ratio depends on reuse distance rather than reuse frequency, reappears unchanged in 8.2's buffer cache).

Where this goes next — Unit 9, Specialized Operating Systems: Design and Performance Overview, the closing unit: RTOS kernel design, scheduling, and priority inversion; embedded OS task management and memory allocation under hard resource limits; mobile OS power-aware scheduling and sandboxing. Every mechanism this book built for a general-purpose desktop — schedulers, locks, memory managers, file systems, I/O scheduling — gets re-examined under constraints (real-time deadlines, milliwatt power budgets, single-app sandboxing) that WriteWell, running on an ordinary Linux or Windows desktop, never had to face.