👩🏿‍🏫 ♏️ 🎅🏽 लॉकफ्री एल्गोरिदम और उनके समाधान विकसित करते समय सामान्य गलतियां 🤲🏼 🧖🏻 🉑

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

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

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

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

ताले का उपयोग करने के बजाय, लॉक-फ्री एल्गोरिदम तुलना और स्वैप (CAS) के रूप में ज्ञात एक कमांड का उपयोग करते हैं। इसके तर्क को निम्नलिखित कोड के टुकड़े द्वारा वर्णित किया जा सकता है, कैस के साथ जो एटमेटिक रूप से किया जाता है:

1 bool CompareAndSwap(Value* addr, Value oldVal, Value newVal){ 2 if(*addr == oldVal){ 3 *addr = newVal; 4 return true; 5 }else{ 6 return false; 7 } 8 }

लॉक-फ्री एल्गोरिदम के साथ मुख्य समस्याएं निम्नलिखित तीन हैं:

1. अक्सर एक लॉक-फ्री कार्यान्वयन लॉक के साथ कार्यान्वयन की तुलना में कम व्यावहारिक होता है।
2. लॉक-फ्री कोड लिखना आसान नहीं है।
3. सही लॉक-फ्री कोड लिखना अविश्वसनीय रूप से कठिन है।

बिंदु तीन साबित करने के लिए, एक साधारण उदाहरण पर विचार करें - लिंक की गई सूचियों पर एक स्टैक लागू करना। यदि आप किसी ऐसे व्यक्ति से पूछते हैं जो स्टैक लिखने के लिए लॉक-फ्री से परिचित नहीं है, तो इसका पहला कार्यान्वयन लगभग इस प्रकार होगा:

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

स्टैक से हटाए गए ऑपरेशन के लिए, स्टैक के वर्तमान शीर्ष को याद रखें, और, कैस का उपयोग करके, इसे अपने पॉइंटर के मूल्य से अगले तत्व में बदलने का प्रयास करें। यदि CAS सफल रहा, तो स्टैक से तत्व को हटा दिया गया था, अन्यथा स्टैक के शीर्ष को दूसरे धागे से बदल दिया गया था, और हम इसे फिर से हटाने की कोशिश कर रहे हैं।

C ++ में, यह कुछ इस तरह दिखेगा:

  1 template <class Entry> 2 class LockFreeStack{ 3 struct Node{ 4 Entry* entry; 5 Node* next; 6 }; 7 8 Node* m_head; 9 10 void Push(Entry* e){ 11 Node* n = new Node; 12 n->entry = e; 13 do{ 14 n->next = m_head; 15 }while(!CompareAndSwap(&m_head, n->next, n)); 16 } 17 18 Entry* Pop(){ 19 Node* old_head; 20 Entry* result; 21 do{ 22 old_head = m_head; 23 if(old_head == NULL){ 24 return NULL; 25 } 26 }while(!CompareAndSwap(&m_head, old_head, old_head->next)); 27 28 result = old_head->entry; 29 delete old_head; 30 return result; 31 } 32 }

दुर्भाग्य से, यह उचित प्रतीत होता है, लॉक-फ्री स्टैक के कार्यान्वयन में बड़ी संख्या में त्रुटियां हैं।

sEGFAULT

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

आइटम नुकसान

एक सफल कैस गारंटी नहीं देता है कि इसके निष्पादन के दौरान मेमोरी को नहीं बदला गया है। वह इस बात की गारंटी देता है कि जिस समय उसने इसे फिर से लिखा था, उस समय इसका मूल्य उस मूल्य के बराबर था जो उसे उम्मीद के मुताबिक दिया गया था। दूसरे शब्दों में, यदि आप उस समय CAS (ptr, 5, 6) को कॉल करते हैं, जब ptr में मान पाँच होता है, तो एक और धागा ptr में मान को सात में बदल देता है, और फिर पाँच को वापस, CAS सफल होगा, पाँच से छह को फिर से सेट करेगा। यह एक समस्या को ABA समस्या के रूप में जाना जा सकता है। निम्नलिखित उदाहरण पर विचार करें:

मान लीजिए कि स्टैक पर दो तत्व हैं, ए -> सी।

