सीपीयू शेड्यूलिंग Algorithms in Operaटिंग सिस्टम्स

सीपीयू शेड्यूलिंग के प्रकार

यहां दो प्रकार की शेड्यूलिंग विधियां दी गई हैं:

प्रीमेप्टिव शेड्यूलिंग

प्रीमेप्टिव शेड्यूलिंग में, कार्यों को अधिकतर उनकी प्राथमिकताओं के साथ असाइन किया जाता है। कभी-कभी किसी कम प्राथमिकता वाले कार्य से पहले उच्च प्राथमिकता वाले कार्य को चलाना महत्वपूर्ण होता है, भले ही कम प्राथमिकता वाला कार्य अभी भी चल रहा हो। कम प्राथमिकता वाला कार्य कुछ समय के लिए रुका रहता है और उच्च प्राथमिकता वाले कार्य के निष्पादन के समाप्त होने पर फिर से शुरू होता है।

गैर-पूर्वानुमानित शेड्यूलिंग

इस प्रकार की शेड्यूलिंग विधि में, CPU को एक विशिष्ट प्रक्रिया को आवंटित किया गया है। जो प्रक्रिया CPU को व्यस्त रखती है, वह संदर्भ स्विच करके या समाप्त करके CPU को रिलीज़ करेगी। यह एकमात्र विधि है जिसका उपयोग विभिन्न हार्डवेयर प्लेटफ़ॉर्म के लिए किया जा सकता है। ऐसा इसलिए है क्योंकि इसमें प्रीमेप्टिव शेड्यूलिंग जैसे विशेष हार्डवेयर (उदाहरण के लिए, टाइमर) की आवश्यकता नहीं होती है।

शेड्यूलिंग कब प्रीमेप्टिव या नॉन-प्रीमेप्टिव होती है?

यह निर्धारित करने के लिए कि शेड्यूलिंग पूर्व-निर्धारित है या गैर-पूर्व-निर्धारित, इन चार मापदंडों पर विचार करें:

1. एक प्रक्रिया चालू अवस्था से प्रतीक्षा अवस्था में चली जाती है।
2. विशिष्ट प्रक्रिया चालू अवस्था से तैयार अवस्था में स्विच हो जाती है।
3. विशिष्ट प्रक्रिया प्रतीक्षा अवस्था से तैयार अवस्था में बदल जाती है।
4. प्रक्रिया का निष्पादन पूरा हो गया और समाप्त हो गई।

केवल शर्तें 1 और 4 लागू होती हैं, शेड्यूलिंग को गैर-प्रीमेप्टिव कहा जाता है।

अन्य सभी शेड्यूलिंग पूर्वनिर्धारित हैं।

महत्वपूर्ण CPU शेड्यूलिंग शब्दावली

• विस्फोट समय/निष्पादन समय: यह प्रक्रिया को पूरा करने के लिए आवश्यक समय है। इसे रनिंग टाइम भी कहा जाता है।
• आगमन का समय: जब कोई प्रक्रिया तैयार अवस्था में प्रवेश करती है
• समय समाप्त: जब प्रक्रिया पूरी हो जाती है और सिस्टम से बाहर निकल जाते हैं
• मल्टीप्रोग्रामिंग: अनेक प्रोग्राम जो एक ही समय में मेमोरी में मौजूद हो सकते हैं।
• नौकरियां: यह एक प्रकार का प्रोग्राम है जिसमें किसी भी प्रकार का उपयोगकर्ता इंटरैक्शन नहीं होता।
• उपयोगकर्ता: यह एक प्रकार का प्रोग्राम है जिसमें उपयोगकर्ता सहभागिता होती है।
• प्रक्रिया: यह संदर्भ है जिसका उपयोग नौकरी और उपयोगकर्ता दोनों के लिए किया जाता है।
• सीपीयू/आईओ बर्स्ट चक्र: प्रक्रिया निष्पादन की विशेषता, जो CPU और I/O गतिविधि के बीच बारी-बारी से होती है। CPU का समय आमतौर पर I/O के समय से कम होता है।

