CPU शेड्यूलिंग: समयरेखा और प्रदर्शन के माप
सीखने के लक्ष्य और मान्यताएँ
FCFS, non-preemptive SJF, SRTF और round robin की समयरेखाएँ बनाकर completion, turnaround, waiting और response times निकालना सीखें। पूर्वज्ञान: ready/running/blocked अवस्थाएँ। हर उदाहरण में एक CPU execution slot, पहले से ज्ञात positive CPU-burst lengths, शून्य context-switch overhead, कोई I/O नहीं और arrival के बाद कोई blocking नहीं है। ये शैक्षिक मान्यताएँ हैं, वास्तविक workloads के बारे में दावे नहीं।
हम [a,b) जैसे half-open intervals लेते हैं: process b−a units चलता है और अंतराल b पर समाप्त होता है। सभी समय एक ही इकाई में हैं। समय b पर आने वाला process उसी समय के scheduling decision में उपलब्ध है, b से पहले नहीं।
1. गणना से पहले चार समय लिखें
किसी process के लिए A arrival time, B आवश्यक CPU service, S पहली बार सचमुच चलने का समय और C completion time लें।
- Turnaround T = C−A: arrival से completion तक बीता कुल समय।
- Response R = S−A: इस पाठ की परिभाषा में पहली CPU service मिलने तक की देरी।
- Waiting W = T−B: हमारी no-I/O और zero-overhead मान्यताओं में ready होकर भी न चलने का कुल समय।
Response completion time नहीं है और बाद की सभी waits का योग भी नहीं। Blocking I/O वाले model में turnaround से केवल CPU service घटाने पर blocked time भी शामिल रहेगा; वह केवल ready-queue waiting नहीं होगी। व्यापक systems में response time पहली दिखाई देने वाली output तक का समय भी कहा जा सकता है; दी हुई परिभाषा अवश्य पढ़ें।
जल्दी जाँच के लिए A≤S≤C और W≥0 होना चाहिए। हर process के CPU intervals की कुल लंबाई उसकी burst B के बराबर हो। Completion times का average लेकर उसे average turnaround न कहें, जब तक सभी arrivals शून्य न हों।
2. एक workload, अलग policies
P1:(A=0,B=5), P2:(A=1,B=3), P3:(A=2,B=1) लें। बराबरी पर पहले arrival और फिर छोटी process संख्या चुनें। ये मौलिक उदाहरण हैं, पिछले वर्षों के प्रश्न नहीं।
यहाँ FCFS, यानी first come, first served, non-preemptive है। P1 समय 0 पर शुरू होकर 5 पर पूरा होता है, भले बीच में P2 और P3 आ चुके हों। फिर P2, फिर P3:
[0,5) P1; [5,8) P2; [8,9) P3।
| Process | S | C | T=C−A | W=T−B | R=S−A |
|---|---|---|---|---|---|
| P1 | 0 | 5 | 5 | 0 | 0 |
| P2 | 5 | 8 | 7 | 4 | 4 |
| P3 | 8 | 9 | 7 | 6 | 6 |
Average waiting (0+4+6)/3=10/3 है। इस one-burst non-preemptive model में हर process के लिए W=R है। यह हर model का नियम नहीं।
3. Non-preemptive SJF और SRTF अलग हैं
इस पाठ में shortest job first या SJF, नया dispatch आवश्यक होने पर ready processes में सबसे छोटी burst चुनता है। समय 0 पर केवल P1 ready है, इसलिए उसी को शुरू करना होगा। बाद के arrivals उसे नहीं रोकते। समय 5 पर P3 की burst 1, P2 की burst 3 से छोटी है:
[0,5) P1; [5,6) P3; [6,9) P2।
P1,P2,P3 के क्रम में completion times 5,9,6 हैं। Turnarounds 5,8,4 और waiting times 0,5,3 हैं। Average waiting 8/3 है। सबसे छोटा job हमेशा सबसे पहले नहीं चलता: उसका आना जरूरी है, और पहले से चल रहे non-preemptive job को बीच में नहीं रोकते।
Shortest remaining time first या SRTF preemptive है। किसी process के आने या running process के समाप्त होने पर चयन फिर देखें। समय 1 पर P1 का 4 काम बचा है और नए P2 को 3 चाहिए, इसलिए P2 चलता है। समय 2 पर P2 का 2 बचा है और P3 को 1 चाहिए, इसलिए P3 चलता है:
[0,1) P1; [1,2) P2; [2,3) P3; [3,5) P2; [5,9) P1।
Completion times 9,5,3; turnarounds 9,4,1; waiting times 4,1,0 हैं। Average waiting 5/3 है। सभी first starts arrivals के बराबर हैं, इसलिए सभी response times 0 हैं, हालांकि P1 बाद में 4 units प्रतीक्षा करता है। SRTF में बची service की तुलना करें, मूल service की नहीं। बराबर remaining times होने से switch जरूरी नहीं हो जाता; दी गई tie rule अपनाएँ।
4. Round robin: queue को स्पष्ट लिखें
Round robin या RR ready queue के पहले process को अधिकतम एक quantum q देता है। Quantum खत्म होने पर अधूरा process queue के अंत में जाता है। पहले पूरा हो जाने वाला process तुरंत CPU छोड़ देता है; बचा quantum उसके लिए reserve नहीं रहता। Arrivals queue के अंत में जुड़ते हैं। यहाँ q=2 है। ठीक quantum boundary पर आने वाले processes पहले queue में जुड़ेंगे, उसके बाद अभी quantum पूरा करने वाला process फिर queue में जाएगा।
- 0–2: P1 चलता है, 3 units बचते हैं। P2 समय 1 पर और P3 समय 2 पर आया। Queue: P2,P3,P1।
- 2–4: P2 चलता है, 1 बचता है। Queue: P3,P1,P2।
- 4–5: P3 एक unit के बाद पूरा। Queue: P1,P2।
- 5–7: P1 चलता है, 1 बचता है। Queue: P2,P1।
- 7–8: P2 पूरा। फिर P1 समय 8–9 में पूरा होता है।
Completion times 9,8,5 हैं। Turnarounds 9,7,3; waiting times 4,4,2; response times 0,1,2 हैं। इसलिए average waiting=10/3 और average response=1। यहाँ RR और FCFS के average waiting बराबर होना इस workload की विशेषता है, सामान्य निष्कर्ष नहीं। छोटा quantum कम average turnaround की गारंटी नहीं; वास्तविक systems में उससे switching overhead अधिक महत्वपूर्ण हो सकता है।
5. Idle gaps और model की सीमाएँ
यदि केवल X:(A=2,B=2) और Y:(A=6,B=1) हों, तो CPU [0,2) में idle, [2,4) में X, [4,6) में idle और [6,7) में Y चलाएगा। दोनों का waiting time शून्य है। [0,7) में utilization 3/7 और [2,7) में 3/5 है। मापन की window बताए बिना utilization का उत्तर अधूरा है।
SJF के average waiting को optimal बताने वाले परिचित कथन की मान्यताएँ होती हैं, जैसे सभी jobs एक साथ उपलब्ध हों, service times ज्ञात हों और संबंधित non-preemptive model लिया गया हो। छोटे trace से सभी arrival patterns, priorities या interactive workloads पर लागू theorem न बना दें। I/O scheduling, priority scheduling, multilevel feedback queues और starvation के उपाय इस पाठ से बाहर हैं।
परीक्षा के लिए विश्वसनीय तरीका
- Arrivals, bursts, policy, quantum, tie rule और overhead लिखें।
- हर event पर remaining work और eligible set या queue अपडेट करें।
- सभी run तथा idle intervals लिखकर कुल executed service जाँचें।
- पहले timeline से S और C निकालें, फिर T,W,R की गणना करें।
- उसी metric का average लें जो पूछा गया है।
सामान्य गलतियाँ हैं: न आए job को चला देना, non-preemptive SJF में preemption करना, SRTF में मूल bursts की तुलना करना, पूरा हुए RR job को फिर चलाना, idle time छोड़ना और response को turnaround समझ लेना।
मौलिक अभ्यास: छह single-correct MCQ
ये मौलिक प्रश्न हैं, पिछले वर्षों के प्रश्न नहीं। हर प्रश्न में ठीक एक विकल्प चुनें। प्रश्न की सभी मान्यताएँ लागू रहेंगी।
C01. P1:(arrival 0, burst 5), P2:(arrival 1, burst 3), P3:(arrival 2, burst 1) zero overhead और बिना I/O के non-preemptive FCFS में चलते हैं। Average waiting time क्या है?
A. 10/3 B. 19/3 C. 7/3 D. 4
उत्तर: A
A: Starts 0,5,8 हैं; waits 0,4,6, इसलिए average 10/3।
B: 19/3 average turnaround (5+7+7)/3 है, waiting नहीं।
C: यह सही ready waits का योग तीन से भाग देने पर नहीं आता।
D: चार केवल P2 का waiting time है, तीनों का average नहीं।
C02. उन्हीं arrivals और bursts पर non-preemptive SJF में execution order क्या है?
A. P3, P2, P1 B. P1, P2, P3 C. P1, P3, P2 D. P2, P1, P3
उत्तर: C
A: P3 समय 0 पर आया नहीं है, इसलिए पहले नहीं चल सकता।
B: P1 के बाद P3 छोटा ready job है, इसलिए P2 से पहले।
C: समय 0 पर केवल P1; समय 5 पर P2 की burst 3 से पहले P3 की burst 1 चुनें।
D: P2 समय 0 पर आया नहीं, जबकि P1 उपलब्ध है।
C03. उसी workload में SRTF के तहत P1 का कुल waiting time कितना है?
A. 0 B. 1 C. 5 D. 4
उत्तर: D
A: शून्य P1 का response time है, बाद की कुल waiting नहीं।
B: P1 शुरू में एक unit चलता है; यह waiting नहीं।
C: पाँच P1 की आवश्यक CPU service है।
D: P1 समय 0–1 चलता, 1–5 प्रतीक्षा, फिर 5–9 चलता है: waiting 4, और 9−0−5=4।
C04. उसी workload में RR का quantum 2 है। Boundary पर arrivals पहले queue में जुड़ते हैं, फिर expired process requeue होता है। P1,P2,P3 क्रम में completion times क्या हैं?
A. 5, 8, 9 B. 9, 8, 5 C. 9, 5, 3 D. 9, 9, 5
उत्तर: B
A: ये FCFS completion times हैं, RR के नहीं।
B: Trace: P1 0–2, P2 2–4, P3 4–5, P1 5–7, P2 7–8, P1 8–9।
C: ये SRTF completion times हैं, इस RR queue trace के नहीं।
D: समय 7 पर P2 की केवल एक unit बची है और वह 8 पर पूरा है; अतिरिक्त quantum नहीं लेता।
C05. Process समय 3 पर आता, पहली बार 5 पर चलता, कुल 4 CPU units माँगता और 12 पर पूरा होता है। कोई I/O या overhead नहीं। क्रमशः turnaround, waiting और response क्या हैं?
A. 12, 8, 5 B. 9, 2, 5 C. 9, 5, 2 D. 7, 3, 2
उत्तर: C
A: इन मानों में completion और first-start से arrival नहीं घटाया गया।
B: Waiting और response उलट गए; बाद की waits भी waiting में आती हैं।
C: T=12−3=9; W=9−4=5; R=5−3=2।
D: सात completion minus first start है; initial delay छूटता है, इसलिए turnaround नहीं।
C06. केवल X:(arrival 2, burst 2) और Y:(arrival 6, burst 1) हैं। Overhead शून्य है और ready होने पर तुरंत dispatch होता है। [0,7) का कितना भाग CPU busy है?
A. 3/7 B. 3/5 C. 1 D. 4/7
उत्तर: A
A: दी गई सात-unit window में कुल CPU service 2+1=3 है।
B: 3/5 अलग window [2,7) लेता है और शुरुआती idle interval छोड़ता है।
C: [0,2) और [4,6), दोनों में idle time है।
D: 4/7 idle भाग है, busy भाग नहीं।
स्रोत और दायरा
यह मौलिक प्रारंभिक पाठ आधिकारिक GATE 2027 CS syllabus के Section 8, Operating System, से जुड़ा है। इससे OS या पूरा syllabus समाप्त नहीं होता। Syllabus विषय की प्रासंगिकता और मूल textbook references आधारभूत concepts की जाँच के लिए हैं। उदाहरण, समयरेखाएँ और अभ्यास मौलिक हैं।
स्रोत जाँचे गए: 2026-10-14।
प्रगति सहेजने के लिए साइन इन करें। साइन इन