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

ऐसा लगता है, हम स्टैक के बारे में क्या कह सकते हैं? यह एक ऐसी तुच्छ डेटा संरचना है जिसमें कहने के लिए बहुत कुछ नहीं है।
वास्तव में, प्रतिस्पर्धी स्टैक के कार्यान्वयन पर बहुत सारे काम नहीं हैं। लेकिन दूसरी ओर, वे जो ढेर की तुलना में दृष्टिकोण के लिए एक बड़ी डिग्री के लिए समर्पित हैं। यह दृष्टिकोण है कि मुझे ब्याज है।

ताला-मुक्त ढेर

स्टैक शायद डेटा संरचनाओं में से पहला है जिसके लिए लॉक-फ्री एल्गोरिदम बनाया गया था। यह माना जाता है कि ट्रेबेर ने इसे अपने 1986 के लेख में प्रकाशित किया था, हालांकि इस बात के सबूत हैं कि इस एल्गोरिथ्म को पहली बार आईबीएम / 360 सिस्टम प्रलेखन में वर्णित किया गया था।

एल्गोरिथ्म इतना सरल है कि मैं libcds से इसका अनुकूलित कोड दे दूंगा (किसी को भी दिलचस्पी है cds::intrusive::TreiberStack दखलंदाजी ढेर):

 // m_Top –   bool push( value_type& val ) { back_off bkoff; value_type * t = m_Top.load(std::memory_order_relaxed); while ( true ) { val.m_pNext.store( t, std::memory_order_relaxed ); if (m_Top.compare_exchange_weak(t, &val, std::memory_order_release, std::memory_order_relaxed)) return true; bkoff(); } } value_type * pop() { back_off bkoff; typename gc::Guard guard; // Hazard pointer guard while ( true ) { value_type * t = guard.protect( m_Top ); if ( t == nullptr ) return nullptr ; // stack is empty value_type * pNext = t->m_pNext.load(std::memory_order_relaxed); if ( m_Top.compare_exchange_weak( t, pNext, std::memory_order_acquire, std::memory_order_relaxed )) return t; bkoff(); } } 

यह एल्गोरिथ्म हड्डियों (उदाहरण के लिए, यहां ) द्वारा बार-बार डिसाइड किया जाता है, इसलिए मैंने इसे दोहराया नहीं। एल्गोरिथ्म का एक संक्षिप्त विवरण इस तथ्य तक कम हो जाता है कि हम वांछित परिणाम प्राप्त करने तक m_Top में परमाणु आदिम CAS की मदद से हथौड़ा m_Top । सरल और काफी आदिम।
मैं दो दिलचस्प विवरणों पर ध्यान देता हूं:

• सुरक्षित मेमोरी रिक्लेमेशन (SMR) की आवश्यकता केवल pop विधि में होती है, केवल वहीं से हम m_Top फ़ील्ड्स को m_Top हैं। कोई भी m_Top फ़ील्ड को push में नहीं पढ़ा जाता है ( m_Top पॉइंटर तक कोई पहुंच नहीं है), इसलिए आपको हेज़र्ड को पॉइंटर से बचाने की आवश्यकता नहीं है। यह दिलचस्प है क्योंकि आमतौर पर लॉक-फ्री कंटेनर क्लास के सभी तरीकों में एसएमआर की आवश्यकता होती है
• रहस्यमय bkoff ऑब्जेक्ट और bkoff() को इसकी कॉल bkoff() यदि CAS असफल है

यहाँ इस bkoff मैं और अधिक विस्तार से ध्यान देना चाहूंगा।

बैक-ऑफ रणनीति

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

 class exp_backoff { int const nInitial; int const nStep; int const nThreshold; int nCurrent; public: exp_backoff( int init=10, int step=2, int threshold=8000 ) : nInitial(init), nStep(step), nThreshold(threshold), nCurrent(init) {} void operator()() { for ( int k = 0; k < nCurrent; ++k ) nop(); nCurrent *= nStep; if ( nCurrent > nThreshold ) nCurrent = nThreshold; } void reset() { nCurrent = nInitial; } }; 

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

