लॉक-फ्री डेटा स्ट्रक्चर्स। थ्योरी: मेमोरी मॉडल

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

इस लेख में, हम C ++ 11 मेमोरी मॉडल को देखेंगे।


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

• क्रमिक संगति
• अधिग्रहित / जारी करना
• आराम स्मृति आदेश

इन सभी मेमोरी मॉडल को C ++ में एक एन्यूमरेशन - std::memory_order साथ परिभाषित किया गया है, जिसमें निम्नलिखित 6 स्थिरांक हैं:

• memory_order_seq_cst - क्रमिक सुसंगत मॉडल को इंगित करता है
• memory_order_acquire , memory_order_release , memory_order_acq_rel , memory_order_consume - अधिग्रहण / विमोचन के आधार पर एक मॉडल का संदर्भ लें
• memory_order_relaxed - एक आराम मॉडल को इंगित करता है

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

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

यहां बताया गया है कि atomic<T> संचालन वास्तव में कैसा दिखता है: std::atomic<T> प्रत्येक विशेषज्ञता std::atomic<T> वर्ग में कम से कम विधियां होनी चाहिए

 void store(T, memory_order = memory_order_seq_cst); T load(memory_order = memory_order_seq_cst) const; T exchange(T, memory_order = memory_order_seq_cst); bool compare_exchange_weak(T&, T, memory_order = memory_order_seq_cst); bool compare_exchange_strong(T&, T, memory_order = memory_order_seq_cst); 

जैसा कि आप देख सकते हैं, C ++ 11 में डिफ़ॉल्ट मेमोरी मॉडल अनुक्रमिक स्थिरता है। हम पहले इस पर विचार करेंगे। लेकिन पहले, संकलक बाधाओं के बारे में कुछ शब्द।

संकलक बाधाएँ

हमारे द्वारा लिखे गए कोड को कौन फिर से व्यवस्थित कर सकता है? हमें पता चला कि प्रोसेसर ऐसा कर सकता है। लेकिन फिर से व्यवस्थित करने का एक और स्रोत है - संकलक।
एकल-थ्रेडेड निष्पादन की धारणा (शायद निहित) के तहत अनुकूलन के कई तरीके (विशेष रूप से वैश्विक) और हेयुरिस्टिक्स विकसित किए गए (और अभी भी विकसित किए जा रहे हैं)। कंपाइलर (बल्कि, सैद्धांतिक रूप से असंभव) के लिए यह समझना काफी मुश्किल है कि आपका कोड मल्टीथ्रेडेड है। इसलिए, संकलक को संकेत - बाधाओं की आवश्यकता होती है। ऐसा अवरोध संकलक को बताता है: अवरोध से पहले कोड को अवरोध के पीछे कोड में स्थानांतरित करने (मिश्रण) करने की हिम्मत न करें और इसके विपरीत। कंपाइलर बैरियर स्वयं कोई कोड उत्पन्न नहीं करता है।
MS Visual C ++ के लिए, कंपाइलर बैरियर छद्म-फ़ंक्शन _ReadWriteBarrier() (यह नाम हमेशा मुझे चकित करता है: मेमोरी बैरियर को पढ़ने / लिखने के साथ पूर्ण संबंध - सबसे भारी मेमोरी बैरियर)। जीसीसी और क्लैंग के लिए, यह एक चिकना डिजाइन है
__asm__ __volatile__ ( "" ::: "memory" )

यह ध्यान दिया जाना चाहिए कि कोडांतरक __asm__ __volatile__ ( … ) किसी तरह से GCC / __asm__ __volatile__ ( … ) लिए एक बाधा है: कंपाइलर को कोड में या तो उन्हें नीचे फेंकने या ऊपर ले जाने का कोई अधिकार नहीं है ( __volatile__ संशोधक __volatile__ )।
memory_order कंपाइलर को प्रभावित करते हैं जो C ++ 11 को प्रोसेसर की तरह सपोर्ट करते हैं - वे एक कंपाइलर बैरियर हैं, जो कंपाइलर की क्षमता को पुन: व्यवस्थित करने (यानी ऑप्टिमाइज) करने के लिए हमारे कोड को सीमित करता है। इसलिए, विशेष संकलक अवरोधों को निर्दिष्ट करने की आवश्यकता नहीं है, जब तक कि निश्चित रूप से, संकलक नए मानक का पूरी तरह से समर्थन करता है।

