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

4.2.38 · D4 · Coding › Operating Systems › Disk scheduling — FCFS, SCAN, C-SCAN, LOOK

Intuition Is page ko kaise use karein

Har problem ko L1 → L5 (Recognition → Application → Analysis → Synthesis → Mastery) grade diya gaya hai. Pehle khud try karo, phir collapsible Solution kholo aur har step check karo. Har level ke baad ek [!mistake] callout hai jo us level par students ke saath sabse zyada hone wala trap clearly batata hai — galat raasta hamesha reasonable lagta hai, isliye hum usse naam dekar fix karte hain.

Yahan sab kuch seedha parent note se build hota hai: the parent topic note. Poore time hum ek hi rule pe rely karte hain: $Total head movement = \sum_{i = 1}^{n} ∣ h_{i} - h_{i - 1} ∣$ jahan $h_{0}$ start position hai aur $h_{1}, \dots, h_{n}$ wo order hai jisme algorithm cylinders visit karna choose karta hai. "Cylinder" = ek track position jahan head baithta hai (hamare elevator ke liye ek "floor"). Dekho Hard Disk Drive structure (cylinders, tracks, sectors) ki cylinder physically kya hota hai.

Pehle block of problems ke liye jo number line use hogi uska ek quick reminder:

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

Level 1 — Recognition

Exercise 1.1 (L1)

Har description ke liye algorithm ka naam batao: FCFS, SCAN, C-SCAN, ya LOOK.

(a) "Requests ko strictly usi order mein serve karo jisme wo aaye." (b) "Ek direction mein sweep karo, physical edge (0 ya max) tak jao, reverse karo, baaki serve karo." (c) "Ek direction mein sirf last request tak sweep karo, phir reverse karo — physical edge kabhi touch mat karo." (d) "Ek direction mein sweep karo, bina serve kiye far extreme par jump karo, wahi direction mein phir sweep karo."

Recall Solution 1.1

(a) FCFS — bilkul koi reordering nahi. (b) SCAN — wo elevator jo wall se takraata hai. (c) LOOK — yeh sirf last request tak "peek" karta hai. (d) C-SCAN — one-way circular escalator.

Kyun: in sabko sirf yeh teen cheezein alag karti hain: (i) kya reorder karte hain, (ii) kya physical boundary touch karte hain, aur (iii) kya return trip par serve karte hain. Yeh triple poori family ko fully classify kar deta hai.

Exercise 1.2 (L1)

Head cylinder 50 par hai aur next request cylinder 90 hai. Is single move ki cost kitne cylinders ki hogi?

Recall Solution 1.2

Ek move ki cost hai $∣ h_{i} - h_{i - 1} ∣ = ∣ 90 - 50 ∣ = 40$ cylinders. Yeh literally formula ke sum ka ek term hai — kuch nahi iske ilawa.

Level 2 — Application

Is poore level ke liye standard setup: Queue (arrival order): 82, 170, 43, 140, 24, 16, 190 Head start $h_{0} = 50$ . Disk range: 0–199. Direction: pehle up (bade cylinders ki taraf). Reference ke liye sorted: 16, 24, 43, 82, 140, 170, 190.

Exercise 2.1 (L2) — FCFS

FCFS ke under total head movement compute karo.

Recall Solution 2.1

KYA: queue ko arrival order mein walk karo, koi sorting nahi. 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$ Bade numbers kyun: $170 \to 43$ aur $16 \to 190$ jumps mein head poori disk cross karta hai — yeh FCFS ki signature waste hai.

Exercise 2.2 (L2) — SCAN

SCAN (up first, disk end = 199) ke under total head movement compute karo.

Recall Solution 2.2

KYA: upar jaao sabko serve karo, 199 touch karo, reverse lo, baaki neeche serve karo. 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$ 199 implicitly do baar kyun aata hai: hum 199 tak travel karte hain (149 ka hissa) aur 199 se travel karte hain (183 ka hissa). SCAN wall tak poora trip pay karta hai chahe 199 par koi request na ho.

Exercise 2.3 (L2) — LOOK

Same setup, LOOK ke under.

Recall Solution 2.3

KYA: identical order, lekin last actual up-request (190) par ruko, 199 kabhi mat jao. 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$ SCAN se check karo: SCAN ki extra cost $2 \times (199 - 190) = 18$ hai, aur indeed $332 - 314 = 18$ . ✔