स्ट्रीम 1 कॉल पॉप, पंक्ति 22 पर m_head (A) पढ़ता है, लाइन 26 पर old_head-> अगला (C) पढ़ता है, और फिर ऑपरेटिंग सिस्टम स्ट्रीम को euthanizes।
थ्रेड 2 पॉप कहता है, और ए तत्व को सफलतापूर्वक हटाता है।
थ्रेड 2 पुश को कॉल करता है, और आइटम B को सफलतापूर्वक सम्मिलित करता है।
स्ट्रीम 2 कॉल फिर से पुश करता है, और ए के पते पर स्थित एक तत्व को सम्मिलित करता है जैसे ए (या तो ए जारी किया गया था और फिर उसी पते पर एक और तत्व शुरू किया गया था, या उपयोगकर्ता ने उस तत्व को सम्मिलित करने का फैसला किया, जिसे उसने स्टैक से लिया था। वापस)
स्ट्रीम 1 उठता है और CAS का कारण बनता है। कैस सफल है, इस तथ्य के बावजूद कि इस समय के दौरान, m_head तीन बार बदल गया है! नतीजतन, तत्व बी खो जाता है।

ताला-मुक्त नहीं

C ++ मानक इस बात की गारंटी नहीं देता है कि नए और डिलीट लॉक-फ्री हैं। यदि यह लाइब्रेरी फ़ंक्शंस को लॉक-फ़्री एल्गोरिदम के रूप में विकसित करने का क्या मतलब है जो लॉक-फ़्री नहीं हैं? एल्गोरिदम को लॉक-फ़्री होने के लिए, मेमोरी के साथ काम करना भी लॉक-फ़्री होना चाहिए।

एक साथ स्मृति का उपयोग

यदि किसी स्मृति स्थान में वर्तमान मान 100 है, और थ्रेड्स में से एक वर्तमान में 200 लिख रहा है, और दूसरा थ्रेड इसका मान पढ़ रहा है (मान लीजिए कि इन दो थ्रेड्स के अलावा सिस्टम में कोई अन्य थ्रेड नहीं हैं)। दूसरी धारा क्या पढ़ेगी? यह उचित प्रतीत होता है कि वह या तो 100 या 200 पढ़ेगा। हालांकि, ऐसा नहीं है। C ++ में, वर्णित परिदृश्य अपरिभाषित व्यवहार की ओर ले जाता है, और दूसरा सूत्र सैद्धांतिक रूप से 42 पढ़ सकता है। C ++ 11 से पहले, लोगों ने उन चर के लिए अस्थिरता का उपयोग किया था जिन्हें एक साथ एक्सेस किया जा सकता था, लेकिन वास्तव में इस उद्देश्य के लिए अस्थिर का उपयोग कभी नहीं किया जाना चाहिए। ।
पुश और पॉप के हमारे कार्यान्वयन में, दोनों ने m_head को पढ़ा और लिखा है, इस प्रकार m_head के प्रत्येक पढ़ने से अपरिभाषित व्यवहार होता है, और वह मान वापस कर सकता है जो कभी भी m_head को नहीं लिखा गया है।

मेमोरी एक्सेस ऑर्डर

यह सर्वविदित है कि कंपाइलर और प्रोसेसर दोनों कमांड के निष्पादन के क्रम को बदल सकते हैं। इस उदाहरण पर विचार करें। X और y दोनों को शून्य होने दें, और फिर दो धागे निम्नलिखित कोड को निष्पादित करते हैं:

स्ट्रीम 1: प्रिंट एक्स; x 1 है; प्रिंट y;
स्ट्रीम 2: प्रिंट y; y = 1; प्रिंट x;

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

तो आप लॉक-फ्री स्टैक कैसे लिखते हैं?

वर्णित अधिकांश समस्याओं में एक से अधिक समाधान हैं। यहां वे समाधान हैं जो हम अपने काम में स्टैक के लिए और अन्य डेटा संरचनाओं के लिए उपयोग करते हैं।

sEGFAULT

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

आइटम नुकसान

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

ताला-मुक्त नहीं

स्मृति की संस्था के साथ समस्या को हल करने के लिए, आप सिर्फ मेमोरी शुरू नहीं कर सकते। हमारे कोड में, हम सीधे तत्व संरचना में अगले तत्व के लिए एक पॉइंटर स्टोर करते हैं। लेकिन यह हमेशा एक स्वीकार्य समाधान नहीं है, क्योंकि यह प्रति तत्व 8 बाइट्स का उपभोग करता है, भले ही वह तत्व स्टैक पर न हो।

एक साथ स्मृति का उपयोग

हम चर :: परमाणु के लिए उपयोग करते हैं जिन्हें कई थ्रेड से एक्सेस किया जा सकता है। यद्यपि हम जो कंपाइलर (g ++ 4.6) का उपयोग करते हैं, उसमें पहले से ही std :: atomic का क्रियान्वयन है, यह बढ़ावा देने की तुलना में काफी कम कुशल है :: atomic, क्योंकि यह प्रत्येक ऑपरेशन के बाद memory_barrier का उपयोग करता है, भले ही इसके बाद memory_barrier की आवश्यकता न हो।

