शेड्यूलिंग (कंप्यूटिंग)

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

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

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

लक्ष्य

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

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

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

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

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

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

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

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

दीर्घकालिक शेड्यूलिंग

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

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

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

मध्यम अवधि शेड्यूलिंग

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

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

अल्पकालिक शेड्यूलिंग

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

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

प्रेषक

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ऑपरेटिंग सिस्टम प्रक्रिया अनुसूचक कार्यान्वयन

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

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

ओएस/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]

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

मैक ओएस 9 थ्रेड्स के लिए सहकारी शेड्यूलिंग का उपयोग करता है, जहां एक प्रक्रिया कई सहकारी थ्रेड्स को नियंत्रित करती है, और मल्टीप्रोसेसिंग कार्यों के लिए प्रीमेप्टिव शेड्यूलिंग भी प्रदान करती है। कर्नेल एक प्रीमेप्टिव शेड्यूलिंग एल्गोरिदम का उपयोग करके मल्टीप्रोसेसिंग कार्यों को शेड्यूल करता है। सभी प्रक्रिया प्रबंधक प्रक्रियाएँ एक विशेष मल्टीप्रोसेसिंग कार्य के अंतर्गत चलती हैं, जिसे ब्लू कार्य कहा जाता है। उन प्रक्रियाओं को राउंड-रॉबिन शेड्यूलिंग एल्गोरिदम का उपयोग करके सहकारी रूप से निर्धारित किया जाता है; एक प्रक्रिया अवरुद्ध करने का कार्य को स्पष्ट रूप से कॉल करके प्रोसेसर का नियंत्रण किसी अन्य प्रक्रिया को प्रदान करती है WaitNextEvent. प्रत्येक प्रक्रिया में थ्रेड मैनेजर की अपनी प्रति होती है जो उस प्रक्रिया के थ्रेड को सहकारी रूप से शेड्यूल करती है; एक थ्रेड कॉल करके प्रोसेसर का नियंत्रण दूसरे थ्रेड को देता है YieldToAnyThread या YieldToThread.^[14] macOS थ्रेड के लिए चार प्राथमिकता बैंड के साथ एक बहुस्तरीय फीडबैक कतार का उपयोग करता है – सामान्य, सिस्टम उच्च प्राथमिकता, केवल कर्नेल मोड, और वास्तविक समय।^[15] थ्रेड्स को पूर्वनिर्धारित रूप से शेड्यूल किया गया है; macOS कार्बन में थ्रेड मैनेजर (एपीआई) के कार्यान्वयन में सहकारी रूप से निर्धारित थ्रेड्स का भी समर्थन करता है।^[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 तक के प्राथमिकता स्तरों के साथ बहुस्तरीय फीडबैक कतार के साथ एक ओ (एनओ(एन) शेड्यूलर का उपयोग किया गया था; 0-99 वास्तविक समय के कार्यों के लिए आरक्षित हैं और 100-140 को अच्छा (यूनिक्स) कार्य स्तर माना जाता है। वास्तविक समय के कार्यों के लिए, स्विचिंग प्रक्रियाओं के लिए समय की मात्रा लगभग 200 एमएस थी, और अच्छे कार्यों के लिए लगभग 10 एमएस थी।^{[citation needed]} शेड्यूलर सभी तैयार प्रक्रियाओं की रन कतार के माध्यम से चला, सर्वोच्च प्राथमिकता वाली प्रक्रियाओं को पहले जाने और उनके समय स्लाइस के माध्यम से चलाने की अनुमति देता है, जिसके बाद उन्हें एक समाप्त कतार में रखा जाएगा। जब सक्रिय कतार खाली हो जाती है तो समाप्त कतार सक्रिय कतार बन जाएगी और इसके विपरीत।

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

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

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

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

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

फ्रीबीएसडी

फ्रीबीएसडी 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]जब कोई प्रक्रिया अपने समय की मात्रा का उपयोग करके की जाती है, तो इसे एक नई प्राथमिकता दी जाती है और कतार में वापस डाल दिया जाता है। सोलारिस 9 ने दो नए शेड्यूलिंग वर्ग पेश किए, अर्थात् निश्चित प्राथमिकता वर्ग और उचित शेयर वर्ग। निश्चित प्राथमिकता वाले थ्रेड्स की प्राथमिकता सीमा समय-साझाकरण वर्ग के समान होती है, लेकिन उनकी प्राथमिकताएँ गतिशील रूप से समायोजित नहीं होती हैं। फेयर शेड्यूलिंग क्लास शेड्यूलिंग निर्णयों के लिए थ्रेड को प्राथमिकता देने के लिए सीपीयू शेयरों का उपयोग करता है। सीपीयू शेयर सीपीयू संसाधनों के अधिकार को दर्शाते हैं। उन्हें प्रक्रियाओं के एक समूह के लिए आवंटित किया जाता है, जिन्हें सामूहिक रूप से एक परियोजना के रूप में जाना जाता है।^[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). "Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment". Journal of the ACM. ACM. 20 (1): 46–61. doi:10.1145/321738.321743. S2CID 207669821. We define the response time of a request for a certain task to be the time span between the request and the end of the response to that request.
↑ Kleinrock, Leonard (1976). Queueing Systems, Vol. 2: Computer Applications (1 ed.). Wiley-Interscience. p. 171. ISBN 047149111X. For a customer requiring x sec of service, his response time will equal his service time x plus his waiting time.
↑ Feitelson, Dror G. (2015). Workload Modeling for Computer Systems Performance Evaluation. Cambridge University Press. Section 8.4 (Page 422) in Version 1.03 of the freely available manuscript. ISBN 9781107078239. Retrieved 2015-10-17. if we denote the time that a job waits in the queue by t_w, and the time it actually runs by t_r, then the response time is r = t_w + t_r.
↑ Silberschatz, Abraham; Galvin, Peter Baer; Gagne, Greg (2012). Operating System Concepts (9 ed.). Wiley Publishing. p. 187. ISBN 978-0470128725. In an interactive system, turnaround time may not be the best criterion. Often, a process can produce some output fairly early and can continue computing new results while previous results are being output to the user. Thus, another measure is the time from the submission of a request until the first response is produced. This measure, called response time, is the time it takes to start responding, not the time it takes to output the response.
↑ Paul Krzyzanowski (2014-02-19). "Process Scheduling: Who gets to run next?". cs.rutgers.edu. Retrieved 2023-06-19.
↑ 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; Greg Gagne (2013). Operating System Concepts. Vol. 9. John Wiley & Sons, Inc. ISBN 978-1-118-06333-0.
↑ 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.
↑ "Windows Administration: Inside the Windows Vista Kernel: Part 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 "Technical Note TN2028: Threading Architectures". 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). "[patch] Modular Scheduler Core and Completely Fair Scheduler [CFS]". linux-kernel (Mailing list).
↑ Tong Li; Dan Baumberger; Scott Hahn. "वितरित भारित राउंड-रॉबिन का उपयोग करके कुशल और स्केलेबल मल्टीप्रोसेसर फेयर शेड्यूलिंग" (PDF). Happyli.org. Retrieved 2016-12-09.
↑ ^19.0 ^19.1 "सोलारिस, लिनक्स और फ्रीबीएसडी कर्नेल की तुलना" (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). "Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment". Journal of the ACM. ACM. 20 (1): 46–61. doi:10.1145/321738.321743. S2CID 207669821. We define the response time of a request for a certain task to be the time span between the request and the end of the response to that request.

[kleinrock1976-2] Kleinrock, Leonard (1976). Queueing Systems, Vol. 2: Computer Applications (1 ed.). Wiley-Interscience. p. 171. ISBN 047149111X. For a customer requiring x sec of service, his response time will equal his service time x plus his waiting time.

[feitelson2014-3] Feitelson, Dror G. (2015). Workload Modeling for Computer Systems Performance Evaluation. Cambridge University Press. Section 8.4 (Page 422) in Version 1.03 of the freely available manuscript. ISBN 9781107078239. Retrieved 2015-10-17. if we denote the time that a job waits in the queue by t_w, and the time it actually runs by t_r, then the response time is r = t_w + t_r.

[silberschatz2012-4] Silberschatz, Abraham; Galvin, Peter Baer; Gagne, Greg (2012). Operating System Concepts (9 ed.). Wiley Publishing. p. 187. ISBN 978-0470128725. In an interactive system, turnaround time may not be the best criterion. Often, a process can produce some output fairly early and can continue computing new results while previous results are being output to the user. Thus, another measure is the time from the submission of a request until the first response is produced. This measure, called response time, is the time it takes to start responding, not the time it takes to output the response.

[5] Paul Krzyzanowski (2014-02-19). "Process Scheduling: Who gets to run next?". cs.rutgers.edu. Retrieved 2023-06-19.

[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; Greg Gagne (2013). Operating System Concepts. Vol. 9. John Wiley & Sons, Inc. ISBN 978-1-118-06333-0.

[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] "Windows Administration: Inside the Windows Vista Kernel: Part 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 "Technical Note TN2028: Threading Architectures". 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). "[patch] Modular Scheduler Core and Completely Fair Scheduler [CFS]". 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 "सोलारिस, लिनक्स और फ्रीबीएसडी कर्नेल की तुलना" (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