सीपीयू शेड्यूलिंग Algorithms in Operaटिंग सिस्टम्स
नाथनियल ब्रूक्स
⚡ स्मार्ट सारांश
सीपीयू शेड्यूलिंग यह निर्धारित करती है कि ऑपरेटिंग सिस्टम अगला कौन सा रेडी प्रोसेस चलाएगा,ping प्रोसेसर को व्यस्त रखते हुए, फर्स्ट कम फर्स्ट सर्व, शॉर्टेस्ट जॉब फर्स्ट, प्रायोरिटी और राउंड रॉबिन जैसे एल्गोरिदम के माध्यम से प्रदर्शन में सुधार किया जाता है।
सीपीयू शेड्यूलिंग क्या है?
सीपीयू शेड्यूलिंग सीपीयू शेड्यूलिंग वह प्रक्रिया है जिसके द्वारा यह निर्धारित किया जाता है कि कौन सी प्रक्रिया सीपीयू पर तब तक रहेगी जब तक कोई अन्य प्रक्रिया निष्क्रिय है। सीपीयू शेड्यूलिंग का मुख्य कार्य यह सुनिश्चित करना है कि जब भी सीपीयू निष्क्रिय रहे, ऑपरेटिंग सिस्टम तैयार कतार में मौजूद प्रक्रियाओं में से कम से कम एक को निष्पादन के लिए चुन ले। यह चयन प्रक्रिया सीपीयू शेड्यूलर द्वारा की जाती है, जो मेमोरी में मौजूद निष्पादन के लिए तैयार प्रक्रियाओं में से एक का चयन करता है।
सीपीयू शेड्यूलिंग के प्रकार
यहां दो प्रकार की शेड्यूलिंग विधियां हैं:
प्रीमेप्टिव शेड्यूलिंग
प्रीएम्प्टिव शेड्यूलिंग में, कार्यों को उनकी प्राथमिकता के अनुसार निर्धारित किया जाता है। कभी-कभी, कम प्राथमिकता वाले कार्य से पहले उच्च प्राथमिकता वाले कार्य को चलाना महत्वपूर्ण होता है, भले ही कम प्राथमिकता वाला कार्य पहले से चल रहा हो। कम प्राथमिकता वाला कार्य कुछ समय के लिए रुका रहता है और उच्च प्राथमिकता वाले कार्य के पूरा होने पर पुनः शुरू हो जाता है।
गैर-पूर्वानुमानित शेड्यूलिंग
इस प्रकार की शेड्यूलिंग विधि में, सीपीयू को एक विशिष्ट प्रक्रिया को आवंटित किया जाता है। जो प्रक्रिया सीपीयू को व्यस्त रखती है, वह या तो संदर्भ बदलकर या समाप्त होकर सीपीयू को मुक्त कर देती है। यह एकमात्र ऐसी विधि है जिसका उपयोग विभिन्न हार्डवेयर प्लेटफार्मों पर किया जा सकता है, क्योंकि इसमें प्रीएम्प्टिव शेड्यूलिंग की तरह विशेष हार्डवेयर (उदाहरण के लिए, टाइमर) की आवश्यकता नहीं होती है।
शेड्यूलिंग कब प्रीएम्प्टिव होती है और कब नॉन-प्रीएम्प्टिव?
यह निर्धारित करने के लिए कि शेड्यूलिंग प्रीएम्प्टिव है या नॉन-प्रीएम्प्टिव, इन चार मापदंडों पर विचार करें:
- एक प्रक्रिया चालू अवस्था से प्रतीक्षा अवस्था में चली जाती है।
- एक विशिष्ट प्रक्रिया रनिंग अवस्था से रेडी अवस्था में परिवर्तित हो जाती है।
- एक विशिष्ट प्रक्रिया प्रतीक्षा अवस्था से तैयार अवस्था में परिवर्तित हो जाती है।
- एक प्रक्रिया अपना निष्पादन पूरा कर लेती है और समाप्त हो जाती है।
यदि केवल शर्तें 1 और 4 लागू होती हैं, तो शेड्यूलिंग को नॉन-प्रीएम्प्टिव कहा जाता है। अन्य सभी शेड्यूलिंग स्थितियां प्रीएम्प्टिव होती हैं।
सीपीयू शेड्यूलिंग से संबंधित महत्वपूर्ण शब्दावलियाँ
- विस्फोट समय/निष्पादन समय: किसी प्रक्रिया को पूरा करने में लगने वाला समय। इसे रनिंग टाइम भी कहा जाता है।
- आगमन का समय: वह समय जब कोई प्रक्रिया तैयार अवस्था में प्रवेश करती है।
- समय समाप्त: वह समय जब कोई प्रक्रिया पूरी हो जाती है और सिस्टम से बाहर निकल जाती है।
- मल्टीप्रोग्रामिंग: कई प्रोग्राम एक ही समय में मेमोरी में मौजूद हो सकते हैं।
- नौकरियां: एक प्रकार का प्रोग्राम जिसमें उपयोगकर्ता की कोई परस्पर क्रिया नहीं होती है।
- उपयोगकर्ता: एक प्रकार का प्रोग्राम जिसमें उपयोगकर्ता की परस्पर क्रिया होती है।
- प्रक्रिया: वह संदर्भ जिसका उपयोग नौकरी और उपयोगकर्ता दोनों के लिए किया जाता है।
- सीपीयू/आईओ बर्स्ट चक्र: यह प्रक्रिया निष्पादन की विशेषता बताता है, जो सीपीयू और इनपुट/आउटपुट गतिविधि के बीच बारी-बारी से चलती रहती है। सीपीयू का समय आमतौर पर इनपुट/आउटपुट समय से कम होता है।
सीपीयू शेड्यूलिंग मानदंड
सीपीयू शेड्यूलिंग एल्गोरिदम निम्नलिखित को अधिकतम और न्यूनतम करने का प्रयास करता है:
अधिकतम करने के लिए
सीपीयू का उपयोग: सीपीयू का उपयोग मुख्य कार्य है जिसमें ऑपरेटिंग सिस्टम को यह सुनिश्चित करना होता है कि सीपीयू यथासंभव व्यस्त रहे। यह 0 से 100 प्रतिशत तक हो सकता है। हालांकि, आरटीओएस के लिए, यह निम्न-स्तरीय सिस्टम के लिए 40 प्रतिशत से लेकर उच्च-स्तरीय सिस्टम के लिए 90 प्रतिशत तक हो सकता है।
प्रवाह क्षमता: प्रति इकाई समय में पूरी होने वाली प्रक्रियाओं की संख्या को थ्रूपुट कहा जाता है। अतः, जब सीपीयू किसी प्रक्रिया को निष्पादित करने में व्यस्त होता है, तब कार्य हो रहा होता है, और प्रति इकाई समय में पूर्ण किए गए कार्य को थ्रूपुट कहते हैं।
कम से कम
इंतजार का समय: प्रतीक्षा समय वह समय है जिसके लिए किसी विशिष्ट प्रक्रिया को तैयार कतार में प्रतीक्षा करनी पड़ती है।
जवाब देने का समय: यह अनुरोध सबमिट करने से लेकर पहली प्रतिक्रिया प्राप्त होने तक का समय है।
बदलाव का समय: टर्नअराउंड टाइम किसी विशिष्ट प्रक्रिया को पूरा करने में लगने वाला समय है। इसमें मेमोरी में प्रवेश पाने के लिए प्रतीक्षा करने, कतार में प्रतीक्षा करने और सीपीयू पर निष्पादन में लगने वाला कुल समय शामिल होता है। प्रक्रिया प्रस्तुत करने के समय और उसके पूरा होने के समय के बीच की अवधि को टर्नअराउंड टाइम कहते हैं।
अंतराल टाइमर
टाइमर रुकावट एक ऐसी विधि है जो प्रीएम्प्शन से बहुत करीब से संबंधित है। जब किसी निश्चित प्रक्रिया को CPU आवंटन मिलता है, तो टाइमर को एक निर्दिष्ट अंतराल पर सेट किया जा सकता है। टाइमर रुकावट और प्रीएम्प्शन दोनों ही प्रक्रिया को CPU बर्स्ट पूरा होने से पहले CPU को वापस करने के लिए मजबूर करते हैं।
अधिकांश मल्टी-प्रोग्राम्ड ऑपरेटिंग सिस्टम किसी प्रक्रिया को सिस्टम को हमेशा के लिए व्यस्त रखने से रोकने के लिए किसी न किसी प्रकार के टाइमर का उपयोग करते हैं।
डिस्पैचर क्या है?
डिस्पैचर एक मॉड्यूल है जो प्रक्रिया को CPU का नियंत्रण प्रदान करता है। डिस्पैचर तेज़ होना चाहिए ताकि यह प्रत्येक कॉन्टेक्स्ट स्विच पर चल सके। डिस्पैच लेटेंसी वह समय है जो CPU शेड्यूलर को एक प्रक्रिया को रोकने और दूसरी प्रक्रिया को शुरू करने के लिए चाहिए होता है।
डिस्पैचर द्वारा निष्पादित कार्य:
- संदर्भ परिवर्तन।
- उपयोगकर्ता मोड में स्विच किया जा रहा है।
- नये लोड किये गये प्रोग्राम में सही स्थान पर जाना।
सीपीयू शेड्यूलिंग के प्रकार Algorithms
मुख्यतः छह प्रकार के होते हैं प्रक्रिया शेड्यूलिंग एल्गोरिदम:
- पहले आओ पहले पाओ (एफसीएफएस)
- सबसे छोटा-कार्य-प्रथम (एसजेएफ) शेड्यूलिंग
- सबसे कम बचा समय
- प्राथमिकता निर्धारण
- राउंड रॉबिन शेड्यूलिंग
- बहुस्तरीय कतार निर्धारण
निर्धारण Algorithms
पहले आयें पहले पायें
एफसीएफएस का मतलब है पहले आयें पहले पायेंयह सबसे सरल और आसान सीपीयू शेड्यूलिंग एल्गोरिदम है। इस प्रकार के एल्गोरिदम में, सीपीयू का अनुरोध करने वाली प्रक्रिया को पहले सीपीयू आवंटन मिलता है। इस शेड्यूलिंग विधि को FIFO क्यू के साथ प्रबंधित किया जा सकता है।
जैसे ही कोई प्रोसेस रेडी क्यू में प्रवेश करता है, उसका पीसीबी (प्रोसेस कंट्रोल ब्लॉक) क्यू के अंत वाले हिस्से से जुड़ जाता है। इसलिए, जब सीपीयू खाली हो जाता है, तो उसे क्यू के शुरुआत में मौजूद प्रोसेस को आवंटित किया जाना चाहिए।
एफसीएफएस विधि की विशेषताएं
- यह एक नॉन-प्रीएम्प्टिव शेड्यूलिंग एल्गोरिदम है।
- नौकरियां हमेशा पहले आओ, पहले पाओ के आधार पर निष्पादित की जाती हैं।
- इसे क्रियान्वित करना और प्रयोग करना आसान है।
- हालाँकि, यह विधि प्रदर्शन में खराब है, और सामान्य प्रतीक्षा समय काफी लंबा है।
सबसे कम बचा समय
एसआरटी का पूरा नाम शॉर्टेस्ट रिमेनिंग टाइम है। इसे एसजेएफ (प्रीएम्प्टिव शेड्यूलिंग) भी कहा जाता है। इस विधि में, प्रक्रिया को उस कार्य को आवंटित किया जाता है जो पूरा होने के सबसे करीब होता है। यह विधि किसी नई तैयार स्थिति वाली प्रक्रिया को किसी पुरानी प्रक्रिया के पूरा होने में बाधा डालने से रोकती है।
एसआरटी शेड्यूलिंग विधि की विशेषताएं
- यह विधि अधिकतर बैच वातावरण में लागू की जाती है जहां छोटे कार्यों को प्राथमिकता देने की आवश्यकता होती है।
- यह एक साझा प्रणाली में लागू करने का आदर्श तरीका नहीं है जहां आवश्यक सीपीयू समय अज्ञात है।
- प्रत्येक प्रक्रिया अपने अगले सीपीयू बर्स्ट की अवधि से जुड़ी होती है, इसलिए ऑपरेटिंग सिस्टम इन अवधियों का उपयोग करके प्रक्रिया को यथासंभव कम समय में शेड्यूल करता है।
प्राथमिकता आधारित निर्धारण
प्राथमिकता निर्धारण यह प्राथमिकता के आधार पर प्रक्रियाओं को निर्धारित करने की एक विधि है। इस विधि में, शेड्यूलर कार्यों को उनकी प्राथमिकता के अनुसार चुनता है।
प्राथमिकता निर्धारण प्रणाली ऑपरेटिंग सिस्टम को प्राथमिकता निर्धारण में भी सहायता करती है। उच्च प्राथमिकता वाली प्रक्रियाओं को पहले निष्पादित किया जाता है, जबकि समान प्राथमिकता वाले कार्यों को राउंड-रोबिन या एफसीएफएस (पहले आओ पहले पाओ) के आधार पर निष्पादित किया जाता है। प्राथमिकता का निर्धारण मेमोरी आवश्यकताओं, समय आवश्यकताओं और अन्य कारकों के आधार पर किया जा सकता है।
राउंड-रॉबिन शेड्यूलिंग
राउंड रोबिन यह सबसे पुराने और सरल शेड्यूलिंग एल्गोरिदम में से एक है। इस एल्गोरिदम का नाम राउंड-रोबिन सिद्धांत से लिया गया है, जिसमें प्रत्येक व्यक्ति को बारी-बारी से किसी चीज़ का बराबर हिस्सा मिलता है। इसका उपयोग मुख्य रूप से मल्टीटास्किंग सिस्टम में शेड्यूलिंग के लिए किया जाता है। यह विधि प्रक्रियाओं के स्टार्वेशन-मुक्त निष्पादन को प्राप्त करने में सहायक है।
राउंड-रॉबिन शेड्यूलिंग की विशेषताएं
- राउंड रॉबिन एक हाइब्रिड मॉडल है जो क्लॉक-ड्रिवन है।
- किसी विशिष्ट कार्य को संसाधित करने के लिए निर्धारित समय सीमा न्यूनतम होनी चाहिए। हालांकि, यह विभिन्न प्रक्रियाओं के लिए भिन्न हो सकती है।
- यह एक टाइम-शेयरिंग सिस्टम की तरह व्यवहार करता है जो प्रत्येक प्रक्रिया पर एक विशिष्ट समय सीमा के भीतर प्रतिक्रिया देता है।
सबसे छोटा काम सबसे पहले
SJF (शॉर्टेस्ट जॉब फर्स्ट) एक शेड्यूलिंग एल्गोरिदम है जिसमें सबसे कम समय में पूरा होने वाली प्रक्रिया को अगली प्रक्रिया के लिए चुना जाता है। यह शेड्यूलिंग विधि प्रीएम्प्टिव या नॉन-प्रीएम्प्टिव हो सकती है। यह अन्य प्रक्रियाओं के निष्पादन की प्रतीक्षा में लगने वाले औसत प्रतीक्षा समय को काफी कम कर देती है।
एसजेएफ शेड्यूलिंग की विशेषताएं
- प्रत्येक कार्य को पूरा करने के लिए एक निश्चित समय सीमा निर्धारित होती है।
- इस विधि में, जब सीपीयू उपलब्ध होता है, तो सबसे कम समय में पूरा होने वाली अगली प्रक्रिया या कार्य को पहले निष्पादित किया जाता है।
- इसे गैर-पूर्वव्यापी नीति के साथ लागू किया गया है।
- यह एल्गोरिदम बैच-प्रकार की प्रोसेसिंग के लिए उपयोगी है, जहां कार्यों के पूरा होने की प्रतीक्षा करना महत्वपूर्ण नहीं है।
- यह छोटे कार्यों को पहले निष्पादित करके कार्य उत्पादन में सुधार करता है, जिनका टर्नअराउंड समय आमतौर पर कम होता है।
बहु-स्तरीय कतार निर्धारण
यह एल्गोरिदम रेडी क्यू को कई अलग-अलग क्यू में विभाजित करता है। इस विधि में, प्रक्रियाओं को उनकी विशिष्ट विशेषताओं, जैसे कि प्रक्रिया की प्राथमिकता, मेमोरी का आकार आदि के आधार पर क्यू में आवंटित किया जाता है।
हालांकि, यह एक स्वतंत्र शेड्यूलिंग एल्गोरिदम नहीं है, क्योंकि इसे जॉब्स को शेड्यूल करने के लिए अन्य प्रकार के एल्गोरिदम का उपयोग करने की आवश्यकता होती है।
बहुस्तरीय कतारों की अनुसूचीकरण की विशेषताएं
- समान विशेषताओं वाली प्रक्रियाओं के लिए कई कतारें बनाए रखी जानी चाहिए।
- प्रत्येक कतार का अपना अलग शेड्यूलिंग एल्गोरिदम हो सकता है।
- प्रत्येक कतार को प्राथमिकताएँ सौंपी जाती हैं।
शेड्यूलिंग एल्गोरिदम का उद्देश्य
शेड्यूलिंग एल्गोरिदम का उपयोग करने के कारण यहां दिए गए हैं:
- सीपीयू अपनी दक्षता में सुधार के लिए शेड्यूलिंग का उपयोग करता है।
- यह आपको प्रतिस्पर्धी प्रक्रियाओं के बीच संसाधनों को आवंटित करने में मदद करता है।
- मल्टीप्रोग्रामिंग के माध्यम से सीपीयू का अधिकतम उपयोग प्राप्त किया जा सकता है।
- जिन प्रक्रियाओं को निष्पादित किया जाना है, उन्हें रेडी क्यू में रखा जाता है।