माना जाता है कि बैक-ऑफ रणनीतियां असफल सीएएस के साथ समस्या को हल करने में मदद करती हैं, लेकिन किसी भी तरह से मुख्य कार्य के कार्यान्वयन में योगदान नहीं करती हैं - स्टैक के साथ संचालन। क्या किसी तरह push / pop और बैक-ऑफ को संयोजित करना संभव है ताकि बैक-ऑफ रणनीति सक्रिय रूप से ऑपरेशन में मदद करे?

उन्मूलन बैक-ऑफ

दूसरी ओर push / pop में विफल कैस की समस्या पर विचार करें। कैस असफल क्यों है? क्योंकि एक और धागा m_Top बदल गया। और यह दूसरा धागा क्या करता है? push() या pop() । अब ध्यान दें कि स्टैक के लिए push और pop ऑपरेशंस पूरक हैं: यदि एक थ्रेड push() करता है push() और दूसरा उसी समय pop() करता है, तो सिद्धांत रूप में यह m_Top स्टैक के शीर्ष तक पहुंचने का कोई मतलब नहीं है: एक पुश स्ट्रीम बस हो सकती है अपने डेटा को पॉप-स्ट्रीम में स्थानांतरित करें, जबकि स्टैक की मुख्य संपत्ति - LIFO - का उल्लंघन नहीं किया गया है। यह पता लगाने के लिए रहता है कि स्टैक के शीर्ष को दरकिनार करके इन दोनों प्रवाह को एक साथ कैसे लाया जाए।


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

आकार एन का एक उन्मूलन सरणी है (एन एक छोटी संख्या है)। यह सरणी स्टैक वर्ग का सदस्य है। यदि CAS विफल होता है, तो बैक-ऑफ़ जा रहा है, थ्रेड अपने ऑपरेशन ( push या pop ) के लिए एक हैंडल बनाता है और इस सरणी में बेतरतीब ढंग से एक मनमाना सेल का चयन करता है। यदि कक्ष खाली है, तो वह इसमें अपने विवरणक के लिए एक संकेतक लिखता है और सामान्य बैक-ऑफ करता है, उदाहरण के लिए, एक्सपेन्शनल। इस मामले में, प्रवाह को निष्क्रिय कहा जा सकता है।
यदि चयनित सेल में पहले से ही किसी अन्य (निष्क्रिय) स्ट्रीम के डिस्क्रिप्टर P के ऑपरेशन के लिए एक पॉइंटर है, तो स्ट्रीम (इसे सक्रिय कहते हैं) यह जांचता है कि यह किस तरह का ऑपरेशन है। यदि ऑपरेशन पूरक हैं - push और pop , तो वे परस्पर अवशोषित होते हैं:

• यदि सक्रिय थ्रेड push करता है, तो यह पी डिस्क्रिप्टर को अपना तर्क लिखता है, इस प्रकार इसे निष्क्रिय थ्रेड के pop ऑपरेशन में पास करता है;
• यदि सक्रिय धागा pop , तो यह हैंडल पी से पूरक push ऑपरेशन के तर्क को पढ़ता है।

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

समतल संयोजन

अब तक, हमने लॉक-फ्री स्टैक के बारे में बात की थी। अब एक नियमित लॉक-आधारित स्टैक पर विचार करें:

 template <class T> class LockStack { std::stack<T *> m_Stack; std::mutex m_Mutex; public: void push( T& v ) { m_Mutex.lock(); m_Stack.push( &v ); m_Mutex.unlock(); } T * pop() { m_Mutex.lock(); T * pv = m_Stack.top(); m_Stack.pop() m_Mutex.unlock(); return pv; } }; 

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

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

निष्कर्ष

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