SSTF Disk Scheduling: Nearest First and Starvation
Always serve the pending request closest to the head — greedy, efficient on average, and capable of starving far-away requests indefinitely.
How SSTF Disk Scheduling Works
SSTF (Shortest Seek Time First) serves the pending request closest to the current head position. It is the disk equivalent of shortest-job-first: at each step it takes the cheapest immediate option, which minimises the next seek but says nothing about the total.
- Look at every pending request, and compute each one's distance from the current head position.
- Pick the smallest of those distances the request that costs the least to reach from where the head is now.
- Move the head there and serve it, adding that distance to the running total.
- Recompute from the new position the nearest request changes every time the head moves, so the choice is made afresh each step.
- Repeat until the queue is empty, always choosing locally and never looking further ahead.
- Chooses the minimum |request − head| at every step
- The choice is recomputed after each move
- Substantially cheaper than FCFS on a typical queue
- Greedy: locally optimal, not globally optimal
Why Greedy Is Not Optimal
SSTF reaches 232 cylinders on the standard queue, the best of the six — but that is a property of this particular queue, not a guarantee. Choosing the nearest request each time can strand the head at one end of the disk with a long return leg still to pay.
The trace shows it: SSTF starts at 53 and immediately works downward to 65, 37, 14, because those are nearby, then has to climb all the way back up through 98, 122, 140 to 183. The final leg from 140 to 183 costs 43 cylinders that a sweeping algorithm would have absorbed on its way past.
Finding the genuinely optimal order is a shortest-path problem over all permutations of the queue, which is not something a disk driver can afford to solve on every request. SSTF is the cheap approximation, and on random workloads it is a good one.
- 232 cylinders here — best of the six on this queue
- Works downward first, then pays to climb back up
- The optimal order needs a search no driver can afford
- Good approximation on random workloads, not a guarantee
SSTF on the standard request queue
def sstf(requests, head):
"""Always serve the nearest pending request. Returns (order, total)."""
pending = list(requests)
order, total, position = [], 0, head
while pending:
nearest = min(pending, key=lambda cylinder: abs(cylinder - position))
total += abs(nearest - position)
position = nearest
pending.remove(nearest)
order.append(nearest)
return order, total
order, total = sstf([98, 183, 37, 122, 14, 140, 65], 53)
print(order, total)#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdlib>
using namespace std;
// Returns total head movement in cylinders; `order` receives the service order.
int sstf(const vector<int>& requests, int head, vector<int>& order) {
int total = 0, position = head;
// Always the nearest pending request, recomputed after every move.
vector<bool> served(requests.size(), false);
for (size_t n = 0; n < requests.size(); n++) {
int best = -1;
for (size_t i = 0; i < requests.size(); i++) {
if (served[i]) continue;
if (best < 0 || abs(requests[i] - position) < abs(requests[best] - position)) best = (int)i;
}
served[best] = true;
total += abs(requests[best] - position);
position = requests[best];
order.push_back(requests[best]);
}
total = 0;
position = head;
for (int cylinder : order) {
total += abs(cylinder - position);
position = cylinder;
}
return total;
}
int main() {
vector<int> requests = {98, 183, 37, 122, 14, 140, 65}, order;
int total = sstf(requests, 53, order);
for (int c : order) cout << c << " ";
cout << "| " << total << " cylinders" << endl;
return 0;
}import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class SstfDiskScheduling {
// Returns total head movement in cylinders; `order` receives the service order.
static int sstf(int[] requests, int head, List<Integer> order) {
int total = 0, position = head;
// Always the nearest pending request, recomputed after every move.
boolean[] served = new boolean[requests.length];
for (int n = 0; n < requests.length; n++) {
int best = -1;
for (int i = 0; i < requests.length; i++) {
if (served[i]) continue;
if (best < 0 || Math.abs(requests[i] - position) < Math.abs(requests[best] - position)) best = i;
}
served[best] = true;
total += Math.abs(requests[best] - position);
position = requests[best];
order.add(requests[best]);
}
total = 0;
position = head;
for (int cylinder : order) {
total += Math.abs(cylinder - position);
position = cylinder;
}
return total;
}
public static void main(String[] args) {
int[] requests = {98, 183, 37, 122, 14, 140, 65};
List<Integer> order = new ArrayList<>();
int total = sstf(requests, 53, order);
System.out.println(order + " | " + total + " cylinders");
}
}Step through it
Running on requests [98, 183, 37, 122, 14, 140, 65], head at 53
The Starvation Problem
The serious objection to SSTF is not cost but starvation. A request far from the head is only served when nothing closer is pending, so a steady stream of requests near the head's current position can postpone it indefinitely.
This is not a contrived scenario. A database scanning a hot region of the disk generates exactly that pattern: a continuous supply of nearby requests, while a single request for a distant cylinder waits behind all of them. The request is never refused and no error is raised — it simply never reaches the front.
The fix is to stop making the decision purely local, which is what SCAN and its relatives do. By committing the head to a direction and serving everything in its path, they give every request a bounded wait: at worst, one full sweep of the disk. That bound is the reason the elevator family displaced SSTF in real drivers.
- A far request can be postponed indefinitely
- Hot-region workloads produce this naturally
- No error is raised — the request just never runs
- SCAN and LOOK fix it by bounding the wait to one sweep
Where SSTF Still Runs Today
SSTF is the algorithm most damaged by the shift to solid-state storage, because its entire premise — that the nearest block is the cheapest block — is false on flash.
An SSD has no arm to move. Its cost is dominated by erase-block granularity and internal parallelism across channels, neither of which correlates with logical block distance. Two blocks with adjacent LBAs may sit on the same channel and serialise, while two distant ones run in parallel. Picking the numerically closest request can therefore be slower than picking an arbitrary one, and the drive's controller — which maps logical to physical addresses — is the only component that knows.
On real hard drives SSTF was rarely deployed unmodified anyway, precisely because of the starvation problem. What shipped was the deadline family: Linux's mq-deadline sorts requests by block like SSTF, but every request carries an expiry (500 ms for reads, 5 s for writes) and an expired one preempts the sorted order. That is SSTF with a fairness cap — the greedy choice, overruled whenever it would starve someone.
- On flash, logical block distance no longer predicts access cost
- The FTL maps LBAs to physical pages, so proximity is an illusion
mq-deadlineis SSTF's sorting plus a per-request expiry that overrides it- Read expiry 500 ms, write expiry 5 s — reads are prioritised deliberately