अनुक्रमिक संगति

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

 // Thread 1 atomic<int> a, b ; a.store( 5 ); int vb = b.load(); // Thread 2 atomic<int> x,y ; int vx = x.load() ; y.store( 42 ) ; 

अनुक्रमिक स्थिरता के लिए मान्य कोई भी निष्पादन स्क्रिप्ट है, सिवाय इसके कि स्वैप a.store / b.load और x.load / y.store । ध्यान दें कि इस कोड में मैं लोड / स्टोर में memory_order तर्क को स्पष्ट रूप से memory_order नहीं memory_order - मैं डिफ़ॉल्ट तर्क मान पर भरोसा करता हूं।
सटीक रूप से एक ही गारंटी संकलक पर लागू होती है: संकलक को हमारे कोड को इस तरह से पुनः व्यवस्थित करने के लिए मना किया जाता है कि memory_order_seq_cst बाद संचालन इस बाधा से ऊपर चला जाएगा, और इसके विपरीत - se__stst- बाधा से पहले संचालन को बाधा से नीचे छोड़ा नहीं जा सकता है।
अनुक्रमिक स्थिरता मॉडल सहज रूप से मनुष्यों के करीब है, लेकिन इसमें एक बहुत महत्वपूर्ण दोष है: यह आधुनिक प्रोसेसर के लिए बहुत सख्त है। यह सबसे गंभीर मेमोरी बाधाओं की ओर जाता है, प्रोसेसर को पूरी तरह से सट्टा निष्पादन का उपयोग करने की अनुमति नहीं देता है। इसलिए, नए C ++ मानक ने ऐसा समझौता अपनाया:

• अनुक्रमिक स्थिरता मॉडल को अपनी कठोरता और स्पष्टता के लिए परमाणु संचालन के लिए डिफ़ॉल्ट मॉडल के रूप में लिया जाना चाहिए।
• C ++ में अन्य, कमजोर मेमोरी मॉडल का परिचय दें जो आधुनिक आर्किटेक्चर की क्षमता को महसूस करने में मदद करते हैं

अनुक्रमिक स्थिरता के अलावा, अधिग्रहित / रिलीज शब्दार्थ पर आधारित एक मॉडल प्रस्तावित किया गया था।

एक्वायर्ड / रिलीज़ शब्दार्थ

नाम अधिग्रहण-रिलीज़ शब्दार्थ से, हम यह निष्कर्ष निकाल सकते हैं कि यह शब्दार्थ किसी तरह संसाधनों के अधिग्रहण (अधिग्रहण) और रिलीज़ (रिलीज़) से संबंधित है। वास्तव में यह है। किसी संसाधन को कैप्चर करना इसे मेमोरी से रजिस्टर करने के लिए पढ़ना है, इसे जारी करना, रजिस्टर से मेमोरी में लिखना है:

 load memory, register ; membar #LoadLoad | #LoadStore ; // acquire- //   acquire/release- ... membar #LoadStore | #StoreStore ; // release- store regiser, memory ; 

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

संभवतः अधिग्रहित / विमोचन का सबसे सरल उदाहरण स्पिन-लॉक है।

यह सबसे सरल स्पिन-लॉक है जो अधिग्रहण / रिलीज पर दिखता है (C ++ विशेषज्ञ इंगित करेंगे कि स्पिन-लॉक को लागू करने के लिए एक विशेष प्रकार के atomic_flag का उपयोग किया जाना चाहिए, लेकिन मैं परमाणु-चर पर स्पिन-लॉक का निर्माण करूंगा (एक बूलियन भी नहीं) - यह इस दृष्टिकोण से अधिक दृश्य है लेख):

 class spin_lock { atomic<unsigned int> m_spin ; public: spin_lock(): m_spin(0) {} ~spin_lock() { assert( m_spin.load(memory_order_relaxed) == 0);} void lock() { unsigned int nCur; do { nCur = 0; } while ( !m_spin.compare_exchange_weak( nCur, 1, memory_order_acquire )); } void unlock() { m_spin.store( 0, memory_order_release ); } }; 

