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

टैग किए गए संकेत

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

template <typename T> struct tagged_ptr { T * ptr ; unsigned int tag ; tagged_ptr(): ptr(nullptr), tag(0) {} tagged_ptr( T * p ): ptr(p), tag(0) {} tagged_ptr( T * p, unsigned int n ): ptr(p), tag(n) {} T * operator->() const { return ptr; } }; 

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

• यह योजना उन प्लेटफार्मों पर कार्यान्वित की जाती है, जिन पर दोहरे शब्द (dwCAS) के ऊपर एक कैस परमाणु आदिम है। 32-बिट आधुनिक प्लेटफार्मों के लिए, यह आवश्यकता पूरी हो गई है, क्योंकि dwCAS 64-बिट शब्दों के साथ काम करता है, और सभी आधुनिक आर्किटेक्चर में 64-बिट निर्देशों का एक पूरा सेट है। लेकिन 64-बिट ऑपरेशन मोड के लिए, 128-बिट (या कम से कम 96-बिट) dwCAS की आवश्यकता होती है, जो सभी आर्किटेक्चर पर लागू नहीं होता है।
  
  हाँ, आपने बकवास लिखा, मेरे दोस्त!

  विशेष रूप से लॉक-फ्री में परिष्कृत आपत्ति कर सकते हैं कि टैग किए गए पॉइंटर्स को लागू करने के लिए विस्तृत 128-बिट (या 96-बिट) कैस होना आवश्यक नहीं है। आप 64-बिट के साथ प्राप्त कर सकते हैं, यह देखते हुए कि आधुनिक प्रोसेसर पते के लिए केवल 48 बिट्स का उपयोग करते हैं, पते के उच्चतम 16 बिट मुफ्त हैं और टैग काउंटर को स्टोर करने के लिए उपयोग किया जा सकता है। खैर, वास्तव में, वे कर सकते हैं। यह boost.lockfree में किया गया है।
  इस दृष्टिकोण में दो "बट" हैं:
  

  • कौन गारंटी देता है कि भविष्य में पते के इन 16 बिट्स शामिल नहीं होंगे? जैसे ही अगली सफलता मेमोरी चिप्स के क्षेत्र में आती है और इसकी मात्रा परिमाण के एक क्रम से बढ़ जाएगी, विक्रेताओं तुरंत 64-बिट पते के साथ नए प्रोसेसर जारी करेंगे
  • क्या 16 बिट्स टैग रखने के लिए पर्याप्त है? इस विषय पर अध्ययन किए गए थे, और इन अध्ययनों का परिणाम निम्नानुसार है: 16 बिट पर्याप्त नहीं हैं, अतिप्रवाह काफी संभव है, जो संभावित रूप से एक एबीए समस्या का कारण बन सकता है। लेकिन 32 बिट्स काफी है।
    वास्तव में, 16 बिट्स 0 - 65535 टैग के मान हैं। आधुनिक ऑपरेटिंग सिस्टम में, स्ट्रीम को आवंटित समय स्लॉट 300-500 हजार कोडांतरक निर्देशों (लिनक्स डेवलपर्स के आंतरिक पत्राचार से लिया गया) के आदेश का है, और यह क्वांटम केवल प्रोसेसर के बढ़ते प्रदर्शन के साथ बढ़ सकता है। यह पता चला है कि एक मात्रा में कैस के रूप में 65 हजार भी ऐसे भारी ऑपरेशन करना संभव है (ठीक है, अगर यह आज असंभव है, तो यह कल संभव होगा)। इस प्रकार, 16-बिट टैग के साथ, हमें ABA समस्या होने का काफी खतरा है।

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

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

