Introduction
On a mechanical disk, the read/write head must physically move across cylinders to service each I/O request, and this seek time dominates disk access latency. When multiple processes issue I/O requests concurrently, the OS queues them and uses a disk-scheduling algorithm to decide the order of service, aiming to minimize total head movement (and therefore total seek time) while keeping response times reasonable for all requests.
Cricket analogy: A ground curator moving the covers on and off the pitch repeatedly for scattered rain interruptions wastes far more time in physical movement than actual play, so the umpires plan cover movements in the most efficient order.
Explanation
First-Come, First-Served (FCFS) services requests strictly in arrival order. It is simple and fair, but ignores the physical layout of the requests, so the head may zig-zag across the disk, producing poor average seek time under heavy load. Shortest Seek Time First (SSTF) always services the pending request whose cylinder is closest to the head's current position. This greatly reduces total head movement compared to FCFS, but it can cause starvation of requests far from the current cluster of activity if closer requests keep arriving. The SCAN algorithm (the 'elevator algorithm') moves the head in one direction, servicing every pending request it passes, until it reaches the end of the disk, then reverses direction and services requests on the way back. This bounds worst-case wait time far better than SSTF while still achieving good average seek performance, because it never reverses direction until it must.
Cricket analogy: A team batting strictly in jersey-number order regardless of form (FCFS) can leave a struggling player facing the crucial over; always sending in "whoever is most in form right now" (SSTF) risks a talented but overlooked player never getting a chance; an elevator-style batting order that commits to a plan and only adjusts at natural breaks (SCAN) balances both.
Example
/* Disk has cylinders 0-199. Head starts at cylinder 53.
Pending request queue (in arrival order):
98, 183, 37, 122, 14, 124, 65, 67 */
/* ---- FCFS: service in arrival order ---- */
/* 53->98 (45) ->183 (85) ->37 (146) ->122 (85)
->14 (108) ->124 (110) ->65 (59) ->67 (2) */
/* Total = 45+85+146+85+108+110+59+2 = 640 cylinders */
/* ---- SSTF: always pick the closest pending request ---- */
/* 53->65 (12) ->67 (2) ->37 (30) ->14 (23)
->98 (84) ->122 (24) ->124 (2) ->183 (59) */
/* Total = 12+2+30+23+84+24+2+59 = 236 cylinders */
/* ---- SCAN: sweep toward 0, then reverse toward the
highest pending request ---- */
/* 53->37 (16) ->14 (23) ->0 (14) [reached the end]
0->65 (65) ->67 (2) ->98 (31) ->122 (24)
->124 (2) ->183 (59) */
/* Total = (53-0) + (183-0) = 53 + 183 = 236 cylinders */Analysis
FCFS produces 640 cylinders of total head movement because it repeatedly reverses direction to chase requests in arrival order rather than physical proximity (for example, jumping from cylinder 183 down to 37, a 146-cylinder swing). SSTF cuts this to 236 cylinders by always choosing the nearest pending request, but notice it initially moves away from the low cylinder numbers (14, 37) toward 65/67/98/122/124/183 before finally doubling back for 37 and 14 -- a low-numbered request could in principle starve if new nearby-high requests kept arriving. SCAN also totals 236 cylinders in this case: it sweeps monotonically from 53 down to 0 (picking up 37 and 14 along the way), then reverses and sweeps up to the highest pending request at 183 (picking up 65, 67, 98, 122, 124 along the way). Because SCAN never reverses until it exhausts requests in the current direction, its total movement is simply the distance from the start position to one end, plus the distance from that end to the furthest request on the other side (53 + 183 = 236 here), and no request ever waits an unbounded amount of time, unlike under SSTF.
Cricket analogy: In a rain-hit match, a captain rotating bowlers purely by squad-list order might cover 640 overs' worth of wasted tactical switching, while always picking "whoever is freshest right now" cuts it to 236, and a planned bowling-order sweep matches that same 236 with none starved of overs.
Key Takeaways
- FCFS is simple and fair but can produce large, inefficient head swings, yielding poor average seek time (640 cylinders in the worked example).
- SSTF minimizes movement for the immediate next request (236 cylinders here) but can starve far-away requests indefinitely.
- SCAN sweeps across the disk in one direction before reversing, bounding worst-case wait time while still achieving strong average performance (also 236 cylinders here).
- Total head movement for a sweeping algorithm equals the distance to the far end reached plus the distance back to the last request serviced.
- Variants like C-SCAN and LOOK further tune SCAN's fairness and efficiency by not always going all the way to the disk edge or by treating the disk as circular.
Practice what you learned
1. Given requests 98, 183, 37, 122, 14, 124, 65, 67 with the head starting at 53, what is the total head movement under FCFS (servicing in arrival order)?
2. What is the primary risk of using SSTF (Shortest Seek Time First) disk scheduling under heavy, continuous load?
3. In the SCAN algorithm, what happens once the head reaches the end of the disk during its sweep?
4. For the same request queue (98, 183, 37, 122, 14, 124, 65, 67; head at 53), what is the total head movement under SSTF?
Was this page helpful?
You May Also Like
File Allocation Methods
How the operating system maps a file's logical blocks onto physical disk blocks: contiguous, linked, and indexed allocation.
File System Basics
How an operating system organizes, names, and provides access to persistent data on secondary storage.
OS Design Tradeoffs
A grounded look at the core engineering tradeoffs behind major operating system design decisions.