ध्यान दें कि इस कोड में, तुलना करने वाली compare_exchange अपने पहले तर्क को संदर्भ द्वारा स्वीकार करती है और इसे बदल देती है यदि CAS असफल है, तो वास्तव में मुझे परेशान करता है! आपको एक गैर-खाली निकाय के साथ do-while लूप लिखना होगा।
lock को महारत हासिल करने की lock विधि में, मैं अधिग्रहण शब्दार्थ का उपयोग करता हूं, और unlock विधि में मैं रिलीज शब्दार्थ का उपयोग करता हूं (वैसे, शब्दार्थ / रिलीज शब्दार्थक ने सिंक्रनाइज़ेशन प्राइमेटिक्स से अपना इतिहास लिया: मानक के डेवलपर्स ने विभिन्न सिंक्रनाइज़ेशन प्राइमेटिक्स के कार्यान्वयन का सावधानीपूर्वक विश्लेषण किया और अधिग्रहण / रिलीज पैटर्न प्राप्त किया। ) जैसा कि मैंने ऊपर लिखा है, इस मामले में रखी गई बाधाएं lock() और unlock() को लीक unlock() बीच संलग्न कोड की अनुमति नहीं देती हैं - यह वही है जो हमें चाहिए! और m_spin वैरिएबल की m_spin हमें गारंटी देती है कि जब तक m_spin=1 , कोई भी लॉक को पकड़ नहीं सकता है, फिर से क्या आवश्यक है!
एल्गोरिथ्म में, हम देखते हैं कि मैं compare_exchange_weak का उपयोग कर रहा compare_exchange_weak । यह क्या है

कमजोर और मजबूत कैस

जैसा कि आपको याद है, प्रोसेसर आर्किटेक्चर दो वर्गों में से एक हो सकता है: या तो प्रोसेसर परमाणु आदिम CAS (तुलना-और-स्वैप), या LL / SC जोड़ी (लोड-लिंक्ड / स्टोर-सशर्त) को लागू करता है। LL / SC जोड़ी आपको परमाणु कैस को लागू करने की अनुमति देती है, लेकिन अपने आप में कई कारणों से परमाणु नहीं है। इनमें से एक कारण यह है कि एलएल / एससी के अंदर चलने वाला कोड ऑपरेटिंग सिस्टम द्वारा बाधित हो सकता है; उदाहरण के लिए, उसी क्षण, OS वर्तमान थ्रेड को बाहर निकालने का निर्णय लेता है। तदनुसार, स्टोर-सशर्त तब, फिर से शुरू होने के बाद, काम नहीं करेगा। यही है, हमारी सीएएस false वापस आ जाएगी, हालांकि वास्तव में इस false का कारण डेटा में नहीं हो सकता है, लेकिन एक थर्ड पार्टी इवेंट में - एक थ्रेड रुकावट।
यह इस विचार पर आधारित था कि मानक के डेवलपर्स ने दो compare_exchange प्राइमेटिव्स को पेश करने के लिए प्रेरित किया - कमजोर और मजबूत। इन compare_exchange_strong compare_exchange_weak और compare_exchange_strong कहा जाता compare_exchange_strong । एक कमजोर संस्करण विफल हो सकता है, अर्थात, false लौटें, भले ही चर का वर्तमान मूल्य अपेक्षित के बराबर हो। अर्थात्, एक कमजोर CAS CAS के शब्दार्थों का उल्लंघन कर सकता है और false वापस कर सकता है जब यह वास्तव में true लौटना आवश्यक true (लेकिन इसके विपरीत!) एक मजबूत CAS ऐसा नहीं कर सकता: यह CAS के शब्दार्थ का सख्ती से पालन करता है। बेशक, यह कुछ के लायक हो सकता है।
आपको कब कमजोर का उपयोग करना चाहिए, और कब - मजबूत कैस? मैं इस नियम के साथ आया था: यदि CAS का उपयोग लूप में किया जाता है (और यह CAS का उपयोग करने के लिए मुख्य पैटर्न है) और लूप में कोई संचालन नहीं हैं (अर्थात, लूप का शरीर हल्का है), तो मैं compare_exchange_weak - कमजोर CAS का उपयोग करता compare_exchange_weak । अन्यथा, एक मजबूत compare_exchange_strong ।

स्मारकों के अधिग्रहण / रिलीज के लिए स्मृति आदेश

जैसा कि मैंने ऊपर उल्लेख किया है, निम्नलिखित memory_order मान अधिग्रहित / जारी करने के लिए परिभाषित हैं:

• memory_order_acquire
• memory_order_consume
• memory_order_release
• memory_order_acq_rel

पढ़ने (लोड) के लिए, मान्य मान हैं memory_order_acquire और memory_order_consume ।
लेखन (स्टोर) के लिए - केवल memory_order_release ।
Memory_order_acq_rel केवल RMW परिचालनों के लिए मान्य है - compare_exchange , exchange , fetch_xxx । सामान्य तौर पर, एक परमाणु RMW आदिम में memory_order_acquire को शब्दार्थ, memory_order_acquire रिलीज सिमेंटिक्स memory_order_release या दोनों, memory_order_acq_rel । RMW परिचालनों के लिए, ये स्थिरांक शब्दार्थ निर्धारित करते हैं, क्योंकि रीड-मॉडिफाई-राइट प्रिमिटिव एक साथ परमाणु रीड एंड राइट करता है। शब्दार्थ, आरएमडब्ल्यू ऑपरेशन को या तो अधिग्रहीत रीड के रूप में, या रिलीज़ रिकॉर्ड या दोनों के रूप में माना जा सकता है।
आरएमडब्ल्यू ऑपरेशन के शब्दार्थ को केवल उस एल्गोरिथ्म में निर्धारित किया जा सकता है जहां इसे लागू किया जाता है। अक्सर, लॉक-फ्री एल्गोरिदम में, कुछ भाग जो स्पिन-लॉक के समान होते हैं, उन्हें प्रतिष्ठित किया जा सकता है: शुरुआत में हम एक निश्चित संसाधन प्राप्त करते हैं (प्राप्त करते हैं), कुछ करते हैं (आमतौर पर एक नए मूल्य की गणना करते हैं) और अंत में हम संसाधन के लिए एक नया मूल्य सेट (रिलीज़) करते हैं। यदि एक संसाधन प्राप्त करना आरएमडब्ल्यू ऑपरेशन (आमतौर पर सीएएस) द्वारा किया जाता है, तो इस तरह के ऑपरेशन से शब्दार्थ प्राप्त करने की संभावना है। यदि आरएमडब्ल्यू आदिम (सीएएस या exchange ) द्वारा एक नए मूल्य की स्थापना की जाती है, तो इसकी संभावना सबसे अधिक है। "काफी संभावना" एक कारण के लिए डाला जाता है: एल्गोरिथ्म का एक विस्तृत विश्लेषण आवश्यक है इससे पहले कि आप यह समझ सकें कि शब्दार्थ एक आरएमडब्ल्यू ऑपरेशन के लिए क्या उपयुक्त हैं।
यदि RMW आदिम को अलग से निष्पादित किया जाता है (अधिग्रहण / रिलीज पैटर्न को अलग करना असंभव है), तो शब्दार्थ के लिए 3 विकल्प संभव हैं:

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

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

शब्दार्थ का उपभोग करते हैं

एक अलग, कमजोर, तरह-तरह के अधिग्रहण-शब्दार्थ - उपभोग-पठन शब्दार्थ है। इस शब्दार्थ को DEC अल्फा प्रोसेसर को "श्रद्धांजलि" के रूप में पेश किया गया था।
अल्फा आर्किटेक्चर में अन्य आधुनिक आर्किटेक्चर से महत्वपूर्ण अंतर है: यह डेटा निर्भरता को तोड़ सकता है। इस कोड उदाहरण में:

 struct foo { int x; int y; } ; atomic<foo *> pFoo ; foo * p = pFoo.load( memory_order_relaxed ); int x = p->x; 

वह p->x पढ़ने में फिर से आ सकता है और वास्तव में p प्राप्त कर सकता है (मुझसे यह न पूछें कि यह कैसे संभव है - यह अल्फा गुण है ; मुझे अल्फा के साथ काम नहीं करना है, इसलिए मैं इसकी पुष्टि नहीं कर सकता और न ही इसे अस्वीकार कर सकता हूं)।
इस पुनरावृत्ति को रोकने के लिए, शब्दार्थ का उपभोग किया गया था। यह एक संरचना के लिए सूचक के परमाणु पढ़ने के लिए लागू होता है, इसके बाद संरचना के क्षेत्रों को पढ़ता है। इस उदाहरण में, pFoo पॉइंटर को इस तरह पढ़ना चाहिए:

 foo * p = pFoo.load( memory_order_consume ); int x = p->x; 

