C / C ++ और GCC में परमाणु चर द्वारा संदर्भ गिनती

अलेक्जेंडर सैंडलर द्वारा पोस्ट, मूल लेख (27 मई, 2009)

परिचय

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

हमें संदर्भ गणना की आवश्यकता क्यों है?

यह समझाने के लिए कि ये दो तंत्र सर्वोत्तम प्रदर्शन क्यों प्रदान करते हैं और परमाणु चर कैसे उपयोगी हो सकते हैं, निम्न स्थिति पर विचार करें।

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

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

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

यदि हम ऐसा करते हैं, तो मैनिपुलेटर थ्रेड किसी ऑब्जेक्ट को खोजते समय म्यूटेक्स को ब्लॉक करेगा। एक बार जब वह वस्तु प्राप्त करता है, तो वह म्यूटेक्स को मुक्त करने में सक्षम होगा, जो डेटा संरचना की सुरक्षा करता है और इरेज़र स्ट्रीम को अपना काम करने की अनुमति देता है।

लेकिन अब, हम कैसे सुनिश्चित कर सकते हैं कि इरेज़र थ्रेड उसी ऑब्जेक्ट को नहीं हटाएगा जो कि पहला थ्रेड बदल रहा है?

कोई अन्य म्यूटेक्स का उपयोग कर सकता है जो वास्तविक वस्तु की सामग्री की रक्षा करता है। लेकिन यह एक महत्वपूर्ण सवाल है जो हमें खुद से पूछना चाहिए। किसी वस्तु की सामग्री की सुरक्षा के लिए कितने म्यूटेक्स आवश्यक हैं?

यदि हम सभी वस्तुओं के लिए एक म्यूटेक्स का उपयोग करते हैं, तो हमें उसी भीड़ से सामना करना पड़ता है जिससे हम बचते हैं। दूसरी ओर, यदि हम प्रत्येक वस्तु के लिए म्यूटेक्स का उपयोग करते हैं, तो हमें थोड़ी अलग समस्या का सामना करना पड़ता है।

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

वास्तव में, कुछ चीजें हैं जो हम कर सकते हैं। उनमें से एक वस्तुओं के संदर्भों का उपयोग करना है। हालाँकि, हमें स्वयं लिंक संख्या की सुरक्षा करनी चाहिए । सौभाग्य से, परमाणु चर के लिए धन्यवाद, हमें काउंटर की सुरक्षा के लिए म्यूटेक्स का उपयोग करने की आवश्यकता नहीं है।

वस्तुओं के संदर्भों की गणना के लिए हम परमाणु चर का उपयोग कैसे करेंगे

सबसे पहले, हम अपने ऑब्जेक्ट रेफरेंस काउंट को एक में इनिशियलाइज़ करते हैं। जब मैनिपुलेटर थ्रेड इसका उपयोग करना शुरू करता है, तो इसे संदर्भ काउंटर को एक से बढ़ाना होगा। ऑब्जेक्ट के साथ काम खत्म करने के बाद, इसे संदर्भ संख्या को कम करना चाहिए। यही है, जब तक मैनिपुलेटर ऑब्जेक्ट का उपयोग करता है, उसे संदर्भ गणना को बढ़ाना चाहिए।

जैसे ही इरेज़र स्ट्रीम किसी ऑब्जेक्ट को हटाने का फैसला करता है, उसे पहले डेटा संरचना से इसे हटाने की आवश्यकता होती है। ऐसा करने के लिए, उसे डेटा संरचना को सुरक्षित रखने वाले म्यूटेक्स को रखना होगा। जिसके बाद इसे वस्तु के संदर्भ काउंटर से घटाना चाहिए।

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

और अगर उसकी लिंक गिनती एक से अधिक है? इस मामले में, हमें प्रतीक्षा करनी चाहिए जब तक कि थ्रेड संदर्भ गणना शून्य न हो जाए। लेकिन यह कैसे करें?

इस सवाल का जवाब देना बहुत मुश्किल हो सकता है। आमतौर पर मैं दो दृष्टिकोणों में से एक पर विचार करता हूं। एक भोली दृष्टिकोण या एक दृष्टिकोण जिसे मैं आरसीयू दृष्टिकोण (रीड-कॉपी अपडेट - लगभग। प्रति) कहता हूं।

भोला दृष्टिकोण

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

परिस्थितियों के आधार पर, इस समाधान में समस्याएं हो सकती हैं। हटाए गए ऑब्जेक्ट की सूची बढ़ सकती है और इसके माध्यम से एक पूर्ण मार्ग प्रोसेसर को अधिभार कर सकता है। कितनी बार वस्तुओं को हटा दिया जाता है, इस पर निर्भर करते हुए, यह एक अच्छा पर्याप्त समाधान हो सकता है, लेकिन यदि यह नहीं है, तो आपको आरसीयू दृष्टिकोण पर विचार करना चाहिए।

RCU दृष्टिकोण

