ऑपरेटिंग सिस्टम में CPU शेड्यूलिंग एल्गोरिदम

CPU निर्धारण क्या है?

CPU शेड्यूलिंग यह निर्धारित करने की एक प्रक्रिया है कि कौन सी प्रक्रिया निष्पादन के लिए CPU का मालिक होगी जबकि दूसरी प्रक्रिया होल्ड पर है। CPU शेड्यूलिंग का मुख्य कार्य यह सुनिश्चित करना है कि जब भी CPU निष्क्रिय रहे, OS कम से कम निष्पादन के लिए तैयार कतार में उपलब्ध प्रक्रियाओं में से एक का चयन करें। चयन प्रक्रिया सीपीयू अनुसूचक द्वारा की जाएगी। यह स्मृति में प्रक्रियाओं में से एक का चयन करता है जो निष्पादन के लिए तैयार हैं।

इस CPU शेड्यूलिंग ट्यूटोरियल में, आप सीखेंगे:

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

CPU निर्धारण के प्रकार

यहाँ दो प्रकार के निर्धारण विधियाँ हैं:

निवारक निर्धारण

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

गैर-निवारक निर्धारण

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

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

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

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

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

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

महत्वपूर्ण सीपीयू निर्धारण शब्दावली

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

सीपीयू निर्धारण मापदंड

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

अधिकतम करें:

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

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

छोटा करना:

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

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

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

अंतराल टाइमर

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

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

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

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

डिस्पैचर द्वारा किए गए कार्य:

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

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

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

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

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

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

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

FCFS विधि के लक्षण:

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

सबसे कम समय शेष

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

एसआरटी समय-निर्धारण विधि के लक्षण:

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

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

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

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

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

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

गोल-रॉबिन निर्धारण के लक्षण

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

सबसे छोटी नौकरी पहली

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

एसजेएफ निर्धारण के लक्षण

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

एकाधिक-स्तरीय कतार निर्धारण

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

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

एकाधिक-स्तरीय कतार निर्धारण की विशेषता:

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

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

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

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

सारांश:

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