खपत शब्दार्थ कहीं आराम और पढ़ने के शब्दार्थ के बीच में हैं। कई आधुनिक आर्किटेक्चर पर, यह आराम से पढ़ने के लिए मैप करता है।

और फिर से कैस के बारे में

ऊपर, मैंने दो कैस के साथ atomic<T> इंटरफ़ेस प्रस्तुत किया - कमजोर और मजबूत। वास्तव में, CAS के दो और संस्करण हैं - अतिरिक्त तर्क memory_order :

 bool compare_exchange_weak(T&, T, memory_order successOrder, memory_order failedOrder ); bool compare_exchange_strong(T&, T, memory_order successOrder, memory_order failedOrder ); 

यह तर्क क्या है - failedOrder
याद रखें कि CAS एक रीड-मॉडिफ़ाइड-राइट प्रिमिटिव है। यहां तक ​​कि विफलता के मामले में, यह परमाणु रीडिंग करता है। failedOrder तर्क सिर्फ इस पढ़ने के शब्दार्थ को परिभाषित करता है यदि कैस विफल रहता है। सामान्य पढ़ने के लिए उन्हीं मूल्यों का समर्थन किया जाता है।
व्यवहार में, "विफलता पर शब्दार्थ" के संकेत की शायद ही कभी आवश्यकता होती है। बेशक, यह सब एल्गोरिथ्म पर निर्भर करता है!

आराम से शब्दार्थ

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

होता है-पहले, सिंक्रनाइज़-इन और अन्य रिश्ते

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

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

लॉक-फ्री एल्गोरिदम का सत्यापन

हाल तक तक, मुझे सत्यापन का केवल एक ही साधन पता था - दिमित्री व्युकोव की निर्भरता पुस्तकालय । दुर्भाग्य से, इस उपकरण को एक विशेष मॉडल के निर्माण की आवश्यकता है। वास्तव में, आपको पहले रिलैक्स लाइब्रेरी के संदर्भ में लॉक-फ्री एल्गोरिदम का एक सरलीकृत मॉडल बनाना चाहिए (क्यों सरलीकृत? - क्योंकि एक मॉडल का निर्माण करते समय, आप आमतौर पर सभी प्रकार के उपयोगी baubles को हटा देते हैं जो सीधे प्रश्न में एल्गोरिथ्म से संबंधित नहीं होते हैं)। इस मॉडल को तब डीबग करने की आवश्यकता होती है, और केवल तब, जब सब कुछ डीबग किया जाता है और सभी परमाणु संचालन सही memory_orderतर्कों से सुसज्जित होते हैं , क्या हम पहले से ही एल्गोरिथ्म का उत्पादन संस्करण लिख सकते हैं। यह दृष्टिकोण डेवलपर्स के लिए आदर्श है।उन लोगों को ताला-मुक्त एल्गोरिदम और डेटा संरचनाएं, जो उन्हें आविष्कार करते हैं। दरअसल, इस मॉडल के डेवलपर्स के लिए यह सब समाप्त हो जाता है। लेकिन कार्यान्वयनकर्ता (मुझे रूसी शब्द "अनुवादक" पसंद है - वह इस बात पर जोर देता है कि विषय कुछ भी आविष्कार नहीं करता है, लेकिन केवल रचनात्मक रूप से किसी के विचार का एहसास करता है) ऐसा दो-चरणीय दृष्टिकोण अक्सर उपयुक्त नहीं होता है (प्राकृतिक आलस्य के कारण) - वे यहां सब कुछ करते हैं और अब, और अधिमानतः तेज।
जाहिर तौर पर, रिलेमी के लेखक, दिमित्री व्युकोव ने अपने दिमाग की उपज की इस कमी को समझा (कोई विडंबना नहीं है - रिलेसी अपने क्षेत्र में वास्तव में एक सफलता परियोजना है), और एक बार इंटेल फोरम पर एक साक्षात्कार में उन्होंने सुझाव दिया - यह सुनिश्चित करने के लिए कि सत्यापन उपकरण (रिलेसी या ऐसा कुछ) ) मानक पुस्तकालय के अंदर सन्निहित था। फिर कोई अतिरिक्त मॉडल नहीं करना होगा। यह कुछ हद तक एसटीएल में सुरक्षित पुनरावृत्तियों की अवधारणा की याद दिलाता है।
हाल ही में, दिमित्री ने Google के अपने सहयोगियों के साथ मिलकर एक नया टूल थ्रेडसनीटाइज़र पेश किया। यह उपकरण आपको कार्यक्रम में डेटा दौड़ की उपस्थिति की जांच करने की अनुमति देता है, अर्थात, वास्तव में, परमाणु संचालन में आदेश देने का सही आवेदन। इसके अलावा, इस उपकरण को STL में भी लागू नहीं किया गया है, लेकिन कंपाइलर (Clang 3.2, और फिर GCC 4.8 ) में भी गहरा है ।
ThreadSanitizer का उपयोग करना काफी सरल है - बस कुछ कुंजियों के साथ प्रोग्राम को संकलित करें, एक परीक्षण चलाएं - और व्यापक लॉग की खोज का आनंद लें। मैं यह सुनिश्चित करने के लिए निकट भविष्य में अपने libcds लाइब्रेरी में इस उपकरण का उपयोग करने की योजना बना रहा हूं कि मैं एक कमीने हूं कि सब कुछ libcds में क्रम में है।

