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

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, या लिनक्स भाषा में 'rbtree', में sched_entity संरचनाओं को समय-क्रम में क्रमबद्ध रूप से व्यवस्थित करती है, जहां सबसे छोटे संचालन समय के स्लाइस प्राप्त करने वाले संगठन (जो संगठन के vruntime फ़ील्ड में सहेजा जाता है) के द्वारा बाईं ओर का नोड आवर्जित होता है। नोड्स को प्रोसेसर "संचालन समय" के आधार पर नैनोसेकंड में सूचीबद्ध किया जाता है।

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

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

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

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

सीएफएस अनुसूचक के cfs_rqरनक्यू में नोड्स को डालने के कलन-विधि की जटिलता O(log N) होती है, यहाँ N कुल एंटिटी की कुल संख्या है। अगले एंटिटी को चलाने का चयन स्थाई समय में होता है क्योंकि सबसे बायां नोड सदैव कैश में रखा जाता है।

इतिहास

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

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

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

2.6.38 कर्नल के लिए नवम्बर 2010 में सीएफएस के लिए लिनक्स कर्नल को पैच मिला, जिसने स्केड्यूलर को डेस्कटॉप और वर्कस्टेशन के उपयोग के लिए "न्यायसंगत" बना दिया है। माइक गैलब्रेथ द्वारा विकसित और लिनस तोरवाल्ड्स द्वारा सुझाए गए विचारों का उपयोग करते हुए, इस पैच ने "ऑटो-समूहीकरण" नामक एक विशेषता को लागू किया है, जो सक्रिय डेस्कटॉप कार्यक्रम के प्रदर्शन को काफी बढ़ा देती है। इस एल्गोरिदम में माता प्रक्रियाएं बच्चे प्रक्रियाओं के टास्क समूह में डाली जाती हैं।

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

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

यह भी देखें

• ब्रेन बाधा अनुसूचक
• स्केड_डेडलाइन

बाहरी संबंध

• 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.