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

From Vigyanwiki
No edit summary
Line 32: Line 32:




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


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

Revision as of 14:20, 16 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 लाल-काले पेड़ (या लिनक्स भाषा में 'आरबीट्री') में समय-क्रमबद्ध फैशन में संरचनाएं, जहां सबसे बाएं नोड पर उस इकाई का कब्जा होता है जिसे निष्पादन समय का सबसे कम टुकड़ा प्राप्त हुआ है (जो कि में सहेजा गया है) vruntime इकाई का क्षेत्र)। नोड्स को नैनोसेकंड में प्रोसेसर निष्पादन समय द्वारा अनुक्रमित किया जाता है।[3] प्रत्येक प्रक्रिया के लिए अधिकतम निष्पादन समय की गणना भी की जाती है ताकि उस समय का प्रतिनिधित्व किया जा सके जो प्रक्रिया एक आदर्श प्रोसेसर पर चलने की उम्मीद करती है। यह वह समय है जब प्रक्रिया चलने की प्रतीक्षा कर रही है, इसे प्रक्रियाओं की कुल संख्या से विभाजित किया जाता है।

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

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

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

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

इतिहास

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

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

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


यह भी देखें

संदर्भ

  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. ↑ The ~200 Line Linux Kernel Patch That Does Wonders
  7. ↑ 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).
  8. ↑ Galbraith, Mike (2010-11-20). "[PATCH v4] sched: automated per session task groups". linux-kernel (Mailing list).
  9. ↑ 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=228500’