"मुझे समझ में नहीं आता ..." - मानक की आलोचना

हां, मैं C ++ 11 मानक की आलोचना करने की स्वतंत्रता लेता हूं! मुझे समझ में नहीं आ रहा है कि परमाणु के तर्क से संकेत मिलने पर दृष्टिकोण को मानक में क्यों चुना गया । टेम्प्लेट का उपयोग करना और कुछ इस तरह परिभाषित करना अधिक तर्कसंगत होगा:

 template <typename T> class atomic { template <memory_order Order = memory_order_seq_cst> T load() const ; template <memory_order Order = memory_order_seq_cst> void store( T val ) ; template <memory_order SuccessOrder = memory_order_seq_cst> bool compare_exchange_weak( T& expected, T desired ) ; //    }; 

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

 extern std::memory_order currentOrder ; std::Atomic<unsigned int> atomicInt ; atomicInt.store( 42, currentOrder ) ; 

यह कोड औपचारिक रूप से C ++ 11 मानक के विपरीत नहीं है। हालांकि, सभी संकलक यहां कर सकते हैं:

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

टेम्पलेट दृष्टिकोण ऐसी कमियों से रहित है। टेम्प्लेट फ़ंक्शंस में, हमें एन्यूमरेशन से कंपाइल-टाइम स्थिरांक को निर्दिष्ट करना होगा memory_order। हां, परमाणु संचालन के लिए कॉल कुछ कोणीय हो सकता है:

 std::Atomic<int> atomicInt ; atomicInt.store<std::memory_order_release>( 42 ) ; //   : atomicInt.template store<std::memory_order_release>( 42 ) ; 

लेकिन, मेरी राय में, इस "कोणीयता" को टेम्पलेट दृष्टिकोण के फायदों द्वारा मुआवजा दिया जाता है, - संकलन के दौरान ऑपरेशन के शब्दार्थ को इंगित करने की अस्पष्टता।
सी ++ 11 दृष्टिकोण का एकमात्र स्पष्टीकरण जो मेरे दिमाग में आता है, सी के साथ कुख्यात संगतता है। आखिरकार, क्लास के अलावा, std::atomicसी ++ 11 मानक मुफ्त सी-वें परमाणु कार्यों का परिचय देता है atomic_load, atomic_storeआदि
मैं ध्यान देता हूं कि एक समय में सी + +। 11 अभी भी परियोजना में ही था, मैंने टेम्पलेट्स के संदर्भ में परमाणु आदिम लागू किया। फिर वह इस निष्कर्ष पर पहुंचा कि किसी को अभी भी मानक का पालन करना चाहिए, और परमाणु संचालन C ++ 11 के इंटरफ़ेस के तहत libcds के अगले संस्करण को हटा दिया गया।

मूल बातें का अंत

यह लेख बुनियादी बातों का निष्कर्ष है ।

इसके अलावा मैं पहले से ही "विषय पर" बताने के लिए उपक्रम करता हूं - लॉक-फ्री डेटा संरचनाएं और संबंधित एल्गोरिदम।