What is SCAN Disk Scheduling?
What SCAN disk scheduling is, how the elevator algorithm sweeps requests, its trade-offs, with OS interview questions answered.
Expected Interview Answer
SCAN disk scheduling moves the disk head in one direction across the disk, servicing every pending request it passes along the way, until it reaches the far edge, then reverses direction and does the same sweep back — behaving like an elevator that services every floor requested along its current path.
Because the head only ever moves in its current direction until it hits the disk boundary (or, in some variants, the last request in that direction) before reversing, no request can be starved indefinitely: every request will eventually be reached within, at worst, two full sweeps of the disk, giving SCAN much better worst-case fairness than SSTF. This directional-sweep behavior is exactly why SCAN is often called the elevator algorithm — like a building elevator, it does not jump back down to serve a lower floor mid-ascent, it keeps going up, servicing requests as it passes them, then reverses. SCAN’s average seek time is usually better than FCFS and close to SSTF, but it is not perfectly uniform: cylinders near the middle of the disk get serviced more often than cylinders near the edges, since the head passes the middle twice as often per full cycle. Variants like C-SCAN (which only services in one direction and jumps back to the start without servicing on the return) and LOOK/C-LOOK (which reverse at the last actual request rather than the physical disk edge) refine this to give more uniform wait times.
- Bounds worst-case wait time, unlike SSTF
- Better average seek time than FCFS in most workloads
- Intuitive elevator-algorithm mental model for explaining scheduling
- Foundation for understanding LOOK, C-SCAN, and C-LOOK variants
AI Mentor Explanation
SCAN disk scheduling is like a groundskeeper walking from one boundary rope to the other in a single direction, fixing every reported patch of damage encountered along the way, and only reversing once the far boundary is reached. This means no patch is ever left unrepaired indefinitely, since the sweep guarantees every patch gets covered within one lap. But a patch right near the halfway line of the ground gets passed twice as often as one at either boundary, so it tends to get attention sooner on average.
Step-by-Step Explanation
Step 1
Choose initial direction
The head starts moving toward one end of the disk (e.g. toward the highest cylinder number).
Step 2
Service along the way
Every pending request whose cylinder lies in the current direction is serviced as the head passes it.
Step 3
Reach the boundary
The head continues to the physical end of the disk (or last request, in the LOOK variant), even if no request lies exactly there.
Step 4
Reverse and repeat
The head reverses direction and sweeps back, servicing requests it now passes, guaranteeing no request waits more than roughly two sweeps.
What Interviewer Expects
- Correct elevator-algorithm mental model: sweep in one direction, service along the way, reverse
- Understanding that SCAN bounds worst-case wait time, unlike SSTF
- Awareness that middle cylinders get serviced more often than edge cylinders
- Ability to distinguish SCAN from its LOOK/C-SCAN/C-LOOK variants when asked
Common Mistakes
- Confusing SCAN with SSTF (SCAN sweeps directionally; SSTF is purely nearest-first with no direction)
- Forgetting SCAN travels to the physical disk edge even without a request there (that is the LOOK variant's optimization)
- Not knowing that middle cylinders are serviced more frequently than edge cylinders
- Claiming SCAN eliminates all unfairness (it reduces but does not perfectly equalize wait times)
Best Answer (HR Friendly)
“SCAN disk scheduling works like a building elevator: the disk head sweeps in one direction, picking up every request it passes along the way, goes all the way to the end, then reverses and sweeps back. This guarantees nothing waits forever the way it can under SSTF, and it usually gives good average performance, though requests near the middle of the disk tend to get served a bit more often than ones at the very edges.”
Code Example
#include <stdio.h>
#include <stdlib.h>
/* requests[] need not be sorted; disk_size is the highest cylinder + 1 */
int total_seek_scan(int requests[], int n, int head_start,
int disk_size, int going_up) {
int sorted[n];
for (int i = 0; i < n; i++) sorted[i] = requests[i];
/* simple insertion sort by cylinder */
for (int i = 1; i < n; i++) {
int key = sorted[i], j = i - 1;
while (j >= 0 && sorted[j] > key) { sorted[j + 1] = sorted[j]; j--; }
sorted[j + 1] = key;
}
int total = 0, head = head_start;
if (going_up) {
for (int i = 0; i < n; i++) if (sorted[i] >= head) {
total += sorted[i] - head; head = sorted[i];
}
total += (disk_size - 1) - head; /* sweep to the far edge */
head = disk_size - 1;
for (int i = n - 1; i >= 0; i--) if (sorted[i] < head_start) {
total += head - sorted[i]; head = sorted[i];
}
}
return total;
}Follow-up Questions
- How does SCAN differ from the LOOK variant?
- What is C-SCAN and why does it give more uniform wait times than plain SCAN?
- Why do middle cylinders get serviced more often than edge cylinders under SCAN?
- Why is SCAN called the elevator algorithm?
MCQ Practice
1. SCAN disk scheduling is commonly nicknamed?
SCAN behaves like a building elevator, sweeping in one direction and servicing every request passed before reversing.
2. What guarantee does SCAN provide that SSTF does not?
Because SCAN sweeps fully in each direction, every request is reached within about two sweeps, unlike SSTF which can starve distant requests.
3. Under plain SCAN, which cylinders tend to be serviced most frequently?
The head passes middle cylinders on both the outward and return sweep, so they are serviced more often than edge cylinders per cycle.
Flash Cards
What is another name for SCAN disk scheduling? — The elevator algorithm.
How does SCAN avoid starving requests? — It sweeps fully to the disk edge and back, so every request is reached within about two sweeps.
What is SCAN's known unfairness? — Middle cylinders are serviced more often than edge cylinders per full cycle.
Name a variant that improves on SCAN's uniformity. — LOOK, C-SCAN, or C-LOOK.