सीएफएस बनाम ओ (1) अनुसूचक

मुझे लगता है कि कई लोगों ने सुना है कि लिनक्स में मानक हे (1) अनुसूचक के अलावा, सीएफएस (पूरी तरह से निष्पक्ष अनुसूचक; "बिल्कुल निष्पक्ष अनुसूचक") दिखाई दिया, जो इंगो मोलनार काम कर रहा है। वास्तव में, मैं इस नोट को इन दो अनुसूचियों की तुलना और उनके मुख्य एल्गोरिदम की एक संक्षिप्त समीक्षा के लिए समर्पित करना चाहूंगा। नोट के अंत में, आप FreeBSD के ULE शेड्यूलिंग के बारे में थोड़ा पढ़ सकते हैं।



प्रस्तावना:

• O (1) अनुसूचक - संक्षेप में, अनुसूचक नीति काफी सरल थी: प्रत्येक सीपीयू में 2 कतारें थीं: एक में ऐसे कार्य हैं जो जल्द ही लॉन्च होंगे, दूसरे में - सोते हुए कार्य। जब पहला चरण खाली हो गया, तो यह दूसरे स्थान के साथ क्रमशः बदल गया, दूसरे चरण में, सभी नींद की प्रक्रियाएं "जाग" गईं, और पहले में यह थकावट और नींद प्रक्रियाओं के लिए एक कतार के रूप में सेवा की। इसलिए, एल्गोरिथ्म का रनिंग टाइम, सबसे पहले, प्रक्रियाओं की श्रेणी पर निर्भर नहीं करता है, और दूसरी बात, यह निरंतर है - ओ (1)।
• पूरी तरह से निष्पक्ष समयबद्धक - प्रक्रियाओं को संग्रहीत करने के लिए एक लाल-काले पेड़ का उपयोग करता है, जहां कुंजी प्रत्येक प्रक्रिया का प्रतीक्षा_ क्रम है। Wait_runtime नैनोसेकंड की संख्या है जो किसी दिए गए प्रक्रिया में विफल रही है या फिर से काम किया है। यानी यदि यह <0 है, तो यह संसाधित हुआ, यदि यह> 0 है, तो इसे अंडरवर्क किया गया है। यह उपाय आपको 'आदर्श मामले' से आउट-ऑफ-बैलेंस का पता लगाने की अनुमति देता है। Wait_runtime के मूल्य के आधार पर, प्रक्रिया पेड़ में अपना स्थान लेती है। अगर Wait_runtime <0, तो, मेरा मानना ​​है कि, प्रक्रिया निचले स्तरों पर बैठ जाएगी, यदि 0 से अधिक है, तो शीर्ष के करीब है। इसलिए, CFS O (1) शेड्यूलर नहीं है , यह O (logN) है।

टहलना:

किसी ने स्लैशडॉट पर एक लेख देखा होगा कि कैसे bsd के यूएल शेड्यूलर के निर्माता जेफ रॉबर्सन ने सीएफएस पर टिप्पणी की :

कल्पना करें कि आप सैकड़ों या हजारों रनिंग थ्रेड के साथ काम कर रहे हैं, लॉग एन बायपास के मामले में कैश की कमी काफी महंगी हो सकती है। विशेष रूप से इसलिए क्योंकि आपके पास कई थ्रेड्स के साथ अधिक शेड्यूलिंग ईवेंट होंगे

वास्तव में, पेड़ से अगली प्रक्रिया को निकालने के लिए कभी-कभी रिबैलेंसिंग की आवश्यकता होती है, इस प्रक्रिया को पेड़ में डालने के लिए एक एकल पॉलीलाइन और संभव असंतुलन की आवश्यकता होती है। लेकिन यह खामी केवल एक बहुत बड़े एन में ही प्रकट होती है, जो कि डेस्कटॉप पर पाए जाने की बहुत संभावना नहीं है, लेकिन बड़े कार्य स्टेशनों पर पाया जा सकता है। यहां से हम यह निष्कर्ष निकाल सकते हैं: लोडेड सर्वर / वर्क स्टेशन और अन्य मशीनों पर इस अनुसूचक को स्थापित करने के लिए इसके लायक नहीं है जो कि बड़ी संख्या में एक साथ चलने वाली प्रक्रियाओं / थ्रेड्स के साथ काम करने के लिए डिज़ाइन किए गए हैं।



