Study smarter with Fiveable
Get study guides, practice questions, and cheatsheets for all your subjects. Join 500,000+ students with a 96% pass rate.
Disk scheduling algorithms sit at the intersection of hardware constraints and software optimization. The mechanical reality of spinning platters and moving read/write heads creates a bottleneck that clever algorithms must navigate. You're being tested on your understanding of seek time minimization, fairness vs. efficiency tradeoffs, and starvation prevention.
These algorithms also demonstrate a fundamental OS design principle: there's no perfect solution, only tradeoffs. Each algorithm sacrifices something (fairness, simplicity, or optimal seek time) to gain something else. When you encounter these on an exam, don't just memorize how each works. Know why you'd choose one over another and what problems each solves or creates.
The most intuitive approach treats disk requests like a line at a store: first in, first out. This provides maximum fairness but ignores the physical reality of disk geometry.
Example: Suppose the head is at cylinder 50 and the request queue is [82, 170, 43, 140, 24, 16, 190]. FCFS processes them in exactly that order. The head bounces back and forth across the disk, racking up a large total seek distance, but every request gets served in the order it arrived.
These algorithms prioritize minimizing immediate seek time by choosing the "closest" request next. They boost throughput but introduce fairness problems.
Compare: FCFS vs. SSTF are both conceptually simple, but FCFS guarantees fairness while SSTF optimizes for throughput. If an exam question asks about starvation, SSTF is your go-to example; if it asks about the convoy effect, think FCFS.
These algorithms impose directional discipline on head movement, sweeping across the disk like an elevator moves through floors. This reduces erratic back-and-forth motion while providing more predictable wait times than SSTF.
Compare: SCAN vs. C-SCAN both use directional sweeping, but SCAN services requests in both directions while C-SCAN only services in one. C-SCAN provides more predictable wait times at the cost of the wasted return sweep. If asked to optimize for fairness among all cylinder positions, C-SCAN is the stronger choice.
These algorithms refine the elevator approach by eliminating unnecessary head movement to disk boundaries when no requests exist there.
Compare: LOOK vs. C-LOOK mirrors the SCAN vs. C-SCAN relationship. LOOK services bidirectionally; C-LOOK uses unidirectional sweeps with jumps. C-LOOK typically wins on wait-time uniformity, while LOOK may have a slight edge on raw throughput in certain workloads.
| Concept | Best Examples |
|---|---|
| Simple/Fair scheduling | FCFS |
| Greedy optimization | SSTF |
| Starvation risk | SSTF, SCAN (at edges) |
| Elevator-style movement | SCAN, C-SCAN, LOOK, C-LOOK |
| Uniform wait times | C-SCAN, C-LOOK |
| Efficiency optimization | LOOK, C-LOOK |
| Convoy effect | FCFS |
| Circular disk treatment | C-SCAN, C-LOOK |
Which two algorithms share the "elevator" movement pattern but differ in how they handle the return sweep? What's the practical impact of this difference?
If a system experiences starvation where requests at cylinder 0 rarely get serviced, which algorithm is likely in use, and what would you recommend instead?
Compare FCFS and SSTF: under what workload conditions would FCFS actually outperform SSTF?
A system administrator notices the disk head frequently travels to the physical end of the disk even when no requests exist there. Which algorithm should replace the current one, and why?
You need to design a scheduling approach that balances throughput and fairness for a busy file server. Which algorithm would you choose, and what tradeoffs would you acknowledge?