I/O scheduling: disk head movement और latency
लक्ष्य और model
Disk scheduling policies trace करें, explicit endpoint rules से total head movement निकालें और seek, rotational, transfer तथा queueing time अलग करें। पूर्वज्ञान: संख्या क्रम और absolute differences। ये mechanical disk के teaching models हैं; SSD में moving heads या rotational latency नहीं। CPU और I/O scheduling अलग resources चुनते हैं, भले policy names मिलते हों।
अलग न कहा हो तो सभी requests शुरू में pending हैं, cylinder numbers देती हैं, एक-एक बार serve होंगी और नई requests नहीं आएँगी। Head movement गिनते समय transfer/rotation costs छोड़ें। Cylinders 0 से 99 हैं और head 50 पर है। आखिरी pending request serve होते ही measurement रोकें। Endpoints, direction और wrap travel गिनने का नियम स्पष्ट होना चाहिए।
1. Cylinders के लिए elevator
Elevator numbered floors के बीच जाता है। निकटतम passenger चुनना अगली यात्रा छोटी कर सकता है, पर नई nearby calls आती रहें तो दूर वाले बार-बार टल सकते हैं। Disk arm भी cylinders के बीच जाता है। x से y की movement=|x−y|। Total सभी legs का योग है, केवल final minus initial position नहीं। यात्रा अपने आरंभ के पास खत्म होकर भी लंबी हो सकती है।
Arrival-order list 70,10,90,20,55 लें। FCFS यही क्रम रखता है:
50→70→10→90→20→55।
Legs 20,60,80,70,35 हैं; total 265 cylinders। यह distance है, milliseconds नहीं; time के लिए seek model चाहिए। FCFS minimum movement की guarantee नहीं।
2. SSTF current position से फिर चुनता है
Distance proxy में shortest seek time first current cylinder से सबसे पास pending request चुनता है। इसी workload में:
50→55→70→90→20→10।
Distance=5+15+20+70+10=120। 90 पर केवल 10,20 बचे हैं, इसलिए arrival order छोड़कर 20 चुनते हैं। Tie हो तो यहाँ छोटा cylinder लेते हैं; इस workload में SSTF tie नहीं। Initial head से दूरी के अनुसार एक बार sort करना पर्याप्त नहीं।
लगातार arrival stream में पास की नई requests दूर वालों को starve कर सकती हैं। Finite all-initially-pending example पूरा होगा; उसकी छोटी path open system में starvation freedom या greedy policy की global optimality नहीं सिद्ध करती।
3. SCAN और LOOK अलग जगह मुड़ते हैं
SCAN एक direction में requests serve करते हुए physical endpoint तक जाता है और pending काम बचा हो तो उलटता है। Upward start में 55,70,90 serve करके endpoint 99, फिर reverse करके 20,10। 10 के बाद कोई request नहीं, इसलिए रुकते हैं। Movement=(99−50)+(99−10)=49+89=138।
LOOK physical endpoint की जगह उस direction की आखिरी pending request पर reverse करता है। Upward path 50→55→70→90→20→10, total=(90−50)+(90−10)=40+80=120। SCAN का extra 90 से 99 और वापस, यानी 18 cylinders है। Endpoint behavior बताए बिना LOOK को SCAN कहने से answer बदल सकता है।
4. Circular policies: वापसी भी गिनें
C-SCAN केवल एक direction में serve करता है। हमारे upward convention में 55,70,90 serve करके 99 जाता है, वापसी में बिना serve किए 0 आता है, फिर 10,20 serve करता है। हम पूरा physical movement गिनते हैं: (99−50)+(99−0)+(20−0)=49+99+20=168। Return 99 cylinders है, 100 नहीं: 0..99 में 100 labels पर endpoints की दूरी 99 है।
C-LOOK सबसे बड़ी pending request पर sweep रोककर सीधे सबसे छोटी तक लौटता है, फिर upward service जारी करता है। यहाँ 50→55→70→90→10→20, total=40+80+10=130। 90→10 jump गिना जाता है, भले बीच के cylinders serve नहीं होते। कुछ questions wrap cost exclude करते हैं; तब stated convention अपनाकर बताएँ, हमारा charged-wrap rule चुपचाप न लगाएँ।
5. Time के अलग हिस्से
Queueing service शुरू होने से पहले की delay है। Seek arm को target cylinder तक ले जाता है। Rotational latency desired sector के head के नीचे आने की प्रतीक्षा है। Transfer time ready होने पर bytes ले जाने का समय है। Controller overhead अलग हो सकता है। Quoted response time में queueing शामिल हो तो उसे फिर न जोड़ें।
हल किया timing: 7500 revolutions/minute पर एक revolution=60/7500 seconds=0.008 s=8 ms। Desired angular position uniform हो तो average rotational latency=आधी revolution=4 ms। Average seek 6 ms और transfer 0.5 ms पर queue/controller overhead छोड़कर service=6+4+0.5=10.5 ms। Queue delay 3 ms हो तो response=13.5 ms। Half-revolution expectation को uniform-position assumption चाहिए; हर request की latency यही नहीं।
परीक्षा checklist और सीमाएँ
Current position, direction, order और endpoints लिखें। FCFS को sorted sweep से अलग रखें; हर move के बाद SSTF फिर चुनें; reversal endpoint तक जाती है या नहीं, लिखें। सभी charged legs और specified wrap जोड़ें। Distance को response time से और mechanical disk को SSD से अलग रखें। यह I/O scheduling के उदाहरण हैं, हर device scheduler का पूरा coverage नहीं।
मौलिक अभ्यास: छह single-correct MCQ
हर प्रश्न में ठीक एक विकल्प चुनें। हर प्रश्न की आवश्यक मान्यताएँ उसी में दी गई हैं।
IO01. Head 50 पर है। FCFS क्रम 70,10,90,20,55 serve करके रुकता है। Total cylinder movement?
A. 5 B. 120 C. 265 D. 315
उत्तर: C
A: 5 केवल final minus start है, path length नहीं।
B: 120 यहाँ SSTF/LOOK है।
C: 20+60+80+70+35=265।
D: Stated path में न होने वाला extra travel जुड़ा है।
IO02. Head 50; pending 70,10,90,20,55। SSTF हर move के बाद closest request चुनता है। Service order?
A. 70,10,90,20,55 B. 55,70,90,20,10 C. 10,20,55,70,90 D. 55,20,70,10,90
उत्तर: B
A: यह FCFS arrival order है।
B: क्रमशः nearest 55,70,90,20,10 हैं।
C: 50 से SSTF सिर्फ ascending order नहीं।
D: 55 से 70 दूरी 15, 20 दूरी 35 है।
IO03. Cylinders 0..99, head 50, pending 70,10,90,20,55। SCAN upward, reverse से पहले 99 जाता है; आखिरी request पर रुकता है। Movement?
A. 120 B. 138 C. 148 D. 168
उत्तर: B
A: 120 में 90 पर reverse, यानी LOOK है।
B: 50→99→10 की cost 49+89=138; रास्ते की requests serve होती हैं।
C: 148 सब serve होने के बाद 10 से 0 भी जाता है।
D: 168 यहाँ charged-wrap C-SCAN है।
IO04. Cylinders 0..99, head 50, pending 70,10,90,20,55। Upward C-SCAN 99, फिर wrap से 0, फिर lower requests serve करता है। Wrap गिनें, आखिरी request पर रुकें। Movement?
A. 69 B. 130 C. 168 D. 169
उत्तर: C
A: 69 में 99-cylinder wrap छूटा है।
B: 130 charged-jump C-LOOK है।
C: (99−50)+(99−0)+(20−0)=168।
D: Endpoints की दूरी 99 है, 100 नहीं।
IO05. Disk 7500 rpm, target angular position uniform है। Average seek 6 ms और transfer 0.5 ms। Queue/controller overhead छोड़कर average service time?
A. 6.5 ms B. 8 ms C. 10.5 ms D. 14.5 ms
उत्तर: C
A: Rotation छूट गई।
B: 8 ms पूरी revolution है, total service नहीं।
C: Revolution 8 ms; average rotation 4 ms; 6+4+0.5=10.5 ms।
D: 14.5 में average half की जगह full revolution ली।
IO06. SSTF में लगातार नई nearby requests आती रहें तो दूर की pending request के साथ क्या हो सकता है?
A. Starvation B. उसका cylinder number बदलता है C. वह अनिवार्य रूप से अगली serve होती है D. Head physical movement बंद कर देता है
उत्तर: A
A: बार-बार करीब वाली चुनने से वह अनिश्चित काल टल सकती है।
B: Scheduling cylinder number नहीं बदलती।
C: SSTF current proximity चुनता है, इसे unconditional priority नहीं।
D: Head चलता है; समस्या unfair postponement है।
स्रोत और दायरा
यह मौलिक पाठ GATE 2026 course के मौजूदा OS foundations को आगे बढ़ाता है। इसका संबंध आधिकारिक 2026 syllabus के Section 8 से है; यह पूरे OS या GATE 2027 की पूर्ण तैयारी का दावा नहीं है। अभ्यास मौलिक हैं, पिछले वर्षों के प्रश्न नहीं।
स्रोत जाँचे गए: 2026-10-14।
प्रगति सहेजने के लिए साइन इन करें। साइन इन