SCAN Disk Scheduling: The Elevator Algorithm
Sweep the head in one direction serving everything on the way, reach the end of the disk, then reverse and sweep back.
How SCAN Disk Scheduling Works
SCAN, universally known as the elevator algorithm, commits the head to one direction and serves every request it passes, continuing to the end of the disk before reversing. A lift does the same thing: it does not jump to whoever pressed the button first, nor to whoever is nearest, but finishes going up before it starts coming down.
- Pick a direction for the head toward higher cylinder numbers, or lower.
- Serve every pending request in that direction, in cylinder order, as the head passes over them.
- Continue to the end of the disk cylinder 199 here — even if no request remains in that direction.
- Reverse direction at the edge, and serve every request on the way back in the same passing order.
- Keep sweeping back and forth, so a newly arrived request waits at most until the head next passes its cylinder.
- Direction is chosen first, then held until the disk edge
- Requests are served in cylinder order as the head passes
- Reverses only at the physical end of the disk
- Identical in behaviour to a lift serving floors
Why Sweeping Removes Starvation
The guarantee SSTF cannot make, SCAN makes easily. Because the head is committed to a direction and will eventually reverse, every request is served within one full sweep of its arrival. A request at cylinder 199 does not depend on nothing closer arriving; it depends only on the head continuing in the direction it is already going.
That bound is what makes SCAN usable under load. New arrivals near the head do not push a distant request back — they are served on the current sweep if the head has not yet passed them, or on the next one if it has. Either way the wait is bounded by the width of the disk, not by the behaviour of other requests.
The cost of the guarantee shows in the total: 331 cylinders against SSTF's 232 on the same queue. SCAN pays for predictability. That trade — worse average, bounded worst case — is the same one that recurs throughout scheduling.
- Every request is served within one sweep of arriving
- New nearby arrivals cannot postpone a distant request
- 331 cylinders against SSTF's 232 on this queue
- Buys a bounded worst case at the price of average cost
SCAN on the standard request queue
def scan(requests, head, disk_size=200):
"""Sweep up to the disk edge, then back down. Returns (order, total)."""
above = sorted(c for c in requests if c >= head)
below = sorted((c for c in requests if c < head), reverse=True)
# The edge is visited even when no request sits there -- that is what
# separates SCAN from LOOK.
order = above + [disk_size - 1] + below if below else above
total, position = 0, head
for cylinder in order:
total += abs(cylinder - position)
position = cylinder
return order, total
order, total = scan([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 scan(const vector<int>& requests, int head, vector<int>& order, int diskSize = 200) {
int total = 0, position = head;
// Up to the disk edge, then back down. The edge is visited even when
// no request sits there.
vector<int> above, below;
for (int c : requests) (c >= head ? above : below).push_back(c);
sort(above.begin(), above.end());
sort(below.rbegin(), below.rend());
for (int c : above) order.push_back(c);
if (!below.empty()) order.push_back(diskSize - 1);
for (int c : below) order.push_back(c);
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 = scan(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 ScanDiskScheduling {
// Returns total head movement in cylinders; `order` receives the service order.
static int scan(int[] requests, int head, List<Integer> order, int diskSize) {
int total = 0, position = head;
// Up to the disk edge, then back down. The edge is visited even when
// no request sits there.
List<Integer> above = new ArrayList<>(), below = new ArrayList<>();
for (int c : requests) (c >= head ? above : below).add(c);
Collections.sort(above);
below.sort(Collections.reverseOrder());
order.addAll(above);
if (!below.isEmpty()) order.add(diskSize - 1);
order.addAll(below);
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 = scan(requests, 53, order, 200);
System.out.println(order + " | " + total + " cylinders");
}
}Step through it
Running on requests [98, 183, 37, 122, 14, 140, 65], head at 53
The Wasted Trip to the Edge
SCAN's obvious inefficiency is that it travels to cylinder 199 even when the highest pending request is at 183. Those 16 cylinders out and 16 back serve nothing at all, and on a disk with thousands of cylinders that overshoot can dominate.
LOOK removes exactly this waste by turning at the last pending request rather than the disk edge, which is why LOOK reaches 299 cylinders where SCAN needs 331 — a saving of 32, precisely twice the 16-cylinder overshoot. In practice, real drivers implement LOOK and call it SCAN.
There is one honest defence of going to the edge: it makes the sweep time predictable regardless of what is queued, which simplifies reasoning about worst-case latency. On a modern drive that argument is weak, and the saving is taken.
- Travelling to 199 when the last request is at 183 serves nothing
- The overshoot costs 32 cylinders — 16 out, 16 back
- LOOK removes it and reaches 299 instead of 331
- Real implementations of 'SCAN' are usually LOOK
Where SCAN Still Runs Today
SCAN is the ancestor of every deadline-based I/O scheduler still in the Linux kernel, even though the sweep itself no longer describes what the hardware does.
The elevator idea assumed a physical arm whose direction was expensive to reverse. On an SSD or NVMe drive there is no arm, no rotational latency, and no penalty for jumping between distant blocks — so sweeping in cylinder order optimises a cost that is not being paid. Linux consequently defaults NVMe devices to the none scheduler, letting the controller exploit its own channel parallelism.
What SCAN contributed was the bounded wait: no request can be passed over indefinitely, because the sweep must eventually reach it. That guarantee is what survives. mq-deadline keeps a block-sorted queue but pairs it with per-request expiry times, and when one expires the scheduler abandons the sweep to serve it. On rotational drives Linux still uses bfq, which retains elevator-style merging beneath a fair-share layer.
- The elevator sweep optimises seek distance, which SSDs do not charge for
- SCAN's lasting contribution is the bounded wait, not the sweep itself
mq-deadlinekeeps sorted order until a request's deadline expiresbfqstill merges elevator-style, under a fairness layer, on rotational disks