सीपीयू शेड्यूलिंग मानदंड

सीपीयू शेड्यूलिंग एल्गोरिदम निम्नलिखित को अधिकतम और न्यूनतम करने का प्रयास करता है:

अधिकतम करने के लिए

सीपीयू का उपयोग:CPU उपयोग वह मुख्य कार्य है जिसमें ऑपरेटिंग सिस्टम को यह सुनिश्चित करने की आवश्यकता होती है कि CPU यथासंभव व्यस्त रहे। यह 0 से 100 प्रतिशत तक हो सकता है। हालाँकि, RTOS के लिए, यह निम्न-स्तर के लिए 40 प्रतिशत और उच्च-स्तरीय सिस्टम के लिए 90 प्रतिशत तक हो सकता है।

प्रवाह क्षमता: प्रति यूनिट समय में अपना निष्पादन पूरा करने वाली प्रक्रियाओं की संख्या को थ्रूपुट कहा जाता है। इसलिए, जब CPU प्रक्रिया को निष्पादित करने में व्यस्त होता है, उस समय, काम किया जा रहा होता है, और प्रति यूनिट समय में पूरा किया गया कार्य थ्रूपुट कहलाता है।

कम से कम

इंतजार का समय: प्रतीक्षा समय वह समय है जो विशिष्ट प्रक्रिया को तैयार कतार में प्रतीक्षा करने के लिए चाहिए।

जवाब देने का समय: यह वह समयावधि है जिसमें अनुरोध प्रस्तुत किया गया तथा प्रथम प्रतिक्रिया प्राप्त हुई।

बदलाव का समय: टर्नअराउंड समय किसी विशिष्ट प्रक्रिया को निष्पादित करने के लिए लगने वाला समय है। यह मेमोरी में आने, कतार में प्रतीक्षा करने और CPU पर निष्पादित होने में लगने वाले कुल समय की गणना है। प्रक्रिया प्रस्तुत करने के समय से लेकर पूरा होने के समय के बीच की अवधि टर्नअराउंड समय है।

अंतराल टाइमर

टाइमर रुकावट एक ऐसी विधि है जो प्रीएम्प्शन से बहुत करीब से संबंधित है। जब किसी निश्चित प्रक्रिया को CPU आवंटन मिलता है, तो टाइमर को एक निर्दिष्ट अंतराल पर सेट किया जा सकता है। टाइमर रुकावट और प्रीएम्प्शन दोनों ही प्रक्रिया को CPU बर्स्ट पूरा होने से पहले CPU को वापस करने के लिए मजबूर करते हैं।

अधिकांश बहु-क्रमादेशित ऑपरेटिंग सिस्टम किसी प्रक्रिया को सिस्टम को हमेशा के लिए बाधित करने से रोकने के लिए किसी न किसी प्रकार के टाइमर का उपयोग करते हैं।

डिस्पैचर क्या है?

यह एक मॉड्यूल है जो प्रक्रिया को CPU का नियंत्रण प्रदान करता है। डिस्पैचर तेज़ होना चाहिए ताकि यह हर संदर्भ स्विच पर चल सके। डिस्पैच विलंबता वह समय है जो CPU अनुसूचक को एक प्रक्रिया को रोकने और दूसरी प्रक्रिया को शुरू करने के लिए चाहिए।

डिस्पैचर द्वारा निष्पादित कार्य:

• प्रसंग स्विचिंग
• उपयोगकर्ता मोड पर स्विच करना
• नये लोड किये गये प्रोग्राम में सही स्थान पर जाना।

सीपीयू शेड्यूलिंग एल्गोरिदम के प्रकार

मुख्यतः छह प्रकार के होते हैं प्रक्रिया शेड्यूलिंग एल्गोरिदम

