गैर-अवरुद्ध एल्गोरिदम: Difference between revisions

From Vigyanwiki
(Created page with "{{Short description|Algorithm in a thread whose failure cannot cause another thread to fail}} {{Distinguish|non-blocking I/O}} कंप्यूटर विज्ञा...")
 
No edit summary
Line 2: Line 2:
{{Distinguish|non-blocking I/O}}
{{Distinguish|non-blocking I/O}}


[[कंप्यूटर विज्ञान]] में, एक [[कलन विधि]] को गैर-अवरुद्ध कहा जाता है यदि किसी [[थ्रेड (कंप्यूटिंग)]] की विफलता या [[ निर्धारण (कंप्यूटिंग) ]] किसी अन्य थ्रेड की विफलता या निलंबन का कारण नहीं बन सकती है;<ref>{{cite book|last1=Göetz|first1=Brian|last2=Peierls|first2=Tim|last3=Bloch|first3=Joshua|last4=Bowbeer|first4=Joseph|last5=Holmes|first5=David|last6=Lea|first6=Doug|title=व्यवहार में जावा संगामिति|date=2006|publisher=Addison-Wesley|location=Upper Saddle River, NJ|isbn=9780321349606|page=[https://archive.org/details/javaconcurrencyi00goet/page/41 41]|url-access=registration|url=https://archive.org/details/javaconcurrencyi00goet/page/41}}</ref> कुछ कार्यों के लिए, ये एल्गोरिदम पारंपरिक लॉक (कंप्यूटर विज्ञान) के लिए एक उपयोगी विकल्प प्रदान करते हैं। एक गैर-अवरुद्ध एल्गोरिथम लॉक-फ्री है यदि सिस्टम-वाइड रिसोर्स भुखमरी की गारंटी है, और प्रति-थ्रेड प्रगति की गारंटी होने पर प्रतीक्षा-मुक्त है। 2003 में बाधा-मुक्ति की शुरूआत तक गैर-अवरुद्ध को साहित्य में लॉक-फ्री के पर्याय के रूप में इस्तेमाल किया गया था।<ref name=obs-free>{{cite conference|last1=Herlihy|first1=M.|last2=Luchangco|first2=V.|last3=Moir|first3=M.|title=Obstruction-Free Synchronization: Double-Ended Queues as an Example|conference=23rd [[International Conference on Distributed Computing Systems]]|year=2003|pages=522|url=http://www.cs.brown.edu/people/mph/HerlihyLM03/main.pdf}}</ref>
[[कंप्यूटर विज्ञान]] में,[[कलन विधि]] को गैर-अवरुद्ध कहा जाता है यदि किसी [[थ्रेड (कंप्यूटिंग)]] की विफलता या [[ निर्धारण (कंप्यूटिंग) ]] किसी अन्य थ्रेड की विफलता या निलंबन का कारण नहीं बन सकती है।<ref>{{cite book|last1=Göetz|first1=Brian|last2=Peierls|first2=Tim|last3=Bloch|first3=Joshua|last4=Bowbeer|first4=Joseph|last5=Holmes|first5=David|last6=Lea|first6=Doug|title=व्यवहार में जावा संगामिति|date=2006|publisher=Addison-Wesley|location=Upper Saddle River, NJ|isbn=9780321349606|page=[https://archive.org/details/javaconcurrencyi00goet/page/41 41]|url-access=registration|url=https://archive.org/details/javaconcurrencyi00goet/page/41}}</ref> कुछ कार्यों के लिए, यह एल्गोरिदम पारंपरिक लॉक (कंप्यूटर विज्ञान) के लिएउपयोगी विकल्प प्रदान करते हैं।गैर-अवरुद्ध एल्गोरिथम लॉक-फ्री है यदि सिस्टम-वाइड रिसोर्स भुखमरी की गारंटी है, और प्रति-थ्रेड प्रगति की गारंटी होने पर प्रतीक्षा-मुक्त है। 2003 में बाधा-मुक्ति की प्रारंभिक तक गैर-अवरुद्ध को साहित्य में लॉक-फ्री के पर्याय के रूप में उपयोग किया गया था।<ref name=obs-free>{{cite conference|last1=Herlihy|first1=M.|last2=Luchangco|first2=V.|last3=Moir|first3=M.|title=Obstruction-Free Synchronization: Double-Ended Queues as an Example|conference=23rd [[International Conference on Distributed Computing Systems]]|year=2003|pages=522|url=http://www.cs.brown.edu/people/mph/HerlihyLM03/main.pdf}}</ref>
नॉन-ब्लॉकिंग शब्द का पारंपरिक रूप से [[दूरसंचार नेटवर्क]] का वर्णन करने के लिए उपयोग किया जाता था जो मौजूदा कॉल को फिर से व्यवस्थित किए बिना रिले के एक सेट के माध्यम से एक कनेक्शन को रूट कर सकता था (Clos नेटवर्क देखें)। इसके अलावा, यदि टेलीफोन एक्सचेंज दोषपूर्ण नहीं है, तो यह हमेशा कनेक्शन बना सकता है (न्यूनतम स्पैनिंग स्विच को अनब्लॉक करना देखें)।
नॉन-ब्लॉकिंग शब्द का पारंपरिक रूप से [[दूरसंचार नेटवर्क]] का वर्णन करने के लिए उपयोग किया जाता था जो उपस्तिथ कॉल को फिर से व्यवस्थित किए बिना रिले केसेट के माध्यम सेकनेक्शन को रूट कर सकता था (Clos नेटवर्क देखें)। इसके अतिरिक्त, यदि टेलीफोन एक्सचेंज दोषपूर्ण नहीं है, तो यह हमेशा कनेक्शन बना सकता है (न्यूनतम स्पैनिंग स्विच को अनब्लॉक करना देखें)।


== प्रेरणा ==
== प्रेरणा ==
{{Main|Lock (computer science)#Disadvantages|l1=Disadvantages of locks}}
{{Main|Lock (computer science)#Disadvantages|l1=Disadvantages of locks}}


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


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


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


ब्लॉकिंग एल्गोरिदम के विपरीत, नॉन-ब्लॉकिंग एल्गोरिदम इन डाउनसाइड्स से ग्रस्त नहीं हैं, और इसके अलावा [[इंटरप्ट हैंडलर]]्स में उपयोग के लिए सुरक्षित हैं: भले ही [[पूर्व-खाली मल्टीटास्किंग]] थ्रेड को फिर से शुरू नहीं किया जा सकता है, फिर भी इसके बिना प्रगति संभव है। इसके विपरीत, आपसी बहिष्करण द्वारा संरक्षित वैश्विक डेटा संरचनाओं को एक इंटरप्ट हैंडलर में सुरक्षित रूप से एक्सेस नहीं किया जा सकता है, क्योंकि प्रीमेप्टेड थ्रेड लॉक को होल्ड करने वाला हो सकता है - लेकिन [[ महत्वपूर्ण अनुभाग ]] के दौरान इंटरप्ट रिक्वेस्ट को मास्क करके इसे आसानी से ठीक किया जा सकता है।<ref name="monit">{{cite journal | doi = 10.1145/358818.358824 | url = http://research.microsoft.com/lampson/23-ProcessesInMesa/Abstract.html | title = मेसा में प्रक्रियाओं और मॉनिटर के साथ अनुभव| author = Butler W. Lampson | author-link = Butler W. Lampson |author2=David D. Redell |author2-link=David D. Redell | journal = Communications of the ACM | volume = 23 | issue = 2 | pages = 105–117 |date=February 1980| citeseerx = 10.1.1.142.5765 | s2cid = 1594544 }}</ref>
ब्लॉकिंग एल्गोरिदम के विपरीत, नॉन-ब्लॉकिंग एल्गोरिदम इन डाउनसाइड्स से ग्रस्त नहीं हैं, और इसके अतिरिक्त [[इंटरप्ट हैंडलर]]्स में उपयोग के लिए सुरक्षित हैं: यदि [[पूर्व-खाली मल्टीटास्किंग]] थ्रेड को फिर से प्रारंभ नहीं किया जा सकता है, फिर भी इसके बिना प्रगति संभव है। इसके विपरीत, आपसी बहिष्करण द्वारा संरक्षित वैश्विक डेटा संरचनाओं कोइंटरप्ट हैंडलर में सुरक्षित रूप से एक्सेस नहीं किया जा सकता है, क्योंकि प्रीमेप्टेड थ्रेड लॉक को होल्ड करने वाला हो सकता है - [[ महत्वपूर्ण अनुभाग ]] के समय इंटरप्ट रिक्वेस्ट को मास्क करके इसे आसानी से ठीक किया जा सकता है।<ref name="monit">{{cite journal | doi = 10.1145/358818.358824 | url = http://research.microsoft.com/lampson/23-ProcessesInMesa/Abstract.html | title = मेसा में प्रक्रियाओं और मॉनिटर के साथ अनुभव| author = Butler W. Lampson | author-link = Butler W. Lampson |author2=David D. Redell |author2-link=David D. Redell | journal = Communications of the ACM | volume = 23 | issue = 2 | pages = 105–117 |date=February 1980| citeseerx = 10.1.1.142.5765 | s2cid = 1594544 }}</ref>
प्रदर्शन को बेहतर बनाने के लिए लॉक-फ्री डेटा संरचना का उपयोग किया जा सकता है।
प्रदर्शन को उत्तम बनाने के लिए लॉक-फ्री डेटा संरचना का उपयोग किया जा सकता है।
एक लॉक-मुक्त डेटा संरचना सीरियल निष्पादन के बजाय समानांतर निष्पादन में बिताए गए समय की मात्रा को बढ़ाती है, [[मल्टी-कोर प्रोसेसर]] पर प्रदर्शन में सुधार करती है, क्योंकि साझा डेटा संरचना तक पहुंच को सुसंगत रहने के लिए क्रमबद्ध करने की आवश्यकता नहीं होती है।<ref>
एक लॉक-मुक्त डेटा संरचना सीरियल निष्पादन के अतिरिक्त समानांतर निष्पादन में बिताए गए समय की मात्रा को बढ़ाती है, [[मल्टी-कोर प्रोसेसर]] पर प्रदर्शन में सुधार करती है, क्योंकि साझा डेटा संरचना तक पहुंच को सुसंगत रहने के लिए क्रमबद्ध करने की आवश्यकता नहीं होती है।<ref>
Guillaume Marçais, and Carl Kingsford.
Guillaume Marçais, and Carl Kingsford.
[https://web.archive.org/web/20140518060917/http://bioinformatics.oxfordjournals.org/content/27/6/764.abstract "A fast, lock-free approach for efficient parallel counting of occurrences of k-mers"].
[https://web.archive.org/web/20140518060917/http://bioinformatics.oxfordjournals.org/content/27/6/764.abstract "A fast, lock-free approach for efficient parallel counting of occurrences of k-mers"].
Line 26: Line 26:


== कार्यान्वयन ==
== कार्यान्वयन ==
कुछ अपवादों के साथ, नॉन-ब्लॉकिंग एल्गोरिदम [[रैखिकता]] [[ पढ़ने के लिए संशोधित-लिखने ]] प्रिमिटिव का उपयोग करते हैं जो हार्डवेयर को प्रदान करना चाहिए, जिनमें से सबसे उल्लेखनीय तुलना-और-स्वैप|तुलना और स्वैप (CAS) है। इन प्रिमिटिव्स पर मानक इंटरफेस का उपयोग करके क्रिटिकल सेक्शन लगभग हमेशा लागू किए जाते हैं (सामान्य स्थिति में, इन प्रिमिटिव्स के साथ लागू होने पर भी क्रिटिकल सेक्शन ब्लॉक हो जाएंगे)। 1990 के दशक में स्वीकार्य प्रदर्शन प्राप्त करने के लिए सभी गैर-अवरुद्ध एल्गोरिदम को अंतर्निहित आदिम के साथ मूल रूप से लिखा जाना था। हालाँकि, [[ सॉफ्टवेयर लेनदेन स्मृति ]] का उभरता हुआ क्षेत्र कुशल नॉन-ब्लॉकिंग कोड लिखने के लिए मानक अमूर्तता का वादा करता है।<ref name=lightweight-transactions>{{cite journal|last1=Harris|first1=Tim|last2=Fraser|first2=Keir|title=हल्के लेनदेन के लिए भाषा समर्थन|journal=ACM SIGPLAN Notices|date=26 November 2003|volume=38|issue=11|pages=388|doi=10.1145/949343.949340|url=http://research.microsoft.com/en-us/um/people/tharris/papers/2003-oopsla.pdf|citeseerx=10.1.1.58.8466}}</ref><ref name=composable-memory-transactions>{{cite book|last1=Harris|first1=Tim|last2=Marlow|first2=S.|last3=Peyton-Jones|first3=S.|last4=Herlihy|first4=M.|title=Proceedings of the 2005 ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP '05 : Chicago, Illinois|publisher=ACM Press|location=New York, NY|isbn=978-1-59593-080-4|pages=48–60|chapter=Composable memory transactions|date=June 15–17, 2005|doi=10.1145/1065944.1065952|s2cid=53245159 }}</ref>
कुछ अपवादों के साथ, नॉन-ब्लॉकिंग एल्गोरिदम [[रैखिकता]] [[ पढ़ने के लिए संशोधित-लिखने ]] प्रिमिटिव का उपयोग करते हैं जो हार्डवेयर को प्रदान करना चाहिए, जिनमें से सबसे उल्लेखनीय तुलना-और-स्वैप|तुलना और स्वैप (CAS) है। इन प्रिमिटिव्स पर मानक इंटरफेस का उपयोग करके क्रिटिकल सेक्शन लगभग हमेशा लागू किए जाते हैं (सामान्य स्थिति में, इन प्रिमिटिव्स के साथ लागू होने पर भी क्रिटिकल सेक्शन ब्लॉक हो जाएंगे)। 1990 के दशक में स्वीकार्य प्रदर्शन प्राप्त करने के लिए सभी गैर-अवरुद्ध एल्गोरिदम को अंतर्निहित आदिम के साथ मूल रूप से लिखा जाना था। चूँकि, [[ सॉफ्टवेयर लेनदेन स्मृति ]] का उभरता हुआ क्षेत्र कुशल नॉन-ब्लॉकिंग कोड लिखने के लिए मानक अमूर्तता का वादा करता है।<ref name=lightweight-transactions>{{cite journal|last1=Harris|first1=Tim|last2=Fraser|first2=Keir|title=हल्के लेनदेन के लिए भाषा समर्थन|journal=ACM SIGPLAN Notices|date=26 November 2003|volume=38|issue=11|pages=388|doi=10.1145/949343.949340|url=http://research.microsoft.com/en-us/um/people/tharris/papers/2003-oopsla.pdf|citeseerx=10.1.1.58.8466}}</ref><ref name=composable-memory-transactions>{{cite book|last1=Harris|first1=Tim|last2=Marlow|first2=S.|last3=Peyton-Jones|first3=S.|last4=Herlihy|first4=M.|title=Proceedings of the 2005 ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP '05 : Chicago, Illinois|publisher=ACM Press|location=New York, NY|isbn=978-1-59593-080-4|pages=48–60|chapter=Composable memory transactions|date=June 15–17, 2005|doi=10.1145/1065944.1065952|s2cid=53245159 }}</ref>
स्टैक ([[डेटा संरचना]]), [[कतार (डेटा संरचना)]], [[सेट (कंप्यूटर विज्ञान)]], और [[ हैश तालिका ]] जैसी बुनियादी डेटा संरचनाएँ प्रदान करने में बहुत शोध किया गया है। ये प्रोग्राम को आसानी से थ्रेड्स के बीच अतुल्यकालिक रूप से डेटा का आदान-प्रदान करने की अनुमति देते हैं।
स्टैक ([[डेटा संरचना]]), [[कतार (डेटा संरचना)]], [[सेट (कंप्यूटर विज्ञान)]], और [[ हैश तालिका ]] जैसी बुनियादी डेटा संरचनाएँ प्रदान करने में बहुत शोध किया गया है। ये प्रोग्राम को आसानी से थ्रेड्स के बीच अतुल्यकालिक रूप से डेटा का आदान-प्रदान करने की अनुमति देते हैं।


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


* एक एकल-पाठक एकल-लेखक परिपत्र बफर FIFO (कंप्यूटिंग और इलेक्ट्रॉनिक्स), एक आकार के साथ जो समान रूप से उपलब्ध अहस्ताक्षरित पूर्णांक प्रकारों में से एक के अतिप्रवाह को विभाजित करता है, बिना शर्त के निर्माता-उपभोक्ता समस्या हो सकती है # केवल एक मेमोरी का उपयोग करके सेमाफोर या मॉनिटर के बिना रुकावट
* एक एकल-पाठक एकल-लेखक परिपत्र बफर FIFO (कंप्यूटिंग और इलेक्ट्रॉनिक्स),आकार के साथ जो समान रूप से उपलब्ध अहस्ताक्षरित पूर्णांक प्रकारों में सेके अतिप्रवाह को विभाजित करता है, बिना शर्त के निर्माता-उपभोक्ता समस्या हो सकती है # केवलमेमोरी का उपयोग करके सेमाफोर या मॉनिटर के बिना रुकावट
* एक लेखक और कितने भी पाठकों के साथ पढ़ें-कॉपी-अपडेट करें। (पाठक प्रतीक्षा-मुक्त हैं; लेखक आमतौर पर लॉक-मुक्त होता है, जब तक कि उसे स्मृति को पुनः प्राप्त करने की आवश्यकता न हो)।
* एक लेखक और कितने भी पाठकों के साथ पढ़ें-कॉपी-अपडेट करें। (पाठक प्रतीक्षा-मुक्त हैं; लेखक सामान्यतः लॉक-मुक्त होता है, जब तक कि उसे स्मृति को पुनः प्राप्त करने की आवश्यकता न हो)।
* कई लेखकों और पाठकों की संख्या के साथ [[रीड-कॉपी-अपडेट]]। (पाठक प्रतीक्षा-मुक्त हैं; कई लेखक आमतौर पर एक ताला के साथ क्रमबद्ध होते हैं और बाधा-मुक्त नहीं होते हैं)।
* कई लेखकों और पाठकों की संख्या के साथ [[रीड-कॉपी-अपडेट]]। (पाठक प्रतीक्षा-मुक्त हैं; कई लेखक सामान्यतःताला के साथ क्रमबद्ध होते हैं और बाधा-मुक्त नहीं होते हैं)।


कई पुस्तकालय आंतरिक रूप से लॉक-फ्री तकनीकों का उपयोग करते हैं,<ref>
कई पुस्तकालय आंतरिक रूप से लॉक-फ्री तकनीकों का उपयोग करते हैं,<ref>
Line 41: Line 41:
</ref><ref>
</ref><ref>
  [http://concurrencykit.org Concurrency Kit] - A C library for non-blocking system design and implementation
  [http://concurrencykit.org Concurrency Kit] - A C library for non-blocking system design and implementation
</ref> लेकिन लॉक-फ्री कोड लिखना मुश्किल है जो सही हो।<ref name="A_FALSE_SENSE_OF_SECURITY">हर्ब सटर। {{cite web | url=http://www.drdobbs.com/article/print?articleId=210600279&siteSectionName=cpp | title=लॉक-फ्री कोड: सुरक्षा की झूठी भावना| archive-url=https://web.archive.org/web/20150901211737/http://www.drdobbs.com/article/print?articleId=210600279&siteSectionName=cpp | archive-date=2015-09-01 |url-status=dead}}</ref><ref name="A_CORRECTED_QUEUE">हर्ब सटर। {{cite web | archive-url=https://web.archive.org/web/20081205072023/http://www.ddj.com/cpp/210604448 | title=लॉक-फ्री कोड लिखना: एक सही कतार| archive-date=2008-12-05 | url-status=dead | url=http://www.ddj.com/cpp/210604448 }}</ref><ref>
</ref> लॉक-फ्री कोड लिखना कठिनाई है जो सही हो।<ref name="A_FALSE_SENSE_OF_SECURITY">हर्ब सटर। {{cite web | url=http://www.drdobbs.com/article/print?articleId=210600279&siteSectionName=cpp | title=लॉक-फ्री कोड: सुरक्षा की झूठी भावना| archive-url=https://web.archive.org/web/20150901211737/http://www.drdobbs.com/article/print?articleId=210600279&siteSectionName=cpp | archive-date=2015-09-01 |url-status=dead}}</ref><ref name="A_CORRECTED_QUEUE">हर्ब सटर। {{cite web | archive-url=https://web.archive.org/web/20081205072023/http://www.ddj.com/cpp/210604448 | title=लॉक-फ्री कोड लिखना: एक सही कतार| archive-date=2008-12-05 | url-status=dead | url=http://www.ddj.com/cpp/210604448 }}</ref><ref>
  Herb Sutter. [http://www.ddj.com/cpp/211601363 "Writing a Generalized Concurrent Queue"].
  Herb Sutter. [http://www.ddj.com/cpp/211601363 "Writing a Generalized Concurrent Queue"].
</ref><ref>
</ref><ref>
  Herb Sutter. [http://www.ddj.com/cpp/184401930 "The Trouble With Locks"].
  Herb Sutter. [http://www.ddj.com/cpp/184401930 "The Trouble With Locks"].
</ref>
</ref>
गैर-अवरुद्ध एल्गोरिदम में आम तौर पर ध्यान से डिज़ाइन किए गए क्रम में पढ़ने, पढ़ने-संशोधित करने-लिखने और निर्देश लिखने की एक श्रृंखला शामिल होती है।
गैर-अवरुद्ध एल्गोरिदम में सामान्यतः ध्यान से डिज़ाइन किए गए क्रम में पढ़ने, पढ़ने-संशोधित करने-लिखने और निर्देश लिखने कीश्रृंखला सम्मिलित होती है।
ऑप्टिमाइज़िंग कंपाइलर आक्रामक रूप से संचालन को फिर से व्यवस्थित कर सकते हैं।
ऑप्टिमाइज़िंग कंपाइलर आक्रामक रूप से संचालन को फिर से व्यवस्थित कर सकते हैं।
यहां तक ​​​​कि जब वे नहीं करते हैं, तब भी कई आधुनिक सीपीयू अक्सर ऐसे कार्यों को फिर से व्यवस्थित करते हैं (उनके पास एक कमजोर स्थिरता मॉडल है),
यहां तक ​​​​कि जब वे नहीं करते हैं, तब भी कई आधुनिक सीपीयू अधिकांशतः ऐसे कार्यों को फिर से व्यवस्थित करते हैं (उनके पासकमजोर स्थिरता मॉडल है),
जब तक कि सीपीयू को पुन: व्यवस्थित न करने के लिए मेमोरी बैरियर का उपयोग नहीं किया जाता है।
जब तक कि सीपीयू को पुन: व्यवस्थित न करने के लिए मेमोरी बैरियर का उपयोग नहीं किया जाता है।
[[C++11]] प्रोग्रामर उपयोग कर सकते हैं <code>std::atomic</code> में <code>&lt;atomic&gt;</code>,
[[C++11]] प्रोग्रामर उपयोग कर सकते हैं <code>std::atomic</code> में <code>&lt;atomic&gt;</code>,
Line 59: Line 59:


== प्रतीक्षा-मुक्ति ==
== प्रतीक्षा-मुक्ति ==
प्रतीक्षा-स्वतंत्रता प्रगति की सबसे मजबूत गैर-अवरुद्ध गारंटी है, संसाधन भुखमरी-स्वतंत्रता के साथ गारंटीकृत सिस्टम-वाइड थ्रूपुट का संयोजन। एक एल्गोरिथम प्रतीक्षा-मुक्त है यदि प्रत्येक ऑपरेशन में ऑपरेशन पूरा होने से पहले एल्गोरिथ्म द्वारा उठाए जाने वाले कदमों की संख्या पर एक सीमा होती है।<ref name="awilliams">
प्रतीक्षा-स्वतंत्रता प्रगति की सबसे मजबूत गैर-अवरुद्ध गारंटी है, संसाधन भुखमरी-स्वतंत्रता के साथ गारंटीकृत सिस्टम-वाइड थ्रूपुट का संयोजन।एल्गोरिथम प्रतीक्षा-मुक्त है यदि प्रत्येक ऑपरेशन में ऑपरेशन पूरा होने से पहले एल्गोरिथ्म द्वारा उठाए जाने वाले कदमों की संख्या परसीमा होती है।<ref name="awilliams">
Anthony Williams.
Anthony Williams.
[https://www.justsoftwaresolutions.co.uk//files/safety_off.pdf "Safety: off: How not to shoot yourself in the foot with C++ atomics"].
[https://www.justsoftwaresolutions.co.uk//files/safety_off.pdf "Safety: off: How not to shoot yourself in the foot with C++ atomics"].
Line 67: Line 67:
यह संपत्ति रीयल-टाइम सिस्टम के लिए महत्वपूर्ण है और जब तक प्रदर्शन लागत बहुत अधिक नहीं है तब तक हमेशा अच्छा होता है।
यह संपत्ति रीयल-टाइम सिस्टम के लिए महत्वपूर्ण है और जब तक प्रदर्शन लागत बहुत अधिक नहीं है तब तक हमेशा अच्छा होता है।


इसे 1980 के दशक में दिखाया गया था<ref name=imp>{{cite conference |last=Herlihy |first=Maurice P. |conference=Proc. 7th Annual ACM Symp. on Principles of Distributed Computing |isbn=0-89791-277-2 |pages=276–290 |doi=10.1145/62546.62593 |title=प्रतीक्षा-मुक्त तुल्यकालन के लिए असंभवता और सार्वभौमिकता परिणाम|year=1988|doi-access=free }}</ref> कि सभी एल्गोरिदम को प्रतीक्षा-मुक्त लागू किया जा सकता है, और सीरियल कोड से कई परिवर्तन, जिन्हें सार्वभौमिक निर्माण कहा जाता है, का प्रदर्शन किया गया है। हालाँकि, परिणामी प्रदर्शन सामान्य रूप से भोले-भाले अवरोधक डिज़ाइनों से मेल नहीं खाता है। उसके बाद से कई पेपरों ने सार्वभौमिक निर्माणों के प्रदर्शन में सुधार किया है, लेकिन फिर भी, उनका प्रदर्शन अवरुद्ध डिजाइनों से काफी नीचे है।
इसे 1980 के दशक में दिखाया गया था<ref name=imp>{{cite conference |last=Herlihy |first=Maurice P. |conference=Proc. 7th Annual ACM Symp. on Principles of Distributed Computing |isbn=0-89791-277-2 |pages=276–290 |doi=10.1145/62546.62593 |title=प्रतीक्षा-मुक्त तुल्यकालन के लिए असंभवता और सार्वभौमिकता परिणाम|year=1988|doi-access=free }}</ref> कि सभी एल्गोरिदम को प्रतीक्षा-मुक्त लागू किया जा सकता है, और सीरियल कोड से कई परिवर्तन, जिन्हें सार्वभौमिक निर्माण कहा जाता है, का प्रदर्शन किया गया है। चूँकि, परिणामी प्रदर्शन सामान्य रूप से भोले-भाले अवरोधक डिज़ाइनों से मेल नहीं खाता है। उसके बाद से कई पेपरों ने सार्वभौमिक निर्माणों के प्रदर्शन में सुधार किया है, फिर भी, उनका प्रदर्शन अवरुद्ध डिजाइनों से अधिक नीचे है।


कई पेपरों ने प्रतीक्षा-मुक्त एल्गोरिथम बनाने की कठिनाई की जांच की है। उदाहरण के लिए, यह दिखाया गया है<ref name=cond-sync>{{cite conference |last1=Fich |first1=Faith|author1-link=Faith Ellen |last2=Hendler |first2=Danny |last3=Shavit |first3=Nir |conference=Proc. 23rd Annual ACM Symp.on Principles of Distributed Computing (PODC) |year=2004 |isbn=1-58113-802-4 |pages=80–87 |doi=10.1145/1011767.1011780 |title=On the inherent weakness of conditional synchronization primitives}}</ref> कि व्यापक रूप से उपलब्ध एटॉमिक कंडीशनल प्रिमिटिव्स, कंपेयर-एंड-स्वैप और लोड-लिंक/स्टोर-कंडीशनल|एलएल/एससी, थ्रेड्स की संख्या में रैखिक रूप से बढ़ने वाली मेमोरी लागत के बिना कई सामान्य डेटा संरचनाओं के भुखमरी-मुक्त कार्यान्वयन प्रदान नहीं कर सकते हैं।
कई पेपरों ने प्रतीक्षा-मुक्त एल्गोरिथम बनाने की कठिनाई की जांच की है। उदाहरण के लिए, यह दिखाया गया है<ref name=cond-sync>{{cite conference |last1=Fich |first1=Faith|author1-link=Faith Ellen |last2=Hendler |first2=Danny |last3=Shavit |first3=Nir |conference=Proc. 23rd Annual ACM Symp.on Principles of Distributed Computing (PODC) |year=2004 |isbn=1-58113-802-4 |pages=80–87 |doi=10.1145/1011767.1011780 |title=On the inherent weakness of conditional synchronization primitives}}</ref> कि व्यापक रूप से उपलब्ध एटॉमिक कंडीशनल प्रिमिटिव्स, कंपेयर-एंड-स्वैप और लोड-लिंक/स्टोर-कंडीशनल|एलएल/एससी, थ्रेड्स की संख्या में रैखिक रूप से बढ़ने वाली मेमोरी लागत के बिना कई सामान्य डेटा संरचनाओं के भुखमरी-मुक्त कार्यान्वयन प्रदान नहीं कर सकते हैं।


लेकिन व्यवहार में ये निचली सीमाएं वास्तविक बाधा नहीं पेश करती हैं क्योंकि साझा मेमोरी में स्टोर प्रति थ्रेड के कैश लाइन या अनन्य आरक्षण ग्रेन्युल (एआरएम पर 2 केबी तक) खर्च करना व्यावहारिक प्रणालियों के लिए बहुत महंगा नहीं माना जाता है (आमतौर पर राशि) तार्किक रूप से आवश्यक स्टोर एक शब्द है, लेकिन एक ही कैश लाइन पर शारीरिक रूप से कैस ऑपरेशंस टकराएंगे, और एलएल / एससी ऑपरेशंस एक ही एक्सक्लूसिव रिजर्वेशन ग्रेन्युल में टकराएंगे, इसलिए भौतिक रूप से आवश्यक स्टोर की मात्रा{{citation needed|date=June 2014}} ज्यादा होता है)।
व्यवहार में ये निचली सीमाएं वास्तविक बाधा नहीं प्रस्तुत करती हैं क्योंकि साझा मेमोरी में स्टोर प्रति थ्रेड के कैश लाइन या अनन्य आरक्षण ग्रेन्युल (एआरएम पर 2 केबी तक) खर्च करना व्यावहारिक प्रणालियों के लिए बहुत महंगा नहीं माना जाता है (सामान्यतः राशि) तार्किक रूप से आवश्यक स्टोरशब्द है, ही कैश लाइन पर शारीरिक रूप से कैस ऑपरेशंस टकराएंगे, और एलएल / एससी ऑपरेशंसही एक्सक्लूसिव रिजर्वेशन ग्रेन्युल में टकराएंगे, इसलिए भौतिक रूप से आवश्यक स्टोर की मात्रा{{citation needed|date=June 2014}} ज्यादा होता है)।


प्रतीक्षा-मुक्त एल्गोरिदम 2011 तक अनुसंधान और व्यवहार दोनों में दुर्लभ थे। हालाँकि, 2011 में कोगन और [[एरेज़ पेट्रैंक]]<ref name=wf-queue>{{cite conference |last1=Kogan |first1=Alex |last2=Petrank |first2=Erez |conference=Proc. 16th ACM SIGPLAN Symp. on Principles and Practice of Parallel Programming (PPOPP) |year=2011 |isbn=978-1-4503-0119-0 |pages=223–234 |doi=10.1145/1941553.1941585 |title=कई एन्क्यूअर्स और डेक्यूअर्स के साथ प्रतीक्षा-मुक्त कतारें|url=http://www.cs.technion.ac.il/~erez/Papers/wfquque-ppopp.pdf}}</ref> आम तौर पर सामान्य हार्डवेयर पर उपलब्ध तुलना-और-स्वैप आदिम पर एक प्रतीक्षा-मुक्त कतार निर्माण प्रस्तुत किया। उनके निर्माण ने माइकल और स्कॉट की लॉक-फ्री कतार का विस्तार किया,<ref name=lf-queue>{{cite conference |last1=Michael |first1=Maged |last2=Scott |first2=Michael |conference=Proc. 15th Annual ACM Symp. on Principles of Distributed Computing (PODC) |year=1996 |isbn=0-89791-800-2 |pages=267–275 |doi=10.1145/248052.248106 |title=सरल, तेज और व्यावहारिक गैर-अवरुद्ध और अवरुद्ध समवर्ती कतार एल्गोरिदम|doi-access=free }}</ref> जो अक्सर अभ्यास में उपयोग की जाने वाली एक कुशल कतार है। कोगन और पेट्रैंक द्वारा एक अनुवर्ती पेपर<ref name=wf-fpsp>{{cite conference |last1=Kogan |first1=Alex |last2=Petrank |first2=Erez |conference=Proc. 17th ACM SIGPLAN Symp. on Principles and Practice of Parallel Programming (PPOPP) |year=2012 |isbn=978-1-4503-1160-1 |pages=141–150 |doi=10.1145/2145816.2145835 |title=A method for creating fast wait-free data structures}}</ref> प्रतीक्षा-मुक्त एल्गोरिदम को तेजी से बनाने के लिए एक विधि प्रदान की और इस पद्धति का उपयोग प्रतीक्षा-मुक्त कतार को अपने लॉक-मुक्त समकक्ष के रूप में तेजी से करने के लिए किया। टिमनाट और पेट्रैंक द्वारा एक बाद का पेपर<ref name=wf-simulation>{{cite conference |last1=Timnat |first1=Shahar |last2=Petrank |first2=Erez |conference=Proc. 17th ACM SIGPLAN Symp. on Principles and Practice of Parallel Programming (PPOPP) |year=2014 |  isbn=978-1-4503-2656-8 | pages = 357–368  | doi=10.1145/2692916.2555261 | title= A Practical Wait-Free Simulation for Lock-Free Data Structures}}</ref> लॉक-फ्री वाले से प्रतीक्षा-मुक्त डेटा संरचना उत्पन्न करने के लिए एक स्वचालित तंत्र प्रदान किया। इस प्रकार, प्रतीक्षा-मुक्त कार्यान्वयन अब कई डेटा-संरचनाओं के लिए उपलब्ध हैं।
प्रतीक्षा-मुक्त एल्गोरिदम 2011 तक अनुसंधान और व्यवहार दोनों में दुर्लभ थे। चूँकि, 2011 में कोगन और [[एरेज़ पेट्रैंक]]<ref name=wf-queue>{{cite conference |last1=Kogan |first1=Alex |last2=Petrank |first2=Erez |conference=Proc. 16th ACM SIGPLAN Symp. on Principles and Practice of Parallel Programming (PPOPP) |year=2011 |isbn=978-1-4503-0119-0 |pages=223–234 |doi=10.1145/1941553.1941585 |title=कई एन्क्यूअर्स और डेक्यूअर्स के साथ प्रतीक्षा-मुक्त कतारें|url=http://www.cs.technion.ac.il/~erez/Papers/wfquque-ppopp.pdf}}</ref> सामान्यतः सामान्य हार्डवेयर पर उपलब्ध तुलना-और-स्वैप आदिम परप्रतीक्षा-मुक्त कतार निर्माण प्रस्तुत किया। उनके निर्माण ने माइकल और स्कॉट की लॉक-फ्री कतार का विस्तार किया,<ref name=lf-queue>{{cite conference |last1=Michael |first1=Maged |last2=Scott |first2=Michael |conference=Proc. 15th Annual ACM Symp. on Principles of Distributed Computing (PODC) |year=1996 |isbn=0-89791-800-2 |pages=267–275 |doi=10.1145/248052.248106 |title=सरल, तेज और व्यावहारिक गैर-अवरुद्ध और अवरुद्ध समवर्ती कतार एल्गोरिदम|doi-access=free }}</ref> जो अधिकांशतः अभ्यास में उपयोग की जाने वालीकुशल कतार है। कोगन और पेट्रैंक द्वाराअनुवर्ती पेपर<ref name=wf-fpsp>{{cite conference |last1=Kogan |first1=Alex |last2=Petrank |first2=Erez |conference=Proc. 17th ACM SIGPLAN Symp. on Principles and Practice of Parallel Programming (PPOPP) |year=2012 |isbn=978-1-4503-1160-1 |pages=141–150 |doi=10.1145/2145816.2145835 |title=A method for creating fast wait-free data structures}}</ref> प्रतीक्षा-मुक्त एल्गोरिदम को तेजी से बनाने के लिएविधि प्रदान की और इस पद्धति का उपयोग प्रतीक्षा-मुक्त कतार को अपने लॉक-मुक्त समकक्ष के रूप में तेजी से करने के लिए किया। टिमनाट और पेट्रैंक द्वाराबाद का पेपर<ref name=wf-simulation>{{cite conference |last1=Timnat |first1=Shahar |last2=Petrank |first2=Erez |conference=Proc. 17th ACM SIGPLAN Symp. on Principles and Practice of Parallel Programming (PPOPP) |year=2014 |  isbn=978-1-4503-2656-8 | pages = 357–368  | doi=10.1145/2692916.2555261 | title= A Practical Wait-Free Simulation for Lock-Free Data Structures}}</ref> लॉक-फ्री वाले से प्रतीक्षा-मुक्त डेटा संरचना उत्पन्न करने के लिएस्वचालित तंत्र प्रदान किया। इस प्रकार, प्रतीक्षा-मुक्त कार्यान्वयन अब कई डेटा-संरचनाओं के लिए उपलब्ध हैं।


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


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


एक एल्गोरिथ्म लॉक-फ्री है अगर कुछ प्रोसेसर द्वारा असीम रूप से अक्सर संचालन एक सीमित संख्या में चरणों में सफल होगा। उदाहरण के लिए, अगर {{var|N}} प्रोसेसर एक ऑपरेशन को अंजाम देने की कोशिश कर रहे हैं, जिनमें से कुछ {{var|N}} प्रक्रियाएं सीमित संख्या में चरणों में संक्रिया को पूरा करने में सफल होंगी और अन्य विफल हो सकते हैं और विफलता पर पुनः प्रयास कर सकते हैं। वेट-फ्री और लॉक-फ्री के बीच का अंतर यह है कि प्रत्येक प्रक्रिया द्वारा वेट-फ्री ऑपरेशन को अन्य प्रोसेसर की परवाह किए बिना सीमित संख्या में चरणों में सफल होने की गारंटी दी जाती है।
एक एल्गोरिथ्म लॉक-फ्री है यदि कुछ प्रोसेसर द्वारा असीम रूप से अधिकांशतः संचालनसीमित संख्या में चरणों में सफल होगा। उदाहरण के लिए, यदि {{var|N}} प्रोसेसरऑपरेशन को अंजाम देने की कोशिश कर रहे हैं, जिनमें से कुछ {{var|N}} प्रक्रियाएं सीमित संख्या में चरणों में संक्रिया को पूरा करने में सफल होंगी और अन्य विफल हो सकते हैं और विफलता पर पुनः प्रयास कर सकते हैं। वेट-फ्री और लॉक-फ्री के बीच का अंतर यह है कि प्रत्येक प्रक्रिया द्वारा वेट-फ्री ऑपरेशन को अन्य प्रोसेसर की परवाह किए बिना सीमित संख्या में चरणों में सफल होने की गारंटी दी जाती है।


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


कब सहायता करनी है, कब रद्द करनी है या बाधा उत्पन्न होने पर प्रतीक्षा करनी है, इस बारे में निर्णय लेना एक विवाद प्रबंधक का उत्तरदायित्व है। यह बहुत सरल हो सकता है (उच्च प्राथमिकता वाले संचालन में सहायता करें, कम प्राथमिकता वाले को निरस्त करें), या बेहतर थ्रूपुट प्राप्त करने के लिए अधिक अनुकूलित हो सकता है, या प्राथमिकता वाले संचालन की विलंबता को कम कर सकता है।
कब सहायता करनी है, कब रद्द करनी है या बाधा उत्पन्न होने पर प्रतीक्षा करनी है, इस बारे में निर्णय लेनाविवाद प्रबंधक का उत्तरदायित्व है। यह बहुत सरल हो सकता है (उच्च प्राथमिकता वाले संचालन में सहायता करें, कम प्राथमिकता वाले को निरस्त करें), या उत्तम थ्रूपुट प्राप्त करने के लिए अधिक अनुकूलित हो सकता है, या प्राथमिकता वाले संचालन की विलंबता को कम कर सकता है।


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


== बाधा-मुक्ति ==
== बाधा-मुक्ति ==
बाधा-मुक्ति सबसे कमजोर प्राकृतिक गैर-अवरोधक प्रगति गारंटी है। एक एल्गोरिथम बाधा-मुक्त होता है यदि किसी भी बिंदु पर, अलगाव में निष्पादित एक एकल थ्रेड (यानी, सभी अवरोधक थ्रेड्स को निलंबित कर दिया जाता है) चरणों की एक सीमित संख्या के लिए अपना ऑपरेशन पूरा करेगा।<ref name="awilliams" />सभी लॉक-फ्री एल्गोरिदम बाधा-मुक्त हैं।
बाधा-मुक्ति सबसे कमजोर प्राकृतिक गैर-अवरोधक प्रगति गारंटी है।एल्गोरिथम बाधा-मुक्त होता है यदि किसी भी बिंदु पर, अलगाव में निष्पादितएकल थ्रेड (अर्थात्, सभी अवरोधक थ्रेड्स को निलंबित कर दिया जाता है) चरणों कीसीमित संख्या के लिए अपना ऑपरेशन पूरा करेगा।<ref name="awilliams" />सभी लॉक-फ्री एल्गोरिदम बाधा-मुक्त हैं।


बाधा-मुक्ति केवल यह मांग करती है कि किसी भी आंशिक रूप से पूर्ण किए गए ऑपरेशन को निरस्त किया जा सकता है और किए गए परिवर्तन वापस ले लिए जा सकते हैं। समवर्ती सहायता को छोड़ने से अक्सर अधिक सरल एल्गोरिदम हो सकते हैं जो मान्य करने में आसान होते हैं। सिस्टम को लगातार livelock|live-locking से रोकना एक कंटेंशन मैनेजर का काम है।
बाधा-मुक्ति केवल यह मांग करती है कि किसी भी आंशिक रूप से पूर्ण किए गए ऑपरेशन को निरस्त किया जा सकता है और किए गए परिवर्तन वापस ले लिए जा सकते हैं। समवर्ती सहायता को छोड़ने से अधिकांशतः अधिक सरल एल्गोरिदम हो सकते हैं जो मान्य करने में आसान होते हैं। सिस्टम को लगातार livelock|live-locking से रोकनाकंटेंशन मैनेजर का काम है।


कुछ बाधा-मुक्त एल्गोरिदम डेटा संरचना में स्थिरता मार्करों की एक जोड़ी का उपयोग करते हैं। डेटा संरचना को पढ़ने वाली प्रक्रियाएं पहले एक संगति मार्कर को पढ़ती हैं, फिर संबंधित डेटा को एक आंतरिक बफर में पढ़ती हैं, फिर अन्य मार्कर को पढ़ती हैं, और फिर मार्करों की तुलना करती हैं। यदि दो मार्कर समान हैं तो डेटा सुसंगत है। डेटा संरचना को अद्यतन करने वाली किसी अन्य प्रक्रिया द्वारा रीड बाधित होने पर मार्कर गैर-समान हो सकते हैं। ऐसी स्थिति में, प्रक्रिया डेटा को आंतरिक बफ़र में छोड़ देती है और पुनः प्रयास करती है।
कुछ बाधा-मुक्त एल्गोरिदम डेटा संरचना में स्थिरता मार्करों कीजोड़ी का उपयोग करते हैं। डेटा संरचना को पढ़ने वाली प्रक्रियाएं पहलेसंगति मार्कर को पढ़ती हैं, फिर संबंधित डेटा कोआंतरिक बफर में पढ़ती हैं, फिर अन्य मार्कर को पढ़ती हैं, और फिर मार्करों की तुलना करती हैं। यदि दो मार्कर समान हैं तो डेटा सुसंगत है। डेटा संरचना को अद्यतन करने वाली किसी अन्य प्रक्रिया द्वारा रीड बाधित होने पर मार्कर गैर-समान हो सकते हैं। ऐसी स्थिति में, प्रक्रिया डेटा को आंतरिक बफ़र में छोड़ देती है और पुनः प्रयास करती है।


== यह भी देखें ==
== यह भी देखें ==

Revision as of 20:03, 31 May 2023

Not to be confused with non-blocking I/O.

कंप्यूटर विज्ञान में,कलन विधि को गैर-अवरुद्ध कहा जाता है यदि किसी थ्रेड (कंप्यूटिंग) की विफलता या निर्धारण (कंप्यूटिंग) किसी अन्य थ्रेड की विफलता या निलंबन का कारण नहीं बन सकती है।[1] कुछ कार्यों के लिए, यह एल्गोरिदम पारंपरिक लॉक (कंप्यूटर विज्ञान) के लिएउपयोगी विकल्प प्रदान करते हैं।गैर-अवरुद्ध एल्गोरिथम लॉक-फ्री है यदि सिस्टम-वाइड रिसोर्स भुखमरी की गारंटी है, और प्रति-थ्रेड प्रगति की गारंटी होने पर प्रतीक्षा-मुक्त है। 2003 में बाधा-मुक्ति की प्रारंभिक तक गैर-अवरुद्ध को साहित्य में लॉक-फ्री के पर्याय के रूप में उपयोग किया गया था।[2] नॉन-ब्लॉकिंग शब्द का पारंपरिक रूप से दूरसंचार नेटवर्क का वर्णन करने के लिए उपयोग किया जाता था जो उपस्तिथ कॉल को फिर से व्यवस्थित किए बिना रिले केसेट के माध्यम सेकनेक्शन को रूट कर सकता था (Clos नेटवर्क देखें)। इसके अतिरिक्त, यदि टेलीफोन एक्सचेंज दोषपूर्ण नहीं है, तो यह हमेशा कनेक्शन बना सकता है (न्यूनतम स्पैनिंग स्विच को अनब्लॉक करना देखें)।

प्रेरणा

Main article: Disadvantages of locks

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

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

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

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


कार्यान्वयन

कुछ अपवादों के साथ, नॉन-ब्लॉकिंग एल्गोरिदम रैखिकता पढ़ने के लिए संशोधित-लिखने प्रिमिटिव का उपयोग करते हैं जो हार्डवेयर को प्रदान करना चाहिए, जिनमें से सबसे उल्लेखनीय तुलना-और-स्वैप|तुलना और स्वैप (CAS) है। इन प्रिमिटिव्स पर मानक इंटरफेस का उपयोग करके क्रिटिकल सेक्शन लगभग हमेशा लागू किए जाते हैं (सामान्य स्थिति में, इन प्रिमिटिव्स के साथ लागू होने पर भी क्रिटिकल सेक्शन ब्लॉक हो जाएंगे)। 1990 के दशक में स्वीकार्य प्रदर्शन प्राप्त करने के लिए सभी गैर-अवरुद्ध एल्गोरिदम को अंतर्निहित आदिम के साथ मूल रूप से लिखा जाना था। चूँकि, सॉफ्टवेयर लेनदेन स्मृति का उभरता हुआ क्षेत्र कुशल नॉन-ब्लॉकिंग कोड लिखने के लिए मानक अमूर्तता का वादा करता है।[5][6] स्टैक (डेटा संरचना), कतार (डेटा संरचना), सेट (कंप्यूटर विज्ञान), और हैश तालिका जैसी बुनियादी डेटा संरचनाएँ प्रदान करने में बहुत शोध किया गया है। ये प्रोग्राम को आसानी से थ्रेड्स के बीच अतुल्यकालिक रूप से डेटा का आदान-प्रदान करने की अनुमति देते हैं।

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

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

कई पुस्तकालय आंतरिक रूप से लॉक-फ्री तकनीकों का उपयोग करते हैं,[7][8][9] लॉक-फ्री कोड लिखना कठिनाई है जो सही हो।[10][11][12][13] गैर-अवरुद्ध एल्गोरिदम में सामान्यतः ध्यान से डिज़ाइन किए गए क्रम में पढ़ने, पढ़ने-संशोधित करने-लिखने और निर्देश लिखने कीश्रृंखला सम्मिलित होती है। ऑप्टिमाइज़िंग कंपाइलर आक्रामक रूप से संचालन को फिर से व्यवस्थित कर सकते हैं। यहां तक ​​​​कि जब वे नहीं करते हैं, तब भी कई आधुनिक सीपीयू अधिकांशतः ऐसे कार्यों को फिर से व्यवस्थित करते हैं (उनके पासकमजोर स्थिरता मॉडल है), जब तक कि सीपीयू को पुन: व्यवस्थित न करने के लिए मेमोरी बैरियर का उपयोग नहीं किया जाता है। C++11 प्रोग्रामर उपयोग कर सकते हैं std::atomic में <atomic>, और C11 (C मानक पुनरीक्षण) प्रोग्रामर उपयोग कर सकते हैं <stdatomic.h>, दोनों आपूर्ति प्रकार और कार्य जो संकलक को ऐसे निर्देशों को फिर से व्यवस्थित नहीं करने और उपयुक्त मेमोरी बाधाओं को सम्मिलित करने के लिए कहते हैं।[14]


प्रतीक्षा-मुक्ति

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

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

कई पेपरों ने प्रतीक्षा-मुक्त एल्गोरिथम बनाने की कठिनाई की जांच की है। उदाहरण के लिए, यह दिखाया गया है[17] कि व्यापक रूप से उपलब्ध एटॉमिक कंडीशनल प्रिमिटिव्स, कंपेयर-एंड-स्वैप और लोड-लिंक/स्टोर-कंडीशनल|एलएल/एससी, थ्रेड्स की संख्या में रैखिक रूप से बढ़ने वाली मेमोरी लागत के बिना कई सामान्य डेटा संरचनाओं के भुखमरी-मुक्त कार्यान्वयन प्रदान नहीं कर सकते हैं।

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

प्रतीक्षा-मुक्त एल्गोरिदम 2011 तक अनुसंधान और व्यवहार दोनों में दुर्लभ थे। चूँकि, 2011 में कोगन और एरेज़ पेट्रैंक[18] सामान्यतः सामान्य हार्डवेयर पर उपलब्ध तुलना-और-स्वैप आदिम परप्रतीक्षा-मुक्त कतार निर्माण प्रस्तुत किया। उनके निर्माण ने माइकल और स्कॉट की लॉक-फ्री कतार का विस्तार किया,[19] जो अधिकांशतः अभ्यास में उपयोग की जाने वालीकुशल कतार है। कोगन और पेट्रैंक द्वाराअनुवर्ती पेपर[20] प्रतीक्षा-मुक्त एल्गोरिदम को तेजी से बनाने के लिएविधि प्रदान की और इस पद्धति का उपयोग प्रतीक्षा-मुक्त कतार को अपने लॉक-मुक्त समकक्ष के रूप में तेजी से करने के लिए किया। टिमनाट और पेट्रैंक द्वाराबाद का पेपर[21] लॉक-फ्री वाले से प्रतीक्षा-मुक्त डेटा संरचना उत्पन्न करने के लिएस्वचालित तंत्र प्रदान किया। इस प्रकार, प्रतीक्षा-मुक्त कार्यान्वयन अब कई डेटा-संरचनाओं के लिए उपलब्ध हैं।

लॉक-फ्रीडम

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

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

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

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

कब सहायता करनी है, कब रद्द करनी है या बाधा उत्पन्न होने पर प्रतीक्षा करनी है, इस बारे में निर्णय लेनाविवाद प्रबंधक का उत्तरदायित्व है। यह बहुत सरल हो सकता है (उच्च प्राथमिकता वाले संचालन में सहायता करें, कम प्राथमिकता वाले को निरस्त करें), या उत्तम थ्रूपुट प्राप्त करने के लिए अधिक अनुकूलित हो सकता है, या प्राथमिकता वाले संचालन की विलंबता को कम कर सकता है।

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

बाधा-मुक्ति

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

बाधा-मुक्ति केवल यह मांग करती है कि किसी भी आंशिक रूप से पूर्ण किए गए ऑपरेशन को निरस्त किया जा सकता है और किए गए परिवर्तन वापस ले लिए जा सकते हैं। समवर्ती सहायता को छोड़ने से अधिकांशतः अधिक सरल एल्गोरिदम हो सकते हैं जो मान्य करने में आसान होते हैं। सिस्टम को लगातार livelock|live-locking से रोकनाकंटेंशन मैनेजर का काम है।

कुछ बाधा-मुक्त एल्गोरिदम डेटा संरचना में स्थिरता मार्करों कीजोड़ी का उपयोग करते हैं। डेटा संरचना को पढ़ने वाली प्रक्रियाएं पहलेसंगति मार्कर को पढ़ती हैं, फिर संबंधित डेटा कोआंतरिक बफर में पढ़ती हैं, फिर अन्य मार्कर को पढ़ती हैं, और फिर मार्करों की तुलना करती हैं। यदि दो मार्कर समान हैं तो डेटा सुसंगत है। डेटा संरचना को अद्यतन करने वाली किसी अन्य प्रक्रिया द्वारा रीड बाधित होने पर मार्कर गैर-समान हो सकते हैं। ऐसी स्थिति में, प्रक्रिया डेटा को आंतरिक बफ़र में छोड़ देती है और पुनः प्रयास करती है।

यह भी देखें

  • गतिरोध
  • जावा समवर्ती मानचित्र # लॉक-फ्री परमाणुता
  • जीवंतता
  • ताला (कंप्यूटर विज्ञान)
  • आपसी बहिष्कार
  • प्राथमिकता उलटा
  • संसाधन भुखमरी

संदर्भ

  1. ↑ Göetz, Brian; Peierls, Tim; Bloch, Joshua; Bowbeer, Joseph; Holmes, David; Lea, Doug (2006). व्यवहार में जावा संगामिति. Upper Saddle River, NJ: Addison-Wesley. p. 41. ISBN 9780321349606.
  2. ↑ Herlihy, M.; Luchangco, V.; Moir, M. (2003). Obstruction-Free Synchronization: Double-Ended Queues as an Example (PDF). 23rd International Conference on Distributed Computing Systems. p. 522.
  3. ↑ Butler W. Lampson; David D. Redell (February 1980). "मेसा में प्रक्रियाओं और मॉनिटर के साथ अनुभव". Communications of the ACM. 23 (2): 105–117. CiteSeerX 10.1.1.142.5765. doi:10.1145/358818.358824. S2CID 1594544.
  4. ↑ Guillaume Marçais, and Carl Kingsford. "A fast, lock-free approach for efficient parallel counting of occurrences of k-mers". Bioinformatics (2011) 27(6): 764-770. doi:10.1093/bioinformatics/btr011 "Jellyfish mer counter".
  5. ↑ Harris, Tim; Fraser, Keir (26 November 2003). "हल्के लेनदेन के लिए भाषा समर्थन" (PDF). ACM SIGPLAN Notices. 38 (11): 388. CiteSeerX 10.1.1.58.8466. doi:10.1145/949343.949340.
  6. ↑ Harris, Tim; Marlow, S.; Peyton-Jones, S.; Herlihy, M. (June 15–17, 2005). "Composable memory transactions". Proceedings of the 2005 ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP '05 : Chicago, Illinois. New York, NY: ACM Press. pp. 48–60. doi:10.1145/1065944.1065952. ISBN 978-1-59593-080-4. S2CID 53245159.
  7. ↑ libcds - C++ library of lock-free containers and safe memory reclamation schema
  8. ↑ liblfds - A library of lock-free data structures, written in C
  9. ↑ Concurrency Kit - A C library for non-blocking system design and implementation
  10. ↑ हर्ब सटर। "लॉक-फ्री कोड: सुरक्षा की झूठी भावना". Archived from the original on 2015-09-01.
  11. ↑ हर्ब सटर। "लॉक-फ्री कोड लिखना: एक सही कतार". Archived from the original on 2008-12-05.
  12. ↑ Herb Sutter. "Writing a Generalized Concurrent Queue".
  13. ↑ Herb Sutter. "The Trouble With Locks".
  14. ↑ Bruce Dawson. "ARM and Lock-Free Programming".
  15. ↑ 15.0 15.1 Anthony Williams. "Safety: off: How not to shoot yourself in the foot with C++ atomics". 2015. p. 20.
  16. ↑ Herlihy, Maurice P. (1988). प्रतीक्षा-मुक्त तुल्यकालन के लिए असंभवता और सार्वभौमिकता परिणाम. Proc. 7th Annual ACM Symp. on Principles of Distributed Computing. pp. 276–290. doi:10.1145/62546.62593. ISBN 0-89791-277-2.
  17. ↑ Fich, Faith; Hendler, Danny; Shavit, Nir (2004). On the inherent weakness of conditional synchronization primitives. Proc. 23rd Annual ACM Symp.on Principles of Distributed Computing (PODC). pp. 80–87. doi:10.1145/1011767.1011780. ISBN 1-58113-802-4.
  18. ↑ Kogan, Alex; Petrank, Erez (2011). कई एन्क्यूअर्स और डेक्यूअर्स के साथ प्रतीक्षा-मुक्त कतारें (PDF). Proc. 16th ACM SIGPLAN Symp. on Principles and Practice of Parallel Programming (PPOPP). pp. 223–234. doi:10.1145/1941553.1941585. ISBN 978-1-4503-0119-0.
  19. ↑ Michael, Maged; Scott, Michael (1996). सरल, तेज और व्यावहारिक गैर-अवरुद्ध और अवरुद्ध समवर्ती कतार एल्गोरिदम. Proc. 15th Annual ACM Symp. on Principles of Distributed Computing (PODC). pp. 267–275. doi:10.1145/248052.248106. ISBN 0-89791-800-2.
  20. ↑ Kogan, Alex; Petrank, Erez (2012). A method for creating fast wait-free data structures. Proc. 17th ACM SIGPLAN Symp. on Principles and Practice of Parallel Programming (PPOPP). pp. 141–150. doi:10.1145/2145816.2145835. ISBN 978-1-4503-1160-1.
  21. ↑ Timnat, Shahar; Petrank, Erez (2014). A Practical Wait-Free Simulation for Lock-Free Data Structures. Proc. 17th ACM SIGPLAN Symp. on Principles and Practice of Parallel Programming (PPOPP). pp. 357–368. doi:10.1145/2692916.2555261. ISBN 978-1-4503-2656-8.


बाहरी संबंध

Retrieved from ‘https://www.vigyanwiki.in/index.php?title=गैर-अवरुद्ध_एल्गोरिदम&oldid=179857’