CPU शिड्यूलिंग (CPU Scheduling) में प्रमुख रूप से शिड्यूलर (scheduler) द्वारा यह निर्णय लिया जाता हैं कि Ready Queue में उपलब्ध किस प्रोसेस (process) को सबसे पहले CPU एलोकेट (allocate) किया जाए। यहां हम लोग निम्नलिखित शिड्यूलिंग एल्गोरिद्म्स (Scheduling Algorithms) की चर्चा करेंगे।
- फर्स्ट-कम-फर्स्ट सर्व्ड शिड्यूलिंग (First-Come-First-Served (FSFS) Scheduling)
- शॉर्टकट-जॉब-फस्ट शिड्यूलिंग (Shortcut-Job-First (SJF) Scheduling)
- राउन्ड-रोबिन शिड्यूलिंग (Round Robin Scheduling)
- प्रायोरिटी बेस्ड शिड्यूलिंग (Priority Based Scheduling)
- मल्टीलेवल-क्यू शिड्यूलिंग (Multilevel-Queue Scheduling)
फर्स्ट-कम-फर्स्ट सर्व्ड शिड्यूलिंग (First-Come-First-Served (FCFS) Scheduling)
FCFS शिड्यूलिंग एल्गोरिद्म्स उपरोक्त सभी शिड्यूलिंग एल्गोरिथ्म में सबसे साधारण है। इस एल्गोरिद्म्स (algorithm) को क्रियान्वित (implement) करना भी आसान है; क्योंकि यह FIFO क्यू (First-Come-First Out Queue) द्वारा मेन्टेन (maintain) की जाती है। इस एल्गोरिद्म्स में जब कोई प्रोसेस (process) ready queue में प्रवेश करता है, तो उस प्रोसेस का PCB (Process Control Block) क्यू (queue) के टेल (tail) से लिंक कर दिया जाता है तथा जब CPU फ्री (free) होता है, तो क्यू (queue) के हेड (head) वाले प्रोसेस के लिए CPU को एलोकेट (allocate) किया जाता है। फिर रनिंग प्रोसेस (running process) को क्यू (queue) से हटा दिया जाता है। अर्थात् इस एल्गोरिद्म्स में कोई भी प्रोसेस CPU को तभी फ्री (free) करता है, जब इसका एक्जक्यूशन पूर्ण (completely) हो जाता है। निम्न चित्र में First-Come-First Out Scheduling को दर्शाया गया है।
चूंकि FCFS शिड्यूलिंग एल्गोरिद्म्स में एक प्रोसेस को पूर्ण-प्रोसेसिंग (complete processing) के लिए CPU एलोकेट किया जाता है। अत: शॉर्ट जॉब्स या प्रोसेसेस को काफी समय तक प्रतीक्षा (wait) करनी पड़ती है, यदि CPU किसी वैसे प्रोसेस के लिए एलोकेट हो चुका हो, या जो प्रोसेस अपने पूर्ण एक्जक्यूशन (complete execution) में काफी लम्बा समय ले।
शॉर्टकट-जॉब-फस्ट शिड्यूलिंग (Shortcut-Job-First (SJF) Scheduling)
Shortest-Job-First शिड्यूलिंग एल्गोरिथ्म में सबसे पहले CPU उस प्रोसेस के लिए एलोकेट किया जाता है, जिस प्रोसेस का एक्जक्यूशन टाइम (execution time) सबसे कम होता है। यदि दो प्रोसेसेस का एक्जक्यूशन टाइम एक समान होता है, तो उन्हें शिड्यूल करने के लिए FCFS एल्गोरिथ्म का प्रयोग किया जाता है। SJF शिड्यूलिंग एल्गोरिद्म दिए गए प्रोसेसेस के सेट के औसत वेटिंग टाइम (average waiting time) को कम से कम करने के संदर्भ में एक ऑप्टिमल शिड्यूलिंग एल्गोरिथ्म (optimal scheduling algorithm) है; क्योंकि यह प्रोसेसेस को शॉर्टर एक्जक्यूशन टाइम (shorter execution time) से लांगर एक्जक्यूशन टाइम (longer execution time) के क्रम में सिलेक्ट करता है।
SJF शिड्यूलिंग एल्गोरिद्म में शिड्यूलर के परफॉरर्मेन्स (performance) को बढ़ाने के लिए, सबसे छोटे प्रोसेस (shortest process) को ready queue से खोजने के बजाए ready queue के प्रोसेस को उनके एक्जक्यूशन टाइम (execution time) के बढ़ते हुए मान (value) के आधार पर शॉर्ट (short) किया जा सकता है जिससे कि shortest execution time वाला प्रोसेस ready queue में सबसे ऊपर तथा longest execution time वाला प्रोसेस ready queue में सबसे नीचे एवं अन्य प्रोसेसेस आरोही (ascending) क्रम में व्यवस्थित हो जाते है।
राउन्ड-रोबिन शिड्यूलिंग (Round Robin Scheduling)
Round Robin Scheduling एल्गोरिथ्म एक पुराना, साधारण तथा आमतौर पर प्रयुक्त होने वाला एल्गोरिथ्म है। Round robin scheduling, एल्गोरिथ्म मुख्य रूप से टाइम शेयरिंग (time-sharing) तथा मल्टी-यूजर (multiuser) सिस्टम मे प्रयुक्त होता हैं; जहां कि अच्छा रेसपॉन्स टाइम (response time) तथा यूजर्स के बीच सिस्टम रिसोर्सेस को शेयर करने की जरूरत पर ज्यादा जोर दिया जाता है।
इस एल्गोरिथ्म में CPU के टाइम को टाइम-स्लाइस (time-slice) में विभाजित कर दिया जाता है। इस time-slice की अवधि 10 से 100 मिलीसेकण्ड्स तक की हो सकती है। प्रत्येक प्रोसेस की एक्जक्यूट करने के लिए (time-slices) प्रदान किए जाते हैं। जब अन्य प्रोसेसेस ready queue में रन अर्थात् एक्जक्यूट करने के लिए प्रतीक्षा (wait) करते रहते हैं तो कोई भी प्रोसेस एक से अधिक time-slice के लिए रन नहीं कर सकता है। यदि कोई प्रोसेस एक्जक्यूट करने के लिए और अधिक time-slice की आवश्यकता होती हैं, तो उसे ready queue के अंत में भेज दिया जाता है, जहां वह अपने अगले time slice के एलोकेशन की प्रतीक्षा (wait) करता है। परन्तु यदि कोई रनिंग प्रोसेस (running process) ऑपरेटिंग सिस्टम को इनपुट/आउटपुट (I/O) के लिए रिक्वेस्ट (request) करता है या अपने टरमिनेशन से सम्बन्धित फाइल ऑपरेटिंग सिस्टम को भेजता है, तो शिड्यूलर (scheduler) किसी दूसरे प्रोसेस को रन अर्थात् एक्जक्यूट करने के लिए शिड्यूल करता है।
Round robin scheduling एल्गोरिद्म द्वारा सिस्टम रिसोर्सेस का एक समान यूटिलाइजेशन (utilization) किया जाता है। जैसा कि हमने पूर्व में कहा कि इस एल्गोरिद्म द्वारा एक-बराबर (time-slice) सभी प्रोसेस को एसाइन (assign) किया जाता है तथा CPU किसी भी प्रोसेस को उसी time-slice के लिए एक्जक्यूट करता है। अत: small process, एक ही time slice में एक्जक्यूट कर सकते हैं; परिणामस्वरूप उसका रेसपॉन्स टाइम (response time) काफी अच्छा (कम) होता है; परन्तु long process जिन्हें एक्जक्यूट करने के लिए एक से अधिक time-slice की जरूरत पड़ सकती है, प्रत्येक time-slice की समाप्ति के पश्चात् अपने एक्जक्यूशन के पूरा होने (completion) तक बार-बार ready queue में रख दिए जाते हैं।
प्रायोरिटी बेस्ड शिड्यूलिंग (Priority Based Scheduling)
किसी भी प्रोसेस को ready queue से सबसे पहले एक्जक्यूट होने के लिए प्राथमिकता (priority) प्रदान करना उच्चतम प्रायोरिटी (highest priority) कहलाती है। जैसा कि हमने Shortest Job First शिड्यूलिंग एल्गोरिथ्म में देखा कि ready queue में उस प्रोसेस को एक्जक्यूट करने के लिए उच्चतम प्रायोरिटी (highest priority) दी जाती है, जिसका एक्जक्यूशन टाइम (execution-time) सबसे कम होता है। अत: shortest job first शिड्यूलिंग एल्गोरिथ्म भी प्रायोरिटी-बेस्ड (priority-based) शिड्यूलिंग एल्गोरिथ्म की एक विशेष स्थिति हैं।
प्रायोरिटी-बेस्ड शिड्यूलिंग में प्रत्येक प्रोसेस की प्रायोरिटी (priority) परिभाषित की जाती है तथा शिड्यूलर ready queue से सर्वोच्च प्रायोरिटी (highest priority) वाले प्रोसेस को ही एक्जक्यूट करने के लिए सिलेक्ट (select) करता है। समान प्रायोरिटी (priority) वाले प्रोसेसेस First Come First Server शिड्यूलिंग एल्गोरिथ्म के आधार पर शिड्यूल (schedule) किए जाते है। कुछ सिस्टम में छोटी संख्या द्वारा High Priority को तो कुछ में low priority को परिभाषित किया जाता है। परन्तु ज्यादातर छोटी संख्या द्वारा high priority को दर्शाया जाता है।
प्रायोरिटी-बेस्ड शिड्यूलिंग एल्गोरिथ्म (priority based scheduling algorithm) के साथ सबसे प्रमुख समस्या यह है, कि law priority process का एक्जक्यूशन high priority process के एक्जक्यूशन की प्राथमिकता के कारण अनिश्चितकाल के लिए ब्लॉक (block) हो सकता है। अत: इस शिड्यूलिंग एल्गोरिद्म द्वारा किसी प्रोसेस के कम्प्लीशन (completion) की गारंटी एक निश्चित समय के लिए नहीं ली जा सकती है। साथ ही कभी-कभी low-priority के प्रोसेसेस पूर्ण-रूपेण एक्जक्यूट भी नहीं कर पाते हैं।
मल्टीलेवल-क्यू शिड्यूलिंग (Multilevel-Queue Scheduling)
मल्टीलेवल – क्यू शिड्यूलिंग (Multilevel Queue Scheduling) एल्गोरिथ्म में प्रोसेसेस को विभिन्न समूहों (groups) में वर्गीकृत (classify) किया जाता हैं। उदाहरण स्वरूप, प्रोसेसेस को foreground या interactive तथा background या batch प्रोसेसेस में वगीकृत किया जा सकता है। जहां interactive प्रोसेसेस एक्जक्यूट करने में short-response time की आवश्यकता होती है, वहीं batch प्रोसेसेस को एक्जक्यूट करने के लिए अवसर वहां long response time की जरूरत होती है। अत: इन्हें अपने-अपने ढंग से शिड्यूल करने की आवश्यकता होती है। इसके अतिरिक्त foreground प्रोसेसेस की प्रायोरिटी background प्रोसेसेस से high होती है।
मल्टी – क्यू शिड्यूलिंग एल्गोरिद्म (Multilevel Queue Scheduling) में ready queue को अलग-अलग क्यूज (queues) में विभाजित किया जाता है। इसके पश्चात् प्रत्येक क्यू (queue) में प्रोसेस को उनके साइज, प्रायोरिटी तथा प्रकार (size, priority and type) के आधार पर स्थायी रूप से (permanently) एसाइन कर दिया जाता है। प्रत्येक क्यू (queue) के अपने-अपने शिड्यूलिंग एल्गोरिथ्म (scheduling algorithm) होते हैं। उदाहरण स्वरूप, इन्ट्रैक्टिव या फोरग्राउन्ड (interactive or foreground) प्रोसेस वाले क्यू (queue) को round robin scheduling algorithm द्वारा शिड्यूल किया जा सकता है; जबकि बैच-प्रोसेस या बैक ग्राउन्ड (batch process or background) प्रोसेस वाले क्यू (queue) को First Come First Sever Scheduling एल्गोरिद्म द्वारा शिड्यूल किया जा सकता है।
जैसा कि ऊपर चित्रित चित्र से स्पष्ट है कि प्रत्येक क्यू (queue) के प्रोसेसेस अपने-अपने शिड्यूलर के द्वारा शिड्यूल किए जाते हैं। परन्तु इन सभी क्यूज (queues) को मैनेज करने के लिए एक खास तरीके की आवश्यकता होती है। जैस, प्रत्येक क्यू को एक time प्रदान करना, जिसमें वह क्यू (queue) अपने प्रोसेसेस को शिड्यूल कर सके। इसकी सम्भावना यह हैं कि high priority वाले क्यू (queue) को सबसे पहले एक्जक्यूट किया जाए। जैसे, बैच क्यू (batch queue) के प्रोसेसेस तब तक एक्जक्यूट करना प्रारम्भ न करें, जब तक कि system process तथा interactive processes के क्यू (queue) के प्रोसेसेस पूरी तरह एक्जक्यूट होकर, क्यू (queue) खाली न हो जाए। यदि batch process के रन करते समय कोई interactive process, ready queue में प्रवेश करता हैं तो वो batch process प्रि-इम्पटेड (pre-empted) हो जाना चाहिए।
