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

From Vigyanwiki
No edit summary
 
(9 intermediate revisions by 3 users not shown)
Line 27: Line 27:
| website                = {{URL|kernel.org}}
| website                = {{URL|kernel.org}}
}}
}}
[[File:Simplified_Structure_of_the_Linux_Kernel.svg|thumb|लिनक्स कर्नेल की सरलीकृत संरचना में पूरी तरह से उचित शेड्यूलर (एक प्रक्रिया शेड्यूलर) का स्थान।]]पूर्णतः निष्पक्ष अनुसूचक (सीएफएस) एक प्रक्रिया अनुसूचक है जो लिनक्स कर्नल के 2.6.23 (अक्टूबर 2007) के प्रकाशन में विलय कर दिया गया था और <code>SCHED_NORMAL</code> वर्ग के कार्य के लिए स्वतः निर्धारित अनुसूचक है अर्थात ऐसे कार्य जिनके पास कोई वास्तविक समय-चक्र निर्बंधन नहीं होते हैं। यह निष्पादन [[प्रक्रिया (कंप्यूटिंग)|प्रक्रिया]] के लिए केंद्रीय प्रसंस्करण इकाई संसाधन आवंटन को संभालता है, और इसका उद्देश्य पारस्परिक प्रदर्शन को अधिकतम करते हुए समग्र सीपीयू उपयोग को अधिकतम करना है।
[[File:Simplified_Structure_of_the_Linux_Kernel.svg|thumb|लिनक्स कर्नेल की सरलीकृत संरचना में पूरी तरह से उचित अनुसूचक  (एक प्रक्रिया अनुसूचक ) का स्थान।]]पूर्णतः निष्पक्ष अनुसूचक (सीएफएस) एक प्रक्रिया अनुसूचक है जो लिनक्स कर्नल के 2.6.23 (अक्टूबर 2007) के प्रकाशन में विलय कर दिया गया था और <code>SCHED_NORMAL</code> वर्ग के कार्य के लिए स्वतः निर्धारित अनुसूचक है अर्थात ऐसे कार्य जिनके पास कोई वास्तविक समय-चक्र निर्बंधन नहीं होते हैं। यह निष्पादन [[प्रक्रिया (कंप्यूटिंग)|प्रक्रिया]] के लिए केंद्रीय प्रसंस्करण इकाई संसाधन आवंटन को संभालता है, और इसका उद्देश्य पारस्परिक प्रदर्शन को अधिकतम करते हुए समग्र सीपीयू उपयोग को अधिकतम करना है।


