LOOK Disk Scheduling: Turn at the Last Request
Sweep like SCAN, but reverse at the last pending request in that direction rather than travelling to the edge of the disk.
How LOOK Disk Scheduling Works
LOOK is SCAN with the wasted travel removed. It sweeps in one direction serving everything it passes, but instead of continuing to the physical end of the disk it looks ahead, finds no further request, and reverses there. The service order is otherwise identical to SCAN's.
- Pick a direction, as SCAN does, and serve every pending request in that direction in cylinder order.
- Check whether any request remains ahead before moving further this is the step that distinguishes LOOK from SCAN.
- Reverse as soon as none does, at the last request rather than at the disk edge.
- Sweep back the other way, again serving every request the head passes over.
- Repeat, so the head is confined to the range the queue actually occupies.
- Reverses at the last request, not the disk edge
- Service order is otherwise identical to SCAN
- The head stays within the range the queue occupies
- The name comes from looking ahead before moving on
Exactly What It Saves
The saving is precise and easy to state, which makes it a common exam question. On the standard queue SCAN travels to cylinder 199 although the highest request is at 183, and pays for those 16 cylinders twice — once going out, once coming back. LOOK skips both.
331 − 299 = 32, exactly twice the 16-cylinder overshoot. There is no other difference between the two runs: both serve 65, 98, 122, 140, 183 going up, then 37 and 14 coming down.
The saving grows with the gap between the outermost request and the disk edge. On a queue clustered in the middle of a large disk, SCAN can spend most of its movement travelling over empty regions, while LOOK spends none.
- SCAN overshoots to 199 when the last request is 183
- The overshoot is paid twice: 16 out, 16 back
- 331 − 299 = 32, exactly twice the overshoot
- The saving grows as the queue clusters away from the edges
LOOK on the standard request queue
def look(requests, head):
"""Sweep up to the last request, 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)
# No disk edge: the head turns at the outermost pending request.
order = above + below
total, position = 0, head
for cylinder in order:
total += abs(cylinder - position)
position = cylinder
return order, total
order, total = look([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 look(const vector<int>& requests, int head, vector<int>& order) {
int total = 0, position = head;
// No disk edge: the head turns at the outermost pending request.
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);
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 = look(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 LookDiskScheduling {
// Returns total head movement in cylinders; `order` receives the service order.
static int look(int[] requests, int head, List<Integer> order) {
int total = 0, position = head;
// No disk edge: the head turns at the outermost pending request.
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);
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 = look(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
Keeping the Starvation Guarantee
The important thing LOOK does not give up is SCAN's bound on waiting. Reversing earlier changes how far the head travels, not the property that it sweeps consistently in one direction and then the other, so a request still waits at most one sweep.
That is what makes LOOK the sensible default: it is strictly cheaper than SCAN and gives up nothing in return. This is unusual — most scheduling choices trade one property for another — and it is why textbooks present SCAN as the concept and LOOK as the implementation.
The one subtlety is that LOOK's sweep length now depends on the queue. If requests arrive in the region the head has just left, the head turns around sooner and the effective sweep shortens, which is good for those requests and neutral for the rest.
- The one-sweep waiting bound is unchanged
- Strictly cheaper than SCAN with no property given up
- SCAN is the concept; LOOK is what gets implemented
- Sweep length adapts to where the requests actually are
Where LOOK Still Runs Today
LOOK is the version of the elevator that actually shipped. Textbooks teach SCAN first, but the kernels that implemented elevator scheduling reversed at the last request rather than the disk edge, because travelling to a cylinder with nothing on it is indefensible.
Linux's long-serving cfq and the earlier as scheduler both merged and sorted requests this way, and the behaviour persists inside bfq, which remains the recommended scheduler for rotational drives. Beneath its fair-share accounting, bfq still merges adjacent requests and serves each process's queue in block order — LOOK's optimisation, applied per process rather than across the whole device.
On NVMe the optimisation disappears. There is no arm to turn around, so knowing where the last request sits saves nothing, and Linux defaults these devices to none. LOOK's saving was always the empty stretch of platter beyond the final request; when seeking is free, that stretch costs nothing to cross.
- Real kernels implemented LOOK, not SCAN — the edge trip was never worth it
bfqstill merges and sorts in block order beneath its fairness layer- It remains the recommended scheduler for rotational drives
- On NVMe the turnaround saves nothing, so Linux defaults to
none