Disk scheduling — FCFS, SCAN, C-SCAN, LOOK: Exercises

Intuition How to use this page

Each problem is graded L1 → L5 (Recognition → Application → Analysis → Synthesis → Mastery). Try it first, then open the collapsible Solution to check every step. After each level there is a [!mistake] callout that steel-mans the trap most students fall into at that level — the wrong path always feels reasonable, so we name it and fix it.

Everything here builds directly on the parent: the parent topic note. The one rule we lean on the whole time: $Total head movement = \sum_{i = 1}^{n} ∣ h_{i} - h_{i - 1} ∣$ where $h_{0}$ is the start position and $h_{1}, \dots, h_{n}$ is the order an algorithm chooses to visit cylinders. "Cylinder" = one track position the head can sit at (a "floor" for our elevator). See Hard Disk Drive structure (cylinders, tracks, sectors) for what a cylinder physically is.

A quick reminder of the number line we live on for the first block of problems:

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

Level 1 — Recognition

Exercise 1.1 (L1)

For each description, name the algorithm: FCFS, SCAN, C-SCAN, or LOOK.

(a) "Serve requests strictly in the order they arrived." (b) "Sweep one way, hit the physical edge (0 or max), reverse, serve the rest." (c) "Sweep one way to the last request only, then reverse — never touch the physical edge." (d) "Sweep one way, jump back to the far extreme without serving, sweep the same way again."

Recall Solution 1.1

(a) FCFS — no reordering at all. (b) SCAN — the elevator that hits the wall. (c) LOOK — it only "peeks" as far as the last request. (d) C-SCAN — the one-way circular escalator.

Why: the only thing that separates these is (i) whether they reorder, (ii) whether they touch the physical boundary, and (iii) whether they serve on the return trip. That triple fully classifies the family.

Exercise 1.2 (L1)

The head is at cylinder 50 and the next request served is cylinder 90. How many cylinders of head movement does this single move cost?

Recall Solution 1.2

One move costs $∣ h_{i} - h_{i - 1} ∣ = ∣ 90 - 50 ∣ = 40$ cylinders. That is literally one term of the sum in the formula — nothing more.

Level 2 — Application

Standard setup for this whole level: Queue (arrival order): 82, 170, 43, 140, 24, 16, 190 Head start $h_{0} = 50$ . Disk range: 0–199. Direction: up (toward larger cylinders) first. Sorted for reference: 16, 24, 43, 82, 140, 170, 190.

Exercise 2.1 (L2) — FCFS

Compute total head movement under FCFS.

Recall Solution 2.1

WHAT: walk the queue in arrival order, no sorting. Order: $50 \to 82 \to 170 \to 43 \to 140 \to 24 \to 16 \to 190$ . $∣ 82 - 50 ∣ + ∣ 170 - 82 ∣ + ∣ 43 - 170 ∣ + ∣ 140 - 43 ∣ + ∣ 24 - 140 ∣ + ∣ 16 - 24 ∣ + ∣ 190 - 16 ∣$ $= 32 + 88 + 127 + 97 + 116 + 8 + 174 = 642$ WHY the big numbers: the $170 \to 43$ and $16 \to 190$ jumps are the head bouncing across the whole disk — the signature waste of FCFS.

Exercise 2.2 (L2) — SCAN

Compute total head movement under SCAN (up first, disk end = 199).

Recall Solution 2.2

WHAT: go up serving everyone, touch 199, reverse, serve the rest down. Up path: $50 \to 82 \to 140 \to 170 \to 190 \to 199$ . Down path: $\to 43 \to 24 \to 16$ . Up movement: $199 - 50 = 149$ . Down movement: $199 - 16 = 183$ . $Total = 149 + 183 = 332$ WHY 199 appears twice implicitly: we travel to 199 (part of the 149) and from 199 (part of the 183). SCAN pays the full trip to the wall even though no request sits at 199.

Exercise 2.3 (L2) — LOOK

Same setup under LOOK.

Recall Solution 2.3

WHAT: identical order, but stop at the last actual up-request (190), never reach 199. Up: $50 \to 82 \to 140 \to 170 \to 190$ . Down: $\to 43 \to 24 \to 16$ . Up movement: $190 - 50 = 140$ . Down movement: $190 - 16 = 174$ . $Total = 140 + 174 = 314$ Check against SCAN: SCAN's extra cost is $2 \times (199 - 190) = 18$ , and indeed $332 - 314 = 18$ . ✔

