निर्धारण (कंप्यूटिंग)

कंप्यूटिंग में, शेड्यूलिंग कार्यों को करने के लिए संसाधनों को निर्दिष्ट करने की क्रिया है। संसाधन केंद्रीय प्रसंस्करण इकाई, दूरसंचार लिंक या विस्तार कार्ड हो सकते हैं। 'कार्य' थ्रेड (कंप्यूटर विज्ञान), प्रक्रिया (कंप्यूटिंग) या डेटा प्रवाह (कंप्यूटर नेटवर्किंग) हो सकते हैं।

शेड्यूलिंग गतिविधि शेड्यूलर नामक प्रक्रिया द्वारा की जाती है। शेड्यूलर्स को अक्सर सभी कंप्यूटर संसाधनों को व्यस्त रखने के लिए डिज़ाइन किया जाता है (जैसा कि लोड संतुलन (कंप्यूटिंग) में), कई उपयोगकर्ताओं को सिस्टम संसाधनों को प्रभावी ढंग से साझा करने की अनुमति देता है, या सेवा की गुणवत्ता का लक्ष्य प्राप्त करने के लिए।

शेड्यूलिंग स्वयं गणना करने के लिए मौलिक है, और कंप्यूटर सिस्टम के निष्पादन मॉडल का एक आंतरिक हिस्सा है; शेड्यूलिंग की अवधारणा एकल सेंट्रल प्रोसेसिंग यूनिट (सीपीयू) के साथ कंप्यूटर मल्टीटास्किंग को संभव बनाती है।

लक्ष्य

एक अनुसूचक एक या अधिक लक्ष्यों को लक्षित कर सकता है, उदाहरण के लिए:

थ्रूपुट को अधिकतम करना (प्रति समय इकाई पूर्ण किए गए कार्य की कुल राशि);
कंप्यूटर के प्रदर्शन को कम करना # प्रतिक्रिया समय (काम के तैयार होने से पहले बिंदु तक निष्पादन शुरू होने तक का समय);
विलंबता (इंजीनियरिंग) या प्रतिक्रिया समय (प्रौद्योगिकी) को कम करना (बैच गतिविधि के मामले में काम तैयार होने से लेकर समाप्त होने तक का समय,^[1]^[2]^[3] या जब तक कि सिस्टम प्रतिक्रिया नहीं करता है और इंटरैक्टिव गतिविधि के मामले में उपयोगकर्ता को पहला आउटपुट सौंपता है);^[4]
निष्पक्षता को अधिकतम करना (प्रत्येक प्रक्रिया के लिए समान CPU समय, या आमतौर पर प्रत्येक प्रक्रिया की प्राथमिकता और कार्यभार के अनुसार उपयुक्त समय)।

व्यवहार में, ये लक्ष्य अक्सर संघर्ष करते हैं (जैसे थ्रूपुट बनाम विलंबता), इस प्रकार एक अनुसूचक एक उपयुक्त समझौता लागू करेगा। उपयोगकर्ता की जरूरतों और उद्देश्यों के आधार पर वरीयता को ऊपर उल्लिखित चिंताओं में से किसी एक द्वारा मापा जाता है।

रीयल-टाइम कंप्यूटिंग|रीयल-टाइम वातावरण में, जैसे उद्योग में स्वत: नियंत्रण के लिए एम्बेडेड सिस्टम (उदाहरण के लिए रोबोटिक्स), अनुसूचक को यह भी सुनिश्चित करना चाहिए कि प्रक्रियाएं समय सीमा को पूरा कर सकती हैं; सिस्टम को स्थिर रखने के लिए यह महत्वपूर्ण है। अनुसूचित कार्यों को एक प्रशासनिक बैक एंड के माध्यम से एक नेटवर्क और डिवाइस प्रबंधन में दूरस्थ उपकरणों के लिए भी वितरित किया जा सकता है।

ऑपरेटिंग सिस्टम शेड्यूलर्स के प्रकार

अनुसूचक एक ऑपरेटिंग सिस्टम मॉड्यूल है जो सिस्टम में भर्ती होने वाली अगली नौकरियों और चलाने के लिए अगली प्रक्रिया का चयन करता है। ऑपरेटिंग सिस्टम में तीन अलग-अलग अनुसूचक प्रकार हो सकते हैं: एक दीर्घकालिक अनुसूचक (जिसे एक प्रवेश अनुसूचक या उच्च-स्तरीय अनुसूचक के रूप में भी जाना जाता है), एक मध्य-अवधि या मध्यम-अवधि अनुसूचक, और एक अल्पकालिक अनुसूचक। नाम उस सापेक्ष आवृत्ति का सुझाव देते हैं जिसके साथ उनके कार्य किए जाते हैं।

प्रक्रिया अनुसूचक

प्रोसेस शेड्यूलर ऑपरेटिंग सिस्टम का एक हिस्सा है जो यह तय करता है कि कौन सी प्रक्रिया एक निश्चित समय पर चलती है। इसमें आम तौर पर एक चल रही प्रक्रिया को रोकने की क्षमता होती है, इसे चल रही कतार के पीछे ले जाती है और एक नई प्रक्रिया शुरू करती है; ऐसे शेड्यूलर को प्रीमेशन (कंप्यूटिंग) शेड्यूलर के रूप में जाना जाता है, अन्यथा यह एक गैर-प्रीमेप्टिव मल्टीटास्किंग शेड्यूलर है।^[5] हम दीर्घावधि शेड्यूलिंग , मध्यम अवधि शेड्यूलिंग और अल्पकालिक शेड्यूलिंग के बीच इस आधार पर अंतर करते हैं कि कितनी बार निर्णय लिए जाने चाहिए।^[6]

लंबी अवधि के समयबद्धन

दीर्घकालिक अनुसूचक, या प्रवेश अनुसूचक, यह तय करता है कि कौन से कार्य या प्रक्रियाओं को तैयार कतार (मुख्य स्मृति में) में भर्ती किया जाना है; अर्थात्, जब किसी कार्यक्रम को निष्पादित करने का प्रयास किया जाता है, तो वर्तमान में निष्पादित प्रक्रियाओं के सेट में इसका प्रवेश या तो अधिकृत होता है या दीर्घकालिक अनुसूचक द्वारा विलंबित होता है। इस प्रकार, यह अनुसूचक निर्धारित करता है कि सिस्टम पर कौन सी प्रक्रियाएँ चलनी हैं, और किसी एक समय में समर्थित होने वाली समवर्तीता की डिग्री – क्या कई या कुछ प्रक्रियाओं को समवर्ती रूप से निष्पादित किया जाना है, और I/O-गहन और CPU-गहन प्रक्रियाओं के बीच विभाजन को कैसे नियंत्रित किया जाना है। मल्टीप्रोग्रामिंग की डिग्री को नियंत्रित करने के लिए दीर्घकालिक अनुसूचक जिम्मेदार है।

