लॉक-फ्री डेटा स्ट्रक्चर्स। सिद्धांत: परमाणु और परमाणु आदिम

लॉक-फ्री डेटा संरचनाओं का निर्माण दो स्तंभों पर आधारित है - परमाणु संचालन और स्मृति तक पहुंच को व्यवस्थित करने के तरीके। यह लेख परमाणु और परमाणु प्रधानता पर ध्यान केंद्रित करेगा।

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

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

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

तुलना करें और स्वैप

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

bool CAS( int * pAddr, int nExpected, int nNew ) atomically { if ( *pAddr == nExpected ) { *pAddr = nNew ; return true ; } else return false ; } 

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

 int FAA( int * pAddr, int nIncr ) { int ncur ; do { ncur = *pAddr ; } while ( !CAS( pAddr, ncur, ncur + nIncr ) ; return ncur ; } 

कैस ऑपरेशन का "शैक्षणिक" संस्करण हमेशा अभ्यास में सुविधाजनक नहीं होता है, क्योंकि अक्सर जब कैस विफल रहता है, तो हम इस बात में रुचि रखते हैं कि सेल में अब क्या मूल्य है। इसलिए, कैस के इस तरह के संस्करण को अक्सर माना जाता है (तथाकथित मूल्यवान कैस , जिसे परमाणु रूप से भी प्रदर्शित किया जाता है):

 int CAS( int * pAddr, int nExpected, int nNew ) atomically { if ( *pAddr == nExpected ) { *pAddr = nNew ; return nExpected ; } else return *pAddr } 

C ++ 11 में, compare_exchange फ़ंक्शन (कड़ाई से बोल रहा है, C ++ 11 में ऐसा कोई फ़ंक्शन नहीं है, इसकी किस्में compare_exchange_strong और compare_exchange_weak , लेकिन मैं उनके बारे में बाद में बात करूंगा) इन दोनों विकल्पों में शामिल हैं:

 bool compare_exchange( int volatile * pAddr, int& nExpected, int nNew ); 

nExpected तर्क nExpected संदर्भ द्वारा पारित किया जाता है और इनपुट में pAddr पर चर का अपेक्षित मूल्य और आउटपुट में परिवर्तन से पहले का मान होता है। फ़ंक्शन एक सफलता संकेत देता है: यह true , यदि पते में nExpected का मान शामिल है (इस मामले में यह nNew बदल जाता है), तो यदि यह विफल हो जाता है (तब nExpected पर चर का वर्तमान मान होगा)। कैस ऑपरेशन का ऐसा सार्वभौमिक निर्माण कैस की "अकादमिक" परिभाषा के दोनों संस्करणों को शामिल करता है, लेकिन व्यवहार में, compare_exchange उपयोग त्रुटियों से भरा होता है, क्योंकि आपको याद रखना होगा कि nExpected तर्क संदर्भ द्वारा पारित किया गया है और इसे बदला जा सकता है, जो हमेशा स्वीकार्य नहीं होता है।
compare_exchange का उपयोग करते compare_exchange ऊपर दिखाया गया compare_exchange -और-ऐड आदिम इस तरह लिखा जा सकता है:

 int FAA( int * pAddr, int nIncr ) { int ncur = *pAddr; do {} while ( !compare_exchange( pAddr, ncur, ncur + nIncr ) ; return ncur ; } 

ABA समस्या

CAS आदिम सभी के लिए अच्छा है, लेकिन जब इसे लागू किया जाता है, तो एक गंभीर समस्या संभव है, जिसे ABA समस्या कहा जाता है । इसका वर्णन करने के लिए, आपको CAS ऑपरेशन का उपयोग करने के एक विशिष्ट पैटर्न पर विचार करना चाहिए:

 int nCur = *pAddr ; while (true) { int nNew =    if ( compare_exchange( pAddr, nCur, nNew )) break; } 

वास्तव में, हम कैस के काम करने तक लूप में "बैंग" करते हैं; लूप आवश्यक है, क्योंकि pAddr पर एक चर के वर्तमान मूल्य को पढ़ने और एक नए मूल्य nNew गणना करने के nNew pAddr पर nNew चर को दूसरे धागे से बदला जा सकता है।


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

यहाँ एक लॉक-फ्री स्टैक का कार्यान्वयन है जो ABA समस्या से ग्रस्त है [Mic04]:

 // Shared variables static NodeType * Top = NULL; // Initially null Push(NodeType * node) { do { /*Push1*/ NodeType * t = Top; /*Push2*/ node->Next = t; /*Push3*/ } while ( !CAS(&Top,t,node) ); } NodeType * Pop() { Node * next ; do { /*Pop1*/ NodeType * t = Top; /*Pop2*/ if ( t == null ) /*Pop3*/ return null; /*Pop4*/ next = t->Next; /*Pop5*/ } while ( !CAS(&Top,t,next) ); /*Pop6*/ return t; } 

क्रियाओं के निम्नलिखित अनुक्रम में स्टैक संरचना का उल्लंघन होता है (ध्यान दें कि यह क्रम ABA समस्या को दर्शाने वाला एकमात्र नहीं है):

थ्रेड एक्स	थ्रेड वाई
Pop() कॉल Pop() । हो गया लाइन Pop4 , चर मान: t == A next == A->next
	NodeType * pTop = Pop() pTop == ढेर के ऊपर, अर्थात् ए Pop() Push( pTop ) अब ढेर का शीर्ष फिर से ए है ध्यान दें कि A->next बदल गया है
लाइन Pop5 । कैस सफल है, लेकिन Top->next क्षेत्र है का मान दिया स्टैक पर कोई नहीं थ्रेड वाई के बाद से स्टैक ए और A->next , और स्थानीय चर next पुराने मूल्य A->next संग्रहीत करता है

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

• पहला चरण ताला-मुक्त कंटेनर से एक तत्व का बहिष्करण है;
• दूसरा चरण (आस्थगित) किसी तत्व का भौतिक निष्कासन है जब इसका कोई संदर्भ नहीं होता है।

मैं निम्नलिखित लेखों में से एक में विभिन्न आस्थगित विलोपन योजनाओं पर ध्यान केंद्रित करूंगा।

लोड-लिंक्ड / स्टोर-कंडिशनल

संभवतः, जब ABA समस्या से प्रभावित नहीं होने वाले अन्य RMW प्रचालनों की तलाश के लिए CAS डिज़ाइनरों को प्रेरित करने के लिए CAS डिज़ाइन करते समय ABA समस्या की उपस्थिति होती है। और ऐसे ऑपरेशन पाए गए - लोड-लिंक्ड / स्टोर-सशर्त (एलएल / एससी) की एक जोड़ी। ये ऑपरेशन बहुत सरल हैं - यहाँ उनका छद्म कोड है:

 word LL( word * pAddr ) { return *pAddr ; } bool SC( word * pAddr, word New ) { if (   pAddr      LL) { *pAddr = New ; return true ; } else return false ; } 

LL / SC जोड़ी ऑपरेटर कोष्ठक के रूप में काम करती है। लोड-लिंक्ड (एलएल) ऑपरेशन केवल चर के मौजूदा मूल्य को pAddr पर pAddr । स्टोर-सशर्त (एससी) ऑपरेशन पहले से पढ़े गए एलएल ऑपरेशन पते pAddr को बचाता है केवल अगर pAddr में डेटा pAddr नहीं बदला है जब से पढ़ा गया था। इस स्थिति में, एक परिवर्तन कैश लाइन के किसी भी संशोधन को संदर्भित करता है जिसमें pAddr पता pAddr । एलएल / एससी जोड़ी को लागू करने के लिए, प्रोसेसर डेवलपर्स को कैश संरचना को बदलना पड़ा: मोटे तौर पर, प्रत्येक कैश लाइन में एक अतिरिक्त स्थिति बिट होनी चाहिए। जब एलएल ऑपरेशन द्वारा पढ़ा जाता है, तो यह बिट सेट (लिंक) होता है, कोई भी कैश लाइन को लिखता है (या इसे कैश से बाहर धकेलता है) बिट को साफ करता है, और एससी ऑपरेशन चेक को बचाने से पहले यह देखने के लिए कि यह बिट कैश लाइन पर सेट है या नहीं - यदि बिट = 1, तो कैश लाइन को किसी ने नहीं बदला है, pAddr पर मान को एक नए pAddr बदल दिया गया है और SC ऑपरेशन सफल है, अन्यथा ऑपरेशन असफल है, pAddr पर मान नहीं बदलता है।

CAS आदिम को LL / SC जोड़े का उपयोग करके इस तरह लागू किया जा सकता है:

 bool CAS( word * pAddr, word nExpected, word nNew ) { if ( LL( pAddr ) == nExpected ) return SC( pAddr, nNew ) ; return false ; } 

ध्यान दें, इस कोड की बहु-चरण प्रकृति के बावजूद, यह परमाणु कैस करता है: लक्ष्य मेमोरी सेल की सामग्री या तो नहीं बदलती है या परमाणु रूप से बदलती है। आर्किटेक्चर पर एक एलएल / एससी जोड़ी लागू करना जो केवल कैस आदिम का समर्थन करता है, लेकिन संभव नहीं है कि आदिम हो; मैं यहाँ इस पर विचार नहीं करूँगा; जो लोग रुचि रखते हैं उन्हें लेख [माइक ०४] में भेजा जाता है।

आधुनिक प्रोसेसर आर्किटेक्चर को दो बड़े शिविरों में विभाजित किया गया है - कुछ अपने कमांड सिस्टम में कैस आदिम का समर्थन करते हैं, अन्य एलएल / एससी की एक जोड़ी का समर्थन करते हैं। CAS को x86, Intel Itanium, Sparc आर्किटेक्चर में लागू किया गया है; आदिम पहली बार आईबीएम सिस्टम 370 वास्तुकला में दिखाई दिया। एलएल / एससी जोड़ी पावरपीसी, एमआइपी, अल्फा, एआरएम आर्किटेक्चर है; पहले DEC द्वारा प्रस्तावित। यह ध्यान देने योग्य है कि आधुनिक आर्किटेक्चर में एलएल / एससी आदिम को सबसे आदर्श तरीके से लागू नहीं किया जाता है: उदाहरण के लिए, आप अलग-अलग पते के साथ नेस्टेड एलएल / एससी कॉल नहीं कर सकते हैं, लिंक किए गए झंडे का गलत रीसेट संभव है (तथाकथित गलत साझाकरण, नीचे देखें), कोई ध्वज सत्यापन आदिम नहीं है LL / SC जोड़ी के अंदर जुड़ा हुआ है।

C ++ की दृष्टि से, C ++ 11 मानक LL / SC जोड़ी पर विचार नहीं करता है, लेकिन इसमें केवल परमाणु compare_exchange (CAS) और उससे प्राप्त होने वाली परमाणु आदिम का वर्णन किया गया है - fetch_add , fetch_sub , exchange , आदि। मानक का अर्थ है कि आप LL का उपयोग करके CAS का उपयोग करते हैं। / SC बहुत सीधा है, लेकिन रिवर्स कार्यान्वयन - LL / SC कैस ​​के माध्यम से - काफी अनुत्तरदायी है। इसलिए, मानक C ++ लाइब्रेरी के डेवलपर्स के जीवन को जटिल नहीं करने के लिए, C ++ में शुरू की गई मानकीकरण समिति केवल compare_exchange , जो सिद्धांत रूप में, लॉक-फ्री एल्गोरिदम को लागू करने के लिए पर्याप्त है।

गलत बंटवारा

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


यदि अलग-अलग साझा किए गए डेटा एक कैशे लाइन में आते हैं (यानी, वे आस-पास के पते में स्थित हैं), तो प्रोसेसर के दृष्टिकोण से, एक ही कैशे लाइन में स्थित अन्य को अमान्य करने के लिए, डेटा लीड में से एक को बदलते हैं। इस स्थिति को झूठी साझाकरण कहा जाता है। LL / SC आदिमियों के लिए, झूठी साझाकरण विनाशकारी है, क्योंकि इन प्राथमिकताओं को कैश लाइनों के संदर्भ में लागू किया जाता है: लोड-लिंक्ड ऑपरेशन कैश लाइन (लिंक) को चिह्नित करता है, और स्टोर-कंडीशनल ऑपरेशन चेक लिखने से पहले यह पता लगाता है कि क्या इस लाइन का लिंक फ्लैग क्लियर किया गया है ; यदि ध्वज साफ़ हो जाता है, तो कोई प्रविष्टियाँ नहीं की जाती हैं और SC गलत साबित होता है चूंकि एल लाइन की लंबाई काफी बड़ी है, इसलिए एससी आदिम (यानी लिंक फ्लैग को रीसेट करना) की एक झूठी विफलता कैश लाइन में किसी भी बदलाव के साथ होती है जो लक्ष्य डेटा से संबंधित नहीं है। नतीजतन, हम लाइवलॉक प्राप्त कर सकते हैं: एक ऐसी स्थिति जहां प्रोसेसर / कोर 100% व्यस्त हैं, लेकिन कोई प्रगति नहीं है।

झूठी साझाकरण के खिलाफ लड़ाई काफी सरल है (लेकिन बेकार): प्रत्येक साझा चर को पूरी कैश लाइन पर कब्जा करना चाहिए; इसके लिए, पैडिंग का उपयोग आमतौर पर किया जाता है:

 struct Foo { int volatile nShared1; char _padding1[64]; // padding for cache line=64 byte int volatile nShared2; char _padding2[64]; // padding for cache line=64 byte }; 

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

किस्म के कैस

मैं संक्षेप में दो और उपयोगी परमाणु आदिम - कैस डबल चौड़ाई (डबल-वर्ड कैस, dwCAS) और डबल कैस (DCAS) पर ध्यान केंद्रित करूंगा।

डबल-चौड़ाई कैस नियमित सीएएस के समान है, लेकिन डबल-बिट मेमोरी सेल के साथ संचालित होता है: 64-बिट 32-बिट आर्किटेक्चर के लिए और 128-बिट (अधिक सटीक, कम से कम 96-बिट) के लिए 64-बिट। ऐसे आर्किटेक्चर के लिए जो CAS के बजाय LL / SC की जोड़ी प्रदान करते हैं, LL / SC को डबल-लेंथ शब्दों पर भी काम करना चाहिए। मुझे पता है कि आर्किटेक्चर में, केवल x86 dwCAS का समर्थन करता है। यह आदिम इतना उपयोगी क्यों है? यह आपको ABA समस्या को हल करने के लिए पहली योजनाओं में से एक को व्यवस्थित करने की अनुमति देता है - टैग किए गए संकेत । यह योजना आईबीएम ने एबीए समस्या को हल करने के लिए प्रस्तावित की थी और पूर्णांक के साथ प्रत्येक टैग पॉइंटर के मिलान में शामिल थी; टैग किए गए सूचक को निम्न संरचना द्वारा वर्णित किया जा सकता है:

 template <typename T> struct tagged_pointer { T * ptr ; uintptr_t tag ; tagged_pointer() : ptr( new T ) , tag( 1 ) {} }; 

परमाणुता सुनिश्चित करने के लिए, इस प्रकार के चर डबल-संरेखित होने चाहिए: 32-बिट आर्किटेक्चर के लिए 8 बाइट और 64-बिट के लिए 16 बाइट्स। टैग में ptr द्वारा इंगित डेटा का "संस्करण संख्या" होता है। मैं सुरक्षित मेमोरी रिक्लेमेशन (SMR) पर निम्नलिखित लेखों में से एक में विस्तार से टैग किए गए बिंदुओं के बारे में बात करूंगा, लेकिन यहां मैं केवल इस तथ्य पर ध्यान दूंगा कि टैग किए गए संकेत का अर्थ है कि टाइप टी के डेटा के लिए आवंटित की गई मेमोरी (और संबंधित tagged_pointer ) भौतिक रूप से नष्ट नहीं किया जाना चाहिए ( delete ), लेकिन एक मुक्त-सूची (प्रत्येक प्रकार के टी के लिए अलग) में रखा जाना चाहिए, जिसमें से भविष्य में टैग को बढ़ाने के साथ डेटा को फिर से वितरित किया जाएगा। यह वही है जो एबीए समस्या का समाधान देता है: वास्तव में, सूचक समग्र है और टैग में संस्करण संख्या (वितरण की क्रम संख्या) शामिल है; इस मामले में, dwCAS सफल नहीं होगा यदि इसके प्रकार के टैग किए tagged_pointer तर्क समान tagged_pointer और टैग मान भिन्न हैं।

दूसरा परमाणु आदिम - डबल कैस (DCAS) - वर्तमान में विशुद्ध रूप से काल्पनिक है और इसे किसी भी आधुनिक तकनीकी आर्किटेक्चर में लागू नहीं किया गया है। DCAS छद्म कोड निम्नानुसार है:

 bool DCAS( int * pAddr1, int nExpected1, int nNew1, int * pAddr2, int nExpected2, int nNew2 ) atomically { if ( *pAddr1 == nExpected1 && *pAddr2 == nExpected2 ) { *pAddr1 = nNew1 ; *pAddr2 = nNew2 ; return true ; } else return false } 

डीसीएएस दो मनमाने ढंग से संरेखित मेमोरी कोशिकाओं पर कार्य करता है और दोनों में मानों को बदलता है यदि वर्तमान मान अपेक्षित हैं।

यह आदिम इतना दिलचस्प क्यों है? तथ्य यह है कि इसकी मदद से एक लॉक-फ्री डबलली लिंक्ड लिस्ट (deque, डबल-लिंक्ड लिस्ट) का निर्माण करना काफी आसान है, और इस तरह की डेटा संरचना कई दिलचस्प एल्गोरिदम का आधार है। डीसीएएस-आधारित डेटा संरचनाओं पर बड़ी संख्या में शैक्षणिक पेपर हैं। हालाँकि यह आदिम "हार्डवेयर" में लागू नहीं किया गया है, वहाँ काम कर रहे हैं (उदाहरण के लिए, [Fra03] - उनमें से सबसे प्रसिद्ध) जो DCAS के निर्माण के लिए एल्गोरिथ्म का वर्णन करते हैं (और आमतौर पर मल्टी-कैस कितने pAddr1 ... pAddrN पते pAddrN ) सामान्य कैस के आधार पर।

उत्पादकता

और परमाणु आदिमों के प्रदर्शन के बारे में क्या?
आधुनिक प्रोसेसर इतने जटिल और अप्रत्याशित हैं कि निर्माता कुछ निर्देशों की अवधि की कोई निश्चित गारंटी नहीं देते हैं, विशेष रूप से परमाणु वाले, जिसमें आंतरिक तुल्यकालन, प्रोसेसर बसों पर सिग्नलिंग आदि शामिल हैं। इसमें काफी संख्या में काम हैं जिनमें लेखक प्रयास करते हैं। प्रोसेसर निर्देशों की अवधि को मापें। मैं [McKen05] से माप दूंगा। इस काम में, लेखक, अन्य बातों के अलावा, परमाणु वृद्धि की अवधि और कैस आदिम की तुलना nop (नो-ऑपरेशन) ऑपरेशन की अवधि के साथ करते हैं। तो, इंटेल Xeon 3.06 GHz (2005 नमूना) के लिए, परमाणु वृद्धि की अवधि 400 एनओपी, कैस - 850 - 1000 एनओपी है। आईबीएम पावर 4 प्रोसेसर 1.45 गीगाहर्ट्ज: परमाणु वृद्धि के लिए 180 एनओपी और कैस के लिए 250 एनओपी। माप काफी पुराने हैं (2005), पिछली बार की तुलना में प्रोसेसर आर्किटेक्चर ने कुछ और कदम आगे बढ़ाए हैं, लेकिन संख्याओं का क्रम, मुझे लगता है, वही बना हुआ है।

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

अस्थिर और परमाणु

C ++ में क्रिप्टिक volatile कीवर्ड है। कभी-कभी volatile परमाणुता और ऑर्डरिंग volatile जुड़ी होती है - यह गलत है, लेकिन इसके कुछ ऐतिहासिक कारण हैं।
वास्तव में, volatile केवल गारंटी देता है कि संकलक रजिस्टर में मूल्य को कैश नहीं करेगा (संकलनकर्ता को ऐसा करने के लिए प्यार करना पसंद है: अधिक रजिस्टर, वे जितना अधिक कैश करते हैं)। अर्थात, वाष्पशील चर को पढ़ना हमेशा स्मृति से पढ़ना होता है, वाष्पशील चर को लिखने का अर्थ हमेशा स्मृति से लिखना होता है। इसलिए, यदि कोई समानांतर में अस्थिर डेटा को बदलता है, तो हम इसे तुरंत देखेंगे।
वास्तव में, हम नहीं देखेंगे। स्मृति बाधाओं की कमी के कारण। कुछ भाषाओं में (Java, C #) volatile एक जादुई स्थिति सौंपी जाती है जो क्रमबद्धता प्रदान करती है, लेकिन C ++ 11 में नहीं। और volatile किसी विशेष संरेखण की गारंटी नहीं देता है, और हम अब जानते हैं कि डेटा संरेखण के लिए सही स्थिति परमाणुता के लिए एक आवश्यक शर्त है।
इस प्रकार, C ++ 11-संगत कंपाइलर के लिए, परमाणु चर के लिए volatile को निर्दिष्ट करना अनावश्यक है। लेकिन पुराने कंपाइलर के लिए यह कभी-कभी आवश्यक होता है यदि आप स्वयं atomic लागू करते हैं। ऐसे विज्ञापन में:

 class atomic_int { int m_nAtomic; //…. }; 

कंपाइलर को m_nAtomic को "ऑप्टिमाइज़" करने का हर अधिकार है (इस तथ्य के बावजूद कि कॉल अप्रत्यक्ष रूप से this माध्यम से है)। इसलिए, int volatile m_nAtomic को इंगित करना int volatile m_nAtomic होगा।

libcds

निष्कर्ष में, हमारे पास लिबकस लाइब्रेरी में क्या है? और हमारे पास x86 / amd64, Intel Itanium और Sparc आर्किटेक्चर के लिए C ++ 11 की भावना में परमाणु आदिम का एक और बाइक कार्यान्वयन है। यदि संकलक C ++ 11 का समर्थन नहीं करता है (और केवल संकलक के नवीनतम संस्करण इसका समर्थन करते हैं - मेरे लिए उपलब्ध जीसीसी 4.7+, एमएस विज़ुअल सी ++ 2012, क्लैंग 3.0+), तो यह libcdsपरमाणु प्राइमेटिक्स के अपने स्वयं के कार्यान्वयन का उपयोग करता है। एक ही समय में, सामान्य परमाणु रीड / राइट के अलावा लॉक-फ्री डेटा संरचनाओं के निर्माण में मुख्य परमाणु आदिम, कैस है, बहुत कम ही जहां कैस का उपयोग दोहरे शब्द (dwCAS) से अधिक किया जाता है। DCAS कार्यान्वयन (और आमतौर पर मल्टी-कैस) मेंlibcds[अभी के लिए] नहीं, लेकिन यह बहुत संभव है कि भविष्य में दिखाई देगा - इस पर बहुत दिलचस्प डेटा संरचनाएं बनाई जा सकती हैं। यह केवल यही रुकता है, कई अध्ययनों के अनुसार, [Fra03] एल्गोरिथ्म के अनुसार DCAS का कार्यान्वयन अक्षम है। लेकिन मैंने पहले ही नोट किया कि प्रभावशीलता की कसौटी लॉक-फ्री दुनिया में एक सख्ती से व्यक्तिगत चीज है: इस हार्डवेयर पर अब क्या अप्रभावी है और इस कार्य के लिए एक अन्य हार्डवेयर या किसी अन्य कार्य के लिए अत्यंत प्रभावी हो सकता है! फंडामेंटल

के अगले लेख में , हम मेमोरी एक्सेस (मेमोरी ऑर्डरिंग) - मेमोरी बैरियर (मेमोरी बाड़, मेमोरी बैरियर) के बारे में बात करेंगे। Ref

:

[Cha05] डीन चैंडलर ने .NET , 2005, Intel Corporation

[Fra03] में अमीर शेसर के लिए गलत शेयरिंग को कम कियाप्रैक्टिकल लॉक फ्रीडम , 2004; तकनीकी रिपोर्ट के। फ्रेजर द्वारा कैम्ब्रिज विश्वविद्यालय, किंग्स कॉलेज

[डॉक्टर McKen05] पॉल मैककेनी, थॉमस हार्ट, जोनाथन वालपैन प्रैक्टिकल चिंताएँ के लिए स्केलेबल सिंक्रोनाइज़ेशन के लिए डॉक्टर की डिग्री के लिए सितंबर 2003 में प्रस्तुत एक शोध पर आधारित है। एबीए रोकथाम एकल-शब्द निर्देश , आईबीएम रिसर्च रिपोर्ट, 2004 का उपयोग करते हुए