The Elevator Algorithm: Why SSTF Starvation Forced SCAN Scheduling
In magnetic disk storage controllers and enterprise storage arrays, disk access latency is dominated by Seek Time: the mechanical physical movement of the actuator arm across concentric disk cylinders.
Operating system disk schedulers reorder pending I/O requests to minimize total head movement.
However, naive optimization introduces severe starvation.
1. FCFS vs Shortest Seek Time First (SSTF)
First-Come, First-Served (FCFS):
Services requests in strict arrival order. If requests bounce between inner and outer tracks (e.g., cylinder 14 → 180 → 22 → 195), the actuator arm violently oscillates back and forth, degrading throughput.
Shortest Seek Time First (SSTF):
Selects the pending request with the minimum seek distance from the current head position.
The SSTF Starvation Trap:
SSTF is a greedy algorithm. If the head is currently at cylinder 53, and requests continuously arrive clustered around cylinders 50–65:
- The head stays localized.
- A request at cylinder 190 will starve indefinitely as long as new requests arrive near the head.
2. The SCAN Algorithm (The Elevator Algorithm)
To eliminate starvation while preserving high throughput, operating systems adopted the SCAN algorithm, mimicking an architectural elevator:
- The actuator arm sweeps continuously in one direction (e.g., from cylinder 0 towards cylinder 199).
- It services all pending requests along its path.
- Upon reaching the end boundary, it reverses direction and sweeps backward, servicing requests on the return journey.
Every request is guaranteed service within a bounded maximum of two full disk sweeps.
3. Circular SCAN (C-SCAN)
Under standard SCAN, tracks in the center of the disk are serviced twice as frequently as tracks at the extreme boundaries.
C-SCAN provides uniform wait times:
- The head sweeps in one direction only (e.g., 0 to 199), servicing requests.
- When it reaches the outer cylinder, it executes a rapid express return back to cylinder 0 without servicing requests.
- It resumes servicing on the next forward sweep.
Explore interactive disk scheduling trajectory charts at Binary Dose.
Top comments (0)