सामान्य तौर पर, अधिकांश प्रक्रियाओं को I/O-बाउंड या CPU-बाउंड के रूप में वर्णित किया जा सकता है। एक I/O-बाध्य प्रक्रिया वह है जो अपना अधिक समय I/O करने में बिताती है, जितना कि यह संगणना करने में खर्च करती है। एक सीपीयू-बाध्य प्रक्रिया, इसके विपरीत, I/O अनुरोधों को बार-बार उत्पन्न करती है, इसके अधिक समय की गणना करते हुए। यह महत्वपूर्ण है कि एक दीर्घकालिक अनुसूचक I/O-बाध्य और CPU-बाध्य प्रक्रियाओं के एक अच्छे प्रक्रिया मिश्रण का चयन करता है। यदि सभी प्रक्रियाएं I/O-बाध्य हैं, तो तैयार कतार लगभग हमेशा खाली रहेगी, और अल्पकालिक अनुसूचक के पास करने के लिए बहुत कम होगा। दूसरी ओर, यदि सभी प्रक्रियाएँ CPU-बाध्य हैं, तो I/O प्रतीक्षा कतार लगभग हमेशा खाली रहेगी, उपकरण अप्रयुक्त हो जाएंगे, और फिर से सिस्टम असंतुलित हो जाएगा। इस प्रकार सर्वश्रेष्ठ प्रदर्शन वाली प्रणाली में सीपीयू-बाउंड और आई/ओ-बाउंड प्रक्रियाओं का संयोजन होगा। आधुनिक ऑपरेटिंग सिस्टम में, इसका उपयोग यह सुनिश्चित करने के लिए किया जाता है कि वास्तविक समय की प्रक्रियाओं को अपने कार्यों को पूरा करने के लिए पर्याप्त CPU समय मिले।^[7] बड़े पैमाने के सिस्टम जैसे बैच प्रोसेसिंग सिस्टम, कंप्यूटर क्लस्टर, सुपरकंप्यूटर और रेंडर फ़ार्म में दीर्घकालिक शेड्यूलिंग भी महत्वपूर्ण है। उदाहरण के लिए, समवर्ती कंप्यूटिंग में, एक दूसरे पर प्रतीक्षा करने के कारण उन्हें अवरुद्ध होने से रोकने के लिए अक्सर परस्पर क्रिया करने वाली प्रक्रियाओं की सह-शेड्यूलिंग की आवश्यकता होती है। इन मामलों में, ऑपरेटिंग सिस्टम में किसी भी अंतर्निहित प्रवेश शेड्यूलिंग समर्थन के अलावा, विशेष-उद्देश्यीय जॉब शेड्यूलर सॉफ़्टवेयर का उपयोग आमतौर पर इन कार्यों की सहायता के लिए किया जाता है।

कुछ ऑपरेटिंग सिस्टम केवल नए कार्यों को जोड़ने की अनुमति देते हैं यदि यह सुनिश्चित हो कि सभी वास्तविक समय की समय सीमा अभी भी पूरी हो सकती है। नए कार्यों को स्वीकार या अस्वीकार करने के लिए एक ऑपरेटिंग सिस्टम द्वारा उपयोग किया जाने वाला विशिष्ट ह्यूरिस्टिक एल्गोरिदम प्रवेश नियंत्रण तंत्र है।^[8]

मध्यम अवधि के समयबद्धन

मध्यम अवधि अनुसूचक मुख्य मेमोरी से प्रक्रियाओं को अस्थायी रूप से हटा देता है और उन्हें द्वितीयक मेमोरी (जैसे हार्ड डिस्क ड्राइव) या इसके विपरीत में रखता है, जिसे आमतौर पर स्वैपिंग आउट या स्वैपिंग इन (गलत तरीके से पेजिंग आउट या पेजिंग इन) के रूप में संदर्भित किया जाता है। . मध्यम अवधि अनुसूचक ऐसी प्रक्रिया को स्वैप करने का निर्णय ले सकता है जो कुछ समय के लिए सक्रिय नहीं है, या ऐसी प्रक्रिया जिसकी प्राथमिकता कम है, या ऐसी प्रक्रिया जो अक्सर पेज फॉल्ट करती है, या एक प्रक्रिया जो बड़ी मात्रा में ले रही है मेमोरी अन्य प्रक्रियाओं के लिए मुख्य मेमोरी को मुक्त करने के लिए, प्रक्रिया को बाद में वापस स्वैप करना जब अधिक मेमोरी उपलब्ध हो, या जब प्रक्रिया को अनब्लॉक कर दिया गया हो और अब किसी संसाधन की प्रतीक्षा नहीं कर रहा हो। [स्टॉलिंग्स, 396] [स्टॉलिंग्स, 370]

आज कई प्रणालियों में (जो स्वैप फ़ाइल के अलावा द्वितीयक भंडारण के लिए आभासी पता स्थान की मैपिंग का समर्थन करते हैं), मध्यम अवधि के अनुसूचक वास्तव में बायनेरिज़ को उनके निष्पादन पर स्वैप आउट प्रक्रियाओं के रूप में मानकर दीर्घकालिक अनुसूचक की भूमिका निभा सकते हैं। इस तरह, जब बाइनरी के एक खंड की आवश्यकता होती है तो इसे ऑन डिमांड में स्वैप किया जा सकता है, या आलसी लोड किया जा सकता है, [स्टालिंग्स, 394] जिसे डिमांड पेजिंग भी कहा जाता है।

शॉर्ट टर्म शेड्यूलिंग

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

प्रीमेप्टिव शेड्यूलर एक प्रोग्रामेबल इंटरवल टाइमर पर निर्भर करता है जो एक इंटरप्ट हैंडलर को कॉल करता है जो कर्नेल मोड में चलता है और शेड्यूलिंग फ़ंक्शन को लागू करता है।

==डिस्पैचर

सीपीयू-शेड्यूलिंग फ़ंक्शन में शामिल एक अन्य घटक डिस्पैचर है, जो मॉड्यूल है जो सीपीयू को शॉर्ट-टर्म शेड्यूलर द्वारा चयनित प्रक्रिया को नियंत्रित करता है। यह एक रुकावट या सिस्टम कॉल के परिणाम के रूप में कर्नेल मोड में नियंत्रण प्राप्त करता है। डिस्पैचर के कार्यों में निम्नलिखित शामिल हैं:

संदर्भ स्विच, जिसमें डिस्पैचर प्रक्रिया (कंप्यूटिंग) या थ्रेड (कंप्यूटिंग) के राज्य (कंप्यूटर विज्ञान) (जिसे संदर्भ (कंप्यूटिंग) के रूप में भी जाना जाता है) को सहेजता है जो पहले चल रहा था; डिस्पैचर तब नई प्रक्रिया की प्रारंभिक या पहले से सहेजी गई स्थिति को लोड करता है।
उपयोगकर्ता मोड में स्विच करना।
उपयोगकर्ता प्रोग्राम में उचित स्थान पर कूदकर उस प्रोग्राम को फिर से शुरू करने के लिए जो उसके नए राज्य द्वारा इंगित किया गया है।

डिस्पैचर जितना तेज़ हो सके उतना तेज़ होना चाहिए, क्योंकि इसे प्रत्येक प्रक्रिया स्विच के दौरान लागू किया जाता है। संदर्भ स्विच के दौरान, प्रोसेसर समय के एक अंश के लिए वस्तुतः निष्क्रिय रहता है, इस प्रकार अनावश्यक संदर्भ स्विच से बचा जाना चाहिए। डिस्पैचर को एक प्रक्रिया को रोकने और दूसरी शुरू करने में लगने वाले समय को डिस्पैच लेटेंसी के रूप में जाना जाता है।^[7]^: 155

शेड्यूलिंग अनुशासन