1. पहले आओ पहले पाओ (एफसीएफएस)
2. सबसे छोटा-कार्य-प्रथम (एसजेएफ) शेड्यूलिंग
3. सबसे कम बचा समय
4. प्राथमिकता निर्धारण
5. राउंड रॉबिन शेड्यूलिंग
6. बहुस्तरीय कतार निर्धारण

पहले आयें पहले पायें

FCFS का पूरा नाम है फर्स्ट कम फर्स्ट सर्व। यह सबसे आसान और सरल CPU शेड्यूलिंग एल्गोरिथम है। इस प्रकार के एल्गोरिथम में, CPU का अनुरोध करने वाली प्रक्रिया को सबसे पहले CPU आवंटन मिलता है। इस शेड्यूलिंग विधि को FIFO कतार के साथ प्रबंधित किया जा सकता है।

जैसे ही प्रक्रिया तैयार कतार में प्रवेश करती है, उसका PCB (प्रोसेस कंट्रोल ब्लॉक) कतार की पूंछ से जुड़ जाता है। इसलिए, जब CPU मुक्त हो जाता है, तो उसे कतार की शुरुआत में प्रक्रिया को सौंपा जाना चाहिए।

एफसीएफएस विधि की विशेषताएं

• यह गैर-प्रीमेप्टिव और प्रीमेप्टिव शेड्यूलिंग एल्गोरिदम प्रदान करता है।
• नौकरियां हमेशा पहले आओ, पहले पाओ के आधार पर निष्पादित की जाती हैं
• इसे क्रियान्वित करना और प्रयोग करना आसान है।
• हालाँकि, यह विधि प्रदर्शन में खराब है, और सामान्य प्रतीक्षा समय काफी लंबा है।

सबसे कम बचा समय

SRT का पूरा नाम है सबसे छोटा बचा हुआ समय। इसे SJF प्रीमेप्टिव शेड्यूलिंग के नाम से भी जाना जाता है। इस विधि में, प्रक्रिया को उस कार्य को आवंटित किया जाएगा, जो इसके पूरा होने के सबसे करीब है। यह विधि एक नई तैयार अवस्था वाली प्रक्रिया को पुरानी प्रक्रिया के पूरा होने से रोकती है।

एसआरटी शेड्यूलिंग विधि की विशेषताएं

• यह विधि ज्यादातर बैच वातावरण में लागू की जाती है जहां छोटी नौकरियों को प्राथमिकता दी जानी आवश्यक होती है।
• यह किसी साझा सिस्टम में इसे लागू करने के लिए आदर्श विधि नहीं है, जहां आवश्यक CPU समय अज्ञात है।
• प्रत्येक प्रक्रिया के साथ उसके अगले CPU बर्स्ट की लंबाई के रूप में संबद्ध करें। ताकि ऑपरेटिंग सिस्टम इन लंबाई का उपयोग करे, जो प्रक्रिया को कम से कम संभव समय के साथ शेड्यूल करने में मदद करता है।

प्राथमिकता आधारित निर्धारण

प्राथमिकता निर्धारण प्राथमिकता के आधार पर प्रक्रियाओं को शेड्यूल करने की एक विधि है। इस विधि में, शेड्यूलर प्राथमिकता के अनुसार काम करने के लिए कार्यों का चयन करता है।

प्राथमिकता निर्धारण ओएस को प्राथमिकता असाइनमेंट शामिल करने में भी मदद करता है। उच्च प्राथमिकता वाली प्रक्रियाओं को पहले किया जाना चाहिए, जबकि समान प्राथमिकता वाले कार्यों को राउंड-रॉबिन या FCFS आधार पर किया जाता है। प्राथमिकता मेमोरी आवश्यकताओं, समय आवश्यकताओं आदि के आधार पर तय की जा सकती है।

राउंड-रॉबिन शेड्यूलिंग