Level 3 — Analysis

Setup for this level: Queue: 98, 183, 37, 122, 14, 124, 65, 67 · Head: 53 · Range: 0–199. (This is the parent note's standard example — reuse its known answers to check yourself.)

Exercise 3.1 (L3) — Direction matters

The parent computed SCAN up-first = 331. Now compute SCAN down-first (head moves toward cylinder 0 first, touches 0, then reverses up). Which direction is cheaper here, and why?

Recall Solution 3.1

Sorted: 14, 37, 65, 67, 98, 122, 124, 183. Down first: $53 \to 37 \to 14 \to 0$ , then up: $\to 65 \to 67 \to 98 \to 122 \to 124 \to 183$ . Down movement: $53 - 0 = 53$ . Up movement: $183 - 0 = 183$ . $Total = 53 + 183 = 236$ Compare: up-first SCAN $= 331$ , down-first SCAN $= 236$ . Down-first is cheaper by $95$ . WHY: the head at 53 is much closer to the bottom edge (0) than the top edge (199). Going toward the near wall first wastes far less on reaching the boundary. Direction is not cosmetic — it can swing the answer by ~30%.

Exercise 3.2 (L3) — C-SCAN with vs without the wrap counted

Compute C-SCAN (up first) two ways: (a) counting the wrap-around jump $199 \to 0$ , (b) ignoring the wrap (some textbooks do). State both totals.

Recall Solution 3.2

Up: $53 \to 65 \to 67 \to 98 \to 122 \to 124 \to 183 \to 199$ , then jump $199 \to 0$ , then up: $0 \to 14 \to 37$ .

Up to end: $199 - 53 = 146$ .
Wrap jump: $199 - 0 = 199$ .
Resume up to last: $37 - 0 = 37$ .

(a) With wrap: $146 + 199 + 37 = 382$ . (b) Without wrap: $146 + 37 = 183$ . WHY the ambiguity: the wrap is a real physical head movement, so counting it (382) is the honest total-travel number. But some courses treat the return as "instantaneous repositioning" and drop it (183). Always state your convention — the grader wants to see which you assumed.

Exercise 3.3 (L3) — C-LOOK

Compute C-LOOK (up first) with the wrap counted, for the same queue/head. Compare to C-SCAN(a).

Recall Solution 3.3

C-LOOK stops at the last up-request (183) and jumps back to the lowest request (14), not to 0. Up: $53 \to \dots \to 183$ , jump $183 \to 14$ , then up: $14 \to 37$ .

Up to last: $183 - 53 = 130$ .
Jump back: $183 - 14 = 169$ .
Resume up: $37 - 14 = 23$ .

$Total = 130 + 169 + 23 = 322$ Compare C-SCAN(a) $= 382$ : C-LOOK saves $382 - 322 = 60$ by avoiding the empty stretches $[183, 199]$ (top) and $[0, 14]$ (bottom). Precisely $2 \times (199 - 183) + 2 \times (14 - 0) = 32 + 28 = 60$ . ✔

Level 4 — Synthesis

Exercise 4.1 (L4) — Rank them all

For queue 98, 183, 37, 122, 14, 124, 65, 67, head 53, up-first, range 0–199, list FCFS / SCAN / LOOK / C-SCAN(with wrap) / C-LOOK(with wrap) totals and rank from least to most head movement.

Recall Solution 4.1

From the parent note and Exercises 3.2–3.3:

FCFS $= 640$
SCAN $= 331$
LOOK $= 299$
C-SCAN (wrap) $= 382$
C-LOOK (wrap) $= 322$

Ranking (least → most travel): $LOOK (299) < C-LOOK (322) < SCAN (331) < C-SCAN (382) < FCFS (640)$ WHY this order makes sense: the elevators (LOOK/SCAN) beat FCFS by killing zig-zag. Within elevators, "no boundary trip" (LOOK) beats "boundary trip" (SCAN), and the circular versions add wrap cost. FCFS is worst because it ignores geometry entirely.

Visual summary of the ranking:

Exercise 4.2 (L4) — Build a worst case for FCFS

Design a request queue of exactly 4 requests (head at 100, range 0–199) that makes FCFS's total head movement as large as possible. What is that maximum, and what ordering achieves it?

Recall Solution 4.2

WHAT to exploit: FCFS pays $∣ h_{i} - h_{i - 1} ∣$ for each consecutive pair, so we want each consecutive pair to span the full disk, alternating extremes. Queue: $0, 199, 0, 199$ (head starts at 100). $∣ 0 - 100 ∣ + ∣ 199 - 0 ∣ + ∣ 0 - 199 ∣ + ∣ 199 - 0 ∣ = 100 + 199 + 199 + 199 = 697$ WHY this is (near) maximal: after the first move lands on an extreme, every later move is a full-width $199$ swing. The only "waste-limited" term is the first ( $100$ , because the head started in the middle). Starting the head at an extreme instead (say 0) would give $199 \times 4 = 796$ , the true maximum for 4 full-swing requests. Lesson: FCFS's worst case is bounded only by how adversarial the arrival order is — this is exactly why smarter scheduling exists.

Level 5 — Mastery

Exercise 5.1 (L5) — Prove the SCAN vs LOOK gap

Head starts at $h_{0}$ , moves up first. Let $L$ be the largest requested cylinder ( $L < max$ ) and $S$ the smallest requested cylinder ( $S > 0$ ), with disk range $0.. M$ . Prove that $SCAN_{total} - LOOK_{total} = 2 (M - L) .$ (Assume there is at least one request below $h_{0}$ , so both algorithms reverse and sweep down to $S$ .)

Recall Solution 5.1

LOOK (up first): go up to the last request $L$ , then down to the smallest $S$ . $LOOK = (L - h_{0}) + (L - S)$ SCAN (up first): go up all the way to $M$ , then down to $S$ . $SCAN = (M - h_{0}) + (M - S)$ Subtract: $SCAN - LOOK = [(M - h_{0}) - (L - h_{0})] + [(M - S) - (L - S)]$ $= (M - L) + (M - L) = 2 (M - L) . ■$ WHY it's exactly this and nothing else: the down-portion of both trips ends at the same $S$ ; the only difference is how high the head climbed before reversing — $M$ vs $L$ — and that overshoot is paid twice (once going up, once coming back down through it). The start $h_{0}$ cancels because both algorithms leave from the same place. This is the algebra behind the parent note's rule "difference $= 2 \times (end - last request)$ ."

Exercise 5.2 (L5) — Latency-aware decision

A disk with range 0–199 has this pending queue (head at 100): 101, 102, 103, 0, 199. Rotational latency is negligible; seek dominates. A real-time request at cylinder 199 must be served within a movement budget of 120 cylinders or it misses its deadline. Under SCAN up-first, does cylinder 199 make its deadline? Under FCFS (arrival order as listed)? Which policy should the OS pick for this deadline, and what does it cost in total travel?

Recall Solution 5.2

SCAN up-first: $100 \to 101 \to 102 \to 103 \to 199$ (then down $\to 0$ ). Movement to reach 199: $199 - 100 = 99$ cylinders $\leq 120$ ✔ — deadline met. Total SCAN travel: up $199 - 100 = 99$ , down $199 - 0 = 199$ → $298$ .

FCFS (order 101, 102, 103, 0, 199): the head visits $100 \to 101 \to 102 \to 103 \to 0 \to 199$ . Movement to reach 199 = sum of all prior legs plus the last: $1 + 1 + 1 + 103 + 199 = 305 cylinders > 120 \Rightarrow deadline MISSED.$ (The detour down to 0 before 199 blows the budget.) Total FCFS travel here $= 305$ .

Decision: choose SCAN (up-first). It meets the 199 deadline (99 ≤ 120) and has lower total travel (298 < 305). Here the elevator wins on both axes — but the general point (see I/O Subsystem and Device Drivers) is that real schedulers weigh deadlines, not just the raw sum.

Recall One-line self-test recap

LOOK ≤ SCAN by 2×(end−last) ::: proven in 5.1 FCFS never reorders ::: even if sorting would help (2.1 trap) C-SCAN pays a wrap jump for fairness ::: 382 with wrap vs 183 without (3.2) Direction can change SCAN's total a lot ::: 331 up-first vs 236 down-first (3.1) "Best" needs a metric ::: total travel vs fairness vs deadline (4.1 trap, 5.2)

Connections

4.2.38 Disk scheduling — FCFS, SCAN, C-SCAN, LOOK (Hinglish)
Seek time vs Rotational latency
Hard Disk Drive structure (cylinders, tracks, sectors)
Process Scheduling — FCFS, SJF, Round Robin
Starvation and Fairness in OS
SSTF (Shortest Seek Time First)
I/O Subsystem and Device Drivers