लेकिन यह दोष इस तरह से प्रकट होता है:

इंगो ने कहा कि 1000 रनिंग टास्क (टास्क - प्रोसेस या थ्रेड) होने से सिस्टम 20% तक संदर्भ स्विचिंग ( संदर्भ स्विचिंग ) की लागत में वृद्धि करेगा। यह 10 स्तरों का पेड़ है। सबसे खराब स्थिति में, अन्य 5 स्तरों को जोड़ा जा सकता है, जिससे मूल्य में 30% की वृद्धि होगी। यह घातक नहीं है, लेकिन आपने इसे अच्छा व्यवहार भी नहीं कहा है।

O (1) अनुसूचक के नुकसान को अपर्याप्त रूप से अच्छा, 'निष्पक्ष' कोर रीबैलेंसिंग के लिए जिम्मेदार ठहराया जा सकता है। यहाँ क्या Ingo खुद इस टिप्पणी में कहते हैं:

इसका वर्णन करने का सबसे आसान तरीका एक सरल उदाहरण के साथ है: अगर मैं अपने आप पर glxgears चलाता हूं, तो यह बिल्कुल 50% CPU का उपयोग करेगा। अगर मैं SD अनुसूचक (उर्फ O (1) अनुसूचक) का उपयोग करता हूं और glxgears के साथ उस पर CPU हॉग चलाता हूं, तो दोनों कार्य CPU संसाधनों को साझा करेंगे। सीपीयू हॉग को प्रोसेसर समय का ~ 60%, और ग्लक्सगियर्स को 40% मिलेगा। यदि मैं सीएफएस का उपयोग करता हूं, तो दोनों कार्यों को प्रोसेसर समय का 50% प्राप्त होगा।

सीएफएस वास्तव में बेहतर सीपीयू समय आवंटित करता है और कोर के आसपास कार्यों को अलग करता है (व्यक्तिगत अभ्यास द्वारा सिद्ध)।

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



सीएफएस कैसे लगाएं:



सबसे पहले, CFS संस्करण 2.6.20 से शुरू होने वाली गुठली के लिए उपलब्ध है।

आप कर्नेल संस्करण> = 2.6.20 के लिए पैच प्राप्त कर सकते हैं ।

इसके बाद, लिनक्स स्रोतों के साथ निर्देशिका पर जाएं और पैच लागू करें:

# पैच -p1 <अनुसूची- cfs-v2.6.2x.1-x.patch

इसके अलावा, सीएफएस अनुसूचक के विकास के लिए एक अलग गिट रिपॉजिटरी आवंटित की गई है। आप यहां से रिपॉजिटरी क्लोन खींच सकते हैं ।



ULE के बारे में fw:



प्रत्येक सीपीयू में प्राथमिकता से अनुक्रमित 3 कतारें होती हैं। 2 कतारों का उपयोग शेड्यूलिंग-कक्षाओं को लागू करने के लिए किया जाता है जैसे इंटरप्ट, रियाल टाइम और टाइम शेयरिंग। अंतिम कतार निष्क्रिय वर्ग के लिए उपयोग की जाती है।

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

जेएल के अनुसार, सीपीयू (साइट) के बीच कार्यों को बिखरने से यूएलई एसएमपी सिस्टम पर लचीली और प्रभावी नीतियों का उपयोग करता है, "कम से कम किसी निष्पक्ष निष्पक्ष से कम नहीं"।



ULE के बारे में अधिक जानकारी: ULE.pdf और यहाँ ।



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

आपका ध्यान देने के लिए धन्यवाद।