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

एक नए योजनाकार पर काम करने की तैयारी करते हुए, मैंने विषयगत संसाधनों की खोज में समय बिताया। वास्तविक कार्यान्वयन के अलावा, कुछ विशेष नहीं मिला। मैंने यह भी पाया कि मौजूदा कार्यान्वयन के लिए स्रोत कोड नेविगेट करना मुश्किल है। इसे ठीक करने के लिए, हमने टोकियो शेड्यूलर को यथासंभव सफाई से लिखने की कोशिश की। मुझे उम्मीद है कि अनुसूचक के कार्यान्वयन पर यह विस्तृत लेख उन लोगों की मदद करेगा जो इस स्थिति में हैं और इस विषय पर जानकारी की असफल तलाश कर रहे हैं।

लेख डिजाइन की उच्च-स्तरीय समीक्षा के साथ शुरू होता है, जिसमें नौकरी पर कब्जा नीतियां भी शामिल हैं। फिर नए Tokio अनुसूचक में विशिष्ट अनुकूलन के विवरण में गोता लगाएँ।

माना अनुकूलन:

• नई एसटीडी :: भविष्य की कार्य प्रणाली
  
• सबसे अच्छा कतार एल्गोरिदम चुनना
  
• संदेश टेम्पलेट
  
• थ्रोटल कैप्चर
  
• थ्रेड्स के बीच सिंक्रनाइज़ेशन कम करें
  
• मेमोरी आवंटन कम करें
  
• परमाणु लिंक की गिनती में कमी

जैसा कि आप देख सकते हैं, मुख्य विषय "कमी" है। आखिरकार, सबसे तेज़ कोड इसकी कमी है!

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

विषय में गोता लगाने से पहले, मैं धन्यवाद देना चाहता हूं:

• @withoutboats और अन्य जो Rust में async / await कार्य पर काम करते थे। आपने बहुत अच्छा काम किया। यह एक किलर फीचर है।
  
• @ cramertj और अन्य जिन्होंने std::task विकसित किया है। यह पहले जो था उस पर बहुत बड़ा सुधार है। और महान कोड।
  
• Buoyant , Linkerd के निर्माता , और इससे भी महत्वपूर्ण बात, मेरे नियोक्ता। मुझे इस काम पर इतना समय देने के लिए धन्यवाद। यदि किसी को सेवा जाल में रुचि है, तो Linkerd पर एक नज़र डालें। जल्द ही इसमें इस लेख में चर्चा किए गए सभी लाभ शामिल होंगे।
  
• ऐसे अच्छे योजनाकार कार्यान्वयन के लिए जाएं ।

एक कप कॉफी लें और वापस बैठें। यह एक लंबा लेख होगा।

योजनाकार कैसे काम करते हैं?

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

आलेख उपयोगकर्ता अंतरिक्ष अनुसूचियों पर चर्चा करता है, अर्थात्, ऑपरेटिंग सिस्टम थ्रेड्स के शीर्ष पर काम कर रहा है (जो बदले में, कर्नेल स्तर शेड्यूलर द्वारा नियंत्रित किया जाता है)। टोकियो शेड्यूलर रस्ट फ्यूचर्स को निष्पादित करता है, जिसे "अतुल्यकालिक हरे धागे" के रूप में सोचा जा सकता है। यह एक M: N मिश्रित स्ट्रीमिंग पैटर्न है जिसमें कई उपयोगकर्ता इंटरफ़ेस कार्य ऑपरेटिंग सिस्टम के कई थ्रेड्स पर बहुसंकेतित होते हैं।

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

 while let Some(task) = self.queue.pop() { task.run(); } 

जब कोई कार्य संभव हो जाता है, तो इसे निष्पादन कतार में डाला जाता है।



यद्यपि आप एक ऐसी प्रणाली को डिज़ाइन कर सकते हैं जिसमें संसाधन, कार्य और एक प्रोसेसर एक ही धागे पर मौजूद होते हैं, टोकियो कई थ्रेड्स का उपयोग करना पसंद करता है। हम एक ऐसी दुनिया में रहते हैं जहां एक कंप्यूटर में कई प्रोसेसर होते हैं। एकल-थ्रेडेड शेड्यूलर के विकास से लोहे की अपर्याप्त लोडिंग हो जाएगी। हम सभी CPU का उपयोग करना चाहते हैं। ऐसा करने के कई तरीके हैं:

• एक वैश्विक निष्पादन कतार, कई प्रोसेसर।
  
• कई प्रोसेसर, प्रत्येक अपनी स्वयं की रन कतार के साथ।

एक बारी, कई प्रोसेसर

इस मॉडल की एक वैश्विक निष्पादन कतार है। जब कार्य पूर्ण हो जाते हैं, तो उन्हें कतार की पूंछ पर रखा जाता है। कई प्रोसेसर हैं, प्रत्येक एक अलग धागे में। प्रत्येक प्रोसेसर कतार के सिर से एक कार्य लेता है या यदि कोई कार्य उपलब्ध नहीं है तो थ्रेड को ब्लॉक करता है।