Level 3 — Analysis

Is level ke liye setup: Queue: 98, 183, 37, 122, 14, 124, 65, 67 · Head: 53 · Range: 0–199. (Yeh parent note ka standard example hai — khud check karne ke liye iske known answers reuse karo.)

Exercise 3.1 (L3) — Direction matters

Parent ne SCAN up-first = 331 compute kiya. Ab SCAN down-first compute karo (head pehle cylinder 0 ki taraf move karta hai, 0 touch karta hai, phir upar reverse karta hai). Yahan kaun sa direction sasta hai, aur kyun?

Recall Solution 3.1

Sorted: 14, 37, 65, 67, 98, 122, 124, 183. Down first: $53 \to 37 \to 14 \to 0$ , phir upar: $\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 $95$ se sasta hai. KYun: head 53 par bottom edge (0) ke bahut paas hai, top edge (199) se nahi. Paas wali wall ki taraf pehle jaane par boundary reach karne mein bahut kam waste hoti hai. Direction cosmetic nahi hai — yeh answer ko ~30% tak swing kar sakta hai.

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

C-SCAN (up first) do taron se compute karo: (a) wrap-around jump $199 \to 0$ count karke, (b) wrap ignore karke (kuch textbooks aisa karte hain). Dono totals batao.

Recall Solution 3.2

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

End tak upar: $199 - 53 = 146$ .
Wrap jump: $199 - 0 = 199$ .
Last tak resume up: $37 - 0 = 37$ .

(a) Wrap ke saath: $146 + 199 + 37 = 382$ . (b) Wrap ke bina: $146 + 37 = 183$ . Ambiguity kyun: wrap ek real physical head movement hai, isliye usse count karna (382) honest total-travel number hai. Lekin kuch courses return ko "instantaneous repositioning" treat karte hain aur drop kar dete hain (183). Hamesha apna convention clearly batao — grader dekhna chahta hai tumne kaunsa assume kiya.

Exercise 3.3 (L3) — C-LOOK

Same queue/head ke liye C-LOOK (up first) wrap count karke compute karo. C-SCAN(a) se compare karo.

Recall Solution 3.3

C-LOOK last up-request (183) par rukta hai aur lowest request (14) par jump karta hai, 0 par nahi. Up: $53 \to \dots \to 183$ , jump $183 \to 14$ , phir upar: $14 \to 37$ .

Last tak upar: $183 - 53 = 130$ .
Jump back: $183 - 14 = 169$ .
Resume up: $37 - 14 = 23$ .

$Total = 130 + 169 + 23 = 322$ C-SCAN(a) $= 382$ se compare karo: C-LOOK $382 - 322 = 60$ bachata hai kyunki empty stretches $[183, 199]$ (top) aur $[0, 14]$ (bottom) se bachta hai. Exactly $2 \times (199 - 183) + 2 \times (14 - 0) = 32 + 28 = 60$ . ✔

Level 4 — Synthesis

Exercise 4.1 (L4) — Rank them all

Queue 98, 183, 37, 122, 14, 124, 65, 67, head 53, up-first, range 0–199 ke liye FCFS / SCAN / LOOK / C-SCAN(with wrap) / C-LOOK(with wrap) ke totals list karo aur least se most head movement tak rank karo.

Recall Solution 4.1

Parent note aur Exercises 3.2–3.3 se:

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)$ Yeh order kyun sense karta hai: elevators (LOOK/SCAN) FCFS ko zig-zag khatam karke beat karte hain. Elevators mein, "no boundary trip" (LOOK) "boundary trip" (SCAN) ko beat karta hai, aur circular versions wrap cost add karte hain. FCFS sabse worst hai kyunki yeh geometry ko completely ignore karta hai.

Ranking ka visual summary:

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

Exactly 4 requests ki ek request queue design karo (head 100 par, range 0–199) jo FCFS ka total head movement jitna ho sake utna bada banaye. Wo maximum kitna hai, aur kaun sa ordering usse achieve karta hai?

Recall Solution 4.2

