Disk scheduling — FCFS, SCAN, C-SCAN, LOOK: Visual walkthrough

We keep the same setup the whole way through so the pictures stack on top of each other:

Step 1 — Draw the disk as a ruler

WHAT: Before any algorithm, we lay out the physical stage. A hard disk's cylinders are numbered concentric rings. We flatten them into a straight number line from $0$ to $199$ . The read/write head sits at one number at a time; here it starts at $53$ .

WHY a straight line and not the real circular platter? Because the cost we care about — seek time — depends only on how far the head slides across cylinders, i.e. the difference between two cylinder numbers. Direction on the physical circle doesn't matter; only the distance-along-the-ruler does. So a 1-D ruler captures 100% of what we need and throws away nothing important.

PICTURE: The eight requests are pink ticks; the head is the yellow dot at $53$ . Notice how scattered the requests are — some below $53$ , most above. This scatter is the entire problem: we must visit every pink tick, and we want the shortest walk.

Figure — Disk scheduling — FCFS, SCAN, C-SCAN, LOOK

Step 2 — Define "cost" as the length of a path

WHAT: We now say precisely what "better" means. Suppose the algorithm decides to serve requests in some order, so the head visits positions $h_{0}, h_{1}, h_{2}, \dots, h_{n}$ in that sequence. One single move from $h_{i - 1}$ to $h_{i}$ slides the head by $∣ h_{i} - h_{i - 1} ∣$ cylinders.

WHY the absolute value $∣ \cdot ∣$ ? Distance can't be negative. If the head goes from $124$ down to $65$ , the number $65 - 124 = - 59$ is negative, but the effort is $59$ cylinders of sliding. The bars $∣ ∣$ mean "throw away the minus sign — I only care how far, not which way."

WHY do we add the moves up? Because the head physically slides one segment, then the next, then the next. Total wear = segment $1$ + segment $2$ + $\dots$ Travel is additive, exactly like adding up the legs of a road trip.

PICTURE: Two example moves drawn as arcs above the ruler, each labelled with its length. The number under each arc is a term in the sum. An algorithm is just a choice of which arcs to draw and in what order — the total is the same picture measured with a ruler.

Step 3 — FCFS: obey the queue, pay for the zig-zag

WHAT: First-Come-First-Served makes no choice — it visits requests in arrival order. So the path is forced: $53 \to 98 \to 183 \to 37 \to 122 \to 14 \to 124 \to 65 \to 67.$

WHY show this first? It is the baseline "dumb" walk. Because it never reorders, the head lurches far up ( $183$ ) then far down ( $37$ ) then up again — every reversal is wasted travel. This is our yardstick: every clever algorithm must beat $640$ .

PICTURE: The path is drawn as a time-graph — vertical axis is cylinder number, horizontal axis is "which request in order." Watch the line stab up and down like a heartbeat. Each near-vertical plunge (like $183 \to 37$ ) is a giant term in the sum.

Step 4 — SCAN: sweep up to the wall, then back down

WHAT: SCAN sorts the requests and sweeps in one direction first. Going up from $53$ , it serves every request in increasing order until it hits the physical end $199$ (the "wall"), even though no request lives at $199$ . Then it turns around and serves the remaining lower requests on the way down.

Path: $53 \to 65 \to 67 \to 98 \to 122 \to 124 \to 183 \to 199 \to 37 \to 14$ .

WHY go all the way to $199$ ? That is SCAN's defining rule — it behaves like a building elevator that always rides to the top floor before reversing. This is contrast fuel for LOOK in the next step: the trip to the empty wall is optional travel.

WHY does this beat FCFS? No zig-zag. All up-requests are done in one clean climb, all down-requests in one clean descent. The line has exactly one turn instead of six.

PICTURE: Same time-graph style. One smooth climb to $199$ (yellow), one smooth descent to $14$ (blue). The little stub from $183$ up to the wall $199$ and back down is highlighted — that stub is what LOOK will delete.

Step 5 — LOOK: don't ride to the empty wall

WHAT: LOOK is SCAN that peeks ahead: it stops climbing at the last actual request in that direction ( $183$ ) instead of the wall ( $199$ ), then reverses.

Path: $53 \to 65 \to 67 \to 98 \to 122 \to 124 \to 183 \to 37 \to 14$ .

WHY is this always at least as good as SCAN? Because it deletes the pointless out-and-back to the wall. SCAN climbed to $199$ then came back down past $183$ — that extra stub costs $2 \times (199 - 183) = 32$ cylinders. LOOK simply never pays it.