शेड्यूलिंग डिसिप्लिन (जिसे शेड्यूलिंग पॉलिसी या शेड्यूलिंग एल्गोरिथम भी कहा जाता है) एक एल्गोरिथम है जिसका उपयोग पार्टियों के बीच संसाधनों को वितरित करने के लिए किया जाता है जो एक साथ और अतुल्यकालिक रूप से अनुरोध करते हैं। शेड्यूलिंग विषयों का उपयोग राउटर (कंप्यूटिंग) (पैकेट ट्रैफिक को संभालने के लिए) के साथ-साथ ऑपरेटिंग सिस्टम (थ्रेड (कंप्यूटर विज्ञान) और प्रक्रिया (कंप्यूटिंग) दोनों के बीच CPU समय साझा करने के लिए), डिस्क ड्राइव (I/O शेड्यूलिंग) में किया जाता है। प्रिंटर (प्रिंट स्पूलर), अधिकांश एम्बेडेड सिस्टम इत्यादि।

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

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

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

एचएसडीपीए (हाई-स्पीड डाउनलिंक पैकेट एक्सेस) 3.5 जी सेलुलर सिस्टम जैसे उन्नत पैकेट रेडियो वायरलेस नेटवर्क में, चैनल-निर्भर शेड्यूलिंग का उपयोग चैनल राज्य की जानकारी का लाभ उठाने के लिए किया जा सकता है। अगर चैनल की स्थिति अनुकूल है, तो थ्रूपुट और सिस्टम स्पेक्ट्रल दक्षता में वृद्धि हो सकती है। एलटीई एडवांस्ड जैसी और भी उन्नत प्रणालियों में, शेड्यूलिंग को चैनल-निर्भर पैकेट-दर-पैकेट डायनेमिक चैनल आवंटन, या उपयोगकर्ताओं को ओएफडीएमए मल्टी-कैरियर या अन्य फ्रीक्वेंसी-डोमेन इक्वलाइजेशन घटकों को असाइन करके जोड़ा जाता है जो उनका सबसे अच्छा उपयोग कर सकते हैं।^[9]

पहले आओ पहले पाओ

प्रतीक्षा कार्यों (नीला) की कतार (फीफो) और पूर्ण कार्यों की कतार (पीला) के साथ एक नमूना थ्रेड पूल (हरे बक्से)

फर्स्ट इन, फर्स्ट आउट (FIFO (कंप्यूटिंग और इलेक्ट्रॉनिक्स)), जिसे पहले आओ, पहले पाओ (FCFS) के रूप में भी जाना जाता है, सबसे सरल शेड्यूलिंग एल्गोरिथम है। फीफो केवल प्रक्रियाओं को कतारबद्ध करता है ताकि वे तैयार कतार में पहुंचें। यह आमतौर पर एक 'के लिए प्रयोग किया जाता हैtask queue, उदाहरण के लिए जैसा कि इस खंड में दिखाया गया है।

चूंकि संदर्भ स्विच केवल प्रक्रिया समाप्ति पर होते हैं, और प्रक्रिया कतार के पुनर्गठन की आवश्यकता नहीं होती है, शेड्यूलिंग ओवरहेड न्यूनतम होता है।
थ्रूपुट कम हो सकता है, क्योंकि लंबी प्रक्रियाएँ सीपीयू को धारण कर सकती हैं, जिससे छोटी प्रक्रियाएँ लंबे समय तक प्रतीक्षा करती हैं (जिसे काफिले प्रभाव के रूप में जाना जाता है)।
कोई भुखमरी नहीं, क्योंकि प्रत्येक प्रक्रिया को एक निश्चित समय के बाद निष्पादित होने का मौका मिलता है।
टर्नअराउंड समय, प्रतीक्षा समय और प्रतिक्रिया समय उनके आगमन के क्रम पर निर्भर करते हैं और ऊपर दिए गए समान कारणों से अधिक हो सकते हैं।
कोई प्राथमिकता नहीं होती है, इस प्रकार इस प्रणाली को प्रक्रिया की समय सीमा को पूरा करने में परेशानी होती है।
प्राथमिकता की कमी का मतलब है कि जब तक हर प्रक्रिया अंततः पूरी हो जाती है, तब तक कोई भुखमरी नहीं है। ऐसे माहौल में जहां कुछ प्रक्रियाएं पूरी नहीं हो सकती हैं, भुखमरी हो सकती है।
यह क्यूइंग पर आधारित है।

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

अर्लीएस्ट डेडलाइन फ़र्स्ट (EDF) या लीस्ट टाइम टू गो एक डायनामिक शेड्यूलिंग एल्गोरिद्म है जिसका उपयोग रीयल-टाइम ऑपरेटिंग सिस्टम में प्रक्रियाओं को प्राथमिकता कतार में रखने के लिए किया जाता है। जब भी कोई शेड्यूलिंग ईवेंट होता है (कोई कार्य समाप्त होता है, नया कार्य जारी किया जाता है, आदि), कतार को उसकी समय सीमा के सबसे निकट की प्रक्रिया के लिए खोजा जाएगा, जो कि निष्पादन के लिए निर्धारित की जाने वाली अगली होगी।

सबसे कम शेष समय पहले

शॉर्टेस्ट जॉब फर्स्ट (एसजेएफ) के समान। इस रणनीति के साथ अनुसूचक कतार में अगले होने के लिए कम से कम अनुमानित प्रसंस्करण समय के साथ प्रक्रियाओं की व्यवस्था करता है। प्रक्रिया को पूरा करने के लिए आवश्यक समय के बारे में इसके लिए उन्नत ज्ञान या अनुमान की आवश्यकता होती है।

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

निश्चित प्राथमिकता प्री-एम्प्टिव शेड्यूलिंग

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

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

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

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

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

बहुस्तरीय क्यू शेड्यूलिंग

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

कार्य-संरक्षण अनुसूचक

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

शेड्यूलिंग अनुकूलन समस्याएं

कई शेड्यूलिंग समस्याएं हैं जिनमें लक्ष्य यह तय करना है कि कौन सी नौकरी किस स्टेशन पर किस समय जाती है, जैसे कि कुल मेकस्पैन कम से कम हो:

जॉब शॉप शेड्यूलिंग – वहाँ हैं $n$ नौकरी और $m$ समान स्टेशन। प्रत्येक कार्य को एक मशीन पर निष्पादित किया जाना चाहिए। इसे आमतौर पर एक ऑनलाइन समस्या के रूप में माना जाता है।
ओपन-शॉप शेड्यूलिंग – वहाँ हैं $n$ नौकरी और $m$ विभिन्न स्टेशनों। प्रत्येक कार्य को प्रत्येक स्टेशन पर कुछ समय निःशुल्क क्रम में व्यतीत करना चाहिए।
फ्लो शॉप शेड्यूलिंग – वहाँ हैं $n$ नौकरी और $m$ विभिन्न स्टेशनों। प्रत्येक कार्य को पूर्व निर्धारित क्रम में प्रत्येक स्टेशन पर कुछ समय व्यतीत करना चाहिए।

मैनुअल शेड्यूलिंग

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

कोई संसाधन भुखमरी की समस्या नहीं
बहुत उच्च भविष्यवाणी; हार्ड रीयल-टाइम सिस्टम के कार्यान्वयन की अनुमति देता है
लगभग कोई ओवरहेड नहीं
सभी अनुप्रयोगों के लिए इष्टतम नहीं हो सकता है
प्रभावशीलता पूरी तरह से कार्यान्वयन पर निर्भर है