KYA exploit karein: FCFS har consecutive pair ke liye $∣ h_{i} - h_{i - 1} ∣$ pay karta hai, to hum chahte hain har consecutive pair full disk span kare, extremes alternate karte hue. Queue: $0, 199, 0, 199$ (head 100 se start karta hai). $∣ 0 - 100 ∣ + ∣ 199 - 0 ∣ + ∣ 0 - 199 ∣ + ∣ 199 - 0 ∣ = 100 + 199 + 199 + 199 = 697$ Yeh (near) maximal kyun hai: pehla move ek extreme par land karne ke baad, baad ki har move full-width $199$ swing hai. Sirf "waste-limited" term pehla hai ( $100$ , kyunki head beech mein start kiya). Agar head extreme par start karta (say 0) to $199 \times 4 = 796$ milta, jo 4 full-swing requests ke liye true maximum hai. Lesson: FCFS ka worst case sirf iss baat se bounded hai ki arrival order kitna adversarial hai — exactly isliye smarter scheduling exist karta hai.

Level 5 — Mastery

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

Head $h_{0}$ par start karta hai, upar jaata hai pehle. $L$ largest requested cylinder hai ( $L < max$ ) aur $S$ smallest requested cylinder hai ( $S > 0$ ), disk range $0.. M$ ke saath. Prove karo ki $SCAN_{total} - LOOK_{total} = 2 (M - L) .$ (Assume karo ki $h_{0}$ se neeche kam se kam ek request hai, to dono algorithms reverse karte hain aur $S$ tak neeche sweep karte hain.)

Recall Solution 5.1

LOOK (up first): last request $L$ tak upar jao, phir smallest $S$ tak neeche. $LOOK = (L - h_{0}) + (L - S)$ SCAN (up first): poore $M$ tak upar jao, phir $S$ tak neeche. $SCAN = (M - h_{0}) + (M - S)$ Subtract karo: $SCAN - LOOK = [(M - h_{0}) - (L - h_{0})] + [(M - S) - (L - S)]$ $= (M - L) + (M - L) = 2 (M - L) . ■$ Exactly yahi kyun aur kuch nahi: dono trips ka down-portion same $S$ par khatam hota hai; sirf yeh farq hai ki reverse karne se pehle head kitna upar gaya — $M$ vs $L$ — aur wo overshoot do baar pay hota hai (ek baar upar jaate hue, ek baar neeche wapas aate hue). Start $h_{0}$ cancel ho jaata hai kyunki dono algorithms same jagah se shuru karte hain. Yeh parent note ke rule ka algebra hai: "difference $= 2 \times (end - last request)$ ."

Exercise 5.2 (L5) — Latency-aware decision

Ek disk range 0–199 mein yeh pending queue hai (head 100 par): 101, 102, 103, 0, 199. Rotational latency negligible hai; seek dominate karta hai. Cylinder 199 par ek real-time request ko 120 cylinders ke movement budget mein serve karna zaroori hai warna deadline miss ho jaati hai. SCAN up-first ke under, cylinder 199 apni deadline meet karta hai? FCFS (arrival order as listed) ke under? Is deadline ke liye OS ko kaunsi policy choose karni chahiye, aur total travel mein uski cost kya hai?

Recall Solution 5.2

SCAN up-first: $100 \to 101 \to 102 \to 103 \to 199$ (phir down $\to 0$ ). 199 reach karne tak movement: $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): head visit karta hai $100 \to 101 \to 102 \to 103 \to 0 \to 199$ . 199 reach karne tak movement = saare prior legs plus last ka sum: $1 + 1 + 1 + 103 + 199 = 305 cylinders > 120 \Rightarrow deadline MISSED.$ (0 tak neeche detour 199 se pehle budget blow kar deta hai.) Total FCFS travel yahan $= 305$ .

Decision: SCAN (up-first) choose karo. Yeh 199 deadline meet karta hai (99 ≤ 120) aur total travel kam hai (298 < 305). Yahan elevator dono axes par jeetta hai — lekin general point (dekho I/O Subsystem and Device Drivers) yeh hai ki real schedulers deadlines weigh karte hain, sirf raw sum nahi.

Recall One-line self-test recap

LOOK ≤ SCAN by 2×(end−last) ::: 5.1 mein prove kiya FCFS kabhi reorder nahi karta ::: chahe sorting help kare (2.1 trap) C-SCAN fairness ke liye wrap jump pay karta hai ::: 382 wrap ke saath vs 183 bina wrap (3.2) Direction SCAN ka total bahut change kar sakta hai ::: 331 up-first vs 236 down-first (3.1) "Best" ke liye metric chahiye ::: 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