Libcds लाइब्रेरी वर्तमान में लॉक-फ्री कंटेनर को लागू करने के लिए टैग किए गए पॉइंटर्स का उपयोग नहीं करती है। इसकी सापेक्ष सादगी के बावजूद, यह योजना प्रत्येक कंटेनर ऑब्जेक्ट के लिए एक मुफ्त-सूची की उपस्थिति के कारण मेमोरी खपत में अनियंत्रित वृद्धि का कारण बन सकती है। Libcds में, मैंने dwCAS का उपयोग किए बिना, अनुमानित मेमोरी खपत के साथ लॉक-फ्री एल्गोरिदम पर ध्यान केंद्रित किया।
टैग किए गए पॉइंटर्स का उपयोग करने का एक अच्छा उदाहरण boost.lockfree लाइब्रेरी है।

टैग किए गए संकेत उदाहरण

शीट के प्रशंसक (यदि कोई हो) - pseudocode MSQueue [MS98] टैग किए गए सूचक के साथ। हां, लॉक-फ्री एल्गोरिदम बहुत क्रियात्मक हैं!
सादगी के लिए, मैंने std:atomic के उपयोग को छोड़ दिया std:atomic ।

 template <typename T> struct node { tagged_ptr next; T data; } ; template <typename T> class MSQueue { tagged_ptr<T> volatile m_Head; tagged_ptr<T> volatile m_Tail; FreeList m_FreeList; public: MSQueue() { //  dummy node // Head & Tail   dummy node m_Head.ptr = m_Tail.ptr = new node(); } }; void enqueue( T const& value ) { E1: node * pNode = m_FreeList.newNode(); E2: pNode–>data = value; E3: pNode–>next.ptr = nullptr; E4: for (;;) { E5: tagged_ptr<T> tail = m_Tail; E6: tagged_ptr<T> next = tail.ptr–>next; E7: if tail == m_Tail { // Tail    ? E8: if next.ptr == nullptr { //       E9: if CAS(&tail.ptr–>next, next, tagged_ptr<T>(node, next.tag+1)) { // ,    E10: break; } E11: } else { // Tail      //   tail    E12: CAS(&m_Tail, tail, tagged_ptr<T>(next.ptr, tail.tag+1)); } } } // end loop //   tail    E13: CAS(&m_Tail, tail, tagged_ptr<T>(pNode, tail.tag+1)); } bool dequeue( T& dest ) { D1: for (;;) { D2: tagged_ptr<T> head = m_Head; D3: tagged_ptr<T> tail = m_Tail; D4: tagged_ptr<T> next = head–>next; // Head, tail  next ? D5: if ( head == m_Head ) { // Queue   tail  ? D6: if ( head.ptr == tail.ptr ) { //  ? D7: if (next.ptr == nullptr ) { //   D8: return false; } // Tail     //   tail D9: CAS(&m_Tail, tail, tagged_ptr<T>(next.ptr, tail.tag+1>)); D10: } else { // Tail  //    CAS,    //  dequeue   next D11: dest = next.ptr–>data; //   head D12: if (CAS(&m_Head, head, tagged_ptr<T>(next.ptr, head.tag+1)) D13: break // ,    } } } // end of loop //   dummy node D14: m_FreeList.add(head.ptr); D15: return true; //  –  dest } 

आइए एन्क्यू और डीक्यू ऑपरेशन के एल्गोरिदम पर एक करीब से नज़र डालें। उनके उदाहरण का उपयोग करते हुए, आप लॉक-फ्री संरचनाओं का निर्माण करते समय कई मानक चाल देख सकते हैं।

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

कतार में पहला तत्व ( m_Head द्वारा m_Head ) एक डमी तत्व (डमी नोड) है। एक डमी तत्व होने से यह सुनिश्चित होता है कि कतार की शुरुआत और अंत में संकेत कभी भी पूर्ण नहीं होते हैं। एक खाली कतार का एक संकेत m_Head == m_Tail && m_Tail->next == NULL (लाइनें D6-D8) है। अंतिम स्थिति ( m_Tail->next == NULL ) आवश्यक है, क्योंकि कतार में जोड़ने की प्रक्रिया के दौरान हम m_Tail नहीं बदलते हैं , लाइन E9 केवल m_Tail->next बदलता है। इस प्रकार, पहली नज़र में, enqueue विधि कतार संरचना का उल्लंघन करती है। दरअसल, m_Tail पूंछ दूसरी विधि और / या किसी अन्य थ्रेड में बदल जाती है: तत्व जाँच (लाइन E8) जोड़ने से पहले enqueue ऑपरेशन जो कि m_Tail अंतिम तत्व (यानी m_Tail->next == NULL ) को m_Tail->next == NULL , और यदि यह नहीं है इसलिए, सूचक को अंत तक ले जाने की कोशिश कर रहा है (लाइन E12); इसी तरह, अपने "तत्काल कर्तव्यों" को निष्पादित करने से पहले m_Tail बदल m_Tail यदि यह कतार के अंत में इंगित नहीं होता है (लाइन D9)। यह हमें लॉक-फ्री प्रोग्रामिंग - प्रवाह की पारस्परिक सहायता ( सहायता ) में एक सामान्य दृष्टिकोण दिखाता है: एक ऑपरेशन का एल्गोरिथ्म कंटेनर के सभी संचालन पर "धब्बा" है और एक ऑपरेशन इस तथ्य पर बहुत निर्भर करता है कि इसका संचालन अगले कॉल द्वारा पूरा किया जाएगा (संभवतः एक और) ऑपरेशन में ( शायद) एक और धागा।

एक अन्य मौलिक अवलोकन: संचालन स्थानीय बिंदुओं में संचय करता है, जिसे उन्हें संचालित करने की आवश्यकता होती है (लाइनों को E5-E6, D2-D4)। तब (रेखाएँ E7, D5), मूल रूप से पढ़े गए मूल्यों की तुलना मूल के साथ की जाती है - एक ठेठ लॉक-फ्री ट्रिक, गैर-प्रतिस्पर्धी प्रोग्रामिंग के लिए अनावश्यक: पढ़ने के बाद से गुजरे समय के दौरान, मूल मान बदल सकते हैं। कंपाइलर कतार के साझा डेटा तक पहुंच का अनुकूलन नहीं करने के लिए (और "स्मार्ट" कंपाइलर E7 या D5 तुलना लाइनों को पूरी तरह से हटाने में सक्षम है), m_Head और m_Tail को C ++ 11 (छद्म-कोड - volatile ) में atomic घोषित किया जाना चाहिए। इसके अलावा, हम याद करते हैं कि CAS आदिम दिए गए एक के साथ लक्ष्य पते के मूल्य की पुष्टि करता है, और यदि वे समान हैं, तो लक्ष्य पते पर डेटा को एक नए मूल्य में बदल देता है। इसलिए, CAS आदिम के लिए, आपको हमेशा वर्तमान मान की एक स्थानीय प्रतिलिपि निर्दिष्ट करनी चाहिए; CAS(&val, val, newVal) को CAS(&val, val, newVal) लगभग हमेशा सफल होगा, जो हमारे लिए एक गलती है।

अब देखते हैं कि dequeue कब dequeue विधि (लाइन D11) में कॉपी किया जाता है: इससे पहले कि आइटम को कतार (लाइन D12) से बाहर रखा जाए। यह देखते हुए कि एक तत्व अपवाद (लाइन D12 पर m_Head अग्रिम) विफल हो सकता है, प्रतिलिपि डेटा (D11) दोहराया जा सकता है। C ++ के दृष्टिकोण से, इसका मतलब है कि कतार में संग्रहीत डेटा बहुत जटिल नहीं होना चाहिए, अन्यथा लाइन D11 में असाइनमेंट ऑपरेटर का ओवरहेड बहुत बड़ा होगा। तदनुसार, उच्च लोड स्थितियों के तहत, सीएएस आदिम की विफलता की संभावना बढ़ जाती है। D11 लाइन को लूप से बाहर ले जाकर एल्गोरिथम को "ऑप्टिमाइज़" करने का प्रयास करने से त्रुटि उत्पन्न होगी: next तत्व को किसी अन्य थ्रेड से हटाया जा सकता है। चूंकि प्रश्न में कतार का कार्यान्वयन टैगेड पॉइंटर स्कीम पर आधारित है, जिसमें तत्वों को कभी भी नष्ट नहीं किया जाता है, इसलिए यह "अनुकूलन" इस तथ्य को जन्म देगा कि हम गलत डेटा (डी 12 लाइन के सफल निष्पादन के समय कतार में मौजूद लोगों को नहीं) को वापस कर सकते हैं।

युग-आधारित पुनर्विचार

फ्रेजर [Fra03] ने एक युग- आधारित योजना प्रस्तावित की। विलंबित विलोपन को एक सुरक्षित क्षण में लागू किया जाता है, जब पूर्ण विश्वास होता है कि थ्रेड्स में से कोई भी हटाए गए तत्व के लिंक नहीं है। यह गारंटी युगों द्वारा प्रदान की जाती है: nGlobalEpoch का एक वैश्विक युग है, और प्रत्येक थ्रेड nThreadEpoch अपने स्थानीय युग में काम करता है। युग-आधारित योजना द्वारा संरक्षित कोड दर्ज करने पर, वैश्विक युग से अधिक नहीं होने पर प्रवाह का स्थानीय युग बढ़ जाता है। एक बार जब सभी धागे वैश्विक युग में पहुंच गए हैं, तो nGlobalEpoch ।

स्कीमा स्यूडो कोड:

 //   static atomic<unsigned int> m_nGlobalEpoch := 1 ; const EPOCH_COUNT = 3 ; // TLS data struct ThreadEpoch { //    unsigned int m_nThreadEpoch ; //      List<void *> m_arrRetired[ EPOCH_COUNT ] ; ThreadEpoch(): m_nThreadEpoch(1) {} void enter() { if ( m_nThreadEpoch <= m_nGlobalEpoch ) m_nThreadEpoch = m_nGlobalEpoch + 1 ; } void exit() { if (     ,   m_nGlobalEpoch ) { ++m_nGlobalEpoch ;  (delete)  m_arrRetired[ (m_nGlobalEpoch – 1) % EPOCH_COUNT ]   ; } } } ; 

रिलीज़ किए गए लॉक-फ़्री कंटेनर तत्वों को उन आइटमों की थ्रेड-लोकल सूची में रखा गया है, जो m_arrRetired[m_nThreadEpoch % EPOCH_COUNT] हटाने की प्रतीक्षा कर रहे हैं। जैसे ही सभी प्रवाह m_nGlobalEpoch वैश्विक युग से m_nGlobalEpoch , सभी m_nGlobalEpoch – 1 की सभी m_nGlobalEpoch – 1 युग प्रवाह को मुक्त किया जा सकता है, और वैश्विक युग में ही वृद्धि हो सकती है।


प्रत्येक लॉक-फ्री कंटेनर ऑपरेशन ThreadEpoch::enter() और ThreadEpoch::exit() कॉल्स में संलग्न है, जो कि महत्वपूर्ण सेक्शन के समान है:

 lock_free_op( … ) { get_current_thread()->ThreadEpoch.enter() ; . . . // lock-free  . //    “ ” epoch-based , //     ,     ,   //  . . . . get_current_thread()->ThreadEpoch.exit() ; } 

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

Libcds लाइब्रेरी में युग-आधारित योजना का कार्यान्वयन नहीं होता है। कारण: मैं यह निर्धारित करने के लिए एक पर्याप्त प्रभावी एल्गोरिथ्म का निर्माण करने में सक्षम नहीं था कि क्या सभी प्रवाह वैश्विक युग में पहुंचे। शायद पाठकों में से कोई एक समाधान सुझाएगा?

खतरा सूचक

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


खतरा सूचक छद्म कोड [Mic02]:

 //  // P :   // K :  hazard pointer    // N :   hazard pointers = K*P // R : batch size, RN=Ω(N), , R=2*N // Per-thread : //  Hazard Pouinter  //     - //    void * HP[K] //   dlist ( 0..R) unsigned dcount = 0; //      void* dlist[R]; //   //     dlist void RetireNode( void * node ) { dlist[dcount++] = node; //    –    Scan if (dcount == R) Scan(); } //   //     dlist,    //  Hazard Pointer void Scan() { unsigned i; unsigned p=0; unsigned new_dcount = 0; // 0 .. N void * hptr, plist[N], new_dlist[N]; // Stage 1 –    HP   //    plist   for (unsigned t=0; t < P; ++t) { void ** pHPThread = get_thread_data(t)->HP ; for (i = 0; i < K; ++i) { hptr = pHPThread[i]; if ( hptr != nullptr ) plist[p++] = hptr; } } // Stage 2 –  hazard pointer' //       sort(plist); // Stage 3 –  ,    hazard for ( i = 0; i < R; ++i ) { //  dlist[i]    plist  Hazard Pointer' //  dlist[i]    if ( binary_search(dlist[i], plist)) new_dlist[new_dcount++] = dlist[i]; else free(dlist[i]); } // Stage 4 –     . for (i = 0; i < new_dcount; ++i ) dlist[i] = new_dlist[i]; dcount = new_dcount; } 

जब pNode लॉक-फ्री कंटेनर तत्व के RetireNode(pNode) को हटा रहे हैं, तो j dlist लंबित (आवश्यक निष्कासन) तत्वों की सूची के लिए dlist को स्थानीय (स्ट्रीम j ) में सूचीबद्ध करें। जैसे ही dlist का आकार R तक पहुँचता है ( R, N = P*K बराबर है, लेकिन dlist से अधिक है; उदाहरण के लिए, R = 2N ), Scan() प्रक्रिया को कहा जाता है, जो लंबित वस्तुओं को हटाने में लगी हुई है। शर्त R > P*K आवश्यक है: केवल अगर यह शर्त पूरी होती है, तो यह गारंटी है कि Scan() लंबित डेटा सरणी से कुछ भी निकालने में सक्षम होगा। यदि इस स्थिति का उल्लंघन किया जाता है, तो Scan() सरणी से कुछ भी नहीं हटा सकता है, और हमें एक एल्गोरिथ्म त्रुटि मिलेगी - सरणी पूरी तरह से भरी हुई है, लेकिन इसका आकार कम नहीं किया जा सकता है।

Scan() में चार चरण होते हैं।

• सबसे पहले, वर्तमान खतरा plist का plist सरणी तैयार किया जाता है, जिसमें सभी प्रवाह के सभी गैर- null खतरनाक बिंदु शामिल होते हैं। केवल पहला चरण साझा किए गए डेटा को पढ़ता है - HP धाराओं की सरणियाँ - शेष चरण केवल स्थानीय डेटा के साथ काम करते हैं।
• स्टेज 2 बाद की खोजों को अनुकूलित करने के लिए plist सरणी को plist ; यहाँ आप plist तत्वों को भी हटा सकते हैं।
• स्टेज 3 - स्वयं को हटा देना: वर्तमान धारा के सूची के सभी तत्व देखे जाते हैं। यदि dlist[i] तत्व plist (अर्थात, कुछ थ्रेड इस पॉइंटर के साथ काम करता है, तो इसे dlist पॉइंटर के रूप में घोषित किया जाता है), आप इसे हटा नहीं सकते हैं और यह dlist में रहता है (इसे dlist में स्थानांतरित कर दिया जाता है)। अन्यथा, dlist[i] तत्व को हटाया जा सकता है - इसके साथ एक भी धागा काम नहीं करता है।
• चरण 4 new_dlist से new_dlist गए dlist को dlist । R > N , Scan() dlist , - .

Hazard Pointer, , :

 std::atomic<T *> atomicPtr ; … T * localPtr ; do { localPtr = atomicPtr.load(std::memory_order_relaxed); HP[i] = localPtr ; } while ( localPtr != atomicPtr.load(std::memory_order_acquire)); 

atomicPtr localPtr ( ) HP[i] HP hazard- . , , atomicPtr , , atomicPtr localPtr . , HP ( hazard) atomicPtr . Hazard Pointer' ( hazard), , .

Hazard Pointer (HP-) C++11 memory ordering [Tor08].


Hazard Pointer ? ? , , — . : hazard pointer' K . – hazard pointer – , , , hazard- . , hazard-. – [Har01]. , HP- .
, HP- hazard-. , . libcds , , , HP-. , — Pass the Buck , — Hazard Pointer, hazard-. .

Hazard Pointer libcds

hazard pointer libcds. – Hazard Pointer Manager — , libcds.dll/.so. — Thread HP Manager , — HP hazard pointer' K () Retired R . Thread HP Manager . P . libcds:

• hazard- K = 8
• P = 100
• ( ) R = 2 * K * P = 1600 .

libcds HP- :

• – ( cds::gc::hzp ). ( T ), . , ( , «» – . , – -, – « ». , , – ).
• – , cds::gc::hzp . (template) - , (- type erasure).
• (API) – cds::gc::HP . , ( ) lock-free libcds, , ( , ) GC . cds::gc::HP – .

HP- libcds, main() cds::gc::HP , , HP-, . , , cds::gc::HP . API HP-.

Hazard Pointer with Reference Counter

Hazard Pointer , lock-free . , , , , : hazard-.

, , (reference counting, RefCount). Valois – lock-free — . RefCount- , – , . , RefCount-, lock-free fetch-and-add (, , – ).
2005 [GPST05], Hazard Pointer RefCount : Hazard Pointers lock-free , RefCount – . HRC (Hazard pointer RefCounting).
Hazard Pointers / , RefCounting- . , (- , . [GPST05]). Hazard Pointers lock-free , HRC :

 void CleanUpNode( Node * pNode); void TerminateNode( Node * pNode); 

TerminateNode pNode . CleanUpNode , , pNode «» ( ) , () ; RefCount- , , CleanUpNode :

 void CleanUpNode(Node * pNode) { for (all x where pNode->link[x] of node is reference-counted) { retry: node1 = DeRefLink(&pNode->link[x]); //  HP if (node1 != NULL and !is_deleted( node1 )) { node2 = DeRefLink(node1->link[x]); //  HP //  ,       //    node1 CompareAndSwapRef(&pNode->link[x],node1,node2); ReleaseRef(node2); //  HP ReleaseRef(node1); //  HP goto retry; //       ,   } ReleaseRef(node1); //  HP } } 

lock-free ( C++) HRC lock-free . , , CleanUpNode , , . lock-free , , MultiCAS .
, Hazard Pointers , . Scan Hazar Pointers ( , CleanUpNode ). : Hazard Pointers ( R > N = P * K ), Scan - ( , hazard-), HRC Scan - ( – ). , Scan , CleanUpAll : CleanUpNode , Scan .

Pass the Buck

lock-free , Herlihy & al Pass-the-Buck (PTB, “ ”) [HLM02, HLM05], HP- ., .
, HP-, PTB- (guarded, hazard pointer HP-). PTB- ( hazard pointer'). (retired) Liberate — Scan HP-. Liberate , . HP-, retired- , PTB- .
guard' (hazard pointer'): , retired-, hand-off (“ ”). Liberate , retired- guard', retired- hand-off guard'. Liberate hand-off , guard, , , .

[HLM05] Liberate : wait-free lock-free. Wait-free dwCAS (CAS ), dwCAS . Lock-free , . (guard' retired-) lock-free Liberate , (, retired-, ). , PTB- , Liberate .

, Liberate PTB-, HP-. PTB libcds HP- hazard- retired-. : «» HP- , PTB, PTB guard'.

निष्कर्ष

safe memory reclamation, Hazard Pointer. HP- lock-free .

lock-free . libcds, , (attach) GC libcds. , Scan() / Liberate() . — .

— RCU, HP-like , — .

UPD 2016: Errandir , Hazard Pointer ( HP).