पारस्परिक अपवर्जन

For तर्क और संभाव्यता सिद्धांत में अवधारणा, see पारस्परिक विशिष्टता.

दो नोड, i और i + 1, एक साथ हटाए जाने के परिणामस्वरूप नोड i + 1 हटाया नहीं जा रहा है।

कंप्यूटर विज्ञान में, पारस्परिक अपवर्जन संगामिति नियंत्रण का गुण है, जिसे दौड़ की स्थिति को रोकने के उद्देश्य से स्थापित किया गया है। यह आवश्यक है कि थ्रेड (कंप्यूटिंग) कभी भी महत्वपूर्ण खंड में प्रवेश न करे, जबकि निष्पादन का समवर्ती कंप्यूटिंग थ्रेड पहले से ही उक्त महत्वपूर्ण खंड तक पहुंच रहा है, जो उस समय के अंतराल को संदर्भित करता है जिसके समय निष्पादन का थ्रेड साझा संसाधन या साझा मेमोरी तक पहुंचता है।

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

पारस्परिक अपवर्जन की आवश्यकता को सबसे पहले एड्जर डब्ल्यू. डिज्कस्ट्रा ने अपने मौलिक 1965 के शोध पत्र समवर्ती प्रोग्रामिंग नियंत्रण में समस्या का समाधान में पहचाना और हल किया था। जिसे समवर्ती एल्गोरिदम के अध्ययन में पहले विषय के रूप में श्रेय दिया जाता है।

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

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

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

समस्या विवरण

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

इस समस्या के सफल समाधान में कम से कम ये दो गुण होने चाहिए:

• इसे आपसी बहिष्कार को प्रयुक्त करना चाहिए: एक समय में केवल एक ही प्रक्रिया महत्वपूर्ण खंड में हो सकती है।
• यह गतिरोध से मुक्त होना चाहिए: यदि प्रक्रियाएं महत्वपूर्ण खंड में प्रवेश करने का प्रयास कर रही हैं, तो उनमें से एक को अंततः सफलतापूर्वक ऐसा करने में सक्षम होना चाहिए, बशर्ते कोई प्रक्रिया स्थायी रूप से महत्वपूर्ण खंड में न रहे।

इनमें से एक या दोनों गुणों को प्रयुक्त करने के लिए डेडलॉक स्वतंत्रता का विस्तार किया जा सकता है:

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

प्रत्येक प्रक्रिया के कार्यक्रम को चार वर्गों में विभाजित किया जा सकता है, जिसके परिणामस्वरूप चार अवस्थाएँ होती हैं। क्रम में इन चार स्थितियों के माध्यम से कार्यक्रम निष्पादन चक्र:

एकल प्रक्रिया के वर्गों का चक्र

नॉन-क्रिटिकल अनुभाग: ऑपरेशन क्रिटिकल अनुभाग के बाहर है; प्रक्रिया साझा संसाधन का उपयोग या अनुरोध नहीं कर रही है। प्रयास कर रहा है: प्रक्रिया महत्वपूर्ण खंड में प्रवेश करने का प्रयास करती है।

क्रिटिकल अनुभाग: प्रक्रिया को इस अनुभाग में साझा संसाधन तक पहुंचने की अनुमति है।

बाहर निकलें: प्रक्रिया महत्वपूर्ण खंड को छोड़ देती है और साझा संसाधनों को अन्य प्रक्रियाओं के लिए उपलब्ध कराती है।

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

आपसी बहिष्कार प्रयुक्त करना

हार्डवेयर समाधान

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

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

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

सॉफ्टवेयर समाधान

हार्डवेयर-समर्थित समाधानों के अतिरिक्त, कुछ सॉफ़्टवेयर समाधान उपस्थित हैं जो परस्पर अपवर्जन प्राप्त करने के लिए व्यस्त प्रतीक्षा का उपयोग करते हैं। उदाहरणों में सम्मिलित:

• डेकर का एल्गोरिदम
• पीटरसन का एल्गोरिदम
• लामपोर्ट का बेकरी एल्गोरिथम
• सिजमेंस्की का एल्गोरिथम
• तौबेनफेल्ड का ब्लैक-एंड-व्हाइट बेकरी एल्गोरिथम* मकावा का एल्गोरिदम

ये एल्गोरिदम काम नहीं करते हैं यदि उन्हें निष्पादित करने वाले प्लेटफॉर्म पर आउट-ऑफ-ऑर्डर निष्पादन का उपयोग किया जाता है। प्रोग्रामर को थ्रेड के अन्दर मेमोरी ऑपरेशंस पर सख्त ऑर्डर देना होता है।

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

पारस्परिक अपवर्जन समस्या पर बाध्य

आपसी अपवर्जन समस्या का डेडलॉक-मुक्त समाधान प्रदान करने के लिए बाइनरी टेस्ट-एंड-सेट टेस्ट और सेट रजिस्टर पर्याप्त है। लेकिन परीक्षण और सेट रजिस्टर के साथ बनाया गया समाधान संभवतः कुछ प्रक्रियाओं की भुखमरी का कारण बन सकता है जो प्रयास करने वाले खंड में फंस जाती हैं। वास्तव में, $\Omega ({\sqrt {n}})$ लॉकआउट से बचने के लिए अलग-अलग मेमोरी स्टेट्स की आवश्यकता होती है। अनबाउंड वेटिंग से बचने के लिए, अलग-अलग मेमोरी स्टेट्स की आवश्यकता होती है।

पुनर्प्राप्त करने योग्य पारस्परिक अपवर्जन

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

पारस्परिक अपवर्जन उपकरणों के प्रकार

ऊपर बताए गए समाधानों का उपयोग नीचे दिए गए सिंक्रोनाइज़ेशन प्रिमिटिव बनाने के लिए किया जा सकता है:

• ताला (कंप्यूटर विज्ञान) (म्यूटेक्स)
• पाठक-लेखक ताले
• पुनः प्रवेशी म्यूटेक्स
• सेमाफोर (प्रोग्रामिंग)
• मॉनिटर (सिंक्रनाइज़ेशन)
• संदेश देना
• टपल स्पेस

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

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

यह भी देखें

• परमाणुता (प्रोग्रामिंग)
• समरूपता नियंत्रण
• भोजन दार्शनिकों की समस्या
• एकमात्र
• परस्पर अनन्य कार्यक्रम
• रेंट्रेंट म्यूटेक्स
• सेमाफोर (प्रोग्रामिंग)
• स्पिनलॉक

अग्रिम पठन

• Michel Raynal: Algorithms for Mutual Exclusion, MIT Press, ISBN 0-262-18119-3
• Sunil R. Das, Pradip K. Srimani: Distributed Mutual Exclusion Algorithms, IEEE Computer Society, ISBN 0-8186-3380-8
• Thomas W. Christopher, George K. Thiruvathukal: High-Performance Java Platform Computing, Prentice Hall, ISBN 0-13-016164-0
• Gadi Taubenfeld, Synchronization Algorithms and Concurrent Programming, Pearson/Prentice Hall, ISBN 0-13-197259-6

बाहरी संबंध

• Common threads: POSIX threads explained – The little things called mutexes" by Daniel Robbins
• Mutual Exclusion Petri Net at the Wayback Machine (archived 2016-06-02)
• Mutual Exclusion with Locks – an Introduction
• Mutual exclusion variants in OpenMP
• The Black-White Bakery Algorithm