शेड्यूलिंग एल्गोरिथम चुनना

एक ऑपरेटिंग सिस्टम को डिजाइन करते समय, एक प्रोग्रामर को विचार करना चाहिए कि कौन सा शेड्यूलिंग एल्गोरिदम उस उपयोग के लिए सबसे अच्छा प्रदर्शन करेगा जो सिस्टम देखने जा रहा है। कोई सार्वभौमिक सर्वश्रेष्ठ शेड्यूलिंग एल्गोरिथम नहीं है, और कई ऑपरेटिंग सिस्टम उपरोक्त शेड्यूलिंग एल्गोरिदम के विस्तारित या संयोजन का उपयोग करते हैं।

उदाहरण के लिए, Windows NT/XP/Vista एक बहुस्तरीय प्रतिक्रिया कतार, निश्चित-प्राथमिकता प्रीमेप्टिव शेड्यूलिंग, राउंड-रॉबिन और पहले इन, पहले आउट एल्गोरिदम का संयोजन का उपयोग करता है। इस प्रणाली में, थ्रेड गतिशील रूप से प्राथमिकता में वृद्धि या कमी कर सकते हैं, यह इस बात पर निर्भर करता है कि क्या यह पहले से ही सर्विस किया गया है, या यदि यह बड़े पैमाने पर प्रतीक्षा कर रहा है। प्रत्येक प्राथमिकता स्तर को अपनी कतार द्वारा दर्शाया जाता है, जिसमें उच्च-प्राथमिकता वाले थ्रेड्स के बीच राउंड-रॉबिन शेड्यूलिंग और निम्न-प्राथमिकता वाले FIFO (कंप्यूटिंग और इलेक्ट्रॉनिक्स) होते हैं। इस अर्थ में, अधिकांश थ्रेड्स के लिए प्रतिक्रिया समय कम होता है, और छोटे लेकिन महत्वपूर्ण सिस्टम थ्रेड्स बहुत जल्दी पूरे हो जाते हैं। चूँकि थ्रेड्स सर्वोच्च-प्राथमिकता वाली कतार में राउंड-रॉबिन की केवल एक समय इकाई का उपयोग कर सकते हैं, इसलिए लंबे समय तक उच्च-प्राथमिकता वाले थ्रेड्स के लिए भुखमरी एक समस्या हो सकती है।

ऑपरेटिंग सिस्टम प्रोसेस शेड्यूलर कार्यान्वयन

इस्तेमाल किया जाने वाला एल्गोरिद्म राउंड-रॉबिन शेड्यूलिंग|राउंड-रॉबिन जितना आसान हो सकता है, जिसमें साइकलिंग सूची में प्रत्येक प्रक्रिया को बराबर समय दिया जाता है (उदाहरण के लिए 1 एमएस, आमतौर पर 1 एमएस और 100 एमएस के बीच)। इसलिए, प्रक्रिया A 1 एमएस के लिए निष्पादित होती है, फिर प्रक्रिया B, फिर प्रक्रिया C, फिर प्रक्रिया A पर वापस आती है।

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

OS/360 और उत्तराधिकारी

IBM OS/360 और उत्तराधिकारी | OS/360 तीन अलग-अलग अनुसूचकों के साथ उपलब्ध था। अंतर ऐसे थे कि वेरिएंट को अक्सर तीन अलग-अलग ऑपरेटिंग सिस्टम माना जाता था:

एकल अनुक्रमिक अनुसूचक विकल्प, जिसे प्राथमिक नियंत्रण कार्यक्रम (पीसीपी) के रूप में भी जाना जाता है, नौकरियों की एकल धारा का अनुक्रमिक निष्पादन प्रदान करता है।
एकाधिक अनुक्रमिक शेड्यूलर विकल्प, जिसे मल्टीप्रोग्रामिंग के रूप में जाना जाता है, निश्चित संख्या में कार्य (एमएफटी) के साथ कई समवर्ती नौकरियों का निष्पादन प्रदान करता है। निष्पादन एक प्राथमिकता द्वारा शासित था जिसमें प्रत्येक धारा के लिए डिफ़ॉल्ट था या प्रत्येक कार्य के लिए अलग से अनुरोध किया जा सकता था। एमएफटी संस्करण II में उप-कार्य (धागे) जोड़े गए, जो मूल कार्य के आधार पर प्राथमिकता पर निष्पादित किए गए। प्रत्येक जॉब स्ट्रीम ने उस स्ट्रीम में किसी भी जॉब द्वारा उपयोग की जा सकने वाली मेमोरी की अधिकतम मात्रा को परिभाषित किया।
मल्टीपल प्रायोरिटी शेड्यूलर्स विकल्प, या मल्टीप्रोग्रामिंग विद ए वेरिएबल नंबर ऑफ टास्क (एमवीटी), फीचर्ड सबटास्क शुरू से; प्रत्येक कार्य ने निष्पादन से पहले आवश्यक प्राथमिकता और स्मृति का अनुरोध किया।

एमवीएस के बाद के वर्चुअल स्टोरेज संस्करणों ने शेड्यूलर में एक वर्कलोड मैनेजर फीचर जोड़ा, जो इंस्टॉलेशन द्वारा परिभाषित एक विस्तृत योजना के अनुसार प्रोसेसर संसाधनों को शेड्यूल करता है।

विंडोज

बहुत पहले के MS-DOS और Microsoft Windows सिस्टम गैर-मल्टीटास्किंग थे, और इसलिए इसमें शेड्यूलर की सुविधा नहीं थी। विंडोज 3.1x ने एक गैर-प्रीमेप्टिव शेड्यूलर का उपयोग किया, जिसका अर्थ है कि यह प्रोग्राम को बाधित नहीं करता है। यह ओएस को समाप्त करने या यह बताने के लिए कार्यक्रम पर निर्भर था कि उसे प्रोसेसर की आवश्यकता नहीं थी ताकि वह दूसरी प्रक्रिया पर जा सके। इसे आमतौर पर सहकारी मल्टीटास्किंग कहा जाता है। विंडोज 95 ने एक अल्पविकसित प्रीमेप्टिव शेड्यूलर पेश किया; हालांकि, लीगेसी समर्थन के लिए 16 बिट अनुप्रयोगों को बिना पूर्वक्रय के चलने का विकल्प चुना गया।^[10] विंडोज एनटी-आधारित ऑपरेटिंग सिस्टम एक बहुस्तरीय प्रतिक्रिया कतार का उपयोग करते हैं। 32 प्राथमिकता स्तरों को परिभाषित किया गया है, 0 से 31 तक, प्राथमिकताओं के साथ 0 से 15 सामान्य प्राथमिकताएं और प्राथमिकताएं 16 से 31 सॉफ्ट रीयल-टाइम प्राथमिकताएं हैं, जिन्हें असाइन करने के लिए विशेषाधिकारों की आवश्यकता होती है। 0 ऑपरेटिंग सिस्टम के लिए आरक्षित है। उपयोगकर्ता इंटरफेस और एपीआई प्रक्रिया के लिए प्राथमिकता वर्गों और प्रक्रिया में थ्रेड्स के साथ काम करते हैं, जो तब सिस्टम द्वारा पूर्ण प्राथमिकता स्तर में संयुक्त होते हैं।

