4.2.38
Ek hard disk mein ek read/write head hota hai jo physically tracks (cylinders) ke upar move karta hai data tak pahunchne ke liye. Head ko move karna time leta hai — ise seek time kehte hain. Jab bahut saari I/O requests queue mein jam jaati hain, toh OS khud choose karta hai ki unhe kis order mein serve kare. Ek smart order ka matlab hai kam total head movement → faster disk.
Poora game yeh hai: total head travel minimize karo (cylinders/tracks mein) .
Seek time woh time hai jo disk head ko current cylinder se us cylinder tak move karne mein lagta hai jahan requested data rakha hai. Yeh disk access latency mein sabse zyada time leta hai, isliye OS requests ko schedule karta hai total head movement reduce karne ke liye.
KYUN matter karta hai: CPU fast hai; disk slow hai. Agar head wild tarike se zig-zag kare (jaise 50 → 180 → 10 → 170 serve karte hue), toh bahut zyada travel waste hota hai. Reordering travel ko aadha ya usse bhi zyada cut kar sakta hai — directly system ko speed up karta hai.
KYA measure karte hain: Total head movement = ∑ ∣ current − next ∣
Definition FCFS (First-Come-First-Served)Requests ko bilkul usi order mein serve karo jisme woh arrive hui hain . Koi reordering nahi. Simple aur fair, lekin head aage-peeche bounce kar sakta hai.
Definition SCAN (Elevator)Head ek direction mein move karta hai raaste mein har request ko service karte hue, disk ke end (cylinder 0 ya max) tak bilkul jaata hai , phir reverse karta hai aur baaki ko service karta hai. Jaise ek building elevator floor-to-floor jaata hai.
Definition C-SCAN (Circular SCAN)SCAN jaisa hai, lekin jab head end tak pahunch jaata hai, toh woh return mein service kiye bina sidha doosre extreme par jump kar jaata hai aur fresh upward sweep shuru karta hai. Zyada uniform wait time deta hai.
SCAN jaisa hai, lekin head sirf us direction mein last request tak jaata hai (woh physical end tak ek bekaar trip nahi karta), phir reverse karta hai.
(C-LOOK = C-SCAN jo sirf last request tak jaata hai, phir lowest request par wapas jump karta hai.)
Koi magic formula nahi hai — total head movement defined hi hai step distances ke sum ke roop mein. Maano head h 0 h 0 , h 1 , h 2 , … , h n
SCAN/C-SCAN ke liye, order mein boundary (0 ya max) ek extra stop ke roop mein hoti hai; LOOK ke liye nahi hoti. Yahi ek difference saare numbers explain karta hai.
Poori discussion mein yeh standard setup use karo:
Queue (arrival order): 98, 183, 37, 122, 14, 124, 65, 67
Head start: 53. Disk range: 0–199. Direction: bade cylinders ki taraf (upar).
Reference ke liye sorted requests: 14, 37, 65, 67, 98, 122, 124, 183.
Order = arrival order: 53 → 98 → 183 → 37 → 122 → 14 → 124 → 65 → 67 ∣98 − 53∣ + ∣183 − 98∣ + ∣37 − 183∣ + ∣122 − 37∣ + ∣14 − 122∣ + ∣124 − 14∣ + ∣65 − 124∣ + ∣67 − 65∣ = 45 + 85 + 146 + 85 + 108 + 110 + 59 + 2 = 640 Yeh step kyun? Koi reordering allowed nahi, isliye hum literally queue ko walk karte hain. Bade jumps (183→37) dikhate hain kyun FCFS wasteful hai.
Worked example SCAN (pehle upar move karte hue)Upar jao: 53 → 65 → 67 → 98 → 122 → 124 → 183 → 199 → 37 → 14 199 − 53 = 146 199 − 14 = 185 Total = 146 + 185 = 331 Yeh step kyun? SCAN sab kuch ek direction mein service karta hai, physical end (199) ko touch karta hai, phir wapas sweep karta hai. "+199 phir 14 tak wapas" hi ise LOOK se alag banata hai.
Worked example LOOK (pehle upar move karte hue)Upar: 53 → 65 → 67 → 98 → 122 → 124 → 183 mat jao), phir neeche: → 37 → 14 183 − 53 = 130 183 − 14 = 169 Total = 130 + 169 = 299 Yeh step kyun? LOOK 199 ki jagah 183 par ruk jaata hai, SCAN se 2 × ( 199 − 183 ) = 32 331 − 299 = 32
Worked example C-SCAN (pehle upar move karte hue)Upar: 53 → ⋯ → 183 → 199 jump 199 → 0 0 → 14 → 37 199 − 53 = 146 199 − 0 = 199 37 − 0 = 37 Total = 146 + 199 + 37 = 382 Yeh step kyun? C-SCAN return trip par kabhi service nahi karta; woh wait times uniform rakhne ke liye 0 par reset karta hai. Bada 199 jump fairness ki cost hai. (Bahut saari textbooks wrap-around jump count karti hain; kuch nahi karti — apna assumption state karo!)
Common mistake "LOOK aur SCAN same answer dete hain."Kyun sahi lagta hai: dono upar jaate hain phir reverse karte hain, same request order. Fix: SCAN physical boundary (199 ya 0) tak ek zaruri trip force karta hai chahe wahan koi request ho ya na ho; LOOK last actual request par ruk jaata hai. Difference exactly 2 × ( end − last request )
Common mistake "C-SCAN total chhota hota hai kyunki yeh 'circular/efficient' hai."Kyun sahi lagta hai: "circular" optimized lagta hai. Fix: C-SCAN total movement ko fairness/uniform waiting ke liye trade karta hai. Return jump (full disk width) aksar iska total bada kar deta hai, lekin koi request far end par starve nahi karti.
Common mistake Start position ya direction bhool jaana.Kyun sahi lagta hai: tum bas numbers sort karte ho aur gaps sum karte ho. Fix: Head h 0 direction choose karna padta hai. Pehla move start se hota hai, aur direction decide karta hai ki kaun se neighbors pehle serve hote hain.
Common mistake Boundary stop ki distance do baar ya zero baar count karna.Kyun sahi lagta hai: confusing ho jaata hai ki kaun sa algorithm end ko touch karta hai. Fix: SCAN mein end ek real stop hai (uski taraf aur usse distance add hoti hai); LOOK kabhi end visit nahi karta; C-SCAN end add karta hai aur full wrap jump bhi.
Recall Feynman: ek 12-saal ke bachche ko samjhaoEk tall building mein elevator imagine karo aur log bahut saari floors par wait kar rahe hain. Dumb tarika (FCFS) yeh hai ki jo pehle press kare uske paas jao, chahe woh top par ho, phir bottom par, phir dobara top par — bahut zyada bekaar riding. Smart elevator (SCAN/LOOK) upar jaata rehta hai, raaste mein sab ko pick up karta hai, top tak pahunchta hai, phir neeche aata hai baaki sab ko pick up karte hue. C-SCAN ek one-way escalator hai: sirf upar jaate hue log pick up karta hai, ground floor par khaali wapas zoom karta hai, aur dobara shuru karta hai — taaki floor 1 wala banda kabhi zyada wait na kare. Disk head elevator hai; cylinders floors hain; hum least riding chahte hain.
"Friends Should Care Less" → F CFS, S CAN, C -SCAN, L OOK.
Aur behavior ke liye: SCAN wall se takraata hai, LOOK sirf jhankta hai, C-SCAN Circle mein daurta hai.
Algo
End tak jaata hai?
Return par service?
Trait
FCFS
n/a
n/a
fair, lekin wasteful zig-zag
SCAN
haan
haan
elevator, edges zyada wait karte hain
C-SCAN
haan + wrap jump
nahi
uniform wait time
LOOK
nahi (last par rukta hai)
haan
elevators mein sabse kam travel
Disk scheduling algorithms kya quantity minimize karne ki koshish karte hain? Total head movement (sum of |seek distances|), yaani seek time.
Service order h0,h1,...,hn diya ho toh total head movement ka formula? ∑ i = 1 n ∣ h i − h i − 1 ∣
FCFS next request kaise choose karta hai? Yeh requests ko exact arrival order mein serve karta hai — koi reordering nahi.
SCAN aur LOOK mein kya fark hai? SCAN reverse karne se pehle physical disk end (0 ya max) tak travel karta hai; LOOK last actual request par reverse karta hai.
C-SCAN ka SCAN par kya key advantage hai? Zyada uniform waiting time (koi request far edge par starve nahi karti), kyunki yeh sirf ek direction mein service karta hai.
C-SCAN mein ek sweep ke end par kya hota hai? Head service kiye bina sidha doosre extreme par jump kar jaata hai, phir same direction mein fresh sweep shuru karta hai.
Head 53 par, SCAN upar pehle end 199 tak phir 14 tak neeche, requests ke liye total? (199−53)+(199−14)=146+185=331 cylinders.
LOOK ka total ≤ SCAN ka total kyun hota hai (same direction)? LOOK 2 × ( end − last request )
Kya chhota total head movement hamesha ek behtar algorithm ka matlab hai? Nahi — C-SCAN ka total bada ho sakta hai lekin fairness/uniform wait deta hai; trade-offs matter karte hain.
Seek time vs Rotational latency Hard Disk Drive structure (cylinders, tracks, sectors) Process Scheduling — FCFS, SJF, Round Robin (analogous ordering trade-offs)Starvation and Fairness in OS I/O Subsystem and Device Drivers SSTF (Shortest Seek Time First)
variant, no boundary trip
no reordering, may zig-zag
Seek time dominates disk latency
Minimize total head movement
Total = sum of |hi - hi-1|
SCAN - sweep to disk end then reverse
C-SCAN - jump back to other extreme
LOOK - stop at last request
C-LOOK - jump back to lowest request