PICTURE: The SCAN path is drawn faint in the background; LOOK is drawn bold on top. The only visible difference is the missing triangle at the top (the deleted $183 \to 199 \to 183$ stub), shaded pink and labelled " $32$ saved."

Step 6 — C-SCAN: one-way service, jump home, sweep again

WHAT: C-SCAN (Circular SCAN) serves only while going up. It climbs to the wall $199$ , then jumps all the way back to $0$ without serving anything on the way, and starts a fresh upward sweep to pick up the requests it skipped ( $14$ , then $37$ ).

Path: $53 \to \dots \to 183 \to 199 \to jump, no service 0 \to 14 \to 37$ .

WHY throw away the return trip? Fairness. In SCAN, a request that just missed the upward sweep waits for the entire down-and-up cycle — the edges wait longest. C-SCAN makes every request wait the same style of trip (always served going up), so no cylinder starves at the far edge. The price is the big empty jump.

PICTURE: The climb (yellow) to $199$ , then a dashed vertical drop straight to $0$ marked "wrap jump — no service," then a short climb (blue) to $37$ . The dashed segment visually screams "this is the cost of fairness."

Step 7 — Edge & degenerate cases (never get surprised)

WHAT: The rules must still work when inputs are weird. Four scenarios, all drawn on tiny rulers:

All requests above the start — then "down first" serves nothing on the way down; the head goes straight up. SCAN/LOOK have effectively one direction.
All requests below the start — mirror image; going up first wastes a trip.
Head starts exactly on a request — first move distance is $0$ ; that request is served free, no double counting.
Empty queue — total head movement is $0$ ; there is nothing to do.

WHY care? The parent note warns you must pick a start and a direction. These cases show the direction choice can change the total dramatically, and the formula still holds (it just sums fewer, or zero, terms).

PICTURE: Four mini-rulers side by side, each with its head dot and requests, and the resulting one-turn path. Case 4 is just a lone dot: "path length $0$ ."

The one-picture summary

WHAT: All four paths on one ruler-vs-time chart, so you can literally see which line is shortest. FCFS zig-zags (longest, $640$ ). SCAN and LOOK each make one clean turn (LOOK shorter by the deleted wall-stub). C-SCAN adds the tall dashed wrap jump.

WHY this is the payoff: total head movement = length of the drawn line. Shorter line = less seek time. But C-SCAN's longer line buys fairness — proof that "smallest total" is not automatically "best."

Algo	Path shape	Total (this setup)	Buys you
FCFS	zig-zag	$640$	simplicity, fairness of order
SCAN	up→wall→down	$331$	elevator smoothness
LOOK	up→last→down	$299$	least travel here
C-SCAN	up→wall→jump→up	$382$	uniform waiting

Recall Feynman: the whole walkthrough in plain words

Picture a hallway numbered $0$ to $199$ and a cleaning robot parked at door $53$ . It has a list of doors to visit. The dumb robot (FCFS) walks to whichever door was requested first, so it sprints up the hall, back down, up again — exhausting ( $640$ steps). The elevator robot (SCAN) is smarter: it walks up the hall opening every door on the way, marches all the way to the far wall at $199$ (even though the last door was $183$ ), then turns and walks back opening the rest ( $331$ ). The peeking robot (LOOK) is the same but says "why touch the wall? my last door up here is $183$ , I'll turn there" — saving those $32$ wasted steps ( $299$ ). The one-way robot (C-SCAN) only opens doors while walking up; when it reaches the wall it zooms straight back to door $0$ opening nothing, then sweeps up again — so the poor soul at door $1$ never waits forever, but the empty sprint back costs a lot ( $382$ ). Measure each robot's footprints: the length of its path is the seek cost. Shortest footprints win on speed — but the one-way robot wins on being fair.

Connections

4.2.38 Disk scheduling — FCFS, SCAN, C-SCAN, LOOK (Hinglish) — parent, Hinglish version
Seek time vs Rotational latency — what the path length actually costs in time
Hard Disk Drive structure (cylinders, tracks, sectors) — why cylinders form our ruler
SSTF (Shortest Seek Time First) — the greedy cousin of these algorithms
Starvation and Fairness in OS — why C-SCAN pays for fairness
Process Scheduling — FCFS, SJF, Round Robin — the same ordering trade-offs for the CPU
I/O Subsystem and Device Drivers — where the request queue lives