राउंड रॉबिन सबसे पुराना, सरल शेड्यूलिंग एल्गोरिथम है। इस एल्गोरिथम का नाम राउंड-रॉबिन सिद्धांत से आया है, जहाँ प्रत्येक व्यक्ति को बारी-बारी से किसी चीज़ का बराबर हिस्सा मिलता है। इसका इस्तेमाल ज़्यादातर मल्टीटास्किंग में शेड्यूलिंग एल्गोरिथम के लिए किया जाता है। यह एल्गोरिथम विधि प्रक्रियाओं के भुखमरी मुक्त निष्पादन में मदद करती है।

राउंड-रॉबिन शेड्यूलिंग की विशेषताएं

• राउंड रॉबिन एक हाइब्रिड मॉडल है जो घड़ी द्वारा संचालित होता है
• टाइम स्लाइस न्यूनतम होना चाहिए, जो किसी विशिष्ट कार्य को संसाधित करने के लिए निर्धारित किया जाता है। हालाँकि, यह विभिन्न प्रक्रियाओं के लिए अलग-अलग हो सकता है।
• यह एक वास्तविक समय प्रणाली है जो एक विशिष्ट समय सीमा के भीतर घटना पर प्रतिक्रिया करती है।

सबसे छोटा काम सबसे पहले

एसजेएफ (सबसे छोटा काम पहले) का पूरा नाम है, यह एक शेड्यूलिंग एल्गोरिदम है जिसमें सबसे कम निष्पादन समय वाली प्रक्रिया को अगले निष्पादन के लिए चुना जाना चाहिए। यह शेड्यूलिंग विधि प्रीमेप्टिव या नॉन-प्रीमेप्टिव हो सकती है। यह निष्पादन की प्रतीक्षा कर रही अन्य प्रक्रियाओं के लिए औसत प्रतीक्षा समय को काफी कम कर देता है।

एसजेएफ शेड्यूलिंग की विशेषताएं

• यह प्रत्येक कार्य को पूरा करने के लिए समय की एक इकाई के रूप में जुड़ा हुआ है।
• इस विधि में, जब CPU उपलब्ध हो, तो सबसे कम समय में पूर्ण होने वाली अगली प्रक्रिया या कार्य को पहले निष्पादित किया जाएगा।
• इसका क्रियान्वयन गैर-निवारक नीति के साथ किया गया है।
• यह एल्गोरिथम विधि बैच-प्रकार प्रसंस्करण के लिए उपयोगी है, जहां कार्य पूरा होने की प्रतीक्षा करना महत्वपूर्ण नहीं है।
• यह छोटे-छोटे कार्यों की पेशकश करके कार्य-निष्पादन में सुधार करता है, जिन्हें पहले निष्पादित किया जाना चाहिए, तथा जिनमें अधिकांशतः कम समय लगता है।

बहु-स्तरीय कतार निर्धारण

यह एल्गोरिथ्म तैयार कतार को विभिन्न अलग-अलग कतारों में विभाजित करता है। इस विधि में, प्रक्रियाओं को प्रक्रिया की एक विशिष्ट संपत्ति, जैसे प्रक्रिया प्राथमिकता, मेमोरी का आकार, आदि के आधार पर कतार में असाइन किया जाता है।

हालाँकि, यह एक स्वतंत्र शेड्यूलिंग ओएस एल्गोरिदम नहीं है क्योंकि इसमें कार्यों को शेड्यूल करने के लिए अन्य प्रकार के एल्गोरिदम का उपयोग करने की आवश्यकता होती है।

बहु-स्तरीय कतार निर्धारण की विशेषता

• कुछ विशेषताओं वाली प्रक्रियाओं के लिए एकाधिक कतारें बनाए रखी जानी चाहिए।
• प्रत्येक कतार का अपना अलग शेड्यूलिंग एल्गोरिदम हो सकता है।
• प्रत्येक पंक्ति के लिए प्राथमिकताएं दी गई हैं।

शेड्यूलिंग एल्गोरिदम का उद्देश्य

शेड्यूलिंग एल्गोरिदम का उपयोग करने के कारण यहां दिए गए हैं:

• सीपीयू अपनी दक्षता में सुधार के लिए शेड्यूलिंग का उपयोग करता है।
• यह आपको प्रतिस्पर्धी प्रक्रियाओं के बीच संसाधनों का आवंटन करने में मदद करता है।
• सीपीयू का अधिकतम उपयोग मल्टी-प्रोग्रामिंग से प्राप्त किया जा सकता है।
• जिन प्रक्रियाओं को निष्पादित किया जाना है वे तैयार कतार में हैं।

सारांश

• सीपीयू शेड्यूलिंग वह प्रक्रिया है जिसमें यह निर्धारित किया जाता है कि कौन सी प्रक्रिया निष्पादन के लिए सीपीयू का स्वामित्व रखेगी, जबकि दूसरी प्रक्रिया होल्ड पर है।
• प्रीमेप्टिव शेड्यूलिंग में, कार्यों को ज्यादातर उनकी प्राथमिकताओं के साथ सौंपा जाता है।
• नॉन-प्रीएमप्टिव शेड्यूलिंग विधि में, सीपीयू को एक विशिष्ट प्रक्रिया को आवंटित किया गया है।
• बर्स्ट समय प्रक्रिया को पूरा करने में लगने वाला समय है। इसे रनिंग टाइम भी कहा जाता है।
• सीपीयू उपयोग वह मुख्य कार्य है जिसमें ऑपरेटिंग सिस्टम को यह सुनिश्चित करना होता है कि सीपीयू यथासंभव व्यस्त रहे।
• प्रति इकाई समय में अपना निष्पादन पूरा करने वाली प्रक्रियाओं की संख्या को थ्रूपुट कहा जाता है।
• प्रतीक्षा समय वह समय है जो किसी विशिष्ट प्रक्रिया को तैयार कतार में प्रतीक्षा करने के लिए चाहिए।
• यह वह समयावधि है जिसमें अनुरोध प्रस्तुत किया गया था और प्रथम प्रतिक्रिया प्राप्त हुई थी।
• टर्नअराउंड समय किसी विशिष्ट प्रक्रिया को निष्पादित करने में लगने वाला समय है।
• टाइमर व्यवधान एक ऐसी विधि है जो कि पूर्वग्रहण से काफी हद तक संबंधित है।
• डिस्पैचर एक मॉड्यूल है जो प्रक्रिया को सीपीयू का नियंत्रण प्रदान करता है।
• प्रक्रिया शेड्यूलिंग एल्गोरिदम के छह प्रकार हैं: पहले आओ पहले पाओ (एफसीएफएस), 2) सबसे छोटा-काम-पहले (एसजेएफ) शेड्यूलिंग, 3) सबसे छोटा शेष समय, 4) प्राथमिकता शेड्यूलिंग, 5) राउंड रॉबिन शेड्यूलिंग, 6) बहुस्तरीय कतार शेड्यूलिंग।
• में पहले आओ पहले पाओ पद्धति, जो प्रक्रिया CPU का अनुरोध करती है उसे पहले CPU आवंटन मिलता है।
• सबसे कम शेष समय में, प्रक्रिया को उसके पूरा होने के सबसे निकट वाले कार्य को आवंटित किया जाएगा।
• प्राथमिकता निर्धारण में, अनुसूचक प्राथमिकता के अनुसार कार्य करने हेतु कार्यों का चयन करता है।
• राउंड रॉबिन शेड्यूलिंग यह उस सिद्धांत पर काम करता है जहां प्रत्येक व्यक्ति को बारी-बारी से किसी चीज का बराबर हिस्सा मिलता है।
• सबसे छोटे कार्य में, अगले निष्पादन के लिए सबसे छोटे निष्पादन समय का चयन किया जाना चाहिए।
• मल्टीलेवल शेड्यूलिंग विधि तैयार कतार को विभिन्न अलग-अलग कतारों में विभाजित करती है। इस विधि में, प्रक्रियाओं को एक विशिष्ट गुण के आधार पर कतार में असाइन किया जाता है।
• सीपीयू अपनी दक्षता में सुधार के लिए शेड्यूलिंग का उपयोग करता है।