निष्पादन लाइन को कई निर्माताओं और उपभोक्ताओं द्वारा समर्थित होना चाहिए। आमतौर पर एक घुसपैठ सूची का उपयोग किया जाता है, जिसमें प्रत्येक कार्य की संरचना में कतार में अगले कार्य के लिए एक संकेतक शामिल होता है (लिंक की गई सूची में कार्यों को लपेटने के बजाय)। इस प्रकार, पुश और पॉप ऑपरेशन के लिए मेमोरी आवंटन से बचा जा सकता है। आप लॉकिंग के बिना पुश ऑपरेशन का उपयोग कर सकते हैं, लेकिन उपभोक्ताओं को समन्वयित करने के लिए, पॉप ऑपरेशन के लिए म्यूटेक्स की आवश्यकता होती है (लॉकिंग के बिना बहु-उपयोगकर्ता कतार को लागू करना तकनीकी रूप से संभव है)।

हालांकि, व्यवहार में, ताले के खिलाफ उचित सुरक्षा के लिए ओवरहेड केवल म्यूटेक्स का उपयोग करने से अधिक है।

इस दृष्टिकोण का उपयोग अक्सर सामान्य प्रयोजन थ्रेड पूल के लिए किया जाता है, क्योंकि इसके कई फायदे हैं:

• कार्य काफी नियोजित हैं।
  
• अपेक्षाकृत सरल कार्यान्वयन। अधिक या कम मानक कतार ऊपर वर्णित प्रोसेसर चक्र के साथ हस्तक्षेप करती है।

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

इस मॉडल में एक नकारात्मक पहलू है। सभी प्रोसेसर कतार के प्रमुख से कार्यों के लिए आवेदन करते हैं। सामान्य प्रयोजन के धागे के लिए, यह आमतौर पर कोई समस्या नहीं है। किसी कार्य को पूरा करने का समय कतार से इसे पुनः प्राप्त करने का समय पार कर जाता है। जब कार्यों को लंबे समय तक किया जाता है, तो कतार में प्रतिस्पर्धा कम हो जाती है। हालांकि, अतुल्यकालिक जंग कार्यों को बहुत जल्दी पूरा करने की उम्मीद है। इस मामले में, कतार में लड़ाई के लिए ओवरहेड की लागत में काफी वृद्धि होती है।

संगामिति और यांत्रिक सहानुभूति

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

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

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

निष्कर्ष स्पष्ट है: जहां तक ​​संभव हो, थ्रेड्स के बीच सिंक्रनाइज़ेशन से बचें, क्योंकि यह धीमा है।

कई प्रोसेसर, प्रत्येक अपने स्वयं के निष्पादन कतार के साथ

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



यह रणनीति Seastar का उपयोग करती है। चूंकि हम लगभग पूरी तरह से सिंक्रनाइज़ेशन से बचते हैं, यह रणनीति बहुत अच्छी गति देती है। लेकिन वह सभी समस्याओं का समाधान नहीं करती है। यदि कार्यभार पूरी तरह से सजातीय नहीं है, तो कुछ प्रोसेसर लोड के अधीन हैं, जबकि अन्य निष्क्रिय हैं, जो संसाधनों का इष्टतम उपयोग नहीं करता है। ऐसा इसलिए होता है क्योंकि एक विशिष्ट प्रोसेसर पर कार्य निर्धारित होते हैं। जब एक प्रोसेसर पर एक पैकेज में कार्यों के एक समूह की योजना बनाई जाती है, तो यह एकल-हाथ से पीक लोड को पूरा करता है, भले ही अन्य बेकार हो।

अधिकांश "वास्तविक" वर्कलोड सजातीय नहीं हैं। इसलिए, सामान्य उद्देश्य नियोजक आमतौर पर इस मॉडल को दूर करते हैं।

जॉब कैप्चर शेड्यूलर

काम चुराने वाले अनुसूचियों के साथ अनुसूचक शार्ल्ड शेड्यूलर मॉडल पर आधारित है और हार्डवेयर संसाधनों के अधूरे लोडिंग की समस्या को हल करता है। प्रत्येक प्रोसेसर अपनी स्वयं की निष्पादन कतार का समर्थन करता है। जो कार्य निष्पादित हो जाते हैं, उन्हें वर्तमान प्रोसेसर की निष्पादन कतार में रखा जाता है, और यह उस पर काम करता है। लेकिन जब प्रोसेसर निष्क्रिय होता है, तो यह बहन प्रोसेसर की कतारों की जांच करता है और वहां से कुछ हड़पने की कोशिश करता है। पीयर-टू-पीयर निष्पादन कतारों से काम नहीं मिलने के बाद ही प्रोसेसर स्लीप मोड में चला जाता है।



मॉडल स्तर पर, यह "दोनों दुनिया के सर्वश्रेष्ठ" दृष्टिकोण है। लोड के तहत, प्रोसेसर स्वतंत्र रूप से काम करते हैं, ओवरहेड सिंक्रनाइज़ेशन से बचते हैं। ऐसे मामलों में जहां प्रोसेसर के बीच लोड असमान रूप से वितरित किया जाता है, शेड्यूलर इसे पुनर्वितरित कर सकता है। यही कारण है कि इस तरह के शेड्यूलर्स का उपयोग गो , एर्लांग , जावा और अन्य भाषाओं में किया जाता है।

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