पिछले O(1) अनुसूचक के सापेक्ष में, जो पुराने लिनक्स 2.6 कर्नल में उपयोग किया जाता था, जिसमें सक्रिय और समाप्त हुए कार्यों की चलने वाली कतारें रखी जाती थीं और स्विच होती थीं, सीएफएस अनुसूचक अंमलन किसी-सीपीयू चलने वाली कतारों पर आधारित है, जिनके नोड समय-क्रम में व्यवस्थित होते हैं और जिन्हें लाल-काले ट्री द्वारा क्रमबद्ध रखा जाता है। सीएफएस प्रति-प्राथमिकता निर्धारित समय-स्लाइस की पुरानी धारणा को दूर करता है और इसके अतिरिक्त इसका उद्देश्य कार्यों को सीपीयू समय का न्यायसंगत भाग  प्रदान किया जाता है <ref>{{Cite book|last=Love|first=Robert|title=लिनक्स कर्नेल विकास|publisher=Addison Wesley|year=2010|isbn=9780672329463|edition=3rd|location=United States of America|pages=41–61}}</ref><ref>{{Cite web|date=2007-04-19|title=Linux: The Completely Fair Scheduler {{!}} KernelTrap|url=http://kerneltrap.org/node/8059|access-date=2021-05-16|archive-url=https://web.archive.org/web/20070419102054/http://kerneltrap.org/node/8059|archive-date=2007-04-19}}</ref>
पिछले O(1) अनुसूचक के सापेक्ष में, जो पुराने लिनक्स 2.6 कर्नल में उपयोग किया जाता था, जिसमें सक्रिय और समाप्त हुए कार्यों की चलने वाली कतारें रखी जाती थीं और स्विच होती थीं, सीएफएस अनुसूचक अंमलन किसी-सीपीयू चलने वाली कतारों पर आधारित है, जिनके नोड समय-क्रम में व्यवस्थित होते हैं और जिन्हें लाल-काले ट्री द्वारा क्रमबद्ध रखा जाता है। सीएफएस प्रति-प्राथमिकता निर्धारित समय-स्लाइस की पुरानी धारणा को दूर करता है और इसके अतिरिक्त इसका उद्देश्य कार्यों को सीपीयू समय का न्यायसंगत भाग  प्रदान किया जाता है <ref>{{Cite book|last=Love|first=Robert|title=लिनक्स कर्नेल विकास|publisher=Addison Wesley|year=2010|isbn=9780672329463|edition=3rd|location=United States of America|pages=41–61}}</ref><ref>{{Cite web|date=2007-04-19|title=Linux: The Completely Fair Scheduler {{!}} KernelTrap|url=http://kerneltrap.org/node/8059|access-date=2021-05-16|archive-url=https://web.archive.org/web/20070419102054/http://kerneltrap.org/node/8059|archive-date=2007-04-19}}</ref>
Line 34: Line 34:
==कलन विधि==
==कलन विधि==


एक कार्य (अर्थात एक थ्रेड के समानार्थी) वह सबसे न्यूनतम इकाई है जिसे लिनक्स कार्यक्रमित कर सकता है। यद्यपि, यह समूहों के थ्रेड, पूरे मल्टी-थ्रेडेड प्रक्रियाओं, और एक निर्दिष्ट उपयोगकर्ता के सभी प्रक्रियाओं का प्रबंधन भी कर सकता है। यह डिज़ाइन शेड्यूल करने योग्य संस्थाओं की अवधारणा की ओर ले जाता है, जहां कार्यों को समग्र रूप से शेड्यूलर द्वारा समूहीकृत और प्रबंधित किया जाता है। इस डिजाइन को काम करने के लिए, प्रत्येक <code>task_struct</code> कार्य विवरणक में एक <code>sched_entity</code> प्रकार का फ़ील्ड सम्मिश्रित होता है, जो उन संस्थाओं के समूह का प्रतिनिधित्व करता है जिनसे कार्य संबंधित है।
एक टास्क वह सबसे न्यूनतम इकाई है जिसे लिनक्स कार्यक्रमित कर सकता है। यद्यपि, यह थ्रेड्स के समूहों, संपूर्ण मल्टी-थ्रेडेड प्रक्रियाओं और यहां तक ​​कि किसी दिए गए उपयोगकर्ता की सभी प्रक्रियाओं को भी प्रबंधित कर सकता है यह आरेखित योजना करने योग्य संस्थाओं की अवधारणा की ओर ले जाता है, जहां कार्यों को संपूर्ण रूप से अनुसूचक  द्वारा समूहीकृत और प्रबंधित किया जाता है इस आरेख को काम करने के लिए, प्रत्येक <code>task_struct</code> कार्य विवरणक में एक <code>sched_entity</code> प्रकार का क्षेत्र सम्मिलित होता है, जो उन संस्थाओं के समूह का प्रतिनिधित्व करता है जिनसे टास्क संबंधित है।
 
प्रति-सीपीयू चलने वाले कतार  <code>cfs_rq</code>  प्रकार या लिनक्स भाषा 'आरबीट्री', में  <code>sched_entity</code>संरचनाओं को समय-क्रम  में क्रमबद्ध रूप से व्यवस्थित करती है, जहां सबसे छोटे संचालन समय के स्लाइस प्राप्त करने वाले संगठन के द्वारा बाईं ओर का नोड आवर्जित होता है। नोड्स को प्रोसेसर "संचालन समय" के आधार पर नैनोसेकंड में सूचीबद्ध किया जाता है।<ref>[https://developer.ibm.com/tutorials/l-completely-fair-scheduler/ CFS description at ibm.com]</ref>
 
प्रत्येक प्रक्रिया के लिए एक "अधिकतम संचालन समय" का गणना किया जाता है जो प्रक्रिया के प्रत्याशित समय का प्रतिनिधित करता है जब प्रक्रिया को एक "आदर्श प्रोसेसर" पर चलाने की उम्मीद रखी जाती है तो यह प्रक्रिया जो चलाने के लिए प्रतीक्षा कर रही है, इसे प्रक्रियाओं की कुल संख्या से विभाजित किया जाता है।
 
जब अनुसूचक को एक नई प्रक्रिया चलाने के लिए लागू किया जाता है:
# अनुसूचीकरण ट्री का सबसे बायां नोड चुना जाता है, और निष्पादन के लिए भेजा जाता है।
# यदि प्रक्रिया सरलता से पूर्ण हो जाती है, तो वह सिस्टम और अनुसूचीकरण ट्री से हटा दी जाती है।
# यदि प्रक्रिया अपने अधिकतम निष्पादन समय तक पहुंच जाती है या रोक दी जाती है तो इसे इसके नए खर्च किए गए निष्पादन समय के आधार पर अनुसूचीकरण ट्री में पुन: सम्मिलित कर दिया जाता है।
# पुनः पुनरावृत्ति को दोहराते हुए, ट्री से सबसे बाईं ओर का नया नोड चुना जाएगा।
 
यदि प्रक्रिया अपना बहुत सारा समय सोने में बिताती है, तो उसके व्यतीत किए गए समय का मूल्य कम होता है और अंततः जब उसे इसकी आवश्यकता होती है तो उसे स्वचालित रूप से प्राथमिकता में वृद्धि मिलती है। इसलिए ऐसे कार्यों को लगातार चलने वाले कार्यों की तुलना में कम प्रोसेसर समय नहीं मिलता हैI
 
सीएफएस अनुसूचक के <code>cfs_rq</code>रनक्यू में नोड्स को डालने के कलन-विधि की जटिलता O(log N) होती है, यहाँ N कुल एंटिटी  की कुल संख्या है। अगले एंटिटी को चलाने का चयन स्थाई समय में होता है क्योंकि सबसे बायां नोड सदैव कैश में रखा जाता है।
 
 
 
 
 
 


प्रति-सीपीयू चलने वाले कतार प्रकार cfs_rq, या लिनक्स भाषा में 'rbtree', में sched_entity संरचनाओं को समय-क्रम में क्रमबद्ध रूप से व्यवस्थित करती है, जहां सबसे छोटे संचालन समय के स्लाइस प्राप्त करने वाले संगठन (जो संगठन के vruntime फ़ील्ड में सहेजा जाता है) के द्वारा बाईं ओर का नोड आवर्जित होता है। नोड्स को प्रोसेसर "संचालन समय" के आधार पर नैनोसेकंड में सूचीबद्ध किया जाता है।<ref>[https://developer.ibm.com/tutorials/l-completely-fair-scheduler/ CFS description at ibm.com]</ref>


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


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


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


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


== इतिहास ==
== इतिहास ==
शेड्यूलिंग के साथ [[ कोलिवास के साथ ]] के काम, सबसे महत्वपूर्ण रूप से [[ घूमने वाली सीढ़ी की समय सीमा ]] नामक [[फेयर-शेयर शेड्यूलिंग]] के उनके कार्यान्वयन ने, इंगो मोल्नार को अपने सीएफएस को विकसित करने के लिए प्रेरित किया, जो कि पहले के ओ (1) शेड्यूलर के प्रतिस्थापन के रूप में था, उन्होंने अपनी घोषणा में कोलिवास को श्रेय दिया।<ref>{{cite mailing list  
अनुसूचीकरण के साथ [[ कोलिवास के साथ |कोलिवास]] का काम, सबसे अधिक महत्वपूर्ण रूप से उनके "न्यायसंगत अनुसूचीकरण" के अनुरूप "रोटेटिंग स्टेयरकेस डेडलाइन" के नाम से उनके अंदर प्रयोग, इंगो मोल्नार को उत्साहित किया और उन्होंने अपने सीएफएस के विकास के लिए नई O(1) अनुसूचीकरण की जगह, अपने घोषणा में कोलिवास को श्रेय दिया।<ref>{{cite mailing list  
       | last=Molnár
       | last=Molnár
       | first=Ingo
       | first=Ingo
Line 59: Line 70:
       | mailing-list=linux-kernel
       | mailing-list=linux-kernel
       | date=2007-04-13}}</ref>
       | date=2007-04-13}}</ref>
सीएफएस एक अच्छी तरह से अध्ययन किए गए, क्लासिक शेड्यूलिंग एल्गोरिदम का कार्यान्वयन है जिसे [[ भारित निष्पक्ष कतार ]] कहा जाता है।<ref name="dwrr">{{Cite journal | last1 = Li | first1 = T. | last2 = Baumberger | first2 = D. | last3 = Hahn | first3 = S. | doi = 10.1145/1594835.1504188 | title = वितरित भारित राउंड-रॉबिन का उपयोग करके कुशल और स्केलेबल मल्टीप्रोसेसर फेयर शेड्यूलिंग| journal = ACM SIGPLAN Notices | volume = 44 | issue = 4 | pages = 65 | year = 2009 | url = http://happyli.org/tongli/papers/dwrr.pdf | citeseerx = 10.1.1.567.2170 }}</ref> मूल रूप से [[पैकेट नेटवर्क]] के लिए आविष्कार किया गया, फेयर क्यूइंग को पहले [[स्ट्राइड शेड्यूलिंग]] नाम के तहत सीपीयू शेड्यूलिंग पर लागू किया गया था। सीएफएस सामान्य प्रयोजन ऑपरेटिंग सिस्टम में व्यापक रूप से उपयोग किए जाने वाले निष्पक्ष कतार प्रक्रिया अनुसूचक का पहला कार्यान्वयन है।<ref name="dwrr"/>


लिनक्स कर्नेल को नवंबर 2010 में 2.6.38 कर्नेल के लिए सीएफएस के लिए एक पैच प्राप्त हुआ जिसने शेड्यूलर को डेस्कटॉप और वर्कस्टेशन पर उपयोग के लिए बेहतर बना दिया है। [[लिनस टोरवाल्ड्स]] द्वारा सुझाए गए विचारों का उपयोग करके माइक गैलब्रेथ द्वारा विकसित, पैच ऑटो-ग्रुपिंग नामक एक सुविधा को लागू करता है जो इंटरैक्टिव डेस्कटॉप प्रदर्शन को महत्वपूर्ण रूप से बढ़ाता है।<ref>[https://www.phoronix.com/scan.php?page=article&item=linux_2637_video&num=1 The ~200 Line Linux Kernel Patch That Does Wonders]</ref> एल्गोरिदम मूल प्रक्रियाओं को चाइल्ड प्रक्रियाओं के समान कार्य समूह में रखता है।<ref>{{cite mailing list  
सीएफएस एक अच्छी तरह से अध्ययन किए गए, पारंपरिक अनुसूचीकरण कलन-विधि  का कार्यान्वयन है जिसे [[ भारित निष्पक्ष कतार | भारित निष्पक्ष कतार]] कहा जाता है।<ref name="dwrr">{{Cite journal | last1 = Li | first1 = T. | last2 = Baumberger | first2 = D. | last3 = Hahn | first3 = S. | doi = 10.1145/1594835.1504188 | title = वितरित भारित राउंड-रॉबिन का उपयोग करके कुशल और स्केलेबल मल्टीप्रोसेसर फेयर शेड्यूलिंग| journal = ACM SIGPLAN Notices | volume = 44 | issue = 4 | pages = 65 | year = 2009 | url = http://happyli.org/tongli/papers/dwrr.pdf | citeseerx = 10.1.1.567.2170 }}</ref> मूल रूप से [[पैकेट नेटवर्क]] के लिए आविष्कार किया गया, फेयर क्यूइंग को पहले [[स्ट्राइड शेड्यूलिंग|स्ट्राइड]] अनुसूचीकरण नाम के तहत सीपीयू अनुसूचीकरण पर लागू किया गया था। सीएफएस सामान्य प्रयोजन ऑपरेटिंग सिस्टम में व्यापक रूप से उपयोग किए जाने वाले निष्पक्ष कतार प्रक्रिया अनुसूचक का पहला कार्यान्वयन है।<ref name="dwrr" />
 
सीएफएस एक प्रसिद्ध, विश्लेषित और पारंपरिक अनुसूचीकरण कलन-विधि का प्रयोग करने का एक अनुमानित भाग है,भारित निष्पक्ष पंक्तियन कहा जाता है। पहले पैकेट नेटवर्क्स के लिए आविष्कृत किया गया, न्यायसंगत क्यूइंग को पहले ही सीपीयू अनुसूचीकरण में प्रगति अनुसूचीकरण के नाम से लागू किया जा चुका था। सीएफएस एक न्यायसंगत क्यूइंग प्रक्रिया अनुसूचक का पहला अम्लित अनुप्रयोग है, जो एक सामान्य उद्देश्य वाले ऑपरेटिंग सिस्टम में व्यापक रूप से प्रयोग किया जाता है।
 
2.6.38 कर्नल के लिए नवम्बर 2010 में सीएफएस के लिए लिनक्स कर्नल को पैच मिला, जिसने स्केड्यूलर को डेस्कटॉप और वर्कस्टेशन के उपयोग के लिए "न्यायसंगत" बना दिया है। माइक गैलब्रेथ द्वारा विकसित और लिनस तोरवाल्ड्स द्वारा सुझाए गए विचारों का उपयोग करते हुए, इस पैच ने "ऑटो-समूहीकरण" नामक एक विशेषता को लागू किया है, जो सक्रिय डेस्कटॉप कार्यक्रम के प्रदर्शन को काफी बढ़ा देती है। इस एल्गोरिदम में माता प्रक्रियाएं बच्चे प्रक्रियाओं के टास्क समूह में डाली जाती हैं।<ref>{{cite mailing list  
       | last=Galbraith
       | last=Galbraith
       | first=Mike
       | first=Mike
Line 69: Line 83:
       | mailing-list=linux-kernel
       | mailing-list=linux-kernel
       | date=2010-11-15}}</ref>
       | date=2010-11-15}}</ref>
(कार्य समूह [http://man7.org/linux/man-pages/man2/setsid.2.html के माध्यम से बनाए गए सत्रों से जुड़े हुए हैं <code>setsid()</code>] सिस्टम कॉल।<ref>{{cite mailing list  
 
टास्क समूह सेटिंग के लिए,  [http://man7.org/linux/man-pages/man2/setsid.2.html <code>setsid()</code>] सिस्टम कॉल के माध्यम से बनाए गए सत्रों से जुड़े होते हैं<ref>{{cite mailing list  
       | last=Galbraith
       | last=Galbraith
       | first=Mike
       | first=Mike
Line 76: Line 91:
       | url=http://marc.info/?l=linux-kernel&m=129028174609578
       | url=http://marc.info/?l=linux-kernel&m=129028174609578
       | mailing-list=linux-kernel
       | mailing-list=linux-kernel
       | date=2010-11-20}}</ref>)
       | date=2010-11-20}}</ref> यह समस्या को हल करता है कि मल्टी-कोर और मल्टी-सीपीयू (एसएमपी) सिस्टम्स पर धीमे संवादात्मक प्रतिक्रिया समय होता था जब वे उन कार्यों को कर रहे थे जिनमें उन कार्यों के कई सीपीयू-प्रमुख धाराएँ प्रयोग कर रही थीं। एक सरल स्पष्टीकरण यह है कि इस पैच का उपयोग करके, हम किसी वीडियो को देखने, ईमेल पढ़ने और लिनक्स कर्नेल या एन्कोडिंग वीडियो को संकलित करते समय बिना किसी कमी या बाधा के अन्य सामान्य डेस्कटॉप गतिविधियाँ कर सकता है।
इससे मल्टी-कोर और मल्टी-सीपीयू ([[ सममित मल्टीप्रोसेसिंग ]]) सिस्टम पर धीमी इंटरैक्टिव प्रतिक्रिया समय की समस्या हल हो गई जब वे अन्य कार्य कर रहे थे जो उन कार्यों में कई सीपीयू-गहन थ्रेड का उपयोग करते थे। एक सरल व्याख्या यह है कि, इस पैच को लागू करने के साथ, कोई व्यक्ति अभी भी एक वीडियो देख सकता है, ईमेल पढ़ सकता है और लिनक्स कर्नेल या एन्कोडिंग वीडियो को संकलित करते समय बिना किसी गड़बड़ी या गड़बड़ी के अन्य सामान्य डेस्कटॉप गतिविधियाँ कर सकता है।
 
2016 में, लिनक्स शेड्यूलर को पेपर, द लिनक्स शेड्यूलर: ए डिकेड ऑफ वेस्टेड कोर में उल्लिखित सुझावों के आधार पर, बेहतर मल्टीकोर प्रदर्शन के लिए पैच किया गया था।<ref>{{cite web |last1=Lozi |first1=Jean-Pierre |last2=Lepers |first2=Baptiste |last3=Funston |first3=Justin |last4=Gaud |first4=Fabien |last5=Quema |first5=Vivian |last6=Fedorova |first6=Alexandra |title=The Linux Scheduler: A Decade of Wasted Cores |url=http://www.ece.ubc.ca/~sasha/papers/eurosys16-final29.pdf |publisher=EuroSys 2016 |access-date=15 June 2019}}</ref>
 


2016 में, लिनक्स अनुसूचक को उत्तम मल्टीकोर प्रदर्शन के लिए पैच किया गया था,<ref>{{cite web |last1=Lozi |first1=Jean-Pierre |last2=Lepers |first2=Baptiste |last3=Funston |first3=Justin |last4=Gaud |first4=Fabien |last5=Quema |first5=Vivian |last6=Fedorova |first6=Alexandra |title=The Linux Scheduler: A Decade of Wasted Cores |url=http://www.ece.ubc.ca/~sasha/papers/eurosys16-final29.pdf |publisher=EuroSys 2016 |access-date=15 June 2019}}</ref> जो विज्ञान पत्र "द लिनक्स अनुसूचक: व्यर्थ कोर का दशक" में उल्लेखित सुझावों पर आधारित था।
==यह भी देखें==
==यह भी देखें==
* [[ब्रेन बकवास शेड्यूलर]]
* [[ब्रेन बकवास शेड्यूलर|ब्रेन बाधा अनुसूचक]]
* SCHED_DEADLINE
* स्केड_डेडलाइन


==संदर्भ==
==संदर्भ==
Line 101: Line 113:


{{Linux kernel}}
{{Linux kernel}}
[[Category: लिनक्स कर्नेल प्रक्रिया अनुसूचक]] [[Category: मुफ्त सॉफ्टवेयर]]


[[Category: Machine Translated Page]]
[[Category:Collapse templates]]
[[Category:Created On 10/07/2023]]
[[Category:Created On 10/07/2023]]
[[Category:Machine Translated Page]]
[[Category:Navigational boxes| ]]
[[Category:Navigational boxes without horizontal lists]]
[[Category:Pages with empty portal template]]
[[Category:Pages with script errors]]
[[Category:Portal-inline template with redlinked portals]]
[[Category:Sidebars with styles needing conversion]]
[[Category:Template documentation pages|Documentation/doc]]
[[Category:Templates Vigyan Ready]]
[[Category:Templates generating microformats]]
[[Category:Templates that are not mobile friendly]]
[[Category:Templates using TemplateData]]
[[Category:Wikipedia metatemplates]]
[[Category:मुफ्त सॉफ्टवेयर]]
[[Category:लिनक्स कर्नेल प्रक्रिया अनुसूचक]]

Latest revision as of 12:51, 28 July 2023

Completely Fair Scheduler
Original author(s)Ingo Molnár
Developer(s)Linux kernel developers
Written inC
Operating systemLinux kernel
Typeprocess scheduler
LicenseGPL-2.0
Websitekernel.org
लिनक्स कर्नेल की सरलीकृत संरचना में पूरी तरह से उचित अनुसूचक (एक प्रक्रिया अनुसूचक ) का स्थान।

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

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


कलन विधि

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

प्रति-सीपीयू चलने वाले कतार cfs_rq प्रकार या लिनक्स भाषा 'आरबीट्री', में sched_entityसंरचनाओं को समय-क्रम में क्रमबद्ध रूप से व्यवस्थित करती है, जहां सबसे छोटे संचालन समय के स्लाइस प्राप्त करने वाले संगठन के द्वारा बाईं ओर का नोड आवर्जित होता है। नोड्स को प्रोसेसर "संचालन समय" के आधार पर नैनोसेकंड में सूचीबद्ध किया जाता है।[3]

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

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

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

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

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







इतिहास

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

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

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

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

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

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

यह भी देखें

संदर्भ

  1. ↑ Love, Robert (2010). लिनक्स कर्नेल विकास (3rd ed.). United States of America: Addison Wesley. pp. 41–61. ISBN 9780672329463.
  2. ↑ "Linux: The Completely Fair Scheduler | KernelTrap". 2007-04-19. Archived from the original on 2007-04-19. Retrieved 2021-05-16.
  3. ↑ CFS description at ibm.com
  4. ↑ Molnár, Ingo (2007-04-13). "[patch] Modular Scheduler Core and Completely Fair Scheduler [CFS]". linux-kernel (Mailing list).
  5. ↑ 5.0 5.1 Li, T.; Baumberger, D.; Hahn, S. (2009). "वितरित भारित राउंड-रॉबिन का उपयोग करके कुशल और स्केलेबल मल्टीप्रोसेसर फेयर शेड्यूलिंग" (PDF). ACM SIGPLAN Notices. 44 (4): 65. CiteSeerX 10.1.1.567.2170. doi:10.1145/1594835.1504188.
  6. ↑ Galbraith, Mike (2010-11-15). "[RFC/RFT PATCH v3] Re: [RFC/RFT PATCH v3] sched: automated per tty task groups [CFS]". linux-kernel (Mailing list).
  7. ↑ Galbraith, Mike (2010-11-20). "[PATCH v4] sched: automated per session task groups". linux-kernel (Mailing list).
  8. ↑ Lozi, Jean-Pierre; Lepers, Baptiste; Funston, Justin; Gaud, Fabien; Quema, Vivian; Fedorova, Alexandra. "The Linux Scheduler: A Decade of Wasted Cores" (PDF). EuroSys 2016. Retrieved 15 June 2019.


बाहरी संबंध

Retrieved from ‘https://www.vigyanwiki.in/index.php?title=पूर्णतया_निष्पक्ष_अनुसूचक&oldid=229184’