What is SSTF Disk Scheduling?
What SSTF disk scheduling is, how it greedily picks the nearest request, its starvation risk, with OS interview questions.
Expected Interview Answer
Shortest-Seek-Time-First (SSTF) disk scheduling always services the pending request whose cylinder is closest to the disk head’s current position, greedily minimizing each individual seek to reduce total seek time compared to FCFS.
At every step, SSTF scans all pending requests and picks the one with the smallest absolute distance from the current head position, moves the head there, services it, and repeats. This greedy strategy noticeably reduces average seek time and improves throughput relative to FCFS, since the head is never sent on a long trip when a nearby request is waiting. The trade-off is fairness: if requests keep arriving near the head’s current location, a request sitting far away at the edge of the disk can be repeatedly passed over and wait indefinitely, a form of starvation. SSTF is also more expensive to implement than FCFS since it must search the whole pending-request set at every step rather than simply dequeuing, and like SJF CPU scheduling it favors nearby (short) requests at the potential expense of distant ones, which is exactly why algorithms like SCAN exist to bound the worst-case wait.
- Lower average seek time than FCFS in the common case
- Greedy, easy-to-reason-about local optimization
- Highlights the classic throughput vs fairness trade-off in scheduling
- Motivates why SCAN/C-SCAN were designed to bound starvation
AI Mentor Explanation
SSTF disk scheduling is like a groundskeeper always walking to whichever reported pitch damage is physically nearest right now, rather than following the order complaints were logged. This keeps the groundskeeper’s total walking distance low since nearby patches are handled first. But a distant patch at the far boundary can keep getting passed over every time a closer complaint comes in nearby, leaving it unrepaired for a very long time — the groundskeeper’s version of starvation.
Step-by-Step Explanation
Step 1
Scan pending requests
At each step, examine every request currently waiting in the queue.
Step 2
Pick nearest
Select the request whose cylinder has the smallest absolute distance from the head's current position.
Step 3
Seek and service
Move the head to that cylinder and service the request, updating the head's position.
Step 4
Repeat, watch for starvation
Repeat the nearest-first selection; a request far from repeatedly-favored areas can be delayed indefinitely.
What Interviewer Expects
- Correct definition: always serve the nearest pending request to the current head position
- Ability to trace a worked example computing total seek distance
- Awareness that SSTF can starve distant requests
- Comparison to FCFS (better average seek time) and to SCAN (which bounds starvation)
Common Mistakes
- Claiming SSTF is starvation-free (it is not — that is exactly its known weakness)
- Confusing SSTF with SCAN (SSTF has no directional sweep, it is purely greedy nearest-first)
- Forgetting SSTF must rescan all pending requests at every step, unlike FCFS's simple dequeue
- Not being able to compute seek distance for a simple SSTF example
Best Answer (HR Friendly)
“SSTF disk scheduling always sends the disk head to whichever pending request is physically closest right now, which cuts down wasted movement compared to just going in arrival order. The catch is that a request sitting far away can keep getting skipped over in favor of closer ones arriving later, so it can end up waiting a very long time — that is the trade-off between speed and fairness.”
Code Example
#include <stdio.h>
#include <stdlib.h>
int total_seek_sstf(int requests[], int n, int head_start) {
int served[n];
for (int i = 0; i < n; i++) served[i] = 0;
int total = 0;
int head = head_start;
for (int count = 0; count < n; count++) {
int best = -1, best_dist = 1 << 30;
for (int i = 0; i < n; i++) {
if (served[i]) continue;
int dist = abs(requests[i] - head);
if (dist < best_dist) {
best_dist = dist;
best = i;
}
}
total += best_dist;
head = requests[best];
served[best] = 1;
}
return total;
}Follow-up Questions
- How does SSTF compare to SJF CPU scheduling conceptually?
- Why can SSTF starve a request even though FCFS never does?
- How would you compute total seek time for a worked SSTF example?
- What algorithm improves on SSTF's starvation risk while keeping good seek performance?
MCQ Practice
1. SSTF disk scheduling selects which request to service next?
SSTF is a greedy algorithm that always services the pending request with the smallest seek distance from the current head.
2. What is the main risk introduced by SSTF compared to FCFS?
Because SSTF always favors the nearest request, a distant request can be repeatedly passed over and wait indefinitely.
3. Compared to FCFS, SSTF typically achieves?
SSTF greedily minimizes each seek, usually lowering average seek time versus FCFS, but sacrifices the fairness guarantee.
Flash Cards
What does SSTF disk scheduling optimize for at each step? — The shortest seek distance from the current head position to a pending request.
What is SSTF's key weakness? — It can starve requests far from the head's frequently-serviced region.
How does SSTF compare to FCFS on average seek time? — SSTF is generally better, since it always services the nearest request.
What algorithm addresses SSTF's starvation problem? — SCAN (and its variants like C-SCAN), which sweeps in one direction and bounds wait time.