इस स्थिति पर विचार करें: प्रोसेसर ए वर्तमान में एक कार्य निष्पादित कर रहा है, और इसकी एक खाली निष्पादन कतार है। प्रोसेसर बी बेकार है; वह कुछ कार्य करने की कोशिश करता है, लेकिन वह असफल हो जाता है, इसलिए वह स्लीप मोड में चला जाता है। तब प्रोसेसर ए के कार्य से 20 कार्य किए जाते हैं। आदर्श रूप से, प्रोसेसर बी को जागना चाहिए और उनमें से कुछ को पकड़ना चाहिए। इसके लिए, शेड्यूलर में कुछ हेयूरिस्टिक्स को लागू करना आवश्यक है, जहां प्रोसेसर अपनी कतार में नए कार्यों की उपस्थिति के बारे में सोअर पीयर प्रोसेसर को संकेत देते हैं। बेशक, इसके लिए अतिरिक्त सिंक्रनाइज़ेशन की आवश्यकता होती है, इसलिए इस तरह के ऑपरेशन को कम से कम किया जाता है।

संक्षेप में:

• कम सिंक्रनाइज़ेशन, बेहतर।
  
• नौकरी पर कब्जा सामान्य उद्देश्य योजनाकारों के लिए इष्टतम एल्गोरिथ्म है।
  
• प्रत्येक प्रोसेसर दूसरों के स्वतंत्र रूप से काम करता है, लेकिन काम को पकड़ने के लिए कुछ सिंक्रनाइज़ेशन की आवश्यकता होती है।

टोकियो 0.1 समयबद्धक

टोकियो के लिए पहला काम करने वाला शेड्यूल मार्च 2018 में जारी किया गया था। कुछ मान्यताओं के आधार पर यह पहला प्रयास था, जो गलत निकला।

सबसे पहले, टोकियो 0.1 अनुसूचक ने सुझाव दिया कि प्रोसेसर थ्रेड्स को बंद कर दिया जाना चाहिए अगर वे एक निश्चित समय के लिए निष्क्रिय थे। शेड्यूलर मूल रूप से रस्ट थ्रेड पूल के लिए "सामान्य उद्देश्य" प्रणाली के रूप में बनाया गया था। उस समय, टोकियो रनटाइम अभी भी विकास के प्रारंभिक चरण में था। तब मॉडल ने माना कि I / O कार्यों को I / O चयनकर्ता (epoll, kqueue, iocp ...) के समान धागे पर किया जाएगा। अधिक कम्प्यूटेशनल कार्यों को थ्रेड पूल के लिए निर्देशित किया जा सकता है। इस संदर्भ में, सक्रिय थ्रेड्स की संख्या का लचीला विन्यास ग्रहण किया जाता है, इसलिए यह निष्क्रिय थ्रेड्स को अक्षम करने के लिए अधिक समझ में आता है। हालांकि, नौकरी पर कब्जा करने के साथ शेड्यूलर में, मॉडल ने सभी अतुल्यकालिक कार्यों को करने के लिए स्विच किया, और इस मामले में यह हमेशा सक्रिय राज्य में थ्रेड की एक छोटी संख्या को बनाए रखने के लिए समझ में आता है।

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

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

अंत में, प्रारंभिक कार्यान्वयन में कई छोटी खामियां थीं। शुरुआती वर्षों में, अतुल्यकालिक जंग मॉडल के कार्यान्वयन का विवरण काफी विकसित हुआ, लेकिन पुस्तकालयों ने हर समय एपीआई को स्थिर रखा। इसके कारण कुछ तकनीकी ऋण जमा हो गए।

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

अगली पीढ़ी टोकियो शेड्यूलर

अब समय आ गया है कि नए शेड्यूलर में क्या बदलाव हुआ है।

नई कार्य प्रणाली

सबसे पहले, यह उजागर करना महत्वपूर्ण है कि टोकियो का हिस्सा क्या नहीं है , लेकिन दक्षता में सुधार के मामले में महत्वपूर्ण है: यह मूल रूप से टेलर क्रेमर द्वारा विकसित std में कार्यों की एक नई प्रणाली है । यह प्रणाली हुक प्रदान करती है कि अनुसूचक को अतुल्यकालिक जंग कार्यों को करने के लिए लागू करना चाहिए, और सिस्टम वास्तव में शानदार डिजाइन और कार्यान्वित किया गया है। यह पिछले पुनरावृत्ति की तुलना में बहुत हल्का और अधिक लचीला है।

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

सबसे अच्छा कतार एल्गोरिदम चुनना

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

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

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

पहले प्रयोगों में से एक के भाग के रूप में, हमने क्रॉसबीम को mpmc से बदल दिया। इससे पुश और पॉप के लिए सिंक्रनाइज़ेशन की मात्रा के कारण एक महत्वपूर्ण सुधार नहीं हुआ। काम पर कब्जा करने की कुंजी यह है कि लोड के तहत कतारों में लगभग कोई प्रतिस्पर्धा नहीं है, क्योंकि प्रत्येक प्रोसेसर केवल अपनी कतार तक पहुंचता है।

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

