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

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 कुल एंटिटी की कुल संख्या है। अगले एंटिटी को चलाने का चयन स्थाई समय में होता है क्योंकि सबसे बायां नोड सदैव कैश में रखा जाता है।

इतिहास

शेड्यूलिंग के साथ कोलिवास के साथ के काम, सबसे महत्वपूर्ण रूप से घूमने वाली सीढ़ी की समय सीमा नामक फेयर-शेयर शेड्यूलिंग के उनके कार्यान्वयन ने, इंगो मोल्नार को अपने सीएफएस को विकसित करने के लिए प्रेरित किया, जो कि पहले के ओ (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.