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

Completely Fair Scheduler

Original author(s)	Ingo Molnár
Developer(s)	Linux kernel developers
Written in	C
Operating system	Linux kernel
Type	process scheduler
License	GPL-2.0
Website	kernel.org

लिनक्स कर्नेल की सरलीकृत संरचना में पूरी तरह से उचित शेड्यूलर (एक प्रक्रिया शेड्यूलर) का स्थान।

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

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

कलन विधि

एक कार्य (यानी, थ्रेड का पर्यायवाची न्यूनतम इकाई है जिसे लिनक्स शेड्यूल कर सकता है। हालाँकि, यह थ्रेड्स के समूहों, संपूर्ण मल्टी-थ्रेडेड प्रक्रियाओं और यहां तक ​​कि किसी दिए गए उपयोगकर्ता की सभी प्रक्रियाओं को भी प्रबंधित कर सकता है। यह डिज़ाइन शेड्यूल करने योग्य संस्थाओं की अवधारणा की ओर ले जाता है, जहां कार्यों को समग्र रूप से शेड्यूलर द्वारा समूहीकृत और प्रबंधित किया जाता है। इस डिज़ाइन के काम करने के लिए, प्रत्येक task_struct कार्य विवरणक एक प्रकार का फ़ील्ड एम्बेड करता है sched_entity यह उन संस्थाओं के समूह का प्रतिनिधित्व करता है जिनसे कार्य संबंधित है।

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

जब शेड्यूलर को एक नई प्रक्रिया चलाने के लिए लागू किया जाता है:

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

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

एल्गोरिदम की जटिलता जो नोड्स को सम्मिलित करती है cfs_rq सीएफएस शेड्यूलर की रनक्यू ओ (लघुगणक एन) है, जहां एन इकाइयों की कुल संख्या है। चलाने के लिए अगली इकाई का चयन निरंतर समय में किया जाता है क्योंकि सबसे बायां नोड हमेशा कैश्ड होता है।

इतिहास

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

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

2016 में, लिनक्स शेड्यूलर को पेपर, द लिनक्स शेड्यूलर: ए डिकेड ऑफ वेस्टेड कोर में उल्लिखित सुझावों के आधार पर, बेहतर मल्टीकोर प्रदर्शन के लिए पैच किया गया था।

यह भी देखें

• ब्रेन बकवास शेड्यूलर
• SCHED_DEADLINE

बाहरी संबंध

• Corbet, Jonathan (2007-04-17). "Schedulers: The Plot Thickens". LWN.net. Archived from the original on 2017-09-06. Retrieved 2016-07-21.
• Corbet, J. (2007-07-02). "CFS Group Scheduling". LWN.net. Archived from the original on 2017-09-06. Retrieved 2016-07-21.
• Corbet, J. (2007-10-16). "Fair user scheduling and other scheduler patches". LWN.net. Archived from the original on 2017-06-12. Retrieved 2016-11-24.
• Corbet, J. (2010-11-17). "TTY-based group scheduling". LWN.net. Archived from the original on 2018-05-21. Retrieved 2016-11-24.
• Corbet, J. (2010-12-06). "Group scheduling and alternatives". LWN.net. Archived from the original on 2017-06-11. Retrieved 2016-11-24.
• Singh Pabla, Chandandeep (2009-08-01). "Completely Fair Scheduler". linuxjournal.com. Archived from the original on 2018-03-18. Retrieved 2014-11-17.
• Jones, Tim (2009-12-15). "Inside the Linux 2.6 Completely Fair Scheduler". IBM.
• Lozi, Jean-Pierre (2016-04-21). "The Linux Scheduler: a Decade of Wasted Cores" (PDF). ACM. Archived from the original (PDF) on 2018-02-05. Retrieved 2016-11-24.