Disk Scheduling
FCFS, SSTF, SCAN — algorithms from the HDD era that still show up in interviews.
Level: intermediate
What is it?
Disk scheduling chooses an order for pending block-device requests. Classic hard-disk policies try to reduce mechanical seek movement, while SSDs have different latency characteristics and internal controllers that make simplistic seek-distance models less predictive.
Why does it matter?
Request ordering can affect latency and throughput when many operations are queued. Scheduling policies trade average response time, fairness, throughput, and starvation risk.
Mental model
On a spinning disk, moving the head to distant tracks is expensive, so request order matters. FCFS preserves arrival order; SSTF seeks toward the nearest request; SCAN sweeps in a direction and services requests along the way.
How it works
- FCFS is simple and fair by arrival order but can produce large head movement.
- SSTF reduces local seek distance but can starve requests far from the current head position.
- SCAN moves across the disk and services requests in order along a sweep, then reverses direction.
- C-SCAN services in one direction and returns to the start, producing a more uniform wait pattern in some models.
- Modern operating systems and devices use complex schedulers; textbook track-distance results are simplified models.
Steps
- Write down the initial head position and the request queue.
- For FCFS, service requests in arrival order and sum each movement distance.
- For SSTF, repeatedly choose the closest pending track, stating tie-breaking assumptions.
- For SCAN/C-SCAN, state direction and whether the model counts travel to the physical end before reversing or wrapping.
Real-world usage
- Solving operating-system exam problems about seek distance.
- Understanding fairness versus average seek cost.
- Diagnosing storage latency in queue-depth-heavy workloads.
Common mistakes
- Switching policy mid-solution without stating assumptions about direction or disk boundaries.
- Assuming SSTF always minimizes every global or fairness objective.
- Applying HDD seek-distance conclusions directly to SSD devices without qualification.
Interview questions
Why can SSTF cause starvation?
Requests far from the current head can continually lose to closer arrivals and wait for a long time.
Why are classic disk-scheduling algorithms less predictive for SSDs?
SSDs have no mechanical head seek; flash translation, parallelism, queue depth, and controller scheduling dominate many costs.