Disks and I/O Scheduling

A hard disk is the last great mechanical device in your computer: a stack of platters spinning at 5 400–15 000 RPM under a head that must physically fly to the right track before it can read a byte. That machinery makes the disk the one place in the system where the order you issue requests changes how long they take — sometimes by an order of magnitude. The block layer's power to reorder requests exists almost entirely to serve this device.

This lesson does two things. First, the mechanics: exactly what makes a random read cost ~10 ms while a sequential read of the same data costs almost nothing. Second, the classic disk-scheduling algorithms — FCFS, SSTF, the SCAN "elevator" family, deadline, CFQ/BFQ — and the twist that makes half of them obsolete on an SSD, where there is no head to move at all.

The anatomy of one disk access

The time to service a single random request is a sum of three physically distinct parts:

T_{\text{access}} \;=\; T_{\text{seek}} \;+\; T_{\text{rotation}} \;+\; T_{\text{transfer}}

Add them up: a random 4 KiB read is roughly 8 + 4.17 + 0.02 \approx 12 ms, of which 99.8% is mechanical positioning. Now read the next block sequentially: no seek, no rotational wait — just 20 µs of transfer. That is why sequential ≫ random on a HDD, by a factor of hundreds. Every storage design in this module is, at bottom, a scheme to convert random access into sequential.

Scheduling: reordering the queue to cut head travel

Because seek time grows with how far the head moves, and because many requests sit in the queue at once, the OS can reorder them to shrink total head travel. This is the classic disk-scheduling problem. Suppose the head is at cylinder 53 and the queue holds requests for 98, 183, 37, 122, 14, 124, 65, 67.

AlgorithmIdeaStrengthWeakness
FCFSserve in arrival orderfair, simple, no starvationwild head swings — worst travel
SSTFalways nearest request nextlow average seekstarves far-away requests
SCAN (elevator)sweep one way, then reversebounded wait, good traveledges wait longest
C-SCANsweep one way, snap back, repeatuniform wait timesthe return trip is "wasted"
Deadlineelevator + expiry deadlinesbounds worst-case latencyslightly lower throughput
CFQ / BFQfair-share time slices per processinteractive fairnessoverhead; less raw throughput

The elevator metaphor is the key intuition: a lift does not rush to whoever pressed the button most recently (that would ping-pong forever). It sweeps steadily up serving every request in its path, then sweeps down. SCAN does exactly this with the disk head — bounding how long any request can wait while still keeping the arm moving efficiently. Deadline refines it by attaching an expiry to each request (e.g. reads 500 ms, writes 5 s); an expiring request jumps the queue, guaranteeing no request starves — the default choice on Linux for spinning disks.

Elevator vs FCFS: count the head travel

The simulation runs the same request queue through FCFS (arrival order) and SCAN (the elevator, sweeping toward larger cylinders first), and totals the head movement. The elevator's win is the reduction in total cylinders travelled — directly proportional to total seek time.

// FCFS vs SCAN (elevator). Head starts at 53; disk has cylinders 0..199. const start = 53, MAXCYL = 199; const queue = [98, 183, 37, 122, 14, 124, 65, 67]; // FCFS: serve in arrival order. let head = start, fcfs = 0; for (const c of queue) { fcfs += Math.abs(c - head); head = c; } // SCAN: sweep UP to the end serving everything >= start, then sweep DOWN. head = start; let scan = 0; const up = queue.filter((c) => c >= start).sort((a, b) => a - b); const down = queue.filter((c) => c < start).sort((a, b) => b - a); for (const c of up) { scan += Math.abs(c - head); head = c; } scan += Math.abs(MAXCYL - head); head = MAXCYL; // reach the edge, then reverse for (const c of down) { scan += Math.abs(c - head); head = c; } console.log(`FCFS order: ${[start, ...queue].join(" -> ")}`); console.log(`FCFS total head movement: ${fcfs} cylinders`); console.log(`SCAN order: ${[start, ...up, MAXCYL, ...down].join(" -> ")}`); console.log(`SCAN total head movement: ${scan} cylinders`); console.log(`elevator saves ${fcfs - scan} cylinders of travel (${(100 * (fcfs - scan) / fcfs).toFixed(0)}% less)`);

Every scheduler above optimises for one physical fact: moving the head is slow and distance matters. An SSD has no head. Any logical block is reachable in about the same ~100 µs no matter where the last one was — access time is essentially uniform and random-friendly. So the elaborate elevator logic buys nothing and its sorting overhead actually hurts. That is why Linux pairs SSDs with none (the old "noop") or the lightweight mq-deadline/kyber schedulers: skip the reordering, just merge adjacent requests and fire them at the device's many parallel queues as fast as possible. The scheduler you pick is a statement about the physics of the media underneath — and NVMe's blk-mq multi-queue design leans into that parallelism rather than fighting it.

Students often blur "shortest seek" (SSTF) with "the elevator" (SCAN) because both prefer nearby requests. They are different, and the difference is starvation. SSTF always jumps to the globally nearest pending request. If a steady trickle of requests keeps arriving near the head, a lone request out at cylinder 190 can wait forever — it is never the nearest. SCAN cannot do this: it commits to a direction and sweeps, so every request is guaranteed service within one full pass, no matter how many closer ones arrive. Low average seek is not enough; a real scheduler must also bound the worst case. That is the whole reason deadline schedulers exist.

A worked seek-time example

Put numbers on a single access. A 7 200 RPM disk has average seek 9 ms and transfers at 150 MB/s. What is the expected time to read one random 4 KiB block?