Disk Scheduling Algorithms

A disk request is characterized primarily by the cylinder number it targets, since moving the arm between cylinders (the seek) costs far more time than waiting for the platter to rotate into position (rotational latency) or transferring data once positioned. Given a queue of pending requests with cylinder numbers $c_1, c_2, \dots, c_n$ and a current head position $h$, a disk scheduling algorithm picks an order of service $\pi$ to reduce some cost function — typically total head movement, $\sum_i |c_{\pi(i)} - c_{\pi(i-1)}|$, or the maximum/average waiting time across requests. Two families of policies emerge. Order-preserving policies like FCFS make no attempt to reorder; they are simple, predictable, and starvation-free by construction, but they let the arm thrash back and forth across the disk if requests arrive in geometrically scattered order. Greedy and sweep policies — SSTF, SCAN, C-SCAN, and LOOK — actively reorder requests based on cylinder position. Greedy policies (SSTF) minimize the immediate next seek distance, which can produce a good average but risks starvation: a request far from the current cluster of activity may wait indefinitely if closer requests keep arriving. Sweep policies impose a global direction of travel — the arm behaves like an elevator, visiting cylinders in one direction until it must reverse — which bounds the worst-case wait for any request to at most one full sweep of the disk. The key terms to fix precisely: seek time is the time to move the arm to the target cylinder; rotational latency is the time waiting for the target sector to rotate under the head; cylinder is the concentric set of tracks at the same radius across all platter surfaces, reachable by a single arm position. Disk scheduling algorithms operate purely on the sequence of cylinder numbers in the request queue — they do not, in their classical form, account for rotational latency or track layout, which is why real controllers layer additional heuristics (such as SPTF, shortest-positioning-time-first) on top of the ideas taught here.

Every algorithm below takes the same inputs — a set of pending request cylinders, the current head position, the total number of cylinders on the disk, and (where relevant) the current direction of travel — and produces an ordering in which to service them. We trace all five over a common example so the differences are visible mechanically, not just in prose.

FCFS (First-Come-First-Served). Service requests strictly in arrival order. No reordering, no knowledge of geometry needed. ``` FCFS(requests, head): order = [] current = head total_movement = 0 for r in requests: # requests already in arrival order total_movement += |r - current| order.append(r) current = r return order, total_movement ```

SSTF (Shortest-Seek-Time-First). At each step, service whichever pending request is closest to the current head position, breaking ties arbitrarily (commonly by direction or FCFS order). ``` SSTF(requests, head): pending = copy(requests) # multiset of cylinder numbers order = [] current = head total_movement = 0 while pending is not empty: r = argmin over x in pending of |x - current| total_movement += |r - current| order.append(r) remove r from pending current = r return order, total_movement ``` A priority structure (e.g., a balanced BST or two sorted lists split around the head) supports the repeated nearest-neighbor query in $O(\log n)$ per step rather than a linear scan.

SCAN (the "elevator" algorithm). The head sweeps in one direction, servicing every pending request it passes, until it reaches the end of the disk (cylinder 0 or the maximum cylinder), then reverses direction and sweeps back. ``` SCAN(requests, head, direction, max_cylinder): left = sorted(r for r in requests if r < head) right = sorted(r for r in requests if r >= head) order = [] if direction == "up": order += right # ascending, head to max order += [max_cylinder] # sweep to the physical end order += reversed(left) # then descend else: # direction == "down" order += reversed(left) # descending, head to 0 order += [0] order += right # then ascend return order ```

C-SCAN (Circular SCAN). Like SCAN, but the head services requests only while moving in one direction; upon reaching the end, it jumps immediately back to the opposite end without servicing on the return trip, then resumes sweeping the same direction. This makes wait times far more uniform, since the disk is treated as a circular list of cylinders. ``` C-SCAN(requests, head, max_cylinder): right = sorted(r for r in requests if r >= head) left = sorted(r for r in requests if r < head) order = [] order += right order += [max_cylinder] # sweep to the end order += [0] # jump back to the start (no service) order += left # resume sweeping upward return order ```

LOOK and C-LOOK. Identical to SCAN and C-SCAN, respectively, except the arm reverses (or jumps) at the last request in the current direction rather than traveling all the way to the physical edge of the disk. This avoids wasted travel when no requests lie near the edges. ``` LOOK(requests, head, direction): left = sorted(r for r in requests if r < head) right = sorted(r for r in requests if r >= head) order = [] if direction == "up": order += right order += reversed(left) else: order += reversed(left) order += right return order C_LOOK(requests, head): right = sorted(r for r in requests if r >= head) left = sorted(r for r in requests if r < head) order = right + left # jump from max(right) directly to min(left) return order ```

Time complexity. Let $n$ be the number of pending requests.

• FCFS requires a single pass over the queue: $O(n)$ to compute the order and total movement, since no sorting or searching is needed.
• SSTF, implemented naively, scans all pending requests at each of the $n$ steps to find the nearest one, giving $O(n^2)$. Using a balanced search structure (e.g., a sorted array or balanced BST of pending cylinders, allowing predecessor/successor queries), each step costs $O(\log n)$, giving $O(n \log n)$ total.
• SCAN, C-SCAN, LOOK, and C-LOOK all begin by partitioning requests into those below and at/above the head, then sorting each partition: $O(n \log n)$ for the sort, and $O(n)$ to emit the final order — so $O(n \log n)$ overall. If the request queue is maintained as an always-sorted structure (common in practice, since requests can be inserted into a sorted set as they arrive), the per-request cost drops to $O(\log n)$ for insertion, and generating an order is $O(n)$.
• Space complexity for all algorithms is $O(n)$, to hold the request queue and the output order.