कर्नेल अपने I/O और CPU उपयोग के आधार पर थ्रेड के प्राथमिकता स्तर को बदल सकता है और क्या यह इंटरैक्टिव है (यानी मानव से इनपुट स्वीकार करता है और प्रतिक्रिया करता है), इंटरैक्टिव और I/O बाध्य प्रक्रियाओं की प्राथमिकता को बढ़ाता है और इसे कम करता है सीपीयू बाध्य प्रक्रियाएं, इंटरैक्टिव अनुप्रयोगों की जवाबदेही बढ़ाने के लिए।^[11] शेड्यूलर को आधुनिक प्रोसेसर के टाइम स्टैम्प काउंटर का उपयोग करने के लिए विंडोज विस्टा में संशोधित किया गया था ताकि यह ट्रैक किया जा सके कि एक अंतराल-टाइमर इंटरप्ट रूटीन का उपयोग करने के बजाय वास्तव में कितने सीपीयू चक्रों को निष्पादित किया गया है।^[12] विस्टा I/O कतार के लिए प्राथमिकता शेड्यूलर का भी उपयोग करता है ताकि डिस्क डीफ़्रेग्मेंटर्स और ऐसे अन्य प्रोग्राम अग्रभूमि संचालन में हस्तक्षेप न करें।^[13]

क्लासिक मैक ओएस और macOS

मैक ओएस 9 थ्रेड्स के लिए सहकारी शेड्यूलिंग का उपयोग करता है, जहां एक प्रक्रिया कई सहकारी थ्रेड्स को नियंत्रित करती है, और मल्टीप्रोसेसिंग कार्यों के लिए प्रीमेप्टिव शेड्यूलिंग भी प्रदान करती है। कर्नेल प्रीमेप्टिव शेड्यूलिंग एल्गोरिथम का उपयोग करके मल्टीप्रोसेसिंग कार्यों को शेड्यूल करता है। सभी प्रक्रिया प्रबंधक प्रक्रियाएं एक विशेष मल्टीप्रोसेसिंग कार्य के भीतर चलती हैं, जिसे नीला कार्य कहा जाता है। राउंड-रॉबिन शेड्यूलिंग एल्गोरिथम का उपयोग करके उन प्रक्रियाओं को सहकारी रूप से शेड्यूल किया जाता है; एक प्रक्रिया स्पष्ट रूप से एक अवरुद्ध कार्य जैसे कॉल करके प्रोसेसर को दूसरी प्रक्रिया में नियंत्रित करती है WaitNextEvent. प्रत्येक प्रक्रिया के पास थ्रेड मैनेजर की अपनी प्रति होती है जो उस प्रक्रिया के थ्रेड्स को सहकारी रूप से शेड्यूल करती है; एक थ्रेड कॉल करके प्रोसेसर को दूसरे थ्रेड पर नियंत्रित करता है YieldToAnyThread या YieldToThread.^[14] macOS थ्रेड के लिए चार प्राथमिकता वाले बैंड के साथ बहुस्तरीय फ़ीडबैक कतार का उपयोग करता है – सामान्य, सिस्टम उच्च प्राथमिकता, केवल कर्नेल मोड और रीयल-टाइम।^[15] थ्रेड्स प्रीमेप्टिवली शेड्यूल किए गए हैं; macOS कार्बन (API) में थ्रेड मैनेजर के कार्यान्वयन में सहकारी रूप से शेड्यूल किए गए थ्रेड्स का भी समर्थन करता है।^[14]

ऐक्स

AIX संस्करण 4 में थ्रेड शेड्यूलिंग नीति के लिए तीन संभावित मान हैं:

फर्स्ट इन, फर्स्ट आउट: एक बार जब इस नीति के साथ एक थ्रेड शेड्यूल हो जाता है, तो यह तब तक पूरा होता है जब तक कि इसे ब्लॉक नहीं किया जाता है, यह स्वेच्छा से सीपीयू का नियंत्रण देता है, या उच्च-प्राथमिकता वाला थ्रेड डिस्पैचेबल हो जाता है। केवल निश्चित-प्राथमिकता वाले थ्रेड्स में FIFO शेड्यूलिंग नीति हो सकती है।
राउंड रॉबिन: यह 10 एमएस टाइम स्लाइस पर आधारित AIX वर्जन 3 शेड्यूलर राउंड-रॉबिन स्कीम के समान है। जब आरआर थ्रेड का समय स्लाइस के अंत में नियंत्रण होता है, तो यह अपनी प्राथमिकता के डिस्पैचेबल थ्रेड्स की कतार के अंत में चला जाता है। केवल निश्चित-प्राथमिकता वाले थ्रेड्स में राउंड रॉबिन शेड्यूलिंग नीति हो सकती है।
अन्य: यह नीति POSIX1003.4a द्वारा कार्यान्वयन-परिभाषित के रूप में परिभाषित की गई है। AIX संस्करण 4 में, इस नीति को RR के समतुल्य के रूप में परिभाषित किया गया है, सिवाय इसके कि यह गैर-निश्चित प्राथमिकता वाले थ्रेड्स पर लागू होती है। प्रत्येक क्लॉक इंटरप्ट पर रनिंग थ्रेड के प्राथमिकता मान की पुनर्गणना का अर्थ है कि एक थ्रेड नियंत्रण खो सकता है क्योंकि इसका प्राथमिकता मान दूसरे डिस्पैचेबल थ्रेड के ऊपर बढ़ गया है। यह AIX संस्करण 3 व्यवहार है।

थ्रेड मुख्य रूप से उन अनुप्रयोगों के लिए रुचि रखते हैं जिनमें वर्तमान में कई अतुल्यकालिक प्रक्रियाएं शामिल हैं। मल्टीथ्रेडेड संरचना में परिवर्तित होने पर ये एप्लिकेशन सिस्टम पर हल्का भार लगा सकते हैं।

AIX 5 निम्नलिखित शेड्यूलिंग नीतियों को लागू करता है: FIFO, राउंड रॉबिन और एक फेयर राउंड रॉबिन। FIFO नीति के तीन अलग-अलग कार्यान्वयन हैं: FIFO, FIFO2 और FIFO3। AIX में राउंड रॉबिन पॉलिसी का नाम SCHED_RR है और फेयर राउंड रॉबिन पॉलिसी को SCHED_OTHER कहा जाता है।^[16]

लिनक्स

लिनक्स कर्नेल की अत्यधिक सरलीकृत संरचना, जिसमें प्रोसेस शेड्यूलर, I/O शेड्यूलर और लिनक्स कर्नेल पैकेट शेड्यूलर शामिल हैं

लिनक्स 2.4

लिनक्स 2.4 में, 0 से 140 तक के प्राथमिकता स्तर वाले बहुस्तरीय फीडबैक क्यू के साथ एक O(n) अनुसूचक का उपयोग किया गया था; 0-99 वास्तविक समय के कार्यों के लिए आरक्षित हैं और 100-140 को अच्छा (यूनिक्स) कार्य स्तर माना जाता है। रीयल-टाइम कार्यों के लिए, प्रक्रियाओं को स्विच करने के लिए समय की मात्रा लगभग 200 एमएस थी, और अच्छे कार्यों के लिए लगभग 10 एमएस थी।^{[citation needed]} अनुसूचक सभी तैयार प्रक्रियाओं की रन कतार के माध्यम से चलता है, उच्चतम प्राथमिकता वाली प्रक्रियाओं को पहले जाने देता है और उनके समय के स्लाइस के माध्यम से चलता है, जिसके बाद उन्हें समाप्त कतार में रखा जाएगा। जब सक्रिय कतार खाली होती है तो समाप्त कतार सक्रिय कतार बन जाएगी और इसके विपरीत।

