मुझे उम्मीद है कि यह लेख लॉक-फ्री डेटा संरचनाओं पर नोटों की एक श्रृंखला की शुरुआत को चिह्नित करता है। मैं अपने अनुभव, टिप्पणियों और विचारों के साथ साझा करना चाहता हूं कि लॉक-फ्री डेटा संरचनाएं क्या हैं, उन्हें कैसे लागू किया जाए, क्या लॉक-फ्री कंटेनरों के लिए उपयुक्त एसटीएल मानक पुस्तकालय की कंटेनर अवधारणाएं हैं, और जब (और यदि हो तो) लॉक का उपयोग करने लायक है मुक्त डेटा संरचनाओं।
परमाणु-संचालन जैसे विषयों को कवर किए बिना लॉक-फ्री डेटा संरचनाओं के बारे में बात करना व्यर्थ है, किसी विशेष प्रोग्रामिंग भाषा में लागू किया गया एक मेमोरी मॉडल (जब तक कि निश्चित रूप से, भाषा अपने मेमोरी मॉडल के बारे में सोचने के लिए पर्याप्त पुरानी है), सुरक्षित मेमोरी फ्रीजिंग, कंपाइलर और बाहर वे जो अनुकूलन करते हैं, आधुनिक प्रोसेसर आर्किटेक्चर - इन सभी विषयों को इस चक्र में एक डिग्री या किसी अन्य को स्पर्श किया जाएगा। मैं इन सभी चीजों के बारे में बताने की स्वतंत्रता लेता हूं, हालांकि मैं खुद को उनमें से किसी में भी पूर्ण विशेषज्ञ नहीं मानता। दूसरी ओर, उनके बारे में कोई विचार नहीं होने के कारण, मैं
libcds पुस्तकालय, ताला मुक्त कंटेनरों का एक खुला स्रोत C ++ पुस्तकालय और सुरक्षित मेमोरी रिक्लेमेशन एल्गोरिदम नहीं लिख और विकसित कर
सका । सीडी समवर्ती डेटा संरचना के लिए खड़ा है, और उपसर्ग "लिब" है, अजीब तरह से पर्याप्त है, एक "पुस्तकालय"।
मैं पुस्तकालय के इतिहास से शुरू करता हूँ। यह 2006 में वापस आ गया था।
फिर मैंने बिग थ्री से एक दूरसंचार ऑपरेटर के लिए एक काफी बड़ी कंपनी लेखन सॉफ्टवेयर के लिए काम किया। हमने हार्डवेयर प्लेटफ़ॉर्म चिड़ियाघर के लिए काफी जटिल सर्वर एप्लिकेशन विकसित किए, जिसमें प्रदर्शन की समस्या (और हमेशा रहेगी)। यह डाटा प्रोसेसिंग को समानांतर करके, हल किया गया था। हमेशा की तरह, समानांतरकरण ने साझा डेटा की उपस्थिति का नेतृत्व किया, जिस तक पहुंच को सिंक्रनाइज़ करने की आवश्यकता थी। एक बार, एक चर्चा में, मेरे सहयोगी ने यह पूछते हुए पूछा: "क्या आपने लॉक-फ्री कतारों के बारे में कुछ भी सुना है?" उस समय मुझे इसके बारे में कुछ भी नहीं पता था। लेकिन, Google से पूछने पर, मुझे कई लेख मिले जिनमें लॉक-फ्री कतार छद्म कोड दिया गया था। कई बार उन्हें पढ़ने के बाद मुझे कुछ समझ नहीं आया। अधिक सटीक रूप से, मैं अपनी आस्तीन को लुढ़कने और "अभी ठीक है!" कहने के बाद "मैं कुछ भी समझ नहीं पाया" की स्थिति में चला गया, पूरी दुनिया के लिए (माना जाता है कि आप सभी मूर्ख हैं, मैं यहाँ अकेला स्मार्ट हूँ), मैंने उनसे मिलान करके एल्गोरिदम को "सरल" करने की कोशिश की। सामान्य ज्ञान के साथ। विभाजन दोष से लड़ने के एक महीने के बाद, मेरे सामान्य ज्ञान ने हार मान ली। तब मुझे कुछ समझ नहीं आया। मुझे समझ नहीं आया कि यह आम तौर पर कैसे काम करता है, और यहां तक कि अगर आईटी किसी तरह काम करता है, तो इसे C ++ में कैसे लागू किया जा सकता है। लेकिन किसी तरह यह काम करना चाहिए, अन्यथा स्मार्ट लोग इन लेखों को नहीं लिखेंगे, और अन्य स्मार्ट लोग उन्हें संदर्भित नहीं करेंगे (लेख वैज्ञानिक थे, और प्रत्येक के अंत में, वैज्ञानिक समुदाय में हमेशा की तरह, साहित्य की सूची दी गई थी)। इन कड़ियों के बाद, एक वर्ष के दौरान मैंने कई दसियों उपयोगी और बहुत जानकारी के नहीं, बहुत सारी जानकारी पढ़ी, जिसमें सॉफ्टवेयर डेवलपर गाइड से लेकर प्रोसेसर आर्किटेक्चर पर सामान्य दृष्टिकोणों पर लेखों की समीक्षा करना शामिल था। रास्ते के साथ, मैं इस विषय पर कुछ (निश्चित रूप से C ++ में) देख रहा था, कुछ आदिम लागू कर रहा था। यह ध्यान दिया जाना चाहिए कि इस समय (वर्ष 2006-2007) C ++ 11 मानक को अभी भी आशावादी रूप से C ++ 0x कहा जाता था, STL में कोई परमाणु आदिम नहीं थे, और इंटरफ़ेस को केवल उल्लिखित किया गया था, और संकलक कभी-कभी मेरे परमाणु आदिम और शरारती होते थे विशेष रूप से महत्वपूर्ण क्षेत्रों में गैर-कार्यशील कोड जारी किया। 2008 तक, libcds लाइब्रेरी की धूमिल रूपरेखा आकार लेने लगी। विभिन्न प्लेटफार्मों पर पहले परीक्षणों ने उत्साहजनक परिणाम दिया, कभी-कभी तेजस्वी ("यह 50 गुना तेज हो गया !!!") परिणाम, और मैं पूरी तरह से लॉक-फ्री की दुनिया में डूब गया। 2010 में, मैंने SourceForge पर लाइब्रेरी का पहला (0.5.0) संस्करण पोस्ट किया। आज लाइब्रेरी का नवीनतम संस्करण 1.4.0 है, संस्करण 1.5.0 पर काम चल रहा है।
मैं लॉक-फ्री डेटा संरचनाओं की सामान्य समीक्षा करने के लिए पास करूंगा। इसलिए, जटिल सॉफ्टवेयर परियोजनाओं के डिजाइन और विकास में एक प्रोग्रामर का मुख्य कार्य, विशेष रूप से सर्वर वाले, लक्ष्य मंच के सभी उपलब्ध संसाधनों का सबसे प्रभावी ढंग से उपयोग करना है। एक आधुनिक कंप्यूटर, यहां तक कि एक स्मार्टफोन या टैबलेट, एक मल्टीप्रोसेसर उपकरण है, इसलिए उत्पादकता बढ़ाने के तरीकों में से एक कार्यक्रम को समानांतर करना है। समानांतर धागे (थ्रेड) कुछ साझा डेटा (साझा डेटा) को संसाधित करते हैं; इसलिए, हमारा मुख्य कार्य ऐसे साझा डेटा के समानांतर पहुंच को व्यवस्थित करना है।
पिछली शताब्दी के 80 के दशक में, तथाकथित संरचनात्मक प्रोग्रामिंग लोकप्रिय थी, अच्छे कार्यक्रमों को लिखने की एक विधि के रूप में तैनात थी। संरचनात्मक प्रोग्रामिंग के लिए माफी देने वाला पास्कल भाषा का लेखक निकोलस विर्थ था, जिसने सबसे अच्छी पुस्तक "अल्गोरिद्म + डेटा स्ट्रक्चर्स = प्रोग्राम्स" लिखी थी। दिलचस्प बात यह है कि यह पुराना फॉर्मूला आधुनिक एपीआई जैसे कमजोरियों की ओर इशारा करता है, जैसे कि ऑपरेटिंग सिस्टम द्वारा दी गई Win32 APIs: API समानांतर प्रोग्राम बनाने के लिए एक उपकरण प्रदान करती है (यह उपकरण थ्रेड, थ्रेड्स है), लेकिन वे समानांतर डेटा संरचनाओं के निर्माण के लिए उपकरण प्रदान नहीं करते हैं जो साझा पहुंच प्रदान करते हैं। इसके बजाय, APIs सिंक्रनाइज़ेशन प्राइमेटरीज के रूप में डेटा एक्सेस को
प्रतिबंधित करने का एक साधन प्रदान करता है। हालांकि, समानांतर कार्यक्रमों में सिंक्रनाइज़ेशन एक अड़चन है। इसके मूल में, सिंक्रनाइज़ेशन समानतावाद का एंटीपोड है: एल्गोरिदम को समानांतर करना, हम अनुक्रमिक डेटा संरचनाओं के साथ काम करते हैं, सिंक्रोनाइज़ेशन प्राइमेटिव्स के साथ अपने काम को प्रदान करते हैं - महत्वपूर्ण खंड, म्यूटेक्स, सशर्त चर (कंवर); नतीजतन, हम डेटा संरचना तक पहुंच के लिए अपने सभी धागे कतारबद्ध करते हैं, जिससे समानता की हत्या होती है। सिंक्रोनाइज़ेशन प्रिमिटिव कभी-कभी OS कर्नेल की ऑब्जेक्ट होते हैं, इसलिए इस तरह की ऑब्जेक्ट को एक्सेस करना बहुत महंगा हो सकता है: आपको संदर्भ को स्विच करने, ओएस कर्नेल लेवल पर जाने, सिंक्रोनाइज़ेशन आदिम द्वारा संरक्षित डेटा तक पहुंचने के लिए समर्थन कतारों की आवश्यकता हो सकती है। डेटा में एक एकल पॉइंटर के मूल्य को बदलने के लिए, अर्थात्, एक या दो कोडांतरक निर्देशों को निष्पादित करें। ओवरहेड लागत (वास्तव में, बहुत अधिक) हो सकती है। इसके अलावा, यह मत भूलो कि ओएस कर्नेल की वस्तु मात्रा में सीमित संसाधन है।
सिंक्रनाइज़ेशन का एक और नुकसान इसकी कम मापनीयता है। जैसे-जैसे थ्रेड की संख्या बढ़ती जाती है, डेटा तक सिंक्रनाइज़ एक्सेस प्रोग्राम की अड़चन बन जाती है; अक्सर समानता की डिग्री में वृद्धि के साथ, उत्पादकता में आनुपातिक वृद्धि के बजाय, हम उच्च भार स्थितियों के तहत इसकी गिरावट प्राप्त करते हैं।
Wirth के सूत्र द्वारा निर्देशित "एल्गोरिदम + डेटा संरचनाएं = प्रोग्राम्स", libcds पर अपने काम में मैंने केवल डेटा संरचनाओं पर ध्यान केंद्रित किया: लाइब्रेरी में आपको समानांतर एल्गोरिदम या प्रत्येक एल्गोरिदम के समानांतर समानांतर नहीं मिलेगा। लाइब्रेरी में केवल प्रतिस्पर्धी डेटा संरचनाएं हैं - कतार, सूची, मानचित्र, सेट, आदि - और लॉक-फ्री डेटा का समर्थन करने के लिए आवश्यक एल्गोरिदम, सबसे पहले, ये सुरक्षित मेमोरी रिक्लेमेशन एल्गोरिदम हैं। अक्सर, एक या दूसरे डेटा संरचना को कई कार्यान्वयनों द्वारा दर्शाया जाता है। यह मूल रूप से कल्पना की गई थी: एक नियम के रूप में, कई दिलचस्प एल्गोरिदम हैं जो कतार या मानचित्र को लागू करते हैं, और मुझे सामान्य मामले में पता नहीं है कि कौन सा "बेहतर" है: सबसे पहले, "बेहतर" या "बदतर" की अवधारणा सापेक्ष है और विशिष्ट हार्डवेयर पर निर्भर करती है और एक विशिष्ट कार्य, दूसरा, जब तक आप एल्गोरिथ्म को लागू नहीं करते हैं और दूसरों के साथ तुलना करते हैं, तब तक आप यह नहीं समझ पाएंगे कि यह बेहतर है या नहीं। ठीक है, अगर एल्गोरिथ्म लागू किया गया है और डीबग किया गया है, तो लाइब्रेरी में इसकी जगह क्यों नहीं ली जाती है (और एक मुश्किल से उपयोगकर्ता प्रदान करें)? ..?
गीतात्मक विषयांतरवैसे, इस संबंध में मेरे पास एसटीएल के लिए एक दावा है: उदाहरण के लिए, मेरे लिए ज्ञात एसटीएल के सभी कार्यान्वयन में नक्शा लाल-काले पेड़ के रूप में क्यों बनाया गया है? मानचित्र को लागू करने के लिए उपयुक्त कई अन्य डेटा संरचनाएं हैं, उदाहरण के लिए, एक एवीएल पेड़, जो एक ही बाइनरी ट्री है, लेकिन एक मजबूत संतुलन मानदंड (इसके अलावा, हमारे विकास) के साथ। जाहिरा तौर पर, न केवल इस तरह के सवाल मुझे पीड़ा देते हैं: मैं उन लेखों से मिला, जो लाल-काले पेड़ और एवीएल पेड़ के कार्यान्वयन की तुलना करते हैं, और इन लेखों में निष्कर्ष लाल-काले पेड़ के पक्ष में असमान रूप से नहीं थे: कई कार्यों में (कई आर्किटेक्चर पर) और पेड़ तेजी से निकला।
शैक्षणिक माहौल में, प्रतिस्पर्धी डेटा संरचनाओं को लागू करने के तरीकों का अध्ययन, जो साझा डेटा तक एक साथ पहुंच प्रदान करते हैं, ने कई मुख्य क्षेत्रों का निर्माण किया है:
- लॉक-मुक्त डेटा संरचनाएं;
- बारीक दाने वाले एल्गोरिदम;
- लेन-देन की स्मृति
Libcds में कोई ट्रांसेक्शनल मेमोरी आधारित कार्यान्वयन नहीं हैं। लेन-देन स्मृति अनुसंधान का एक विशाल क्षेत्र है जो मुख्य रूप से भविष्य पर केंद्रित है। ट्रांसेक्शनल मेमोरी के आधार पर एल्गोरिदम, मोटे तौर पर, उस मेमोरी को परमाणु लेन-देन का समर्थन करता है, जिसे परमाणु स्वीकार (कमिट) या अस्वीकृत (रोलबैक) किया जा सकता है। जाहिर है, ऐसी मेमोरी को हार्डवेयर में लागू किया जाना चाहिए; मौजूदा सॉफ्टवेयर कार्यान्वयन, शोधकर्ताओं के अनुसार, पर्याप्त प्रदर्शन नहीं करते हैं। न्याय की खातिर, यह ध्यान देने योग्य है कि हसवेल इंटेल प्रोसेसर का पहले से ही उनके निर्देश प्रणाली में लेन-देन का समर्थन है, इसलिए यह उम्मीद की जाती है कि लेनदेन स्मृति के सिद्धांतों के आधार पर एल्गोरिदम के हेयडे बस कोने के आसपास है।
बारीक दाने वाले एल्गोरिदम परिष्कृत सिंक्रोनाइज़ेशन के तरीके हैं, जो आमतौर पर OC द्वारा प्रदान किए गए सिंक्रोनाइज़ेशन प्राइमेटिव्स के उपयोग पर नहीं बनाए जाते हैं, लेकिन उदाहरण के लिए, स्पिन-लॉक "लाइट" परमाणु प्रिमिटिव्स के उपयोग पर। ऐसी प्राथमिकताओं के आधार पर, डेटा संरचनाओं का निर्माण किया जाता है जो समानांतर रीडिंग या यहां तक कि समानांतर रिकॉर्डिंग की अनुमति देते हैं, जिसमें डेटा संरचना के नोड (नोड) या पेज (पेज, बाल्टी) के स्तर पर सिंक्रनाइज़ेशन किया जाता है और इस संरचना के संचालन के लिए एल्गोरिदम में बनाया गया है। प्रायः महीन दाने वाले कंटेनर अपेक्षाकृत हल्के भार के तहत लॉक-फ्री कंटेनरों के प्रदर्शन के तुलनीय होते हैं। Libcds लाइब्रेरी ऐसी डेटा संरचनाओं का तिरस्कार नहीं करती है।
लॉक-फ्री डेटा स्ट्रक्चर्स मैं उन डेटा स्ट्रक्चर्स को कॉल करूंगा जिन्हें
बाहरी एक्सेस सिंक्रोनाइज़ेशन की आवश्यकता नहीं है। यह एक अनौपचारिक, विशुद्ध रूप से तकनीकी परिभाषा है, कंटेनर की आंतरिक संरचना और उस पर संचालन को दर्शाता है। शब्द "बाहरी" यहां जानबूझकर उजागर किया गया है: यह समझना चाहिए कि लॉक-फ्री डेटा संरचना के प्रोसेसर से विशेष समर्थन के उपयोग के बिना, इसका निर्माण करना सबसे अधिक संभावना है। लेकिन लॉक-फ्री कंटेनरों में इस तरह का समर्थन कंटेनर
के अनुक्रमिक तरीकों तक पहुंच को सिंक्रनाइज़ करके नहीं किया जाता है, बल्कि कंटेनर के तरीकों के अंदर वायर्ड एक
परमाणु संशोधन तंत्र द्वारा, या कंटेनर के घटकों (नोड्स, बाल्टी, पेज) के स्तर पर आंतरिक सिंक्रनाइज़ेशन द्वारा किया जाता है।
लॉक-फ्री ऑब्जेक्ट की औपचारिक परिभाषा है [Her91]: एक साझा ऑब्जेक्ट को लॉक-फ्री ऑब्जेक्ट (नॉन-ब्लॉकिंग, नॉन-ब्लॉकिंग ऑब्जेक्ट) कहा जाता है यदि यह सुनिश्चित करता है कि
कुछ थ्रेड चरणों की एक सीमित संख्या में ऑब्जेक्ट पर कार्रवाई को पूरा करता है, भले ही दूसरों के काम का परिणाम हो। धागे (भले ही ये अन्य धागे दुर्घटनाग्रस्त हो गए)। प्रतीक्षा-मुक्त ऑब्जेक्ट की एक अधिक कठोर अवधारणा कहती है: यदि
प्रत्येक थ्रेड चरणों की एक सीमित संख्या में किसी ऑब्जेक्ट पर एक ऑपरेशन को पूरा करता है, तो एक वस्तु प्रतीक्षा-मुक्त है। लॉक-मुक्त स्थिति कम से कम एक धागे के प्रचार की गारंटी देती है, जबकि मजबूत प्रतीक्षा-मुक्त स्थिति सभी थ्रेड्स के लिए सफल निष्पादन की गारंटी देती है। प्रतिस्पर्धी डेटा संरचनाओं के सिद्धांत में लीनरिज़ेबिलिटी [Her90] की अवधारणा भी है, जो लॉक-फ्री एल्गोरिदम की शुद्धता के औपचारिक प्रमाण में एक महत्वपूर्ण भूमिका निभाता है। मोटे तौर पर, एक एल्गोरिथ्म रैखिक है अगर इसका परिणाम एल्गोरिदम के अंत में दिखाई देता है। उदाहरण के लिए, सूची में डालने का परिणाम सम्मिलित फ़ंक्शन के अंत में दिखाई देता है। यह मुहावरेदार लगता है, लेकिन एक एल्गोरिथ्म के साथ आना संभव है जो सूची में प्रविष्टि करता है और रैखिक नहीं है। उदाहरण के लिए, सभी प्रकार की बफरिंग इस संपत्ति का उल्लंघन कर सकती है: डालने के बजाय, हम एक नए तत्व को एक बफर में डाल सकते हैं, दूसरे धागे को एक कमांड दे सकते हैं "सूची में बफर से एक तत्व डालें" और तत्व के सम्मिलित होने का इंतजार न करें; या हम केवल तभी सम्मिलित करेंगे जब पर्याप्त संख्या में तत्व बफर में जमा हो गए हों। फिर, सूची में सम्मिलित फ़ंक्शन के अंत में, हम यह गारंटी नहीं दे सकते कि तत्व सूची में है; हम सभी गारंटी दे सकते हैं कि तत्व निश्चित रूप
से (भविष्य में तनाव!) सूची में अभी या बाद में डाला जाएगा।
इन अवधारणाओं का व्यापक रूप से अनुसंधान परियोजनाओं में उपयोग किया जाता है; मेरा लेख एक शोध एक होने का ढोंग नहीं करता है, इसलिए मैं पारंपरिक सिंक्रनाइज़ेशन पैटर्न के उपयोग के बिना या बाहरी तुल्यकालन के बिना बनाए गए प्रतिस्पर्धी कंटेनरों के वर्ग को संदर्भित करने के लिए "फिलिस्तीन" अर्थ में लॉक-फ्री शब्द का उपयोग करूंगा।
पाचन 2 - समय के बारे मेंयह ध्यान दिया जाना चाहिए कि समय की अवधारणा (कारण-प्रभाव संबंध) लॉक-फ्री डेटा संरचनाओं में किसी तरह धुंधली है। पारंपरिक दृष्टिकोण में, हम इस तरह से कार्य करते हैं: कंटेनर तक पहुंच को अवरुद्ध करें, इसके साथ कुछ करें (उदाहरण के लिए, एक तत्व जोड़ें), अनलॉक करें। अनलॉक करने के समय, हम जानते हैं कि डाला गया सामान कंटेनर में है। लॉक-फ्री कंटेनर में, ऐसा नहीं है। हमें एक्सेस ब्लॉक करने की आवश्यकता नहीं है, हम सिर्फ ऐड मेथड को कहते हैं। यदि यह सही लौटा, तो इंसर्ट सफल रहा। लेकिन इसका मतलब यह नहीं है कि तत्व कंटेनर में है - यह पहले से ही एक प्रतिस्पर्धा स्ट्रीम द्वारा हटाया जा सकता है। यह लॉक-फ्री कंटेनरों और पारंपरिक ला एसटीएल के बीच महत्वपूर्ण अंतर को प्रदर्शित करता है - हम कंटेनर कार्यान्वयन इंटर्ल्स को बाहर नहीं निकाल सकते हैं; उदाहरण के लिए, व्यापक रूप से एसटीएल में उपयोग किए जाने वाले पुनरावृत्तियों की अवधारणा प्रतिस्पर्धी डेटा संरचनाओं पर लागू नहीं है। मैं निम्नलिखित लेखों में से एक में प्रतिस्पर्धी कंटेनर वर्ग इंटरफेस के निर्माण पर विस्तार से चर्चा करने की उम्मीद करता हूं।
लॉक-फ्री एल्गोरिदम की विशेषता क्या है? शायद पहली चीज जो आपकी आंख को पकड़ती है, वह उनकी जटिलता है। क्या आप कल्पना कर सकते हैं कि एक नियमित रूप से कतार क्या है, एक एकल लिंक की गई सूची पर लागू की गई है? बहुत सरल कोड:
बहुत सरल कोड दिखाएंstruct Node { Node * m_pNext ; }; class queue { Node * m_pHead ; Node * m_pTail ; public: queue(): m_pHead( NULL ), m_pTail( NULL ) {} void enqueue( Node * p ) { p->m_pNext = m_pTail ; m_pTail = p ; if ( !m_pHead ) m_pHead = p ; } Node * dequeue() { if ( !m_pHead ) return NULL ; Node * p = m_pHead ; m_pHead = p->m_pNext ; if ( !m_pHead ) m_pTail = NULL ; return p ; } };
आप लिख भी सकते हैं और कम भी। और यहां क्लासिक माइकल एंड स्कॉट लॉक-फ्री कतार एल्गोरिदम ([Mic96] जैसा दिखता है) के एन्क्यू / डीक्यू तरीके (पुश / पॉप समानार्थक शब्द) हैं, कोड को
cds::intrusive::MSQueue से न्यूनतम संक्षिप्त रूप के साथ लिया गया था
cds::intrusive::MSQueue :
cds::intrusive::MSQueue लाइब्रेरी का
cds::intrusive::MSQueue वर्ग):
वही दिखाओ, लेकिन बहुत बोझिल लिखा है bool enqueue( value_type& val ) { node_type * pNew = node_traits::to_node_ptr( val ) ; typename gc::Guard guard ; back_off bkoff ; node_type * t ; while ( true ) { t = guard.protect( m_pTail, node_to_value() ) ; node_type * pNext = t->m_pNext.load(memory_model::memory_order_acquire) ; if ( pNext != null_ptr<node_type *>() ) { // Tail is misplaced, advance it m_pTail.compare_exchange_weak( t, pNext, memory_model::memory_order_release, CDS_ATOMIC::memory_order_relaxed ) ; continue ; } node_type * tmp = null_ptr<node_type *>() ; if ( t->m_pNext.compare_exchange_strong( tmp, pNew, memory_model::memory_order_release, CDS_ATOMIC::memory_order_relaxed )) { break ; } bkoff() ; } ++m_ItemCounter ; m_pTail.compare_exchange_strong( t, pNew, memory_model::memory_order_acq_rel, CDS_ATOMIC::memory_order_relaxed ); return true ; } value_type * dequeue() { node_type * pNext ; back_off bkoff ; typename gc::template GuardArray<2> guards ; node_type * h ; while ( true ) { h = guards.protect( 0, m_pHead, node_to_value() ) ; pNext = guards.protect( 1, h->m_pNext, node_to_value() ) ; if ( m_pHead.load(memory_model::memory_order_relaxed) != h ) continue ; if ( pNext == null_ptr<node_type *>() ) return NULL ; // empty queue node_type * t = m_pTail.load(memory_model::memory_order_acquire); if ( h == t ) { // It is needed to help enqueue m_pTail.compare_exchange_strong( t, pNext, memory_model::memory_order_release, CDS_ATOMIC::memory_order_relaxed ) ; continue ; } if ( m_pHead.compare_exchange_strong( h, pNext, memory_model::memory_order_release, CDS_ATOMIC::memory_order_relaxed )) { break ; } bkoff() ; } --m_ItemCounter ; dispose_node( h ) ; return pNext ; }
एल्गोरिथ्म जटिल है। समान रूप से जुड़ी हुई सूची, लेकिन नियमित और लॉक-मुक्त कतारों की एक सरल दृश्य तुलना पहले से ही कुछ कहती है। लॉक-फ्री कतार में हम देखते हैं:
- अंतहीन लूप - हम ऑपरेशन को पूरा करने की कोशिश करते हैं जब तक कि यह काम नहीं करता। यह परमाणु ऑपरेशन
compare_exchange का उपयोग करने का एक विशिष्ट पैटर्न है; - लॉक-फ्री एल्गोरिदम में मेमोरी (पॉइंटर्स) के साथ सुरक्षित कार्य के तरीकों में से एक का उपयोग करते हुए स्थानीय चर (
guards ) की सुरक्षा, इस मामले में यह हेज़र्ड पॉइंटर्स विधि है; - परमाणु आदिम सी ++ 11 के आवेदन -
load, compare_exchange , मेमोरी बाधाओं memory_order_xxx ; - लॉक-फ्री एल्गोरिदम में मदद करना एक बहुत ही सामान्य चाल है जब एक धागा दूसरे को काम करने में मदद करता है;
- बैक-ऑफ रणनीतियों (
bkoff functor) का अनुप्रयोग, जो वैकल्पिक हैं, लेकिन कुछ मामलों में प्रोसेसर को भारी लोड के तहत अनलोड करने की अनुमति देते हैं, जब कई थ्रेड्स एक साथ कतार में पहुंचते हैं।
अब मैं कुछ भी नहीं समझाऊंगा, क्योंकि ये सभी चीजें बहुत व्यापक हैं और एक अलग चर्चा की आवश्यकता है। साज़िश जारी रखो। मैं भविष्य के लेखों में इन विषयों को कवर करने की उम्मीद करता हूं।
अगला लेख आधारशिला अवधारणा के लिए समर्पित होगा, जिस पर सभी लॉक-फ्री डेटा संरचनाएं आधारित हैं - परमाणुता और परमाणु आदिमता।
और अंत में - उपयोगी किताबें (लेख नहीं), जिसमें, मेरे दृष्टिकोण से, प्रतिस्पर्धी प्रोग्रामिंग के सबसे पूर्ण रूप से संबोधित मुद्दे।
आज तक, मुझे दो अच्छे कामों का पता है:
1. Nir Shavit, मौरिस हेरलहि
द आर्ट ऑफ़ मल्टीप्रोसेसर प्रोग्रामिंग । रूसी में अनुवाद, जहाँ तक मुझे पता है, नहीं। दुनिया में बहुत प्रसिद्ध लॉक-फ्री लेखकों की पुस्तक कई समानांतर एल्गोरिदम और उनके निर्माण के तरीकों का वर्णन करती है। सभी उदाहरण जावा में हैं, इसलिए लेखकों को मेमोरी खाली करने के बारे में चिंता करने की ज़रूरत नहीं थी, सी ++ मेमोरी मॉडल (जावा में, मेमोरी मॉडल अधिक सख्त है) और अन्य चीजें जो भाषा में जावा में ही एम्बेडेड हैं, और सी ++ में आपको यह सब खुद लिखना होगा। इसके बावजूद यह पुस्तक बहुत उपयोगी है।
2. एंथनी विलियम्स
C ++ कंसर्ट इन एक्शन (एक
रूसी अनुवाद है )। विश्व प्रसिद्ध C ++ के लेखक की पुस्तक C ++ में मल्टीथ्रेड प्रोग्रामिंग के लिए समर्पित है, यह नए C ++ 11 मानक और समानांतर एल्गोरिदम को लागू करने के लिए मानक द्वारा प्रदान की गई नई सुविधाओं का वर्णन करता है। अत्यधिक पढ़ने की सलाह दी।
संदर्भ:
[Her90] एम। हेरलहि, जेएम विंग लिनियरिज़ेबिलिटी
: समवर्ती वस्तुओं के लिए एक सही स्थिति , प्रोग्रामिंग लैंग्वेजेज एंड सिस्टम्स पर ACM ट्रांज़ैक्शन, 1990
[हेर १ ९ १] एम। हर्लिहि
ए मेथॉलॉजी
फॉर इम्प्लीमेंटिंग हाइली कंसंट्रेट
डेटा ऑब्जेक्ट , १ ९९ १
[माइक96] एम। माइकल, एम। स्कॉट
सरल, तेज और व्यावहारिक गैर-अवरुद्ध और अवरुद्ध समवर्ती कतार एल्गोरिदमलॉक-फ्री डेटा स्ट्रक्चर्सशुरुआतमूल बातें:
अंदर:
बाहर से: