Non-blocking algorithm
कंप्यूटर विज्ञान में, एक एल्गोरिथ्म को गैर-अवरुद्ध कहा जाता है यदि किसी धागे की विफलता या निलंबन किसी अन्य धागे की विफलता या निलंबन का कारण नहीं बन सकता है; कुछ कार्यों के लिए, ये एल्गोरिदम पारंपरिक अवरुद्ध कार्यान्वयन के लिए एक उपयोगी विकल्प प्रदान करते हैं। एक गैर-अवरुद्ध एल्गोरिथ्म लॉक-मुक्त है यदि प्रणाली-व्यापी प्रगति की गारंटी है, और प्रतीक्षा-मुक्त है यदि प्रति-थ्रेड प्रगति की भी गारंटी है। 2003 में बाधा-स्वतंत्रता की शुरुआत होने तक साहित्य में "नॉन-ब्लॉकिंग" का उपयोग "लॉक-फ्री" के पर्याय के रूप में किया जाता था। "गैर-अवरुद्ध" शब्द का उपयोग पारंपरिक रूप से दूरसंचार नेटवर्क का वर्णन करने के लिए किया जाता था जो "मौजूदा कॉल को फिर से व्यवस्थित किए बिना" रिले के एक सेट के माध्यम से एक कनेक्शन को रूट कर सकता था (क्लोज नेटवर्क देखें)। इसके अलावा, यदि टेलीफोन एक्सचेंज "दोषपूर्ण नहीं है, तो यह हमेशा कनेक्शन बना सकता है" (नॉनब्लॉकिंग मिनिमल स्पैनिंग स्विच देखें)। प्रेरणा बहु-थ्रेडेड प्रोग्रामिंग के लिए पारंपरिक दृष्टिकोण साझा संसाधनों तक पहुंच को समन्वित करने के लिए ताले का उपयोग करना है। सिंक्रोनाइजेशन प्रिमिटिव्स जैसे म्यूटेक्स, सेमाफोर और क्रिटिकल सेक्शन वे सभी तंत्र हैं जिनके द्वारा एक प्रोग्रामर यह सुनिश्चित कर सकता है कि कोड के कुछ खंड समवर्ती रूप से निष्पादित नहीं होते हैं, यदि ऐसा करने से साझा स्मृति संरचनाएँ दूषित हो जाएंगी। यदि एक धागा एक ताला प्राप्त करने का प्रयास करता है जो पहले से ही दूसरे धागे से पकड़ा हुआ है, तो धागा तब तक अवरुद्ध रहेगा जब तक कि ताला मुक्त नहीं हो जाता। किसी धागे को अवरुद्ध करना कई कारणों से अवांछनीय हो सकता है। एक स्पष्ट कारण यह है कि जब धागा अवरुद्ध होता है, तो यह कुछ भी पूरा नहीं कर सकता हैः यदि अवरुद्ध धागा उच्च प्राथमिकता या वास्तविक समय का कार्य कर रहा होता, तो इसकी प्रगति को रोकना अत्यधिक अवांछनीय होता। अन्य समस्याएं कम स्पष्ट हैं। उदाहरण के लिए, ताले के बीच कुछ अंतःक्रियाएँ त्रुटि की स्थिति पैदा कर सकती हैं जैसे कि गतिरोध, लाइवलॉक और प्राथमिकता व्युत्क्रम। ताले के उपयोग में मोटे-दाने वाले ताला लगाने के बीच एक समझौता भी शामिल है, जो समानांतरता के अवसरों को काफी कम कर सकता है, और महीन-दाने वाले ताला लगाने, जिसके लिए अधिक सावधानीपूर्वक डिजाइन की आवश्यकता होती है, ऊपर से ताला लगाने को बढ़ाता है और कीड़े के लिए अधिक प्रवण होता है। ब्लॉकिंग एल्गोरिदम के विपरीत, नॉन-ब्लॉकिंग एल्गोरिदम इन डाउनसाइड से पीड़ित नहीं होते हैं, और इसके अलावा इंटरप्ट हैंडलर में उपयोग के लिए सुरक्षित हैंः भले ही प्रीएम्प्ट किए गए धागे को फिर से शुरू नहीं किया जा सकता है, फिर भी इसके बिना प्रगति संभव है। इसके विपरीत, पारस्परिक बहिष्कार द्वारा संरक्षित वैश्विक डेटा संरचनाओं को एक अवरोधन नियंत्रक में सुरक्षित रूप से एक्सेस नहीं किया जा सकता है, क्योंकि पूर्वनिर्धारित धागा ताला पकड़ने वाला हो सकता है-लेकिन महत्वपूर्ण खंड के दौरान अवरोधन अनुरोध को छिपाकर इसे आसानी से ठीक किया जा सकता है। प्रदर्शन में सुधार के लिए एक लॉक-फ्री डेटा संरचना का उपयोग किया जा सकता है। एक लॉक-फ्री डेटा संरचना सीरियल निष्पादन के बजाय समानांतर निष्पादन में बिताए गए समय की मात्रा को बढ़ाती है, जिससे मल्टी-कोर प्रोसेसर पर प्रदर्शन में सुधार होता है, क्योंकि साझा डेटा संरचना तक पहुंच को सुसंगत रहने के लिए क्रमबद्ध करने की आवश्यकता नहीं होती है। कार्यान्वयन कुछ अपवादों के साथ, गैर-अवरुद्ध एल्गोरिदम परमाणु पढ़ने-संशोधित-लिखने वाले आदिम का उपयोग करते हैं जो हार्डवेयर को प्रदान करना चाहिए, जिनमें से सबसे उल्लेखनीय तुलना और अदला-बदली (सीएएस) है। महत्वपूर्ण खंडों को लगभग हमेशा इन आदिमों पर मानक इंटरफेस का उपयोग करके लागू किया जाता है (सामान्य मामले में, महत्वपूर्ण खंड अवरुद्ध होंगे, भले ही इन आदिमों के साथ लागू किया गया हो)। 1990 के दशक में सभी गैर-अवरुद्ध एल्गोरिदम को स्वीकार्य प्रदर्शन प्राप्त करने के लिए अंतर्निहित आदिम के साथ "मूल रूप से" लिखा जाना था। हालांकि, सॉफ्टवेयर लेनदेन स्मृति का उभरता हुआ क्षेत्र कुशल गैर-अवरुद्ध कोड लिखने के लिए मानक अमूर्तता का वादा करता है। ढेर, कतार, सेट और हैश टेबल जैसी बुनियादी डेटा संरचनाएँ प्रदान करने में भी बहुत शोध किया गया है। ये कार्यक्रमों को असिंक्रोनस रूप से धागे के बीच आसानी से डेटा का आदान-प्रदान करने की अनुमति देते हैं। इसके अतिरिक्त, कुछ गैर-अवरुद्ध डेटा संरचनाएँ इतनी कमजोर हैं कि उन्हें विशेष परमाणु आदिम के बिना लागू किया जा सकता है। इन अपवादों में शामिल हैंः एक एकल-पाठक एकल-लेखक रिंग बफर एफ. आई. एफ. ओ., एक आकार के साथ जो उपलब्ध अहस्ताक्षरित पूर्णांक प्रकारों में से एक के अतिप्रवाह को समान रूप से विभाजित करता है, बिना शर्त केवल एक स्मृति बाधा रीड-कॉपी-अपडेट का उपयोग करके सुरक्षित रूप से लागू किया जा सकता है। (पाठक प्रतीक्षा-मुक्त होते हैं; लेखक आमतौर पर ताला-मुक्त होता है, जब तक कि उसे स्मृति को पुनः प्राप्त करने की आवश्यकता नहीं होती है)। कई लेखकों और किसी भी संख्या में पाठकों के साथ पढ़ें-प्रतिलिपि-अद्यतन। (पाठक प्रतीक्षा-मुक्त होते हैं; कई लेखक आम तौर पर एक ताला के साथ क्रमबद्ध होते हैं और बाधा-मुक्त नहीं होते हैं)। कई पुस्तकालय आंतरिक रूप से लॉक-फ्री तकनीकों का उपयोग करते हैं, लेकिन लॉक-फ्री कोड लिखना मुश्किल है जो सही हो। गैर-अवरुद्ध एल्गोरिदम में आम तौर पर सावधानीपूर्वक डिज़ाइन किए गए क्रम में पढ़ने, पढ़ने-संशोधित करने-लिखने और निर्देश लिखने की एक श्रृंखला शामिल होती है। संकलकों को अनुकूलित करने से आक्रामक रूप से संचालन को फिर से व्यवस्थित किया जा सकता है। यहां तक कि जब वे ऐसा नहीं करते हैं, तब भी कई आधुनिक सीपीयू अक्सर इस तरह के संचालन को फिर से व्यवस्थित करते हैं (उनके पास एक "कमजोर स्थिरता मॉडल" होता है), जब तक कि सीपीयू को फिर से व्यवस्थित न करने के लिए एक मेमोरी बैरियर का उपयोग नहीं किया जाता है। सी + + 11 प्रोग्रामर एसटीडीःः एटॉमिक इन <एटॉमिक> का उपयोग कर सकते हैं, और सी11 प्रोग्रामर <stdatomic.h> का उपयोग कर सकते हैं, जो दोनों प्रकार और कार्यों की आपूर्ति करते हैं जो संकलक को इस तरह के निर्देशों को फिर से व्यवस्थित नहीं करने के लिए कहते हैं, और उपयुक्त स्मृति बाधाओं को सम्मिलित करने के लिए कहते हैं। प्रतीक्षा-स्वतंत्रता प्रतीक्षा-स्वतंत्रता प्रगति की सबसे मजबूत गैर-अवरोधक गारंटी है, जो भुखमरी-स्वतंत्रता के साथ गारंटीकृत प्रणाली-व्यापी प्रवाह को जोड़ती है। एक एल्गोरिथ्म प्रतीक्षा-मुक्त होता है यदि प्रत्येक ऑपरेशन में ऑपरेशन पूरा होने से पहले एल्गोरिथ्म द्वारा उठाए जाने वाले चरणों की संख्या पर एक सीमा होती है। यह गुण वास्तविक-समय प्रणालियों के लिए महत्वपूर्ण है और जब तक प्रदर्शन लागत बहुत अधिक नहीं है तब तक रखना हमेशा अच्छा होता है। 1980 के दशक में यह दिखाया गया था कि सभी एल्गोरिदम को प्रतीक्षा-मुक्त रूप से लागू किया जा सकता है, और सीरियल कोड से कई परिवर्तन, जिन्हें सार्वभौमिक निर्माण कहा जाता है, प्रदर्शित किए गए हैं। हालांकि, परिणामी प्रदर्शन सामान्य रूप से सरल अवरोधक डिजाइनों से भी मेल नहीं खाता है। कई शोधपत्रों ने तब से सार्वभौमिक निर्माण के प्रदर्शन में सुधार किया है, लेकिन फिर भी, उनका प्रदर्शन अवरोधक डिजाइनों से बहुत कम है। कई शोधपत्रों ने प्रतीक्षा-मुक्त एल्गोरिदम बनाने की कठिनाई की जांच की है। उदाहरण के लिए, यह दिखाया गया है कि व्यापक रूप से उपलब्ध परमाणु सशर्त आदिम, सीएएस और एलएल/एससी, धागे की संख्या में रैखिक रूप से बढ़ती स्मृति लागत के बिना कई सामान्य डेटा संरचनाओं के भुखमरी-मुक्त कार्यान्वयन प्रदान नहीं कर सकते हैं। लेकिन व्यवहार में ये निचली सीमाएं एक वास्तविक बाधा प्रस्तुत नहीं करती हैं क्योंकि साझा स्मृति में प्रति धागे की कैश लाइन या विशेष आरक्षण कणिका (ए. आर. एम. पर 2 के. बी. तक) खर्च करना व्यावहारिक प्रणालियों के लिए बहुत महंगा नहीं माना जाता है (आमतौर पर तार्किक रूप से आवश्यक स्टोर की मात्रा एक शब्द है, लेकिन भौतिक रूप से उसी कैश लाइन पर सी. ए. एस. संचालन टकरा जाएगा, और उसी विशेष आरक्षण कणिका में एल. एल./एस. सी. संचालन टकरा जाएगा, इसलिए भौतिक रूप से आवश्यक स्टोर की मात्रा अधिक है)। 2011 तक अनुसंधान और व्यवहार दोनों में प्रतीक्षा-मुक्त एल्गोरिदम दुर्लभ थे। हालाँकि, 2011 में कोगन और पेट्रैंक ने सीएएस आदिम पर एक प्रतीक्षा-मुक्त कतार भवन प्रस्तुत किया, जो आम तौर पर सामान्य हार्डवेयर पर उपलब्ध था। उनके निर्माण ने माइकल और स्कॉट की ताला-मुक्त कतार का विस्तार किया, जो अक्सर व्यवहार में उपयोग की जाने वाली एक कुशल कतार है। कोगन और पेट्रैंक द्वारा एक अनुवर्ती पेपर ने प्रतीक्षा-मुक्त एल्गोरिदम को तेज़ बनाने के लिए एक विधि प्रदान की और प्रतीक्षा-मुक्त कतार को व्यावहारिक रूप से अपने लॉक-फ्री समकक्ष के रूप में तेज़ बनाने के लिए इस विधि का उपयोग किया। टिमनैट और पेट्रैंक द्वारा एक बाद के पेपर ने लॉक-फ्री से प्रतीक्षा-मुक्त डेटा संरचनाओं को उत्पन्न करने के लिए एक स्वचालित तंत्र प्रदान किया। इस प्रकार, अब कई डेटा-संरचनाओं के लिए प्रतीक्षा-मुक्त कार्यान्वयन उपलब्ध हैं। लॉक-फ्रीडम लॉक-फ्रीडम अलग-अलग धागे को भूखे रहने की अनुमति देता है लेकिन सिस्टम-वाइड थ्रूपुट की गारंटी देता है। एक एल्गोरिथ्म लॉक-फ्री होता है यदि, जब प्रोग्राम थ्रेड्स को पर्याप्त रूप से लंबे समय तक चलाया जाता है, तो कम से कम एक थ्रेड प्रगति करता है (प्रगति की कुछ समझदार परिभाषा के लिए)। सभी प्रतीक्षा-मुक्त एल्गोरिदम ताला-मुक्त हैं। विशेष रूप से, यदि एक धागे को निलंबित कर दिया जाता है, तो एक लॉक-फ्री एल्गोरिदम गारंटी देता है कि शेष धागे अभी भी प्रगति कर सकते हैं। इसलिए, यदि दो धागे एक ही म्यूटेक्स लॉक या स्पिनलॉक के लिए प्रतिस्पर्धा कर सकते हैं, तो एल्गोरिथ्म लॉक-फ्री नहीं है। (यदि हम एक धागे को लटकाते हैं जो ताला रखता है, तो दूसरा धागा अवरुद्ध हो जाएगा।) एक एल्गोरिथ्म लॉक-फ्री होता है यदि अनंत रूप से अक्सर कुछ प्रोसेसर द्वारा संचालन सीमित संख्या में चरणों में सफल होगा। उदाहरण के लिए, यदि प्रोसेसर एक ऑपरेशन को निष्पादित करने का प्रयास कर रहे हैं, तो कुछ प्रक्रियाएं सीमित संख्या में चरणों में ऑपरेशन को समाप्त करने में सफल होंगी और अन्य विफल हो सकती हैं और विफलता पर फिर से प्रयास कर सकती हैं। प्रतीक्षा-मुक्त और ताला-मुक्त के बीच का अंतर यह है कि प्रत्येक प्रक्रिया द्वारा प्रतीक्षा-मुक्त संचालन अन्य प्रोसेसर की परवाह किए बिना, सीमित संख्या में चरणों में सफल होने की गारंटी देता है। सामान्य तौर पर, एक लॉक-फ्री एल्गोरिथ्म चार चरणों में चल सकता हैः अपने स्वयं के संचालन को पूरा करना, एक अवरोधक संचालन में सहायता करना, एक अवरोधक संचालन को रद्द करना और प्रतीक्षा करना। समवर्ती सहायता और गर्भपात की संभावना के कारण अपने स्वयं के ऑपरेशन को पूरा करना जटिल है, लेकिन यह हमेशा पूरा होने का सबसे तेज़ रास्ता है। बाधा आने पर कब सहायता करनी है, उसे रोकना है या इंतजार करना है, इस बारे में निर्णय लेना एक विवाद प्रबंधक की जिम्मेदारी है। यह बहुत सरल हो सकता है (उच्च प्राथमिकता वाले संचालन में सहायता करना, कम प्राथमिकता वाले संचालन को रद्द करना), या बेहतर थ्रूपुट प्राप्त करने के लिए अधिक अनुकूलित किया जा सकता है, या प्राथमिकता वाले संचालन की विलंबता को कम किया जा सकता है। सही समवर्ती सहायता आम तौर पर एक लॉक-फ्री एल्गोरिथ्म का सबसे जटिल हिस्सा होता है, और अक्सर निष्पादित करने के लिए बहुत महंगा होता हैः न केवल सहायक धागा धीमा हो जाता है, बल्कि साझा स्मृति के यांत्रिकी के लिए धन्यवाद, सहायता प्राप्त धागा भी धीमा हो जाएगा, अगर यह अभी भी चल रहा है। बाधा-स्वतंत्रता-बाधा-स्वतंत्रता सबसे कमजोर प्राकृतिक गैर-अवरुद्ध प्रगति गारंटी है। एक एल्गोरिथ्म बाधा-मुक्त होता है यदि किसी भी बिंदु पर, एक सीमित संख्या में चरणों के लिए अलगाव में निष्पादित एक एकल धागा (यानी, सभी बाधा डालने वाले धागे निलंबित होने के साथ) अपने संचालन को पूरा करेगा। सभी लॉक-फ्री एल्गोरिदम बाधा-मुक्त हैं। बाधा-स्वतंत्रता केवल यह माँग करती है कि किसी भी आंशिक रूप से पूर्ण ऑपरेशन को निरस्त किया जा सकता है और किए गए परिवर्तनों को वापस लिया जा सकता है। समवर्ती सहायता को छोड़ने के परिणामस्वरूप अक्सर बहुत सरल एल्गोरिदम हो सकते हैं जिन्हें मान्य करना आसान होता है। सिस्टम को लगातार लाइव-लॉकिंग से रोकना एक विवाद प्रबंधक का काम है। कुछ बाधा-मुक्त एल्गोरिदम डेटा संरचना में "स्थिरता मार्करों" की एक जोड़ी का उपयोग करते हैं। डेटा संरचना को पढ़ने वाली प्रक्रियाएं पहले एक स्थिरता मार्कर को पढ़ती हैं, फिर प्रासंगिक डेटा को एक आंतरिक बफर में पढ़ती हैं, फिर दूसरे मार्कर को पढ़ती हैं, और फिर मार्करों की तुलना करती हैं। यदि दोनों मार्कर समान हैं तो डेटा सुसंगत है। मार्कर गैर-समान हो सकते हैं जब डेटा संरचना को अद्यतन करने वाली किसी अन्य प्रक्रिया द्वारा पढ़ने में बाधा आती है। ऐसे मामले में, प्रक्रिया आंतरिक बफर में डेटा को छोड़ देती है और फिर से प्रयास करती है। डेडलॉक जावा ConcurrentMap#Lock-मुक्त परमाणु जीवंतता लॉक (कंप्यूटर विज्ञान) पारस्परिक बहिष्कार प्राथमिकता व्युत्क्रम संसाधन भुखमरी संदर्भ बाहरी लिंक लॉक-फ्री प्रोग्रामिंग गैर-अवरुद्ध एल्गोरिदम सिंक्रोनाइजेशन समवर्ती नियंत्रण समवर्ती नियंत्रण एल्गोरिदम का परिचय