What are I/O Scheduling Strategies?
Learn I/O scheduling strategies — FCFS, SSTF, SCAN, C-SCAN, LOOK — with tradeoffs and OS interview questions answered.
Expected Interview Answer
I/O scheduling strategies are the algorithms an OS uses to order pending disk requests so as to minimize seek time and maximize throughput, with FCFS, SSTF, SCAN, C-SCAN, and LOOK being the classic named strategies.
First-Come-First-Served (FCFS) services requests strictly in arrival order, which is fair and simple but can cause the disk head to zigzag wastefully across the platter. Shortest-Seek-Time-First (SSTF) always services whichever pending request is nearest the current head position, minimizing seek distance per request but risking starvation of far-away requests if nearby ones keep arriving. SCAN moves the head in one direction servicing every request it passes, then reverses at the far edge like an elevator, giving more uniform wait times than SSTF; C-SCAN is a variant that only services requests on the sweep in one direction and then jumps back to the start without servicing on the return trip, giving more uniform wait times across the whole disk. LOOK and C-LOOK are practical refinements of SCAN and C-SCAN that reverse or jump as soon as the last request in that direction is serviced, rather than travelling all the way to the physical end of the disk. Modern OS I/O schedulers such as Linux’s mq-deadline, BFQ, and Kyber build on these ideas while also considering deadlines and fairness across processes, not just raw seek distance.
- Reduces total seek time compared to naive arrival-order servicing
- SCAN/LOOK variants avoid the starvation risk of pure SSTF
- Elevator-style algorithms give more predictable worst-case wait times
- Understanding these underpins modern schedulers like mq-deadline and BFQ
AI Mentor Explanation
FCFS I/O scheduling is like a groundsman fixing pitch damage strictly in the order complaints arrive, even if that means walking back and forth across the ground repeatedly. SSTF is like always fixing whichever nearby patch is closest first, which is efficient locally but could leave a far corner’s damage unfixed indefinitely if closer complaints keep coming in. SCAN is like the groundsman sweeping steadily from one end of the ground to the other fixing everything along the way, then turning around at the boundary and sweeping back, guaranteeing every patch eventually gets attention without excessive backtracking.
Step-by-Step Explanation
Step 1
Requests queue up
Pending disk I/O requests, each targeting a specific cylinder/track, accumulate in the scheduler queue.
Step 2
Algorithm orders requests
FCFS keeps arrival order; SSTF picks nearest; SCAN/LOOK sweep across the disk in one direction before reversing.
Step 3
Head moves and services
The disk head physically seeks to each selected request in the chosen order and performs the I/O.
Step 4
Reversal or wraparound
SCAN reverses direction at the disk edge (or last request, for LOOK); C-SCAN/C-LOOK jump back to the start instead.
What Interviewer Expects
- Naming at least three strategies: FCFS, SSTF, SCAN (or LOOK)
- Explaining the starvation risk of pure SSTF
- Describing the elevator analogy for SCAN correctly
- Distinguishing SCAN from C-SCAN (return sweep behavior)
Common Mistakes
- Confusing SCAN with SSTF
- Thinking FCFS is always worst — it is simplest and fair, just not seek-optimal
- Not knowing C-SCAN skips servicing on the return sweep
- Forgetting real schedulers (mq-deadline, BFQ) add fairness/deadlines on top
Best Answer (HR Friendly)
“I/O scheduling strategies decide the order in which the OS services pending disk requests so the disk head does not waste time zigzagging. Simple ones like first-come-first-served are fair but inefficient, shortest-seek-first is efficient but can starve far-away requests, and elevator-style algorithms like SCAN sweep steadily across the disk in one direction before reversing, giving a good balance of efficiency and fairness.”
Code Example
int scan_schedule(int requests[], int n, int head, int disk_size, int direction) {
/* direction: +1 moving toward higher cylinders, -1 toward lower */
int total_movement = 0;
int served = 0;
while (served < n) {
int closest = -1;
int best_dist = disk_size + 1;
for (int i = 0; i < n; i++) {
if (requests[i] < 0) continue; /* already served */
int ahead = (direction > 0) ? requests[i] >= head : requests[i] <= head;
if (!ahead) continue;
int dist = (requests[i] > head) ? requests[i] - head : head - requests[i];
if (dist < best_dist) { best_dist = dist; closest = i; }
}
if (closest == -1) { /* reverse at the edge */
direction = -direction;
continue;
}
total_movement += best_dist;
head = requests[closest];
requests[closest] = -1;
served++;
}
return total_movement;
}Follow-up Questions
- How does C-SCAN differ from SCAN in its return sweep?
- Why can SSTF starve far-away requests?
- How does LOOK improve on SCAN in practice?
- What fairness features does Linux mq-deadline add beyond classic SCAN?
MCQ Practice
1. Which strategy always services the nearest pending request to the current head?
Shortest-Seek-Time-First always picks whichever request is closest to the current head position.
2. What is the main risk of pure SSTF scheduling?
If nearby requests keep arriving, SSTF can indefinitely postpone a request that is far from the head — starvation.
3. How does C-SCAN differ from SCAN?
C-SCAN treats the disk as circular: it sweeps one way servicing requests, then jumps back to the start without servicing on the way back, giving more uniform wait times.
Flash Cards
Name three classic I/O/disk scheduling strategies. — FCFS, SSTF, and SCAN (with LOOK/C-SCAN/C-LOOK as variants).
What is the downside of SSTF? — It can starve requests far from the current head position.
How does SCAN behave? — It sweeps across the disk in one direction servicing requests, then reverses at the edge — the elevator algorithm.
What distinguishes C-SCAN from SCAN? — C-SCAN only services requests in one sweep direction and jumps back to the start without servicing on return.