हालांकि, कुछ एंटरप्राइज़ लिनक्स वितरण जैसे एसयूएसई लिनक्स एंटरप्राइज़ सर्वर ने इस शेड्यूलर को ओ (1) शेड्यूलर (जिसे एलन कॉक्स (कंप्यूटर प्रोग्रामर) द्वारा अपने लिनक्स 2.4-एसी कर्नेल श्रृंखला में बनाए रखा गया था) के बैकपोर्ट के साथ लिनक्स 2.4 कर्नेल में बदल दिया। वितरण द्वारा उपयोग किया जाता है।

लिनक्स 2.6.0 से लिनक्स 2.6.22

संस्करण 2.6.0 से 2.6.22 में, कर्नेल ने Linux 2.5 के विकास के दौरान Ingo Molnar और कई अन्य कर्नेल डेवलपर्स द्वारा विकसित O(1) अनुसूचक का उपयोग किया। समय सीमा में कई कर्नेल के लिए, कोन कोलिवस ने पैच सेट विकसित किए जो इस अनुसूचक के साथ अन्तरक्रियाशीलता में सुधार करते हैं या यहां तक कि इसे अपने स्वयं के अनुसूचकों के साथ बदल देते हैं।

====लिनक्स 2.6.23==== के बाद से कोन कोलिवास का काम, सबसे महत्वपूर्ण रूप से रोटेटिंग स्टेयरकेस डेडलाइन नाम के फेयर-शेयर शेड्यूलिंग के उनके कार्यान्वयन ने इंगो मोलनार को पहले के ओ (1) शेड्यूलर के प्रतिस्थापन के रूप में कंप्लीटली फेयर शेड्यूलर विकसित करने के लिए प्रेरित किया, अपनी घोषणा में कोलिवास को श्रेय दिया।^[17] सीएफएस एक सामान्य उद्देश्य ऑपरेटिंग सिस्टम में व्यापक रूप से उपयोग किए जाने वाले उचित क्यूइंग प्रोसेस शेड्यूलर का पहला कार्यान्वयन है।^[18] कंप्लीटली फेयर शेड्यूलर (सीएफएस) एक अच्छी तरह से अध्ययन किए गए, क्लासिक शेड्यूलिंग एल्गोरिदम का उपयोग करता है जिसे फेयर क्यूइंग कहा जाता है जो मूल रूप से पैकेट नेटवर्क के लिए आविष्कार किया गया था। स्ट्राइड शेड्यूलिंग नाम के तहत सीपीयू शेड्यूलिंग के लिए फेयर क्यूइंग को पहले लागू किया गया था। फेयर क्यूइंग सीएफएस शेड्यूलर की शेड्यूलिंग जटिलता है $O(\log N)$ , कहां $N$ रन कतार में कार्यों की संख्या है। एक कार्य का चयन निरंतर समय में किया जा सकता है, लेकिन एक कार्य के चलने के बाद उसे फिर से सम्मिलित करने की आवश्यकता होती है $O(\log N)$ ऑपरेशन, क्योंकि रन कतार को लाल-काले पेड़ के रूप में लागू किया जाता है।

ब्रेन फक शेड्यूलर, जिसे कोन कोलिवास द्वारा भी बनाया गया है, सीएफएस का एक विकल्प है।

फ्रीबीएसडी

FreeBSD 0-255 से लेकर प्राथमिकताओं के साथ एक बहुस्तरीय प्रतिक्रिया कतार का उपयोग करता है। 0-63 इंटरप्ट्स के लिए आरक्षित हैं, 64-127 कर्नेल के शीर्ष आधे के लिए, 128-159 रीयल-टाइम उपयोगकर्ता थ्रेड्स के लिए, 160-223 समय-साझा उपयोगकर्ता थ्रेड्स के लिए, और 224-255 निष्क्रिय उपयोगकर्ता थ्रेड्स के लिए आरक्षित हैं। इसके अलावा, लिनक्स की तरह, यह सक्रिय क्यू सेटअप का उपयोग करता है, लेकिन इसमें एक निष्क्रिय कतार भी है।^[19]

नेटबीएसडी

नेटबीएसडी 0-223 की प्राथमिकताओं के साथ एक बहुस्तरीय प्रतिक्रिया कतार का उपयोग करता है। 0–63 समय-साझा थ्रेड्स के लिए आरक्षित हैं (डिफ़ॉल्ट, SCHED_OTHER नीति), 64-95 उपयोगकर्ता थ्रेड्स के लिए आरक्षित हैं जो कर्नेल स्पेस में प्रवेश करते हैं, 96-128 कर्नेल थ्रेड्स के लिए, 128-191 उपयोगकर्ता रीयल-टाइम थ्रेड्स के लिए (SCHED_FIFO और SCHED_RR नीतियां) , और 192–223 इंटरप्ट के लिए।

सोलारिस

सोलारिस (ऑपरेटिंग सिस्टम) 0 और 169 के बीच की प्राथमिकताओं के साथ एक बहुस्तरीय प्रतिक्रिया कतार का उपयोग करता है। प्राथमिकताएं 0–59 समय-साझा थ्रेड्स के लिए आरक्षित हैं, 60–99 सिस्टम थ्रेड्स के लिए, 100–159 रीयल-टाइम थ्रेड्स के लिए, और 160–169 कम प्राथमिकता वाले व्यवधानों के लिए। लिनक्स के विपरीत,^[19]जब कोई प्रक्रिया अपने समय की मात्रा का उपयोग करके की जाती है, तो उसे एक नई प्राथमिकता दी जाती है और कतार में वापस रखा जाता है। Solaris 9 ने दो नए शेड्यूलिंग क्लास पेश किए, जिनके नाम हैं फिक्स्ड प्रायोरिटी क्लास और फेयर शेयर क्लास। निश्चित प्राथमिकता वाले थ्रेड्स में समय-साझाकरण वर्ग के समान प्राथमिकता सीमा होती है, लेकिन उनकी प्राथमिकताओं को गतिशील रूप से समायोजित नहीं किया जाता है। शेड्यूलिंग निर्णयों के लिए थ्रेड्स को प्राथमिकता देने के लिए फेयर शेड्यूलिंग क्लास CPU शेयरों का उपयोग करता है। सीपीयू शेयर सीपीयू संसाधनों की पात्रता को दर्शाता है। उन्हें प्रक्रियाओं के एक समूह के लिए आवंटित किया जाता है, जिन्हें सामूहिक रूप से एक परियोजना के रूप में जाना जाता है।^[7]

सारांश