मेमोरी एक्सेस ऑर्डर

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

अधिग्रहण / रिलीज क्या है

अधिग्रहण / रिलीज़ गारंटी को निम्न परिदृश्य द्वारा वर्णित किया जा सकता है: यदि स्ट्रीम 1 ने रिलीज़ गारंटी के साथ चर ए को बदल दिया, और फिर रिलीज़ गारंटी के साथ चर बी, और स्ट्रीम 2 ने गारंटी के साथ बी को पढ़ा, और स्ट्रीम 1 द्वारा रिकॉर्ड किए गए मूल्य को देखा, तो यह गारंटी है कि यदि तब स्ट्रीम 2 अधिग्रहण की गारंटी के साथ ए पढ़ता है, फिर यह स्ट्रीम 1 द्वारा किए गए बदलाव को देखेगा।

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

थ्रेड 1 पॉप निष्पादित करने के लिए तैयार करता है और स्टैक के शीर्ष को पढ़ता है
थ्रेड 1 अपने स्थानीय पॉइंटर को स्टैक के ऊपर लिखता है (रिलीज़ गारंटी का उपयोग करके)
थ्रेड 1 स्टैक के शीर्ष को फिर से पढ़ता है, यह बदल नहीं गया है
स्ट्रीम 2 स्टैक के शीर्ष को हटा देता है, और इसे हटाने का निर्णय लेता है (या इसे हटाने की कतार में जोड़ता है, और दूसरा धागा इसे हटाने का निर्णय लेता है - चलो तत्व को हटाने वाली धारा को स्ट्रीम 3 कहते हैं )
थ्रेड 3 अधिग्रहण की गारंटी के साथ स्थानीय पॉइंटर्स की एक सरणी को पढ़ता है। यहां एक ब्रेकडाउन होता है - यह गारंटी नहीं है कि हम स्ट्रीम 1 द्वारा किए गए परिवर्तन को देखते हैं।
थ्रेड 3 मेमोरी को हटाता है।
थ्रेड 1 dereferences स्टैक के संग्रहीत शीर्ष को हटा दिया गया है और SegFault के साथ क्रैश होता है।

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

उत्पादकता

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

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

यह देखना दिलचस्प है कि विभिन्न कार्यान्वयन कितने संसाधनों का उपभोग करते हैं:
यह है कि एचटीओपी 16 थ्रेड्स में बिना सोचे-समझे लॉक-स्टैक के साथ चलता है:

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

इस तरह से HTOP 16 धागे में लॉक के साथ लॉक-फ्री स्टैक के साथ चलता है:

प्रोसेसर लगभग निष्क्रिय है। थ्रेड्स जो प्रोसेसर पर कब्जा किए बिना तुरंत शीर्ष नींद को बदलने में विफल रहते हैं। यह एक अद्भुत अवलोकन है - usleep के जोड़ ने न केवल उपयोगी प्रदर्शन को 10 गुना बढ़ा दिया, बल्कि सीपीयू की खपत को भी काफी कम कर दिया।

यह है कि 16 धागे में ताले के साथ एचटीओपी कैसे दिखता है:

यहां आप स्पष्ट रूप से देख सकते हैं कि प्रोसेसर पूरी तरह से सिस्टम कॉल द्वारा कब्जा कर लिया गया है। दूसरे शब्दों में, लगभग सभी प्रोसेसर समय ताले के साथ काम करते हुए बिताए गए थे।

निष्कर्ष

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

कोड

स्रोत कोड

ताले के साथ:

  1 #include <mutex> 2 #include <stack> 3 4 template<class T> 5 class LockedStack{ 6 public: 7 void Push(T* entry){ 8 std::lock_guard<std::mutex> lock(m_mutex); 9 m_stack.push(entry); 10 } 11 12 // For compatability with the LockFreeStack interface, 13 // add an unused int parameter. 14 // 15 T* Pop(int){ 16 std::lock_guard<std::mutex> lock(m_mutex); 17 if(m_stack.empty()){ 18 return nullptr; 19 } 20 T* ret = m_stack.top(); 21 m_stack.pop(); 22 return ret; 23 } 24 25 private: 26 std::stack<T*> m_stack; 27 std::mutex m_mutex; 28 };

