ऑपरेटिंग सिस्टम में CPU शेड्यूलिंग: अल्गोरिथम और उदाहरण

शेड्यूलिंग क्या है? (cpu scheduling in hindi)

ऑपरेटिंग सिस्टम में शेड्यूलिंग को करने का कारण होता है कि काम समय पर पूरा हो जाये। नीचे वाले तालिका में आप देख सकते हैं कि प्रक्रिया और समय में क्या सम्बन्ध है:

Arrival Time:     वो समय जब प्रोसेस रेडी क्यू में आता है।
Completion Time:  वो समय जब प्रोसेस का execution पूरा होता है।
Burst Time:       CPU execution के लिए प्रोसेस द्वारा लिया गया समय।
Turn Around Time: कम्पलीशन टाइम और अर्रिवल टाइम के बीच का अंतर।         
     Turn Around Time = Completion Time - Arrival Time

Waiting Time(W.T): टर्न अराउंड टाइम और बर्स्ट टाइम के बीच का अंतर।
     Waiting Time = Turn Around Time - Burst Time

शेड्यूलिंग की जरूरत क्यों?

एक सामान्य प्रोसेस में I/O टाइम और CPU टाइम दोनों की ही जरूरत होती है। की यूनीप्रोग्रामिंग सिस्टम जैसे कि MS-DOS में, I/O के इन्तजार में समय बर्बाद होता है और CPU तब तक खाली बैठा रहता है।

वहीं मल्टीप्रोग्रामिंग सिस्टम में, एक प्रोसेस CPU का प्रयोग कर सकता है जबकि दूसरा I/O के लिए इन्तजार करता रहता है। ऐसा सिर्फ प्रोसेस शेड्यूलिंग के कारण ही सम्भव है।

प्रोसेस शेड्यूलिंग अल्गोरिथम का ऑब्जेक्टिव:

Max CPU utilization [CPU को जितना सम्भव हो व्यस्त रखें।]
Fair allocation of CPU.
Max throughput [एक यूनिट टाइम में एक्सीक्यूट हुए प्रोसेसर की संख्या]
Min turnaround time [किसी प्रोसेस द्वारा execution पूरा करने में लगा समय]
Min waiting time [वो समय जितनी देर प्रोसेस रेडी क्यू में इन्तजार करता है।]
Min response time [वो समय जब प्रोसेस पहला रिस्पांस प्रोडूस करता है]

विभिन्न शेड्यूलिंग अल्गोरिथम (cpu scheduling algorithms in hindi)

First Come First Serve (FCFS): एक सिंपल शेड्यूलिंग अल्गोरिथम जो प्रोसेस के पहुँचने के हिसाब से उसे शेड्यूल करता है।

Shortest Job First(SJF): ऐसे प्रोसेस जिनका बर्स्ट टाइम सबसे कम हो उन्हें पहले शेड्यूल किया जाता है।

Shortest Remaining Time First(SRTF):  SJF अल्गोरिथम का preemptive मोड है जिसमे जॉब को शबे कम बचे समय के आधार पर शेड्यूल किया जाता है।

Round Robin Scheduling:हर एक प्रोसेस को साइक्लिक वे में एक निश्चित समय दिया जाता है।

Priority Based scheduling (Non Preemptive):  इस शेड्यूलिंग में सारे प्रोसेस को उनकी प्रायोरिटी के आधार पर शेड्यूल किया जाता है। जैसे जिनकी प्रायोरिटी सबसे ज्यादा होगी, पहले उसे शेड्यूल किया जाएगा। अगर दो प्रोसेस की प्रायोरिटी समान हो जाये तब उनके पहुँचने के समय को देखा जाएगा।

Highest Response Ratio Next (HRRN): इन शेड्यूलिंग में ऐसे प्रोसेस को पहले शेड्यूल किया जाता है जिसका रिस्पांस अनुपात शबे ज्यादा हो।ये अल्गोरिथम starvation से बचता है।

Response Ratio = (Waiting Time + Burst time) / Burst time

Multilevel Queue Scheduling:  सभी प्रोसेस को उनकी प्रोरिटी के आधार पर पहले विभिन्न क्यू में डाला जाता है। सामान्यतः ज्यादा प्रायोरिटी वाले प्रोसेस को टॉप लेवल क्यू में डाला जाता है। जब टॉप लेवल क्यू के सारे प्रोसेस ख़त्म हो जाएँ तभी लोअर लेवल के प्रोसेस को शेड्यूल किया जाता है।

Multi level Feedback Queue Scheduling: ये प्रोसेस को क्यू के बीच इधर-उधर होने की अनुमति देता है। इसके पीछे ये विचार होता है कि प्रोसेस को उनके CPU बर्स्ट के characteristics के आधार पर अलग-अलग किया जाये। अगर कोई प्रोसेस बहुत ज्यादा CPU टाइम का प्रयोग करता है तो उसे लोअर लेवल के प्रायोरिटी क्यू में डाल दिया जाता है।

शेड्यूलिंग अल्गोरिथम के बारे में कुछ जानकारियाँ

1) FCFS लम्बे वेटिंग समय का कारण बन सकता है, खासकर तब जब पहली जॉब बहुत ज्यादा CPU टाइम खा जाये।

2) SJF और SRTF- दोनों ही starvation की वजह बन सकते हैं। एक ऐसी स्थिति की कल्पना कीजिये जब रेडी क्यू में लम्बा प्रोसेस और छोटे-छोटे प्रोसेस आते रहें।

3) अगर राउंड रोबिन शेड्यूलिंग के लिए टाइम क्वांटम बहुत बड़ा हो, तब ये FCFS शेड्यूलिंग की तरह ही व्यवहार करने लगता है।

4) किसी दिए गये प्रोसेस के सेट के लिए SJP औसत वेटिंग टाइम के मामले में काफी ऑप्टीमल है। इस शेड्यूलिंग में इन्तजार का औसत समय सबसे कम होता है लेकिन समस्या ये है कि अगले जॉब के समय को जानने या अनुमान लगाने के लिए क्या किया जाये?

शेड्यूलिंग के उदाहरण (examples of cpu scheduling in hindi)

अब हम एक उदाहरण को हल कर के बतायेंगे कि शेड्यूलिंग के प्रश्न को कैसे हल किया जाता है।

Q. नीचे दी गई तालिका पर ध्यान दीजिये जहां तीन प्रोसेसर P0, P1 और P2 के लिए अराइवल टाइम और बर्स्ट टाइम दिया गया है।

Process   Arrival time   Burst Time
P0            0 ms          9 ms
P1            1 ms          4 ms
P2            2 ms          9 ms

इसमें preemptive शोर्टेस्ट फर्स्ट अल्गोरिथम का प्रयोग किया जाएगा। केवल प्रोसेस के अराइवल और कम्पलीशन पर ही शेड्यूलिंग को किया जाएगा। अब तीनो के लिए औसत समय निकालिए।

हल:
प्रोसेस P0 को प्रोसेसर 0ms पर allocate किया गया क्योंकि क्यू में अभी कोई और प्रोसेस तैयार नहीं है। P0 को 1ms के बाद प्रीम्प्ट किया जाएगा क्योंकि 1ms पर P1 आ जाएगा क्योंकि P1 का बर्स्ट टाइम P0 के बचे हुए समय से कम है। अब P1 4ms तक रन करेगा।

P2 2ms पर ही आ जाएगा लेकिन P1 रन होता रहेगा क्योंकि P2 का बर्स्ट टाइम P1 से लम्बा है। P1 के पूरा होते ही P0 को फिर से शेड्यूल किया जाएगा क्योंकि P0 का बचा हुआ समय P2के बर्स्ट टाइम से कम है।

P0 4ms के लिए इन्तजार करेगा, P1 0 ms के लिए इन्तजार करेगा और P2 इन्तजार करेगा 11 ms के लिए.

इसीलिए एवरेज ईटिंग टाइम= (0+4+11)/3 = 5ms

इस लेख से सम्बंधित यदि आपका कोई भी सवाल या सुझाव है, तो आप उसे नीचे कमेंट में लिख सकते हैं।