Operating System	Preemption	Algorithm
Amiga OS	Yes	Prioritized round-robin scheduling
FreeBSD	Yes	Multilevel feedback queue
Linux kernel before 2.6.0	Yes	Multilevel feedback queue
Linux kernel 2.6.0–2.6.23	Yes	O(1) scheduler
Linux kernel after 2.6.23	Yes	Completely Fair Scheduler
classic Mac OS pre-9	None	Cooperative scheduler
Mac OS 9	Some	Preemptive scheduler for MP tasks, and cooperative for processes and threads
macOS	Yes	Multilevel feedback queue
NetBSD	Yes	Multilevel feedback queue
Solaris	Yes	Multilevel feedback queue
Windows 3.1x	None	Cooperative scheduler
Windows 95, 98, Me	Half	Preemptive scheduler for 32-bit processes, and cooperative for 16-bit processes
Windows NT (including 2000, XP, Vista, 7, and Server)	Yes	Multilevel feedback queue

यह भी देखें

गतिविधि चयन समस्या
एजिंग (समयबद्धन)
एट्रोपोस अनुसूचक
स्वचालित योजना और शेड्यूलिंग
चक्रीय कार्यकारी
गतिशील प्राथमिकता निर्धारण
अग्रभूमि पृष्ठभूमि
इंटरप्टिबल ऑपरेटिंग सिस्टम
कम से कम सुस्त समय निर्धारण
लॉटरी शेड्यूलिंग
प्राथमिकता उलटा
प्रक्रिया राज्य
कतार सिद्धांत
दर-मोनोटोनिक शेड्यूलिंग
संसाधन-कार्य नेटवर्क
निर्धारण (उत्पादन प्रक्रियाएं)
स्टोकेस्टिक शेड्यूलिंग
समय-उपयोगिता समारोह

↑ C. L., Liu; James W., Layland (January 1973). "हार्ड-रियल-टाइम एनवायरनमेंट में मल्टीप्रोग्रामिंग के लिए शेड्यूलिंग एल्गोरिदम". Journal of the ACM. ACM. 20 (1): 46–61. doi:10.1145/321738.321743. S2CID 207669821. हम एक निश्चित कार्य के लिए अनुरोध के प्रतिक्रिया समय को अनुरोध और उस अनुरोध की प्रतिक्रिया के अंत के बीच के समय के अंतराल के रूप में परिभाषित करते हैं।
↑ Kleinrock, Leonard (1976). क्यूइंग सिस्टम्स, वॉल्यूम। 2: कंप्यूटर अनुप्रयोग (1 ed.). Wiley-Interscience. p. 171. ISBN 047149111X. एक ग्राहक के लिए सेवा के एक्स सेकंड की आवश्यकता होती है, उसका प्रतिक्रिया समय उसके सेवा समय एक्स प्लस उसके प्रतीक्षा समय के बराबर होगा।
↑ Feitelson, Dror G. (2015). कंप्यूटर सिस्टम प्रदर्शन मूल्यांकन के लिए वर्कलोड मॉडलिंग. Cambridge University Press. Section 8.4 (Page 422) in Version 1.03 of the freely available manuscript. ISBN 9781107078239. Retrieved 2015-10-17. यदि हम उस समय को निरूपित करते हैं जो एक नौकरी क्यू में प्रतीक्षा करती है t_w, और समय यह वास्तव में t_r द्वारा चलता है, तो प्रतिक्रिया समय r = t_{डब्ल्यू</उप> + टी<उप>आर</उप>।}
↑ Silberschatz, Abraham; Galvin, Peter Baer; Gagne, Greg (2012). ऑपरेटिंग सिस्टम अवधारणाओं (9 ed.). Wiley Publishing. p. 187. ISBN 978-0470128725. एक इंटरैक्टिव सिस्टम में, टर्नअराउंड समय सबसे अच्छा मानदंड नहीं हो सकता है। अक्सर, एक प्रक्रिया काफी पहले कुछ आउटपुट उत्पन्न कर सकती है और नए परिणामों की गणना जारी रख सकती है, जबकि पिछले परिणाम उपयोगकर्ता के लिए आउटपुट हो रहे हैं। इस प्रकार, एक अन्य उपाय एक अनुरोध प्रस्तुत करने से लेकर पहली प्रतिक्रिया उत्पन्न होने तक का समय है। यह उपाय, जिसे प्रतिक्रिया समय कहा जाता है, प्रतिक्रिया शुरू करने में लगने वाला समय है, न कि प्रतिक्रिया को आउटपुट करने में लगने वाला समय।
↑ Paul Krzyzanowski (2014-02-19). "प्रक्रिया निर्धारण: आगे कौन दौड़ेगा?". cs.rutgers.edu. Retrieved 2015-01-11.
↑ Raphael Finkel. "An Operating Systems Vade Mecum". Prentice Hall. 1988. "chapter 2: Time Management". p. 27.
↑ ^7.0 ^7.1 ^7.2 Abraham Silberschatz, Peter Baer Galvin and Greg Gagne (2013). ऑपरेटिंग सिस्टम अवधारणाओं. Vol. 9. John Wiley & Sons, Inc. ISBN 978-1-118-06333-0.{{cite book}}: CS1 maint: uses authors parameter (link)
↑ Robert Kroeger (2004). "Admission Control for Independently-authored Realtime Applications". UWSpace. http://hdl.handle.net/10012/1170 . Section "2.6 Admission Control". p. 33.
↑ Guowang Miao; Jens Zander; Ki Won Sung; Ben Slimane (2016). मोबाइल डेटा नेटवर्क के मूल तत्व. Cambridge University Press. ISBN 978-1107143210.
↑ Early Windows at the Wayback Machine (archive index)
↑ Sriram Krishnan. "ए टेल ऑफ़ टू शेड्यूलर्स विंडोज एनटी और विंडोज सीई". Archived from the original on July 22, 2012.
↑ "विंडोज एडमिनिस्ट्रेशन: विंडोज विस्टा कर्नेल के अंदर: भाग 1". Technet.microsoft.com. 2016-11-14. Retrieved 2016-12-09.
↑ "संग्रहीत प्रति". blog.gabefrost.com. Archived from the original on 19 February 2008. Retrieved 15 January 2022.
↑ ^14.0 ^14.1 "तकनीकी नोट TN2028: थ्रेडिंग आर्किटेक्चर". developer.apple.com. Retrieved 2019-01-15.
↑ "मैक शेड्यूलिंग और थ्रेड इंटरफेस". developer.apple.com. Retrieved 2019-01-15.
↑ [1] Archived 2011-08-11 at the Wayback Machine
↑ Molnár, Ingo (2007-04-13). "[पैच] मॉड्यूलर शेड्यूलर कोर और कंप्लीटली फेयर शेड्यूलर [सीएफएस]". linux-kernel (Mailing list).
↑ Tong Li; Dan Baumberger; Scott Hahn. "वितरित भारित राउंड-रॉबिन का उपयोग करके कुशल और स्केलेबल मल्टीप्रोसेसर फेयर शेड्यूलिंग" (PDF). Happyli.org. Retrieved 2016-12-09.
↑ ^19.0 ^19.1 "Solaris, Linux, और FreeBSD कर्नेल की तुलना" (PDF). Archived from the original (PDF) on August 7, 2008.

संदर्भ

Błażewicz, Jacek; Ecker, K.H.; Pesch, E.; Schmidt, G.; Weglarz, J. (2001). Scheduling computer and manufacturing processes (2 ed.). Berlin [u.a.]: Springer. ISBN 3-540-41931-4.
Stallings, William (2004). Operating Systems Internals and Design Principles (fourth ed.). Prentice Hall. ISBN 0-13-031999-6.
Information on the Linux 2.6 O(1)-scheduler