एक कतार कार्यान्वयन एक परिपत्र बफर है जो एक सरणी में मूल्यों को संग्रहीत करता है। कतार के सिर और पूंछ को पूर्णांक मानों के साथ परमाणु संचालन द्वारा ट्रैक किया जाता है।

 struct Queue { /// Concurrently updated by many threads. head: AtomicU32, /// Only updated by producer thread but read by many threads. tail: AtomicU32, /// Masks the head / tail position value to obtain the index in the buffer. mask: usize, /// Stores the tasks. buffer: Box<[MaybeUninit<Task>]>, } 

एकल थ्रेड द्वारा पंक्तिबद्ध किया जाता है:

 loop { let head = self.head.load(Acquire); // safety: this is the **only** thread that updates this cell. let tail = self.tail.unsync_load(); if tail.wrapping_sub(head) < self.buffer.len() as u32 { // Map the position to a slot index. let idx = tail as usize & self.mask; // Don't drop the previous value in `buffer[idx]` because // it is uninitialized memory. self.buffer[idx].as_mut_ptr().write(task); // Make the task available self.tail.store(tail.wrapping_add(1), Release); return; } // The local buffer is full. Push a batch of work to the global // queue. match self.push_overflow(task, head, tail, global) { Ok(_) => return, // Lost the race, try again Err(v) => task = v, } } 

ध्यान दें कि इस push फ़ंक्शन में, केवल परमाणु संचालन लोड हो रहा है और Release ऑर्डर के साथ बचत Acquire कर रहे हैं। पहले की तरह कोई आरएमडब्ल्यू ऑपरेशन ( compare_and_swap , fetch_and ...) या क्रमिक क्रम नहीं हैं। यह महत्वपूर्ण है क्योंकि x86 चिप्स पर सभी डाउनलोड / सेव पहले से ही "परमाणु" हैं। इस प्रकार, सीपीयू स्तर पर, यह फ़ंक्शन सिंक्रनाइज़ नहीं किया जाएगा । परमाणु संचालन संकलक में कुछ अनुकूलन को रोक देगा, लेकिन यह सब है। सबसे अधिक संभावना है, पहले load ऑपरेशन को Relaxed ऑर्डर करने के साथ सुरक्षित रूप से किया जा सकता है, लेकिन प्रतिस्थापन किसी भी ध्यान देने योग्य ओवरहेड को नहीं ले जाता है।

जब कतार भर जाती है, तो push_overflow ।यह फ़ंक्शन स्थानीय से वैश्विक कतार में आधे कार्य करता है। वैश्विक कतार एक म्यूटेक्स द्वारा संरक्षित एक घुसपैठ सूची है। जब वैश्विक कतार में जाते हैं, तो कार्यों को पहले एक साथ जोड़ा जाता है, फिर एक म्यूटेक्स बनाया जाता है, और सभी कार्यों को सूचक को वैश्विक कतार की पूंछ में अपडेट करके डाला जाता है। यह छोटे महत्वपूर्ण अनुभाग आकार को बचाता है।

यदि आप परमाणु मेमोरी ऑर्डरिंग के विवरण से परिचित हैं, तो आप ऊपर दिखाए गए फ़ंक्शन के साथ एक संभावित "समस्या" देख सकते हैं push। परमाणु loadक्रम संचालन Acquireबल्कि कमजोर है। यह अप्रचलित मान लौटा सकता है, अर्थात, एक समानांतर कैप्चर ऑपरेशन पहले से ही मूल्य बढ़ा सकता है self.head, लेकिन स्ट्रीम कैश मेंpushपुराना मान बना रहेगा, इसलिए यह कैप्चर ऑपरेशन को नोटिस नहीं करेगा। यह एल्गोरिथ्म की शुद्धता के साथ कोई समस्या नहीं है। मुख्य (तेज़) तरीके से, pushहम केवल इस बात की परवाह करते हैं कि स्थानीय कतार भरी हुई है या नहीं। चूंकि केवल वर्तमान धागा कतार को धकेल सकता है, एक पुराना ऑपरेशन loadबस कतार को और अधिक पूर्ण दिखाई देगा, क्योंकि यह वास्तव में है। यह गलत तरीके से निर्धारित कर सकता है कि कतार भरी हुई है, और कारण है push_overflow, लेकिन इस फ़ंक्शन में एक मजबूत परमाणु ऑपरेशन शामिल है। यदि यह push_overflowनिर्धारित करता है कि कतार वास्तव में भरी नहीं है, तो w / लौटाता है Err, और ऑपरेशन pushफिर से शुरू होता है। यह एक और कारण हैpush_overflowनिष्पादन कतार का आधा भाग वैश्विक कतार में ले जाता है। इस आंदोलन के बाद, इस तरह के झूठे सकारात्मक अक्सर कम होते हैं।

स्थानीय pop(प्रोसेसर से, जो कतार के अंतर्गत आता है) भी बस लागू किया जाता है:

 loop { let head = self.head.load(Acquire); // safety: this is the **only** thread that updates this cell. let tail = self.tail.unsync_load(); if head == tail { // queue is empty return None; } // Map the head position to a slot index. let idx = head as usize & self.mask; let task = self.buffer[idx].as_ptr().read(); // Attempt to claim the task read above. let actual = self .head .compare_and_swap(head, head.wrapping_add(1), Release); if actual == head { return Some(task.assume_init()); } } 

इस फ़ंक्शन में, एक परमाणु loadऔर एक compare_and_swapएस Release। मुख्य ओवरहेड से आता है compare_and_swap।

फ़ंक्शन stealके समान है pop, लेकिन self.tailपरमाणु भार से स्थानांतरित किया जाना चाहिए। इसके अलावा, इसी तरह push_overflow, ऑपरेशन stealएकल कार्य के बजाय आधा कतार होने का नाटक करने की कोशिश करता है। इससे प्रदर्शन पर अच्छा प्रभाव पड़ता है, जिसके बारे में हम बाद में चर्चा करेंगे।

अंतिम अनुपलब्ध भाग वैश्विक कतार का विश्लेषण है, जो ऐसे कार्यों को प्राप्त करता है जो स्थानीय कतारों को ओवरफ्लो करता है, साथ ही गैर-प्रोसेसर थ्रेड्स से शेड्यूलर को कार्यों को स्थानांतरित करने के लिए। यदि प्रोसेसर लोड हो रहा है, अर्थात, स्थानीय कतार में कार्य हैं, तो प्रोसेसर स्थानीय कतार में प्रत्येक 60 कार्यों के बाद वैश्विक कतार से कार्यों को खींचने का प्रयास करेगा। यह नीचे दी गई "खोज" स्थिति में होने पर वैश्विक कतार की जाँच भी करता है।

संदेश टेम्पलेट

टोकियो अनुप्रयोगों में आमतौर पर कई छोटे स्वतंत्र कार्य होते हैं। वे संदेशों के माध्यम से एक-दूसरे के साथ बातचीत करते हैं। ऐसा टेम्पलेट अन्य भाषाओं जैसे गो और एर्लांग के समान है। यह देखते हुए कि टेम्प्लेट कितना सामान्य है, यह प्लानर के लिए इसे ऑप्टिमाइज़ करने के लिए समझ में आता है।

मान लीजिए कि कार्य A और B दिए गए हैं। कार्य A अब निष्पादित कर रहा है और ट्रांसमिशन चैनल पर कार्य B को संदेश भेजता है। एक चैनल एक संसाधन है जिस पर कार्य बी वर्तमान में बंद है, इसलिए एक संदेश भेजने की क्रिया से कार्य बी को एक निष्पादन योग्य राज्य में संक्रमण का कारण होगा - और इसे वर्तमान प्रोसेसर की निष्पादन कतार में रखा जाएगा। फिर प्रोसेसर निष्पादन कतार से अगले कार्य को काट देगा, इसे निष्पादित करेगा और इस चक्र को तब तक दोहराएगा जब तक यह कार्य बी तक नहीं पहुंच जाता।

समस्या यह है कि एक संदेश भेजने और कार्य बी को पूरा करने के बीच एक महत्वपूर्ण देरी हो सकती है। इसके अलावा, गर्म डेटा, जैसे कि एक संदेश, सीपीयू कैश में संग्रहीत किया जाता है, लेकिन जब तक कार्य पूरा नहीं हो जाता, तब तक संभावना है कि संबंधित कैश को साफ कर दिया जाएगा।

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

थ्रोटल कैप्चर

एक कार्य कैप्चर शेड्यूलर में, यदि प्रोसेसर निष्पादन कतार खाली है, तो प्रोसेसर पीयर सीपीयू से कार्यों को पकड़ने का प्रयास करता है। सबसे पहले, एक यादृच्छिक पीयर सीपीयू का चयन किया जाता है, अगर इसके लिए कोई कार्य नहीं मिलते हैं, तो अगले को खोजा जाता है, और इसी तरह, जब तक कि कार्य नहीं मिलते हैं।

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

इस समस्या को हल करने के लिए, नया शेड्यूलर समानांतर प्रोसेसर की संख्या को सीमित करता है जो कैप्चर ऑपरेशन करते हैं। हम उस प्रोसेसर की स्थिति को कहते हैं जिसमें वह अन्य लोगों के कार्यों "नौकरी खोज" या "खोज" को संक्षिप्त रूप में (बाद में) पर कब्जा करने की कोशिश कर रहा है। इस तरह के अनुकूलन को परमाणु मूल्य का उपयोग करके किया जाता हैint, जो खोज शुरू करने से पहले प्रोसेसर बढ़ जाता है और खोज की स्थिति से बाहर निकलते समय घट जाता है। एक खोज राज्य में जितना संभव हो उतना प्रोसेसर की कुल संख्या का आधा हो सकता है। यही है, अनुमानित सीमा निर्धारित है, और यह सामान्य है। हमें केवल थ्रॉटलिंग में सीपीयू की संख्या पर एक कठिन सीमा की आवश्यकता नहीं है। हम एल्गोरिथ्म दक्षता के लिए सटीकता का त्याग करते हैं।

खोज स्थिति में प्रवेश करने के बाद, प्रोसेसर पीयर सीपीयू से काम पर कब्जा करने की कोशिश करता है और वैश्विक कतार की जांच करता है।

थ्रेड्स के बीच सिंक्रनाइज़ेशन घटाएं

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

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

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

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

मेमोरी आवंटन कम करें

नए टोकियो शेड्यूलर को प्रत्येक स्पॉन्ड टास्क के लिए केवल एक मेमोरी आवंटन की आवश्यकता होती है, जबकि पुराने को दो की आवश्यकता होती है। पहले, कार्य संरचना कुछ इस तरह दिखती थी:

 struct Task { /// All state needed to manage the task state: TaskState, /// The logic to run is represented as a future trait object. future: Box<dyn Future<Output = ()>>, } 

में संरचना Taskपर भी प्रकाश डाला जाएगा Box। बहुत लंबे समय से मैं इस जोड़ को ठीक करना चाहता था (मैंने पहली बार 2014 में कोशिश की थी)। पुराने टोकियो प्लानर के बाद से दो चीजें बदल गई हैं। सबसे पहले, स्थिर std::alloc। दूसरे, भविष्य की कार्य प्रणाली एक स्पष्ट व्यवहार्य रणनीति में बदल गई है । यह दो चीजें थीं जो गायब थीं, आखिरकार, प्रत्येक कार्य के लिए अक्षम डबल मेमोरी आवंटन से छुटकारा पाने के लिए।

अब संरचना Taskनिम्नलिखित रूप में प्रस्तुत की गई है:

 struct Task<T> { header: Header, future: T, trailer: Trailer, } 

कार्य आवश्यक है और के लिए Headerऔर Trailerहै, लेकिन वे 'हॉट' डेटा (सिर) के बीच विभाजित कर रहे हैं और "ठंडा" (पूंछ), एम। ई लगभग बीच डेटा बार-बार पहुँचा और उन है कि शायद ही कभी इस्तेमाल किया जाता है। "हॉट" डेटा को संरचना के सिर पर रखा जाता है और जितना संभव हो उतना कम संग्रहीत किया जाता है। जब प्रोसेसर टास्क पॉइंटर को डिफर करता है, तो यह तुरंत कैश लाइन (64 से 128 बाइट्स) को लोड करता है। हम चाहते हैं कि यह डेटा यथासंभव प्रासंगिक हो।

परमाणु लिंक की गिनती में कमी

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

पुराने टोकियो शेड्यूलर में, शेड्यूलर और सभी वकर्स दोनों एक टास्क डिस्क्रिप्टर का लिंक रखते थे, लगभग:

 struct Waker { task: Arc<Task>, } impl Waker { fn wake(&self) { let task = self.task.clone(); task.scheduler.schedule(task); } } 

जब कार्य उठता है, तो लिंक क्लोन किया जाता है (एक परमाणु वृद्धि होती है)। फिर लिंक को निष्पादन कतार में रखा गया है। जब प्रोसेसर कार्य को प्राप्त करता है और इसके निष्पादन को पूरा करता है, तो यह लिंक को डिस्कनेक्ट करता है, जिससे परमाणु कटौती होती है। ये परमाणु संचालन (वृद्धि और कमी) जोड़ते हैं।

इस समस्या को पहले कार्य प्रणाली के डेवलपर्स द्वारा पहचाना गया था std::future। उन्होंने देखा कि फोन करते समय, Waker::wakeमूल लिंक की wakerजरूरत नहीं रह जाती है। जब आप किसी कार्य को निष्पादन कतार में ले जाते हैं तो परमाणु लिंक काउंटर का पुन: उपयोग कर सकते हैं। कार्य प्रणाली std::futureमें "जागने" के लिए दो एपीआई कॉल शामिल हैं:

• wake जो स्वीकार करता है self
  
• wake_by_ref जो स्वीकार करता है &self

इस तरह के एक एपीआई निर्माण wake, परमाणु वृद्धि से बचने के लिए, कॉल करते समय इसका उपयोग करता है । कार्यान्वयन इस तरह हो जाता है:

 impl Waker { fn wake(self) { task.scheduler.schedule(self.task); } fn wake_by_ref(&self) { let task = self.task.clone(); task.scheduler.schedule(task); } } 

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

नया योजनाकार selfपरमाणु वृद्धि से बचने के द्वारा "जागने" की समस्या को हल करता है wake_by_ref, जो इसे उतना ही प्रभावी बनाता हैwake(self)। ऐसा करने के लिए, अनुसूचक उन सभी कार्यों की सूची रखता है जो वर्तमान में सक्रिय हैं (अभी तक पूरे नहीं हुए हैं)। सूची निष्पादन कतार में कार्य को प्रस्तुत करने के लिए आवश्यक संदर्भ काउंटर का प्रतिनिधित्व करती है।

इस अनुकूलन की जटिलता इस तथ्य में निहित है कि अनुसूचक अपनी सूची से कार्यों को तब तक नहीं हटाएगा जब तक कि यह गारंटी नहीं मिलती है कि कार्य को फिर से निष्पादन कतार में रखा जाएगा। इस योजना के कार्यान्वयन का विवरण इस लेख के दायरे से परे है, लेकिन मैं दृढ़ता से अनुशंसा करता हूं कि आप स्रोत को देखें।

लूम के साथ बोल्ड (असुरक्षित) संगामिति

ताले के बिना सही, समानांतर कोड लिखना बहुत मुश्किल है। धीरे-धीरे, लेकिन सही तरीके से काम करना बेहतर है, जल्दी से, लेकिन ग्लिट्स के साथ, खासकर अगर बग स्मृति सुरक्षा से संबंधित हैं। हालांकि, सबसे अच्छा विकल्प, जल्दी और त्रुटियों के बिना काम करना चाहिए। नए अनुसूचक ने कुछ अधिक आक्रामक अनुकूलन किए और यह stdविशेषज्ञता के लिए अधिकांश प्रकारों से बचता है । सामान्य तौर पर, इसमें बहुत सारे असुरक्षित कोड होते हैं unsafe।

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

हमें यह स्थिति अस्वीकार्य लगी। जब हम कोड जारी करते हैं, तो हम आश्वस्त महसूस करना चाहते हैं (जितना संभव हो), विशेष रूप से ताले के बिना समानांतर कोड के मामले में। टोकियो उपयोगकर्ताओं को विश्वसनीयता की आवश्यकता है।

इसलिए, हमने लूम विकसित किया : समानांतर कोड के क्रमचय परीक्षण के लिए एक उपकरण। टेस्ट हमेशा की तरह लिखे जाते हैं, लेकिनloomयह उन्हें कई बार चलाएगा, निष्पादन और व्यवहार के सभी संभावित विकल्पों को पुनर्व्यवस्थित करता है जो परीक्षण एक स्ट्रीमिंग वातावरण में सामना कर सकते हैं। यह सही मेमोरी एक्सेस, मेमोरी को फ्री करने आदि के लिए भी जाँच करता है।

एक उदाहरण के रूप में, यहाँ नए अनुसूचक के लिए करघा परीक्षण है:

 #[test] fn multi_spawn() { loom::model(|| { let pool = ThreadPool::new(); let c1 = Arc::new(AtomicUsize::new(0)); let (tx, rx) = oneshot::channel(); let tx1 = Arc::new(Mutex::new(Some(tx))); // Spawn a task let c2 = c1.clone(); let tx2 = tx1.clone(); pool.spawn(async move { spawn(async move { if 1 == c1.fetch_add(1, Relaxed) { tx1.lock().unwrap().take().unwrap().send(()); } }); }); // Spawn a second task pool.spawn(async move { spawn(async move { if 1 == c2.fetch_add(1, Relaxed) { tx2.lock().unwrap().take().unwrap().send(()); } }); }); rx.recv(); }); } 

यह बहुत सामान्य लग रहा है, लेकिन एक ब्लॉक में कोड का एक टुकड़ा loom::modelकई हजारों बार (संभवतः लाखों) चलता है, हर बार व्यवहार में मामूली बदलाव के साथ। प्रत्येक रन थ्रेड्स का सटीक क्रम बदलता है। इसके अलावा, प्रत्येक परमाणु संचालन के लिए, करघा C ++ 11 मेमोरी मॉडल में अनुमत सभी अलग-अलग व्यवहारों की कोशिश करता है। याद रखें कि परमाणु भार के साथ Acquireबल्कि कमजोर था और अप्रचलित मूल्यों को वापस कर सकता है। परीक्षण loomसभी संभावित मूल्यों की कोशिश करेगा जिन्हें लोड किया जा सकता है।

loomएक नया योजनाकार विकसित करने में एक अमूल्य उपकरण बन गया। उन्होंने दस से अधिक बग पकड़े जो सभी यूनिट परीक्षण, मैनुअल परीक्षण और लोड परीक्षण पास कर गए।

एक समझदार पाठक को संदेह हो सकता है कि करघा "सभी संभावित क्रमपरिवर्तन" की जाँच करता है, और वह सही होगा। Naive क्रमपरिवर्तन एक दहन विस्फोट की ओर ले जाएगा। कोई भी गैर-तुच्छ परीक्षण कभी खत्म नहीं होगा। इस समस्या का कई वर्षों तक अध्ययन किया गया है, और एक दहनशील विस्फोट को रोकने के लिए कई एल्गोरिदम विकसित किए गए हैं। करघा बुनियादी आधार पर एल्गोरिथ्म आंशिक आदेश के साथ गतिशील कमी (गतिशील आंशिक-आदेश कमी)। यह एल्गोरिथ्म एक ही परिणाम के लिए अग्रणी क्रमपरिवर्तन को समाप्त करता है। लेकिन राज्य स्थान अभी भी इतने आकार तक बढ़ सकता है कि इसे उचित समय (कई मिनट) में संसाधित नहीं किया जाएगा। लूम आपको आंशिक आदेश के साथ गतिशील कमी का उपयोग करके इसे और सीमित करने की अनुमति देता है।

सामान्य तौर पर, करघा मैं का उपयोग कर व्यापक परीक्षण करने के लिए धन्यवाद अब कर रहा हूँ बहुत अधिक अनुसूचक की शुद्धता में विश्वास।

परिणाम

इसलिए, हमने देखा कि शेड्यूलर्स क्या हैं और नए टोकियो शेड्यूलर ने कैसे बहुत बड़ा प्रदर्शन बढ़ाया है ... लेकिन यह किस तरह का विकास है? यह देखते हुए कि नया शेड्यूलर केवल विकसित किया गया है, वास्तविक दुनिया में यह अभी तक पूर्ण रूप से परीक्षण नहीं किया गया है। यहाँ हम जानते हैं।

सबसे पहले, नया शेड्यूलर माइक्रो बेंचमार्क में बहुत तेज है:

पुराना प्लानर

 परीक्षण chained_spawn ... बेंच: 2,019,796 ns / iter (+/- 302,168)
परीक्षण पिंग_पोंग ... बेंच: 1,279,948 एनएस / पुनरावृति (+/- 154,365)
परीक्षण spawn_many ... बेंच: 10,283,608 ns / iter (+/- 1,284,275)
टेस्ट यील्ड_मनी ... बेंच: 21,450,748 ns / iter (+/- 1,201,337) 

नया प्लानर

 परीक्षण chained_spawn ... बेंच: 168,854 ns / iter (+/- 8,339)
परीक्षण पिंग_पोंग ... बेंच: 562,659 ns / iter (+/- 34,410)
टेस्ट स्पॉन_मनी ... बेंच: 7,320,737 ns / iter (+/- 264,620)
टेस्ट यील्ड_मनी ... बेंच: 14,638,563 ns / iter (+/- 1,573,678) 

इस बेंचमार्क में निम्नलिखित शामिल हैं:

• chained_spawn नए कार्यों को पुनरावर्ती रूप से प्रस्तुत करना, अर्थात्, एक ऐसा कार्य उत्पन्न करना जो किसी अन्य कार्य को उत्पन्न करता है, जो एक कार्य भी उत्पन्न करता है, आदि।
  
• ping_pongएक चैनल का चयन करता है oneshotऔर एक कार्य करता है जो उस चैनल पर एक संदेश भेजता है। मूल कार्य संदेश का इंतजार कर रहा है। यह "वास्तविक दुनिया" के सबसे करीब है।
  
• spawn_many शेड्यूलर में कार्यों के कार्यान्वयन की जाँच करता है, अर्थात् इसके संदर्भ के बाहर से कार्य उत्पन्न करता है।
  
• yield_many स्वतंत्र कार्य जागृति के लिए जाँच।

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

यहाँ सबसे सरल हाइपर सर्वर है, जिसका प्रदर्शन प्रयोग करके मापा जाता है wrk -t1 -c50 -d10:

पुराना प्लानर

 रनिंग 10s टेस्ट @ http://127.0.0.1 {000
  1 धागे और 50 कनेक्शन
  थ्रेड स्टैट्स एक्सप्रेस Stdev Max +/- Stdev
    विलंबता 371.53us 99.05us 1.97ms 60.53%
    Req / Sec 114.61k 8.45k 133.85k 67.00%
  10.00 में 1139307 अनुरोध, 95.61MB पढ़ा
अनुरोध / सेकंड: 113923.19
स्थानांतरण / सेकंड: 9.56MB 

नया प्लानर

 रनिंग 10s टेस्ट @ http://127.0.0.1 {000
  1 धागे और 50 कनेक्शन
  थ्रेड स्टैट्स एक्सप्रेस Stdev Max +/- Stdev
    लेटेंसी 275.05us 69.81us 1.09ms 73.57%
    Req / Sec 153.17k 10.68k 171.51k 71.00%
  10.00 में 1522671 अनुरोध, 127.79MB पढ़ा
अनुरोध / सेकंड: 152258.70
स्थानांतरण / सेकंड: 12.78MB 

हम शेड्यूलर के परिवर्तन के बाद प्रति सेकंड अनुरोधों में 34% की वृद्धि देखते हैं! पहली बार जब मैंने यह देखा, तो मैं बहुत खुश था, क्योंकि मुझे अधिकतम 5-10% की वृद्धि की उम्मीद थी। लेकिन फिर मुझे दुख हुआ, क्योंकि इस परिणाम से यह भी पता चला कि पुराना टोकियो शेड्यूलर इतना अच्छा नहीं है। तब मुझे याद आया कि हाइपर पहले से ही TechEmpower रेटिंग में अग्रणी है । यह देखना दिलचस्प है कि नए योजनाकार रेटिंग को कैसे प्रभावित करेंगे। नए अनुसूचक के साथ

टॉनिक , जीआरपीसी क्लाइंट और सर्वर में लगभग 10% की तेजी आई है, जो यह देखते हुए बहुत प्रभावशाली है कि टॉनिक अभी पूरी तरह से अनुकूलित नहीं है।

निष्कर्ष

मैं कई महीनों के काम के बाद इस परियोजना को पूरा करने के लिए वास्तव में बहुत खुश हूं। यह रस्ट के अतुल्यकालिक I / O के लिए एक बड़ा सुधार है। मैं किए गए सुधारों से बहुत प्रसन्न हूं। टोकियो कोड में अनुकूलन के लिए अभी भी बहुत जगह है, इसलिए हम अभी तक प्रदर्शन में सुधार के साथ नहीं हैं।

मुझे उम्मीद है कि लेख में सामग्री उन सहयोगियों के लिए उपयोगी होगी जो अपने कार्य अनुसूचक को लिखने की कोशिश करते हैं।