§37.5–37.6Disk Scheduling … Summary

Random I/O is brutally expensive — so, given a batch of pending requests, the OS (and the drive) can reorder them to minimize positioning cost.

37.5 Disk Scheduling

Unlike CPU jobs (whose length is unknown), a disk request’s cost is estimable from its seek and rotation — so disk scheduling disk scheduling Choosing which of several pending disk I/O requests to service next (by the OS and/or the drive). Unlike CPU jobs, a disk request's cost is estimable from its seek and rotation, so schedulers approximate SJF by servicing the cheapest-to-reach request first. defined in ch. 37 — open in glossary can greedily approximate SJF, servicing the cheapest request first. Step through the classic policies:

SSTF shortest seek time first SSTF: a disk-scheduling policy that services the request on the nearest track first (at the OS level, approximated as nearest-block-first, NBF). Fast, but a steady stream of near-track requests can starve requests to far-away tracks. defined in ch. 37 — open in glossary serves the nearest track first (the OS, lacking geometry, approximates it as nearest-block-first). It’s fast but can starve far tracks. The elevator (SCAN) elevator algorithm SCAN: a disk-scheduling policy that sweeps the head back and forth across the disk, servicing requests in track order per sweep and deferring requests that arrive behind the head to the next sweep — which avoids the starvation of pure SSTF. Like an elevator that keeps going one direction rather than always serving the nearest floor. Variants: C-SCAN (one-way sweeps, fairer) and F-SCAN (freeze the queue during a sweep). defined in ch. 37 — open in glossary fixes that by sweeping back and forth in track order, deferring requests behind the head to the next sweep — like an elevator that keeps going one way instead of always serving the nearest floor. But SSTF and SCAN both ignore rotation; SPTF shortest positioning time first SPTF (a.k.a. SATF, shortest access time first): a disk-scheduling policy that accounts for BOTH seek and rotation, servicing whichever request has the shortest total positioning time. It beats SSTF/SCAN (which ignore rotation) when seek and rotation are comparable, but needs exact head position and track layout — so it is usually performed inside the drive. defined in ch. 37 — open in glossary (a.k.a. SATF) accounts for seek and rotation, winning when the two are comparable.

Where scheduling happens, and two more tricks

On modern systems, scheduling is split. The OS picks its best few requests (say 16) and hands them to the drive; the drive — which alone knows exact head position and track layout — does the final SPTF ordering internally. Two related tricks: I/O merging combines adjacent-block requests (e.g. read 33 and 34 → one two-block request), cutting overhead; and instead of always issuing work immediately (work-conserving), an anticipatory scheduler may briefly wait — a better (nearby) request might be about to arrive.

37.6 Summary

We’ve built a functional model of the disk: its geometry, the seek + rotation + transfer of every request, the huge sequential-vs-random gap, and how scheduling minimizes positioning cost. It skips the physics and materials science — but it’s enough to build real systems on. Next: gluing many disks together for capacity and reliability — RAID.