RCU एक और टाइमिंग मैकेनिज्म है। यह मुख्य रूप से लिनक्स कर्नेल में उपयोग किया जाता है। आप इसके बारे में यहां पढ़ सकते हैं। मैं इसे RCU दृष्टिकोण कहता हूं क्योंकि इसमें कुछ समानताएं हैं कि RCU सिंक्रनाइज़ेशन तंत्र कैसे काम करता है।

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

मान लें कि मैनिपुलेटर धागा मूल रूप से अपने जोड़तोड़ को पूरा करने में एक मिनट लेता है। यहाँ मैं विशेष रूप से अतिशयोक्ति करता हूं। जब इरेज़र स्ट्रीम किसी ऑब्जेक्ट को हटाने की कोशिश करता है, तो उसे केवल एक म्यूटेक्स या स्पिनलॉक को पकड़ना होता है जो ऑब्जेक्ट्स से युक्त डेटा संरचना की सुरक्षा करता है और ऑब्जेक्ट को इस डेटा संरचना से हटाता है।

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


ध्यान दें कि सूची के अंत में वस्तुओं को जोड़ने से उन्हें उस समय तक हल किया जाता है जब वे हटाए गए थे। सूची में पहले की वस्तुएं जो पहले नष्ट हो चुकी हैं।

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

यह दिखाने के लिए कि यह कैसे काम करता है, ऊपर की तस्वीर देखें। अब कहते हैं 15:35:12। पहली वस्तु को हटाने के बाद यह एक मिनट से अधिक है। इसलिए, जैसे ही इरेज़र सक्रिय होता है और सूची की जांच करता है, वह तुरंत देखेगा कि सूची में पहली वस्तु एक मिनट से अधिक पहले हटा दी गई थी। यह सूची से ऑब्जेक्ट को हटाने और अगले एक की जांच करने का समय है।

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

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

परमाणु चर कब दिखाई दिए?

संस्करण 4.1.2 के साथ शुरू, gcc में परमाणु चर के लिए अंतर्निहित समर्थन है। वे अधिकांश आर्किटेक्चर पर काम करते हैं, लेकिन उनका उपयोग करने से पहले, कृपया जांच लें कि आपका आर्किटेक्चर उनका समर्थन करता है।

ऐसे कार्यों का एक समूह है जो परमाणु चर के साथ काम करते हैं।

type __sync_fetch_and_add (type *ptr, type value); type __sync_fetch_and_sub (type *ptr, type value); type __sync_fetch_and_or (type *ptr, type value); type __sync_fetch_and_and (type *ptr, type value); type __sync_fetch_and_xor (type *ptr, type value); type __sync_fetch_and_nand (type *ptr, type value); 

 type __sync_add_and_fetch (type *ptr, type value); type __sync_sub_and_fetch (type *ptr, type value); type __sync_or_and_fetch (type *ptr, type value); type __sync_and_and_fetch (type *ptr, type value); type __sync_xor_and_fetch (type *ptr, type value); type __sync_nand_and_fetch (type *ptr, type value); 

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

इनमें से प्रत्येक फ़ंक्शन एक निश्चित प्रकार के चर पर संचालित होता है। प्रकार या तो चार , छोटा , इंट , लंबा , लंबा लंबा , या उनके अहस्ताक्षरित समकक्ष हो सकते हैं।

कार्यान्वयन के विवरण को छिपाने वाली चीज़ों के साथ इन कार्यों को लपेटना एक अच्छा विचार है। यह एक परमाणु चर या एक सार डेटा प्रकार का प्रतिनिधित्व करने वाला एक वर्ग हो सकता है।

अंत में, लेख में परमाणु चर के उपयोग पर मेरा अच्छा उदाहरण है, एक सरल बहु-थ्रेडेड प्रकार का डेटा एक्सेस और परमाणु चर ।

निष्कर्ष

मुझे उम्मीद है कि लेख दिलचस्प होगा। अतिरिक्त प्रश्नों के लिए, कृपया ई-मेल (मूल - अनुमानित प्रति।) में लिखें।

अनुवादक का नोट

यह और लेखक के अन्य लेख विषय पर सामग्री के अपने कवरेज में व्यापक होने का दावा नहीं करते हैं, लेकिन उनकी एक अच्छी प्रस्तुति प्रस्तुति शैली है।

मैं ध्यान देता हूं कि इस समय परमाणु चर:

• मानकों में वर्णित C11 (पी। 7.17) और C ++ 11 (पृष्ठ 29) - उनके कार्यान्वयन ज्यादातर मामलों में उपलब्ध हैं (हालांकि C11 के लिए अभी भी समस्याएं हैं);
• बूस्ट के रूप में बूस्ट के लिए वर्णित और कार्यान्वित किया गया। परमाणु (हालांकि, यह कार्यान्वयन 1.50 को बढ़ावा देने में कभी शामिल नहीं किया गया था);
• इंटेल थ्रेडिंग बिल्डिंग ब्लॉक में लागू किया गया।

RCU पर दस्तावेज़ के लेखक के लिंक के अलावा , यह उपयोगकर्ता के RCU प्रोजेक्ट को ध्यान देने योग्य है जो RCU को उपयोगकर्ता के लिए लागू करता है।