CPU priorities, aging और switching overhead
लक्ष्य और मान्यताएँ
मौजूदा FCFS/SJF/SRTF/RR पाठ को priority scheduling, starvation/aging, context-switch cost और छोटे multilevel-feedback trace से आगे बढ़ाएँ। पूर्वज्ञान: arrival, burst, completion, turnaround, waiting, response। जब उदाहरण न बदले: एक CPU, no I/O, known bursts, zero overhead, छोटी priority संख्या अधिक priority, ties में earlier arrival फिर छोटी process संख्या। Priority numbers की दिशा कभी अनुमान से न लें।
1. Priority एक dispatch rule है
Clinic urgency level के अनुसार अगला patient चुनती है। नया urgent patient पहले से चल रही examination को बीच में रोकेगा या नहीं, यह अलग preemption rule है। CPU priority scheduling भी preemptive या non-preemptive हो सकती है। Priority जरूरी नहीं कि छोटा burst या early arrival हो।
P1:(arrival 0,burst 5,priority 3), P2:(1,2,1), P3:(2,1,2) लें। Non-preemptive में समय 0 पर केवल P1 है; बाद के arrivals उसे नहीं रोकते। फिर P2 की priority P3 से अधिक:
[0,5) P1; [5,7) P2; [7,8) P3।
P1,P2,P3 completion 5,7,8; turnaround C−A=5,6,6; waiting T−B=0,4,5। हर process एक बार चलता है, इसलिए response=wait। Average waiting=3।
2. Preemption से trace बदलता है
उसी workload में preemptive priority पर समय 1 का P2 higher priority से P1 को रोकता है। P3 समय 2 पर आता है, पर running P2 से lower priority है, इसलिए उसे नहीं रोकता। समय 3 पर P2 खत्म; तब P3, remaining P1 से higher है:
[0,1) P1; [1,3) P2; [3,4) P3; [4,8) P1।
Completion 8,3,4; turnaround 8,2,2; waits 3,0,1; responses 0,0,1। P1 की तीन-unit wait [1,4) में, first run के बाद है। Average wait=4/3। यह सुधार इसी workload का है; हर metric/workload में priority optimal नहीं। यहाँ strictly higher priority arrival ही preempt करती है; समान priority पर stated tie rule लागू है।
3. Starvation और aging
Higher-priority work लगातार आए तो low-priority job अनिश्चित काल ready रह सकता है। वह I/O पर blocked नहीं; बाकी system progress कर सकता है। Aging waiting के साथ priority सुधारता है। एक specific formula लें: effective priority=max(1,base priority−floor(ready-wait/2))। Running/blocked time ready-wait में नहीं जुड़ते। Base-5 job के 6 ready-wait units पर effective priority=max(1,5−3)=2।
Aging कई policies का परिवार है, एक universal formula नहीं। Fairness claim priority bounds, ties, arrivals, execution lengths और scheduling पर निर्भर है। “Aging है” कहने से हर job की finite real-time deadline सिद्ध नहीं होती। Priority inversion अलग है: high-priority thread low-priority holder के lock पर wait करे, और intermediate work holder को delay करे। Priority inheritance holder को temporary higher priority दे सकती है; यह हर पुराने ready job का aging नहीं।
4. Overhead समय है, useful service नहीं
अब model बदलें। P1,P2 दोनों 0 पर आते हैं, हर एक को 4 service units चाहिए। RR quantum 2, पहले P1। एक process से दूसरे पर हर change की cost 1; initial dispatch और final termination zero। अन्य events/I/O नहीं और switching में unfinished processes ready रहते हैं। Trace:
[0,2) P1; [2,3) switch; [3,5) P2; [5,6) switch; [6,8) P1; [8,9) switch; [9,11) P2।
Useful service=8, switching=3, total elapsed=11। [0,11) में useful-service fraction=8/11। OS measurement switching को CPU busy गिने तो busy fraction अलग होगा। Completion 8,11 और arrivals zero होने से turnaround भी वही। Dispatch delay सहित ready waiting 4,7। First responses 0,3। Switching interval किसी burst में credit नहीं होता।
Quantum 4 पर P1 0–4, switch 4–5, P2 5–9। Useful fraction 8/9 होता है, पर P2 response 3 से बढ़कर 5। इससे overhead/responsiveness tradeoff दिखता है। Actual process change न हो तो quantum expiry पर अलग model में वही cost जरूरी नहीं; प्रश्न जिन events पर charge करे वही गिनें।
5. Multilevel feedback के rules जरूरी हैं
Multilevel queue fixed job classes अलग रख सकती है। MLFQ observed behavior से jobs को levels में move होने देता है। उसे total burst पहले से जानना जरूरी नहीं। Exact policies अलग हैं; केवल नाम से numeric trace नहीं निकलता।
Specified example: Q0 higher, quantum 1; Q1 quantum 2। New jobs Q0 में; पूरा Q0 quantum लेकर unfinished रहे तो Q1 में demote। एक level में FIFO, zero overhead। P1,P2 उसी क्रम में 0 पर, service 3 और 1। P1 0–1 चलता, 2 remaining लेकर Q1 जाता है। P2 Q0 में 1–2 पूरा होता है। फिर P1 Q1 में 2–4 पूरा। Periodic boost एक anti-starvation feature हो सकता है, पर इस छोटे trace में boost नहीं माना।
परीक्षा checklist
Priority direction, preemption, ties और aging formula लिखें। Remaining burst और priority अलग रखें। Switching intervals स्पष्ट करें; utilization का window/definition दें; MLFQ trace से पहले movement rules लिखें।
मौलिक अभ्यास: छह single-correct MCQ
हर प्रश्न में ठीक एक विकल्प चुनें। हर प्रश्न की आवश्यक मान्यताएँ उसी में दी गई हैं।
CP01. छोटा number higher priority है। P1=(A0,B5,p3), P2=(A1,B2,p1), P3=(A2,B1,p2)। Non-preemptive priority, zero overhead/no I/O में average wait?
A. 4/3 B. 3 C. 5 D. 0
उत्तर: B
A: 4/3 इसी workload का preemptive result है।
B: P1,P2,P3 क्रम से waits 0,4,5; average 3।
C: पाँच केवल P3 wait है।
D: P2,P3 को P1 के चलते wait है।
CP02. छोटा number higher priority। P1=(A0,B5,p3), P2=(A1,B2,p1), P3=(A2,B1,p2)। Strictly higher पर तुरंत preempt, no overhead/I/O। P1 total wait?
A. 0 B. 1 C. 3 D. 5
उत्तर: C
A: Zero first-response delay है।
B: एक initial execution है।
C: P1 0–1 चलता, 1–4 wait, 4–8 चलता; wait=3।
D: पाँच required service है।
CP03. Aging formula=max(1,base−floor(ready-wait/2)), छोटा higher। Base=5, ready-wait=6। Effective priority?
A. 1 B. 2 C. 3 D. 5
उत्तर: B
A: अभी floor 1 तक नहीं पहुँचा।
B: floor(6/2)=3; max(1,5−3)=2।
C: तीन घटाने वाला amount है, result नहीं।
D: इसमें aging छोड़ी गई।
CP04. दो jobs 0 पर आते, हर एक 4 CPU units। RR q=2, पहले P1। Process change cost=1; initial dispatch/final termination zero। दोनों खत्म होने तक useful-service fraction?
A. 1 B. 8/9 C. 8/11 D. 8/12
उत्तर: C
A: तीन switches छूटे हैं।
B: 8/9 एक switch पर है, जैसे यहाँ q=4।
C: चार run segments में 8 service, बीच में तीन switches: 8/11।
D: Stated endpoints में तीन switches, चार नहीं।
CP05. नए jobs Q0 में आते हैं। Q0 higher, quantum=1। पूरा quantum लेकर unfinished job Q1 (quantum=2) में जाता है। Level में FIFO, zero overhead। P1 फिर P2 समय 0, bursts 3,1। P2 कब पूरा?
A. 1 B. 2 C. 3 D. 4
उत्तर: B
A: पहला Q0 quantum P1 लेता है।
B: P1 0–1 demote; P2 Q0 में 1–2 पूरा।
C: Demoted P1 के पूरा होने की प्रतीक्षा नहीं।
D: चार यहाँ P1 completion है।
CP06. High-priority thread low-priority holder के lock पर wait करता है; medium-priority CPU work holder को delay करता है। Holder को temporary ऊँचा करके कौन सा mechanism इस dependency को address करता है?
A. Priority inheritance B. FIFO disk scheduling C. हर CPU burst बढ़ाना D. Page replacement
उत्तर: A
A: Holder waiting higher priority inherit करके जल्दी lock छोड़ सकता है।
B: Disk order यह CPU/lock dependency नहीं बदलता।
C: लंबी service inversion नहीं सुधारती।
D: Page eviction इस dependency से असंबंधित है।
स्रोत और दायरा
यह मौलिक पाठ GATE 2026 course के मौजूदा OS foundations को आगे बढ़ाता है। इसका संबंध आधिकारिक 2026 syllabus के Section 8 से है; यह पूरे OS या GATE 2027 की पूर्ण तैयारी का दावा नहीं है। अभ्यास मौलिक हैं, पिछले वर्षों के प्रश्न नहीं।
- Official GATE 2026 CS syllabus, Section 8
- OSTEP: Scheduling Introduction
- OSTEP: Multilevel Feedback Queue
स्रोत जाँचे गए: 2026-10-14।
प्रगति सहेजने के लिए साइन इन करें। साइन इन