Intuition What this page isThe parent note taught you the four algorithms on one tidy queue. Real exams and real disks throw messier inputs: the head at the very edge, all requests on one side, a tie, a degenerate single request, "which direction did we start?", and word problems in milliseconds instead of cylinders. This page marches through every case class so you never meet a scenario you haven't seen.
Before we start, one reminder of the only rule that matters (built in the parent):
Definition The C-SCAN / C-LOOK wrap jump — do we count it?When a circular scan finishes a sweep it jumps across the disk to reset (e.g. 199→0). On this page we count that jump as real head travel , because the head physically slews across the platter and that takes time. Some textbooks instead treat the reset as "free" (a fast full-speed seek not charged to any request) and drop it from the total. Both conventions are common — always state which you use. Every C-SCAN/C-LOOK number below includes the wrap jump.
Every disk-scheduling problem is built from a few independent choices. This table lists each case class — the odd corners that trip people up — and the example below that nails it.
#
Case class
What makes it special
Example
A
Head in the middle , requests both sides
the "normal" case, all 4 algos
Ex 1
B
Head at the low edge (0)
no down-travel exists; SCAN reversal is trivial
Ex 2
C
Head at the high edge (max)
starts already at the wall
Ex 3
D
All requests above the headdirection down wastes a whole trip
Ex 4
E
Direction = down first mirror image; tests you didn't hard-code "up"
Ex 5
F
Degenerate: one request (and empty queue)limiting case, sum has one term or zero
Ex 6
G
Duplicate / tie at head or between requests$
h_i-h_{i-1}
H
Word problem in milliseconds (seek-rate given)convert cylinders → time, real units
Ex 8
I
Exam twist: C-LOOK + "compare all four" wrap-jump to last request, ranking
Ex 9
J
Circular scans going DOWN first C-SCAN/C-LOOK jump upward on the wrap
Ex 10
K
Request sits exactly ON a wall (0 or 199)is the trip to the wall "free" or paid?
Ex 11
We use a fresh, small queue so the arithmetic is checkable by hand:
Queue = {90, 20, 150, 60, 10} , disk range 0–199 , unless a case overrides it.
Sorted for reference: 10, 20, 60, 90, 150 .
The figure below draws exactly this setup. Keep it in view as you read Case A — the amber square is the head, the cyan dots are pending requests, and the two arrows show how the head position "cuts" the queue into an up-side and a down-side. Every algorithm below is just a different rule for combining those two sides.
Figure s01 — the standard scenario on a cylinder axis (0 to 199): amber square = head at 70, cyan dots = requests {10, 20, 60, 90, 150}. The amber arrow points to the up-side requests {90, 150}; the cyan arrow points to the down-side requests {60, 20, 10}.
Worked example (Cell A) Head at 70, all four algorithms, up first.Queue = {90, 20, 150, 60, 10}, head = 70, range 0–199, direction up .
Forecast: which do you think travels least — FCFS, SCAN, LOOK, or C-SCAN? Guess before reading. (Look at figure s01 above — the head at 70 has two requests up and three down.)
Sorted: 10, 20, 60, 90, 150. Head 70 splits them: below = {60, 20, 10}, above = {90, 150}.
Step 1 — FCFS (arrival order 90, 20, 150, 60, 10). Here h 0 = 70 ∣90 − 70∣ + ∣20 − 90∣ + ∣150 − 20∣ + ∣60 − 150∣ + ∣10 − 60∣ = 20 + 70 + 130 + 90 + 50 = 360 Why this step? FCFS forbids reordering, so we literally walk the queue as it arrived — the 20→150→60 zig-zag is the cost of "fairness with no thinking".
Step 2 — SCAN up. Go up hitting 90, 150, then to the wall 199, reverse down to 60, 20, 10.
Up part: 199 − 70 = 129 199 − 10 = 189 Total = 129 + 189 = 318 Why this step? SCAN must touch the physical boundary 199 even though no request is there — that's the definition. Up-distance is just (end − start); down-distance is (end − lowest request) because it sweeps from 199 down to 10.
Step 3 — LOOK up. Up to the last request 150 (not 199), then down to 10.
Up: 150 − 70 = 80 150 − 10 = 140 Total = 80 + 140 = 220 Why this step? LOOK peeks — it reverses at 150, the furthest real request, saving the wasted 2 × ( 199 − 150 ) = 98 318 − 220 = 98
Step 4 — C-SCAN up. Up to 150 then wall 199, jump 199→0, then up 0→10→20→60.
Up to end: 199 − 70 = 129 199 − 0 = 199 60 − 0 = 60 Total = 129 + 199 + 60 = 388 Why this step? C-SCAN never serves on the way back; it resets to 0 for uniform waiting. The 199 jump is the price of fairness (and, per the convention box, we count it).
Verify: Ranking LOOK (220) < SCAN (318) < FCFS (360) < C-SCAN (388). Units are cylinders throughout. Sanity: LOOK ≤ SCAN always (it never adds boundary trips) ✔; C-SCAN largest here because of the wrap jump ✔.
Before the edge cases, let's nail down a fact we'll reuse. First, two names we'll keep using:
E the "end" , i.e. the physical wall SCAN is heading toward (the high wall is E = 199 E = 0 L the "last real request" , i.e. the furthest cylinder in that direction that an actual request lives on.
Suppose SCAN is sweeping up , so the last real request is at cylinder L E E − L up to reach the wall, and then — because it reverses and comes back down through that same empty stretch — it travels E − L down again before it meets any request. So the wasted distance for touching an unneeded wall is:
waste = 2 ( E − L ) 2 is the up-then-back-down round trip. LOOK avoids it entirely by turning around at L 2 × ( 199 − 150 ) E = 199 L = 150 Keep this "×2" in mind — it only appears when the head both goes to the wall and comes back through the same gap. When the head starts on a wall, there is no coming back through that gap, so the ×2 does not apply (see Case B).
Worked example (Cell B) Head at 0, SCAN and LOOK, up first.Queue = {90, 20, 150, 60, 10}, head = 0 , range 0–199.
Forecast: If the head is already at 0, does "reverse and go down" cost anything?
Step 1 — SCAN up from 0. There is nothing below 0, so the down-sweep is empty. Head goes 0→10→20→60→90→150→199.
Total = 199 − 0 = 199 Why this step? When the head sits on a boundary, one of SCAN's two sweeps has zero requests. The reversal distance collapses to nothing — you only pay the up trip to 199.
Step 2 — LOOK up from 0. Stops at last request 150.
Total = 150 − 0 = 150 Why this step? Recall the "×2" rule from the box above (with E = 199 L = 150 2 ( E − L ) and comes back down through the empty stretch. But here the head starts at the low wall and only ever sweeps upward — it never returns through the 150 → 199 once , and LOOK's saving is therefore the single 199 − 150 = 49 2 × 49
Verify: 199 − 150 = 49
Worked example (Cell C) Head at 199, LOOK, natural direction = down.Queue = {90, 20, 150, 60, 10}, head = 199 .
Forecast: From the top wall, which way can the head even go?
Step 1 — pick direction. Every request is below 199, so the only sensible direction is down . Serve 150, 90, 60, 20, 10.
Total = 199 − 10 = 189 Why this step? At the high edge, "up first" would immediately reverse (nothing above), so LOOK really just does one clean down-sweep from 199 to the lowest request 10.
Verify: 199 − 10 = 189 ∣199 − 150∣ + ∣150 − 90∣ + ∣90 − 60∣ + ∣60 − 20∣ + ∣20 − 10∣ = 49 + 60 + 30 + 40 + 10 = 189
Worked example (Cell D) Head at 5, all requests above, SCAN down-first vs up-first.Queue = {90, 20, 150, 60, 10}, head = 5 .
Forecast: If you wrongly start SCAN going down , how much do you waste?
Step 1 — SCAN up first (correct instinct). Nothing below 5, so up: 5→10→20→60→90→150→199, no return.
Total = 199 − 5 = 194 Why this step? All requests are above, so "up first" needs no return sweep — the down side is empty.
Step 2 — SCAN down first (the trap). Head must first go 5→0 (to the low wall), then reverse all the way up to 199.
Down: 5 − 0 = 5 199 − 0 = 199 Total = 5 + 199 = 204 Why this step? Choosing the empty direction first forces a wasted round trip to the near wall. Cost of the wrong choice: 204 − 194 = 10 = 2 × 5
Verify: The wasted amount is exactly 2 × ( head − 0 ) = 2 × 5 = 10
Worked example (Cell E) Head at 70, SCAN and LOOK, directiondown first.
Queue = {90, 20, 150, 60, 10}, head = 70, range 0–199.
Forecast: Same queue as Case A but going down first — will LOOK's total change?
Step 1 — LOOK down. Serve below first: 70→60→20→10, then reverse up: →90→150.
Down: 70 − 10 = 60 150 − 10 = 140 Total = 60 + 140 = 200 Why this step? Now the down-side is served first. We go to the lowest request 10, then sweep up to the highest 150. Direction changed the order , hence the number (was 220 up-first).
Step 2 — SCAN down. 70→0 (low wall), reverse up to 199.
Down: 70 − 0 = 70 199 − 0 = 199 Total = 70 + 199 = 269 Why this step? SCAN touches the low wall 0 this time. Compare LOOK: SCAN wastes 2 × ( 10 − 0 ) = 20 199 − 150 = 49 200 + 20 + 49 = 269
Verify: LOOK down (200) < LOOK up (220) here — direction genuinely affects the answer, so "which direction" is never optional. ✔
Worked example (Cell F) The limiting cases.F1 — one request. Head 53, queue = {110}. F2 — empty queue. Head 53, queue = {}.
Forecast: What does the sum ∑ ∣ h i − h i − 1 ∣
Step 1 — one request (F1). Order is just 53 → 110 Total = ∣110 − 53∣ = 57 Why this step? With one request every algorithm agrees — there is no ordering to choose. FCFS = SCAN = LOOK = C-SCAN = 57 (ignoring boundary/wrap, which no textbook counts when there's nothing beyond).
Step 2 — empty queue (F2). The service order is just h 0 empty .
Total = ∑ i = 1 0 ∣ h i − h i − 1 ∣ = 0 Why this step? An empty sum is 0 by definition — the head never moves because there is nothing to serve. This is the smallest possible answer and a good "does my code crash?" test.
Verify: F1 = 57 for every algorithm; F2 = 0. These are the boundary values that stress-test any implementation. ✔
Worked example (Cell G) Head at 60, a request AT the head and a tie.Queue = {60, 60, 120, 20}, head = 60 , LOOK up first.
Forecast: A request equal to the current position — does it add travel?
Step 1 — serve the requests at the head. Two requests sit at 60, exactly where the head is.
∣60 − 60∣ + ∣60 − 60∣ = 0 + 0 = 0 Why this step? ∣ h i − h i − 1 ∣ = 0 free travel . Serve them immediately, cost zero.
Step 2 — continue LOOK up then down. Remaining sorted: below = {20}, above = {120}. Up first: 60→120, then down 120→20.
Up: 120 − 60 = 60 120 − 20 = 100 Total = 0 + 60 + 100 = 160 Why this step? Ties never change the distance total (they add zeros); they only affect the count of I/O operations, not head travel. Order among equal cylinders is arbitrary.
Verify: Total = 160; the two duplicate 60's contribute exactly 0, so removing one would give the same head movement. ✔
Worked example (Cell H) Real units. Seek rate given.Head at 100, queue = {40, 180, 90}, range 0–199. Each cylinder crossed costs 0.2 ms of seek time; there is a flat 1 ms per request for rotation+transfer. Use LOOK, up first . How long total?
Forecast: Which dominates — the seek time or the fixed per-request time?
Step 1 — find head movement (cylinders). Sorted: 40, 90, 180. Above 100 = {180}, below = {40, 90}. LOOK up: 100→180, then down: 180→90→40.
Up: 180 − 100 = 80 180 − 40 = 140 Movement = 80 + 140 = 220 cylinders Why this step? Time comes from travel, so we must get the cylinder count first — the algorithm's whole job.
Step 2 — convert cylinders to seek time.
220 × 0.2 ms = 44 ms Why this step? "0.2 ms per cylinder" is a rate (ms/cylinder). Multiplying rate × cylinders cancels cylinders and leaves ms — a units check that we did it right. See Seek time vs Rotational latency .
Step 3 — add fixed per-request cost. There are 3 requests, each 1 ms.
3 × 1 ms = 3 ms Total = 44 ms + 3 ms = 47 ms Why this step? Seek is only part of disk access; rotation and transfer are separate flat costs here. Total access = seek + fixed.
Verify: 220 × 0.2 = 44 + 3 = 47 ( cyl ) ( ms/cyl ) + ( req ) ( ms/req ) = ms
Worked example (Cell I) Head at 50, C-LOOK, then rank all four.Queue = {82, 170, 43, 140, 24, 16, 190}, head = 50 , range 0–199, up first.
Forecast: C-LOOK is C-SCAN's thrifty cousin. Where does it jump to — 0 or the lowest request?
Sorted: 16, 24, 43, 82, 140, 170, 190. Above 50 = {82,140,170,190}; below = {43,24,16}.
Step 1 — C-LOOK sweep up. 50→82→140→170→190 (last request, not 199).
Up: 190 − 50 = 140 Why this step? Like LOOK, C-LOOK stops at the last real request (190), never the physical wall.
Step 2 — jump to the lowest request (not 0). Jump 190→16.
Jump: 190 − 16 = 174 Why this step? C-LOOK resets to the lowest pending request (16), not cylinder 0 — that's the "LOOK" saving applied to the wrap. (C-SCAN would jump to 0.) Per the convention box, we count this jump.
Step 3 — finish the upward sweep. 16→24→43.
16 → 24 → 43 : 43 − 16 = 27 Total = 140 + 174 + 27 = 341 Why this step? After the wrap we continue up through the remaining low requests, ending at the highest of them (43).
Step 4 — the other three for ranking.
LOOK up: up 50→190 = 140; down 190→16 = 174. Total = 140 + 174 = 314 SCAN up: up 50→199 = 149; down 199→16 = 183. Total = 149 + 183 = 332 C-SCAN up: up 50→199 = 149; jump 199→0 = 199; up 0→43 = 43. Total = 149 + 199 + 43 = 391 Why this step? Exams love "compute all four and rank". The pattern: LOOK ≤ SCAN, and C-LOOK ≤ C-SCAN, with the circular pair usually larger due to the jump.
Verify: Ranking LOOK (314) < SCAN (332) < C-LOOK (341) < C-SCAN (391). Checks: LOOK ≤ SCAN (314≤332) ✔; C-LOOK ≤ C-SCAN (341≤391) ✔; SCAN−LOOK = 332 − 314 = 18 = 2 ( 199 − 190 )
So far C-SCAN and C-LOOK swept up and wrapped downward (to 0 or to the lowest request). The mirror case sweeps down first and therefore wraps upward — you must flip every "0/lowest" to "199/highest". This is the case textbooks omit and exams exploit.
Worked example (Cell J) Head at 100, C-SCAN and C-LOOK, directiondown first.
Queue = {90, 20, 150, 60, 10}, head = 100 , range 0–199.
Forecast: Going down first, does the wrap jump go to 0 or to 199?
Sorted: 10, 20, 60, 90, 150. Below 100 = {90, 60, 20, 10}; above = {150}.
Step 1 — C-SCAN down. Sweep down 100→90→60→20→10→0 (low wall), then jump up 0→199, then continue down 199→150.
Down to wall: 100 − 0 = 100 199 − 0 = 199 199 − 150 = 49 Total = 100 + 199 + 49 = 348 Why this step? C-SCAN going down services on the way down only, drives to the low wall 0, then resets to the high wall 199 and keeps servicing downward. The wrap is a full-disk 199 − 0
Step 2 — C-LOOK down. Sweep down 100→90→60→20→10 (last request, not 0), then jump up 10→150 (highest pending request, not 199), done.
Down to last: 100 − 10 = 90 150 − 10 = 140 Total = 90 + 140 = 230 Why this step? C-LOOK trims both ends: it reverses at the lowest request 10 (not wall 0) and wraps to the highest request 150 (not wall 199). Down-first flips the roles of "lowest" and "highest" compared with Case I.
Verify: C-LOOK (230) < C-SCAN (348), same ordering as the up-first pair. The C-SCAN wrap is the full width 199 − 0 = 199 150 − 10 = 140
Worked example (Cell K) Head at 80, a request AT cylinder 0 and one AT 199.Queue = {199, 30, 0, 120}, head = 80 , range 0–199, SCAN and LOOK, up first.
Forecast: SCAN and LOOK normally differ by 2 ( E − L ) at the wall, does that gap vanish?
Sorted: 0, 30, 120, 199. Above 80 = {120, 199}; below = {30, 0}.
Step 1 — LOOK up. Last up-request is 199 (which happens to be the wall). Up 80→120→199, then down 199→30→0.
Up: 199 − 80 = 119 199 − 0 = 199 Total = 119 + 199 = 318 Why this step? LOOK reverses at the last real request. Here that request is 199, so LOOK is forced to the top anyway — the trip to the wall is no longer "wasted", it is paid for by a real request .
Step 2 — SCAN up. SCAN also stops at 199 (the wall), then reverses to 0.
Up: 199 − 80 = 119 199 − 0 = 199 Total = 119 + 199 = 318 Why this step? Because a request lives exactly at 199, the "last request" L E E − L = 0 2 × 0 = 0 coincide exactly. The same happens at the low wall: the request at 0 means both algorithms bottom out at 0 with no wasted stretch.
Verify: SCAN total = = 318 2 ( E − L ) 2 ( 199 − 199 ) = 0
Common mistake Jumping C-LOOK back to 0 instead of the lowest request.Why it feels right: C-SCAN jumps to 0, so surely C-LOOK does too. The fix: the "LOOK" in C-LOOK means both ends are trimmed to real requests — it wraps to the lowest pending request (up-first) or the highest pending request (down-first), never the physical wall. Wrapping to the wall overcounts.
Common mistake Assuming circular scans only ever wrap downward.Why it feels right: every textbook example sweeps up and jumps to 0. The fix: direction flips the wrap. Down-first C-SCAN drives to the low wall then jumps up to 199; down-first C-LOOK reverses at the lowest request then wraps up to the highest request (Case J).
Common mistake Treating the trip to a wall as always "wasted" (LOOK < SCAN).Why it feels right: the ×2 rule says LOOK saves 2 ( E − L ) The fix: if a real request sits on the wall, then L = E 2 × 0 = 0
Common mistake Using the boundary in a limiting case with no requests beyond it.Why it feels right: "SCAN always touches the wall." The fix: if the head starts at the edge (Case B/C) or there's a single request (Case F), there's no meaningful second sweep — don't invent a return trip. Let the empty sum be 0.
Recall Self-test — one line eachEmpty queue total head movement? ::: 0 (empty sum, head never moves).
C-LOOK wraps back to which cylinder (up-first)? ::: The lowest pending request, not physical 0.
C-SCAN going down-first jumps to which wall? ::: The high wall 199 (then keeps servicing downward).
If a real request sits exactly on the wall, how do SCAN and LOOK compare? ::: They coincide, since E − L = 0 2 ×
4.2.38 Disk scheduling — FCFS, SCAN, C-SCAN, LOOK (Hinglish) — parent (Hinglish)Seek time vs Rotational latency — the ms conversion in Case HHard Disk Drive structure (cylinders, tracks, sectors) — why cylinders are the unitSSTF (Shortest Seek Time First) — the greedy cousin that can starveStarvation and Fairness in OS — why C-SCAN/C-LOOK existProcess Scheduling — FCFS, SJF, Round Robin — same ordering trade-offsI/O Subsystem and Device Drivers 