इस पेज में लापता आंतरिक लिंक की सूची

आगे की पढाई

Operating Systems: Three Easy Pieces by Remzi H. Arpaci-Dusseau and Andrea C. Arpaci-Dusseau. Arpaci-Dusseau Books, 2014. Relevant chapters: Scheduling: Introduction Multi-level Feedback Queue Proportional-share Scheduling Multiprocessor Scheduling
Brief discussion of Job Scheduling algorithms
Understanding the Linux Kernel: Chapter 10 Process Scheduling
Kerneltrap: Linux kernel scheduler articles
AIX CPU monitoring and tuning
Josh Aas' introduction to the Linux 2.6.8.1 CPU scheduler implementation
Peter Brucker, Sigrid Knust. Complexity results for scheduling problems [2]
TORSCHE Scheduling Toolbox for Matlab is a toolbox of scheduling and graph algorithms.
A survey on cellular networks packet scheduling
Large-scale cluster management at Google with Borg

श्रेणी:संचालन अनुसंधान श्रेणी:योजना श्रेणी: सॉफ्टवेयर डिजाइन पैटर्न

[liu1973-1] C. L., Liu; James W., Layland (January 1973). "हार्ड-रियल-टाइम एनवायरनमेंट में मल्टीप्रोग्रामिंग के लिए शेड्यूलिंग एल्गोरिदम". Journal of the ACM. ACM. 20 (1): 46–61. doi:10.1145/321738.321743. S2CID 207669821. हम एक निश्चित कार्य के लिए अनुरोध के प्रतिक्रिया समय को अनुरोध और उस अनुरोध की प्रतिक्रिया के अंत के बीच के समय के अंतराल के रूप में परिभाषित करते हैं।

[kleinrock1976-2] Kleinrock, Leonard (1976). क्यूइंग सिस्टम्स, वॉल्यूम। 2: कंप्यूटर अनुप्रयोग (1 ed.). Wiley-Interscience. p. 171. ISBN 047149111X. एक ग्राहक के लिए सेवा के एक्स सेकंड की आवश्यकता होती है, उसका प्रतिक्रिया समय उसके सेवा समय एक्स प्लस उसके प्रतीक्षा समय के बराबर होगा।

[feitelson2014-3] Feitelson, Dror G. (2015). कंप्यूटर सिस्टम प्रदर्शन मूल्यांकन के लिए वर्कलोड मॉडलिंग. Cambridge University Press. Section 8.4 (Page 422) in Version 1.03 of the freely available manuscript. ISBN 9781107078239. Retrieved 2015-10-17. यदि हम उस समय को निरूपित करते हैं जो एक नौकरी क्यू में प्रतीक्षा करती है t_w, और समय यह वास्तव में t_r द्वारा चलता है, तो प्रतिक्रिया समय r = t_{डब्ल्यू</उप> + टी<उप>आर</उप>।}

[silberschatz2012-4] Silberschatz, Abraham; Galvin, Peter Baer; Gagne, Greg (2012). ऑपरेटिंग सिस्टम अवधारणाओं (9 ed.). Wiley Publishing. p. 187. ISBN 978-0470128725. एक इंटरैक्टिव सिस्टम में, टर्नअराउंड समय सबसे अच्छा मानदंड नहीं हो सकता है। अक्सर, एक प्रक्रिया काफी पहले कुछ आउटपुट उत्पन्न कर सकती है और नए परिणामों की गणना जारी रख सकती है, जबकि पिछले परिणाम उपयोगकर्ता के लिए आउटपुट हो रहे हैं। इस प्रकार, एक अन्य उपाय एक अनुरोध प्रस्तुत करने से लेकर पहली प्रतिक्रिया उत्पन्न होने तक का समय है। यह उपाय, जिसे प्रतिक्रिया समय कहा जाता है, प्रतिक्रिया शुरू करने में लगने वाला समय है, न कि प्रतिक्रिया को आउटपुट करने में लगने वाला समय।

[5] Paul Krzyzanowski (2014-02-19). "प्रक्रिया निर्धारण: आगे कौन दौड़ेगा?". cs.rutgers.edu. Retrieved 2015-01-11.

[6] Raphael Finkel. "An Operating Systems Vade Mecum". Prentice Hall. 1988. "chapter 2: Time Management". p. 27.

[galvin-7] 7.0 ^7.1 ^7.2 Abraham Silberschatz, Peter Baer Galvin and Greg Gagne (2013). ऑपरेटिंग सिस्टम अवधारणाओं. Vol. 9. John Wiley & Sons, Inc. ISBN 978-1-118-06333-0.{{cite book}}: CS1 maint: uses authors parameter (link)

[8] Robert Kroeger (2004). "Admission Control for Independently-authored Realtime Applications". UWSpace. http://hdl.handle.net/10012/1170 . Section "2.6 Admission Control". p. 33.

[Miao-9] Guowang Miao; Jens Zander; Ki Won Sung; Ben Slimane (2016). मोबाइल डेटा नेटवर्क के मूल तत्व. Cambridge University Press. ISBN 978-1107143210.

[10] Early Windows at the Wayback Machine (archive index)

[11] Sriram Krishnan. "ए टेल ऑफ़ टू शेड्यूलर्स विंडोज एनटी और विंडोज सीई". Archived from the original on July 22, 2012.

[12] "विंडोज एडमिनिस्ट्रेशन: विंडोज विस्टा कर्नेल के अंदर: भाग 1". Technet.microsoft.com. 2016-11-14. Retrieved 2016-12-09.

[13] "संग्रहीत प्रति". blog.gabefrost.com. Archived from the original on 19 February 2008. Retrieved 15 January 2022.

[appletn2028-14] 14.0 ^14.1 "तकनीकी नोट TN2028: थ्रेडिंग आर्किटेक्चर". developer.apple.com. Retrieved 2019-01-15.

[15] "मैक शेड्यूलिंग और थ्रेड इंटरफेस". developer.apple.com. Retrieved 2019-01-15.

[16] [1] Archived 2011-08-11 at the Wayback Machine

[17] Molnár, Ingo (2007-04-13). "[पैच] मॉड्यूलर शेड्यूलर कोर और कंप्लीटली फेयर शेड्यूलर [सीएफएस]". linux-kernel (Mailing list).

[dwrr-18] Tong Li; Dan Baumberger; Scott Hahn. "वितरित भारित राउंड-रॉबिन का उपयोग करके कुशल और स्केलेबल मल्टीप्रोसेसर फेयर शेड्यूलिंग" (PDF). Happyli.org. Retrieved 2016-12-09.

[opensolaris-queue-19] 19.0 ^19.1 "Solaris, Linux, और FreeBSD कर्नेल की तुलना" (PDF). Archived from the original (PDF) on August 7, 2008.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

v t e Processor scheduling
Algorithms	Deadline-monotonic Earliest deadline Fair-share Fixed-priority pre-emptive Foreground-background Gang Generalized foreground-background Highest response ratio next Lottery Multilevel feedback queue Process Contention Scope Proportional share Rate-monotonic Round-robin Shortest job next Shortest remaining time Statistical time-division multiplexing Stride Two-level Windows NT YDS algorithm
Linux	Brain Fuck Completely Fair O(1) O(n) SCHED DEADLINE SCHED FIFO SCHED NORMAL
Other	Processor affinity Starvation