Correctness argument for SCAN/C-SCAN/LOOK (no starvation). Define a sweep as one traversal of the head from one extreme (or from its farthest pending request, for LOOK variants) to the other. The invariant maintained by SCAN is: at the start of each sweep, every request present in the queue is served exactly once before the sweep ends, in monotonic cylinder order relative to the sweep direction. This holds because the algorithm partitions all currently pending requests into "ahead of the head" and "behind the head" relative to the current direction, and visits the "ahead" partition in full, sorted order, before reversing. Consequently, any request present when a sweep begins is serviced within that sweep or the very next one — bounding the worst-case wait to at most two sweep lengths (roughly $2 \times$ the number of cylinders in the worst case, independent of how many other requests arrive). This is why SCAN and C-SCAN are described as starvation-free: no request can be perpetually skipped, unlike SSTF.

Why SSTF can starve. SSTF always chooses the globally nearest pending request. Consider a steady stream of new requests arriving near the current head position while a single old request sits far away (say, at cylinder 0 while the head oscillates near cylinder 190). Every greedy choice prefers the nearby newcomers, since $|nearby - head| \ll |0 - head|$, so the distant request's wait time is unbounded as long as nearby arrivals continue — an unbounded delay is possible in principle, which is the formal meaning of starvation here.

Why C-SCAN gives more uniform response time than SCAN. SCAN's cost per direction is asymmetric: a request that was just missed on an upward sweep must wait for the full downward-then-upward return, while a request just serviced waits almost a full cycle before being revisited. C-SCAN removes this asymmetry by always servicing in the same direction and treating the cylinder space as circular (wrapping from the max cylinder back to 0 with no intervening service). The variance in wait time across requests is provably smaller for C-SCAN because every request's maximum wait is bounded by one full circular sweep, rather than by the sum of two unequal partial sweeps.

Tradeoffs, honestly stated. FCFS minimizes implementation complexity and variance-free fairness in arrival order but can have the worst average seek distance under adversarial or bursty arrival patterns. SSTF minimizes average seek distance for a fixed static request set but is not starvation-free and its optimal reordering (the true minimum-total-movement tour) is actually an instance of the NP-hard Traveling Salesman Problem on a line — SSTF is a greedy heuristic, not an exact optimizer, though on a line metric greedy nearest-neighbor is known to perform reasonably close to optimal in practice. SCAN and LOOK trade a small amount of average-case efficiency for a hard bound on worst-case wait. C-SCAN sacrifices some total movement (the "free" return trip in SCAN is replaced by a full unserviced jump in C-SCAN) in exchange for much more uniform per-request response times, which matters more for real-time and interactive workloads than raw throughput does.

Consider a disk with cylinders numbered 0 to 199, head currently at cylinder 53, and the pending request queue, in arrival order:

Assume the head's most recent direction of travel was toward increasing cylinder numbers (relevant for SCAN/LOOK variants).

Let's verify FCFS by hand as a sanity check: from 53 to 98 is 45; 98 to 183 is 85; 183 to 37 is 146; 37 to 122 is 85; 122 to 14 is 108; 14 to 124 is 110; 124 to 65 is 59; 65 to 67 is 2. Sum: $45+85+146+85+108+110+59+2 = 640$. This confirms FCFS produces by far the worst total movement here, since arrival order zig-zags across nearly the entire disk multiple times. SSTF's superiority in total movement is visible immediately (236 vs. 640), but notice the service order: 14, the smallest cylinder and second request to arrive, is serviced fifth, after several closer requests are picked up first. If new nearby requests kept arriving near cylinders 60–130, cylinder 14 (and 183) could wait far longer under SSTF than under any SCAN variant — this is the starvation risk made concrete. Comparing LOOK to SCAN: LOOK skips the "dead" trips to the physical edges (199 and 0) that no pending request actually needed, saving $345 - 299 = 46$ cylinders of movement while producing the same relative service order. Comparing C-LOOK to C-SCAN similarly saves the wasted trip to 199, at the cost of the long jump back from 124 down to 14 (a distance of 110 cylinders that services nothing) — but that entire circular-wrap distance is still cheaper than the two dead-edge trips C-SCAN pays.

Disk scheduling emerged directly from the economics of early magnetic disk storage: mechanical seek time was the dominant cost of an I/O operation for decades, so operating systems researchers and industry engineers invested heavily in scheduling heuristics throughout the 1960s and 1970s, as multiprogrammed and time-sharing systems made disk contention a first-order performance concern.

Every general-purpose operating system kernel ships a disk (or block-layer) I/O scheduler descended from these ideas. Linux's historical schedulers — including the deadline scheduler and CFQ (Completely Fair Queuing) — build on SCAN-like sweeping combined with deadline guarantees to prevent starvation while preserving throughput; even `mq-deadline` and `kyber`, used with modern multi-queue block layers, retain sweep-inspired sequencing for spinning media. Database systems and RAID controllers historically tuned their own request reordering layers on top of the OS scheduler to batch and sort I/O for mechanical drives. Real-time and embedded systems favored SCAN/C-SCAN variants specifically because of the provable bound on worst-case wait time, which matters when a control-loop deadline cannot be missed. Even as solid-state drives (with no moving arm and effectively uniform access latency across addresses) have made seek-time minimization less relevant for consumer storage, the conceptual toolkit — greedy heuristics versus bounded sweeps, throughput versus fairness, starvation-avoidance guarantees — reappears throughout systems design: in network packet schedulers, in CPU process schedulers, and in any resource-allocation policy where request reordering trades efficiency for predictability. Disk scheduling is also a natural bridge to File-System Implementation and Layout, where file systems place related blocks physically close together specifically to make the scheduler's job easier and reduce the seek distances it must manage in the first place.

Ask the tutor: How would you modify SCAN to bound the maximum wait time for any single request to a fixed number of I/O operations, regardless of arrival pattern?