कोई लॉक नहीं (मेमोरी साफ़ करने के लिए ज़िम्मेदार कोड में कोई तर्क नहीं है)

  1 class LockFreeStack{ 2 public: 3 //      Node 4 // 5 struct Node{ 6 boost::atomic<Node*> next; 7 }; 8 9 10 //  ,  -    . 11 //     gcc   x86_64. 12 // 13 class TaggedPointer{ 14 public: 15 TaggedPointer(): m_node(nullptr), m_counter(0) {} 16 17 Node* GetNode(){ 18 return m_node.load(boost::memory_order_acquire); 19 } 20 21 uint64_t GetCounter(){ 22 return m_counter.load(boost::memory_order_acquire); 23 } 24 25 bool CompareAndSwap(Node* oldNode, uint64_t oldCounter, Node* newNode, uint64_t newCounter){ 26 bool cas_result; 27 __asm__ __volatile__ 28 ( 29 "lock;" 30 "cmpxchg16b %0;" 31 "setz %3;" 32 33 : "+m" (*this), "+a" (oldNode), "+d" (oldCounter), "=q" (cas_result) 34 : "b" (newNode), "c" (newCounter) 35 : "cc", "memory" 36 ); 37 return cas_result; 38 } 39 private: 40 boost::atomic<Node*> m_node; 41 boost::atomic<uint64_t> m_counter; 42 } 43 //   16      double cas 44 // 45 __attribute__((aligned(16))); 46 47 48 bool TryPushStack(Node* entry){ 49 Node* oldHead; 50 uint64_t oldCounter; 51 52 oldHead = m_head.GetNode(); 53 oldCounter = m_head.GetCounter(); 54 entry->next.store(oldHead, boost::memory_order_relaxed); 55 return m_head.CompareAndSwap(oldHead, oldCounter, entry, oldCounter + 1); 56 } 57 58 bool TryPopStack(Node*& oldHead, int threadId){ 59 oldHead = m_head.GetNode(); 60 uint64_t oldCounter = m_head.GetCounter(); 61 if(oldHead == nullptr){ 62 return true; 63 } 64 m_hazard[threadId*8].store(oldHead, boost::memory_order_seq_cst); 65 if(m_head.GetNode() != oldHead){ 66 return false; 67 } 68 return m_head.CompareAndSwap(oldHead, oldCounter, oldHead->next.load(boost::memory_order_acquire), oldCounter + 1); 69 } 70 71 void Push(Node* entry){ 72 while(true){ 73 if(TryPushStack(entry)){ 74 return; 75 } 76 usleep(250); 77 } 78 } 79 80 Node* Pop(int threadId){ 81 Node* res; 82 while(true){ 83 if(TryPopStack(res, threadId)){ 84 return res; 85 } 86 usleep(250); 87 } 88 } 89 90 private: 91 TaggedPointer m_head; 92 //          93 //   -,      . 94 // 95 boost::atomic<Node*> m_hazard[MAX_THREADS*8]; 96 };

बेंचमार्क कोड भी जीथब पर उपलब्ध है (यदि आप स्थानीय स्तर पर परीक्षण चलाना चाहते हैं):

https://github.com/memsql/lockfree-bench

अपडेट:

सुझाव पर, गुमशुदा ने बेंचमार्क के लिए std :: mutex के बजाय स्पिनलॉक के साथ एक स्टैक जोड़ा। प्रयोग की शुद्धता के लिए, मैंने स्पिनलॉक का उपयोग किया, जो लॉकफ्री कार्यान्वयन की तरह, 250 मिलीसेकंड सोता है यदि पहली कोशिश में लॉक को पकड़ना संभव नहीं है। अप्रत्याशित रूप से, ऐसा कार्यान्वयन लॉक-फ्री कार्यान्वयन की तुलना में अधिक उत्पादक निकला, और std :: mutex के साथ कार्यान्वयन। सीपीयू की खपत नेत्रहीन रूप से usleep (250) के साथ लॉक-फ्री कार्यान्वयन के समान है।

एक नए कार्यान्वयन के साथ जीथब रिपॉजिटरी को भी अपडेट किया गया है।

लॉकफ्री एल्गोरिदम और उनके समाधान विकसित करते समय सामान्य गलतियां

sEGFAULT

आइटम नुकसान

ताला-मुक्त नहीं

एक साथ स्मृति का उपयोग

मेमोरी एक्सेस ऑर्डर

तो आप लॉक-फ्री स्टैक कैसे लिखते हैं?

sEGFAULT

आइटम नुकसान

ताला-मुक्त नहीं

एक साथ स्मृति का उपयोग

मेमोरी एक्सेस ऑर्डर

उत्पादकता

निष्कर्ष

कोड

अपडेट:

More articles: