गैर-अवरुद्ध एल्गोरिदम: Difference between revisions
No edit summary |
No edit summary |
||
| Line 4: | Line 4: | ||
[[कंप्यूटर विज्ञान]] में,[[कलन विधि]] को गैर-अवरुद्ध कहा जाता है यदि किसी [[थ्रेड (कंप्यूटिंग)]] की विफलता या [[ निर्धारण (कंप्यूटिंग) ]] किसी अन्य थ्रेड की विफलता या निलंबन का कारण नहीं बन सकता है।<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 नेटवर्क देखें)। इसके अतिरिक्त, यदि टेलीफोन एक्सचेंज "दोषपूर्ण नहीं होता है, तब यह हमेशा कनेक्शन बना सकता है" (न्यूनतम स्पैनिंग स्विच को अनअवरुद्ध करना देखें)। | ||
== प्रेरणा == | == प्रेरणा == | ||
{{Main|Lock (computer science)#Disadvantages|l1=अवरुद्ध की हानियाँ}} | {{Main|Lock (computer science)#Disadvantages|l1=अवरुद्ध की हानियाँ}} | ||
बहु-थ्रेडेड प्रोग्रामिंग के लिए पारंपरिक दृष्टिकोण साझा [[संसाधन (कंप्यूटर विज्ञान)]] तक पहुंच को सिंक्रनाइज़ करने के लिए लॉक (कंप्यूटर विज्ञान) का उपयोग करना है। पारस्परिक बहिष्करण, [[सेमाफोर (प्रोग्रामिंग)]], और महत्वपूर्ण खंड जैसे सिंक्रनाइज़ेशन प्रिमिटिव्स सभी तंत्र हैं जिनके | बहु-थ्रेडेड प्रोग्रामिंग के लिए पारंपरिक दृष्टिकोण साझा [[संसाधन (कंप्यूटर विज्ञान)]] तक पहुंच को सिंक्रनाइज़ करने के लिए लॉक (कंप्यूटर विज्ञान) का उपयोग करना होता है। इस प्रकार पारस्परिक बहिष्करण, [[सेमाफोर (प्रोग्रामिंग)]], और महत्वपूर्ण खंड जैसे सिंक्रनाइज़ेशन प्रिमिटिव्स सभी तंत्र होते हैं जिनके द्वारा प्रोग्रामर यह सुनिश्चित कर सकता है कि कोड के कुछ खंड समवर्ती रूप से निष्पादित नहीं होते हैं, यदि ऐसा करने से साझा मेमोरी संरचना दूषित हो जाती है। यदि थ्रेड किसी अन्य थ्रेड द्वारा पहले से रखे गए लॉक को प्राप्त करने का प्रयास करता है, तब लॉक मुक्त होने तक थ्रेड अवरुद्ध हो जाता है। | ||
किसी थ्रेड को | किसी थ्रेड को अवरुद्ध करना अनेक कारणों से अवांछनीय हो सकता है। अतः स्पष्ट कारण यह है कि जब थ्रेड अवरुद्ध होता है, तब यह कुछ भी पूर्ण नहीं कर सकता है। यदि अवरुद्ध थ्रेड उच्च-प्राथमिकता या [[वास्तविक]] [[काल]] कार्य कर रहा था, तब इसकी प्रगति को रोकना अत्यधिक अवांछनीय होता है। | ||
अन्य समस्याएं कम स्पष्ट हैं। उदाहरण के लिए, तालों के | सामान्यतः अन्य समस्याएं कम स्पष्ट होती हैं। उदाहरण के लिए, तालों के मध्य कुछ अंतःक्रियाएं [[गतिरोध]], [[ 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> | |||
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 25: | Line 25: | ||
</ref> | </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> | ||
स्टैक ([[डेटा संरचना]]), [[कतार (डेटा संरचना)]], [[सेट (कंप्यूटर विज्ञान)]], और [[ हैश तालिका ]] जैसी बुनियादी डेटा संरचनाएँ प्रदान करने में बहुत शोध किया गया है। ये प्रोग्राम को आसानी से थ्रेड्स के | स्टैक ([[डेटा संरचना]]), [[कतार (डेटा संरचना)]], [[सेट (कंप्यूटर विज्ञान)]], और [[ हैश तालिका ]] जैसी बुनियादी डेटा संरचनाएँ प्रदान करने में बहुत शोध किया गया है। ये प्रोग्राम को आसानी से थ्रेड्स के मध्य अतुल्यकालिक रूप से डेटा का आदान-प्रदान करने की अनुमति देते हैं। | ||
इसके अतिरिक्त, कुछ गैर-अवरुद्ध डेटा संरचनाएं विशेष परमाणु आदिम के बिना लागू करने के लिए पर्याप्त कमजोर हैं। इन अपवादों में सम्मिलित हैं: | इसके अतिरिक्त, कुछ गैर-अवरुद्ध डेटा संरचनाएं विशेष परमाणु आदिम के बिना लागू करने के लिए पर्याप्त कमजोर हैं। इन अपवादों में सम्मिलित हैं: | ||
| Line 32: | Line 32: | ||
* एक एकल-पाठक एकल-लेखक परिपत्र बफर FIFO (कंप्यूटिंग और इलेक्ट्रॉनिक्स),आकार के साथ जो समान रूप से उपलब्ध अहस्ताक्षरित पूर्णांक प्रकारों में सेके अतिप्रवाह को विभाजित करता है, बिना शर्त के निर्माता-उपभोक्ता समस्या हो सकती है # केवलमेमोरी का उपयोग करके सेमाफोर या मॉनिटर के बिना रुकावट | * एक एकल-पाठक एकल-लेखक परिपत्र बफर FIFO (कंप्यूटिंग और इलेक्ट्रॉनिक्स),आकार के साथ जो समान रूप से उपलब्ध अहस्ताक्षरित पूर्णांक प्रकारों में सेके अतिप्रवाह को विभाजित करता है, बिना शर्त के निर्माता-उपभोक्ता समस्या हो सकती है # केवलमेमोरी का उपयोग करके सेमाफोर या मॉनिटर के बिना रुकावट | ||
* एक लेखक और कितने भी पाठकों के साथ पढ़ें-कॉपी-अपडेट करें। (पाठक प्रतीक्षा-मुक्त हैं; लेखक सामान्यतः लॉक-मुक्त होता है, जब तक कि उसे स्मृति को पुनः प्राप्त करने की आवश्यकता न हो)। | * एक लेखक और कितने भी पाठकों के साथ पढ़ें-कॉपी-अपडेट करें। (पाठक प्रतीक्षा-मुक्त हैं; लेखक सामान्यतः लॉक-मुक्त होता है, जब तक कि उसे स्मृति को पुनः प्राप्त करने की आवश्यकता न हो)। | ||
* | * अनेक लेखकों और पाठकों की संख्या के साथ [[रीड-कॉपी-अपडेट]]। (पाठक प्रतीक्षा-मुक्त हैं; अनेक लेखक सामान्यतःताला के साथ क्रमबद्ध होते हैं और बाधा-मुक्त नहीं होते हैं)। | ||
अनेक पुस्तकालय आंतरिक रूप से लॉक-फ्री तकनीकों का उपयोग करते हैं,<ref> | |||
[http://libcds.sourceforge.net/ libcds] - C++ library of lock-free containers and safe memory reclamation schema | [http://libcds.sourceforge.net/ libcds] - C++ library of lock-free containers and safe memory reclamation schema | ||
</ref><ref> | </ref><ref> | ||
| Line 50: | Line 50: | ||
ऑप्टिमाइज़िंग कंपाइलर आक्रामक रूप से संचालन को फिर से व्यवस्थित कर सकते हैं। | ऑप्टिमाइज़िंग कंपाइलर आक्रामक रूप से संचालन को फिर से व्यवस्थित कर सकते हैं। | ||
यहां तक कि जब वे नहीं करते हैं, तब भी | यहां तक कि जब वे नहीं करते हैं, तब भी अनेक आधुनिक सीपीयू अधिकांशतः ऐसे कार्यों को फिर से व्यवस्थित करते हैं (उनके पासकमजोर स्थिरता मॉडल है), | ||
जब तक कि सीपीयू को पुन: व्यवस्थित न करने के लिए मेमोरी बैरियर का उपयोग नहीं किया जाता है। | जब तक कि सीपीयू को पुन: व्यवस्थित न करने के लिए मेमोरी बैरियर का उपयोग नहीं किया जाता है। | ||
| Line 71: | Line 71: | ||
यह संपत्ति रीयल-टाइम सिस्टम के लिए महत्वपूर्ण है और जब तक प्रदर्शन लागत बहुत अधिक नहीं है तब तक हमेशा अच्छा होता है। | यह संपत्ति रीयल-टाइम सिस्टम के लिए महत्वपूर्ण है और जब तक प्रदर्शन लागत बहुत अधिक नहीं है तब तक हमेशा अच्छा होता है। | ||
इसे 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> कि व्यापक रूप से उपलब्ध एटॉमिक कंडीशनल प्रिमिटिव्स, कंपेयर-एंड-स्वैप और लोड-लिंक/स्टोर-कंडीशनल|एलएल/एससी, थ्रेड्स की संख्या में रैखिक रूप से बढ़ने वाली मेमोरी लागत के बिना अनेक सामान्य डेटा संरचनाओं के भुखमरी-मुक्त कार्यान्वयन प्रदान नहीं कर सकते हैं। | |||
व्यवहार में ये निचली सीमाएं वास्तविक बाधा नहीं प्रस्तुत करती हैं | व्यवहार में ये निचली सीमाएं वास्तविक बाधा नहीं प्रस्तुत करती हैं जिससे कि साझा मेमोरी में स्टोर प्रति थ्रेड के कैश लाइन या अनन्य आरक्षण ग्रेन्युल (एआरएम पर 2 केबी तक) खर्च करना व्यावहारिक प्रणालियों के लिए बहुत महंगा नहीं माना जाता है (सामान्यतः राशि) तार्किक रूप से आवश्यक स्टोरशब्द है, ही कैश लाइन पर शारीरिक रूप से कैस ऑपरेशंस टकराएंगे, और एलएल / एससी ऑपरेशंसही एक्सक्लूसिव रिजर्वेशन ग्रेन्युल में टकराएंगे, इसलिए भौतिक रूप से आवश्यक स्टोर की मात्रा ज्यादा होता है)। | ||
प्रतीक्षा-मुक्त एल्गोरिदम 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> लॉक-फ्री वाले से प्रतीक्षा-मुक्त डेटा संरचना उत्पन्न करने के लिएस्वचालित तंत्र प्रदान किया। इस प्रकार, प्रतीक्षा-मुक्त कार्यान्वयन अब अनेक डेटा-संरचनाओं के लिए उपलब्ध हैं। | ||
== लॉक-फ्रीडम == | == लॉक-फ्रीडम == | ||
| Line 86: | Line 86: | ||
विशेष रूप से, यदिथ्रेड को निलंबित कर दिया जाता है, तोलॉक-फ्री एल्गोरिथम गारंटी देता है कि शेष थ्रेड अभी भी प्रगति कर सकते हैं। इसलिए, यदि दो धागेही म्यूटेक्स लॉक या स्पिनलॉक के लिए प्रतिस्पर्धा कर सकते हैं, तो एल्गोरिदम लॉक-फ्री नहीं है। (यदि हमधागे को निलंबित कर देते हैं जो ताला रखता है, तो दूसरा धागा अवरुद्ध हो जाएगा।) | विशेष रूप से, यदिथ्रेड को निलंबित कर दिया जाता है, तोलॉक-फ्री एल्गोरिथम गारंटी देता है कि शेष थ्रेड अभी भी प्रगति कर सकते हैं। इसलिए, यदि दो धागेही म्यूटेक्स लॉक या स्पिनलॉक के लिए प्रतिस्पर्धा कर सकते हैं, तो एल्गोरिदम लॉक-फ्री नहीं है। (यदि हमधागे को निलंबित कर देते हैं जो ताला रखता है, तो दूसरा धागा अवरुद्ध हो जाएगा।) | ||
एक एल्गोरिथ्म लॉक-फ्री है यदि कुछ प्रोसेसर द्वारा असीम रूप से अधिकांशतः संचालनसीमित संख्या में चरणों में सफल होगा। उदाहरण के लिए, यदि {{var|N}} प्रोसेसरऑपरेशन को अंजाम देने की कोशिश कर रहे हैं, जिनमें से कुछ {{var|N}} प्रक्रियाएं सीमित संख्या में चरणों में संक्रिया को पूरा करने में सफल होंगी और अन्य विफल हो सकते हैं और विफलता पर पुनः प्रयास कर सकते हैं। वेट-फ्री और लॉक-फ्री के | एक एल्गोरिथ्म लॉक-फ्री है यदि कुछ प्रोसेसर द्वारा असीम रूप से अधिकांशतः संचालनसीमित संख्या में चरणों में सफल होगा। उदाहरण के लिए, यदि {{var|N}} प्रोसेसरऑपरेशन को अंजाम देने की कोशिश कर रहे हैं, जिनमें से कुछ {{var|N}} प्रक्रियाएं सीमित संख्या में चरणों में संक्रिया को पूरा करने में सफल होंगी और अन्य विफल हो सकते हैं और विफलता पर पुनः प्रयास कर सकते हैं। वेट-फ्री और लॉक-फ्री के मध्य का अंतर यह है कि प्रत्येक प्रक्रिया द्वारा वेट-फ्री ऑपरेशन को अन्य प्रोसेसर की परवाह किए बिना सीमित संख्या में चरणों में सफल होने की गारंटी दी जाती है। | ||
सामान्यतः,लॉक-फ्री एल्गोरिदम चार चरणों में चल सकता है: अपने स्वयं के ऑपरेशन को पूरा करना,अवरोधक ऑपरेशन में सहायता करना,बाधा डालने वाले ऑपरेशन को रद्द करना और प्रतीक्षा करना। समवर्ती सहायता और गर्भपात की संभावना से खुद का ऑपरेशन पूरा करना जटिल है, यह हमेशा पूरा करने का सबसे तेज़ रास्ता है। | सामान्यतः,लॉक-फ्री एल्गोरिदम चार चरणों में चल सकता है: अपने स्वयं के ऑपरेशन को पूरा करना,अवरोधक ऑपरेशन में सहायता करना,बाधा डालने वाले ऑपरेशन को रद्द करना और प्रतीक्षा करना। समवर्ती सहायता और गर्भपात की संभावना से खुद का ऑपरेशन पूरा करना जटिल है, यह हमेशा पूरा करने का सबसे तेज़ रास्ता है। | ||
Revision as of 15:37, 1 June 2023
कंप्यूटर विज्ञान में,कलन विधि को गैर-अवरुद्ध कहा जाता है यदि किसी थ्रेड (कंप्यूटिंग) की विफलता या निर्धारण (कंप्यूटिंग) किसी अन्य थ्रेड की विफलता या निलंबन का कारण नहीं बन सकता है।[1] तब कुछ कार्यों के लिए, यह एल्गोरिदम पारंपरिक अवरोधन (कंप्यूटर विज्ञान) के लिए उपयोगी विकल्प प्रदान करते हैं। इस प्रकार गैर-अवरुद्ध एल्गोरिथम लॉक-फ्री होते है यदि गारंटीकृत सिस्टम-वाइड प्रगति है और प्रति-थ्रेड प्रगति की गारंटी होने पर प्रतीक्षा-मुक्त है। इस प्रकार सन्न 2003 में बाधा-मुक्ति के प्रारंभ तक "गैर-अवरुद्ध" को साहित्य में "लॉक-फ्री" के पर्याय के रूप में उपयोग किया गया था।[2]
सामान्यतः गैर-अवरुद्धिंग शब्द का पारंपरिक रूप से दूरसंचार नेटवर्क का वर्णन करने के लिए उपयोग किया जाता था, जो "उपस्तिथ कॉल को फिर से व्यवस्थित किए बिना" रिले के समूह के माध्यम से कनेक्शन को रूट कर सकता था (Clos नेटवर्क देखें)। इसके अतिरिक्त, यदि टेलीफोन एक्सचेंज "दोषपूर्ण नहीं होता है, तब यह हमेशा कनेक्शन बना सकता है" (न्यूनतम स्पैनिंग स्विच को अनअवरुद्ध करना देखें)।
प्रेरणा
बहु-थ्रेडेड प्रोग्रामिंग के लिए पारंपरिक दृष्टिकोण साझा संसाधन (कंप्यूटर विज्ञान) तक पहुंच को सिंक्रनाइज़ करने के लिए लॉक (कंप्यूटर विज्ञान) का उपयोग करना होता है। इस प्रकार पारस्परिक बहिष्करण, सेमाफोर (प्रोग्रामिंग), और महत्वपूर्ण खंड जैसे सिंक्रनाइज़ेशन प्रिमिटिव्स सभी तंत्र होते हैं जिनके द्वारा प्रोग्रामर यह सुनिश्चित कर सकता है कि कोड के कुछ खंड समवर्ती रूप से निष्पादित नहीं होते हैं, यदि ऐसा करने से साझा मेमोरी संरचना दूषित हो जाती है। यदि थ्रेड किसी अन्य थ्रेड द्वारा पहले से रखे गए लॉक को प्राप्त करने का प्रयास करता है, तब लॉक मुक्त होने तक थ्रेड अवरुद्ध हो जाता है।
किसी थ्रेड को अवरुद्ध करना अनेक कारणों से अवांछनीय हो सकता है। अतः स्पष्ट कारण यह है कि जब थ्रेड अवरुद्ध होता है, तब यह कुछ भी पूर्ण नहीं कर सकता है। यदि अवरुद्ध थ्रेड उच्च-प्राथमिकता या वास्तविक काल कार्य कर रहा था, तब इसकी प्रगति को रोकना अत्यधिक अवांछनीय होता है।
सामान्यतः अन्य समस्याएं कम स्पष्ट होती हैं। उदाहरण के लिए, तालों के मध्य कुछ अंतःक्रियाएं गतिरोध, लाइवलॉक और प्राथमिक व्युत्क्रम जैसी त्रुटि स्थितियों का कारण बन सकती हैं। इस प्रकार ताले का उपयोग करने में मोटे अनाज वाले लॉकिंग के मध्यव्यापार-बंद भी सम्मिलित होता है, जो समानांतर कंप्यूटिंग के अवसरों को अधिक कम कर सकता है और उचित-दाने वाले लॉकिंग, जिसके लिए अधिक सावधान डिजाइन की आवश्यकता होती है, अतः लॉकिंग ओवरहेड को बढ़ाता है और बगों के लिए अधिक प्रवण होता है।
अवरुद्ध एल्गोरिदम के विपरीत, गैर-अवरुद्ध एल्गोरिदम इन डाउनसाइड्स से ग्रस्त नहीं होता हैं और इसके अतिरिक्त अवरोध हैंडलर में उपयोग के लिए सुरक्षित होता हैं। यदि पूर्व-रिक्त मल्टीटास्किंग थ्रेड को फिर से प्रारंभ नहीं किया जा सकता है, फिर भी इसके बिना प्रगति संभव होती है। इसके विपरीत, आपसी बहिष्करण द्वारा संरक्षित वैश्विक डेटा संरचनाओं को अवरोध हैंडलर में सुरक्षित रूप से एक्सेस नहीं किया जा सकता है, जिससे कि पूर्वाधिकृत थ्रेड लॉक को होल्ड करने वाला हो सकता है अतःमहत्वपूर्ण अनुभाग के समय अवरोध रिक्वेस्ट को मास्क करके इसे सरलता से ठीक किया जा सकता है।[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 केबी तक) खर्च करना व्यावहारिक प्रणालियों के लिए बहुत महंगा नहीं माना जाता है (सामान्यतः राशि) तार्किक रूप से आवश्यक स्टोरशब्द है, ही कैश लाइन पर शारीरिक रूप से कैस ऑपरेशंस टकराएंगे, और एलएल / एससी ऑपरेशंसही एक्सक्लूसिव रिजर्वेशन ग्रेन्युल में टकराएंगे, इसलिए भौतिक रूप से आवश्यक स्टोर की मात्रा ज्यादा होता है)।
प्रतीक्षा-मुक्त एल्गोरिदम 2011 तक अनुसंधान और व्यवहार दोनों में दुर्लभ थे। चूँकि, 2011 में कोगन और एरेज़ पेट्रैंक[18] सामान्यतः सामान्य हार्डवेयर पर उपलब्ध तुलना-और-स्वैप आदिम परप्रतीक्षा-मुक्त कतार निर्माण प्रस्तुत किया। उनके निर्माण ने माइकल और स्कॉट की लॉक-फ्री कतार का विस्तार किया,[19] जो अधिकांशतः अभ्यास में उपयोग की जाने वालीकुशल कतार है। कोगन और पेट्रैंक द्वाराअनुवर्ती पेपर[20] प्रतीक्षा-मुक्त एल्गोरिदम को तेजी से बनाने के लिएविधि प्रदान की और इस पद्धति का उपयोग प्रतीक्षा-मुक्त कतार को अपने लॉक-मुक्त समकक्ष के रूप में तेजी से करने के लिए किया। टिमनाट और पेट्रैंक द्वाराबाद का पेपर[21] लॉक-फ्री वाले से प्रतीक्षा-मुक्त डेटा संरचना उत्पन्न करने के लिएस्वचालित तंत्र प्रदान किया। इस प्रकार, प्रतीक्षा-मुक्त कार्यान्वयन अब अनेक डेटा-संरचनाओं के लिए उपलब्ध हैं।
लॉक-फ्रीडम
लॉक-फ्रीडम अलग-अलग थ्रेड्स को भूखे रहने की अनुमति देता है सिस्टम-वाइड थ्रूपुट की गारंटी देता है।एल्गोरिद्म लॉक-फ्री होता है, जब प्रोग्राम थ्रेड पर्याप्त रूप से लंबे समय तक चलाए जाते हैं, कम से कमथ्रेड बनाता है प्रगति (प्रगति की कुछ समझदार परिभाषा के लिए)। सभी वेट-फ्री एल्गोरिदम लॉक-फ्री हैं।
विशेष रूप से, यदिथ्रेड को निलंबित कर दिया जाता है, तोलॉक-फ्री एल्गोरिथम गारंटी देता है कि शेष थ्रेड अभी भी प्रगति कर सकते हैं। इसलिए, यदि दो धागेही म्यूटेक्स लॉक या स्पिनलॉक के लिए प्रतिस्पर्धा कर सकते हैं, तो एल्गोरिदम लॉक-फ्री नहीं है। (यदि हमधागे को निलंबित कर देते हैं जो ताला रखता है, तो दूसरा धागा अवरुद्ध हो जाएगा।)
एक एल्गोरिथ्म लॉक-फ्री है यदि कुछ प्रोसेसर द्वारा असीम रूप से अधिकांशतः संचालनसीमित संख्या में चरणों में सफल होगा। उदाहरण के लिए, यदि N प्रोसेसरऑपरेशन को अंजाम देने की कोशिश कर रहे हैं, जिनमें से कुछ N प्रक्रियाएं सीमित संख्या में चरणों में संक्रिया को पूरा करने में सफल होंगी और अन्य विफल हो सकते हैं और विफलता पर पुनः प्रयास कर सकते हैं। वेट-फ्री और लॉक-फ्री के मध्य का अंतर यह है कि प्रत्येक प्रक्रिया द्वारा वेट-फ्री ऑपरेशन को अन्य प्रोसेसर की परवाह किए बिना सीमित संख्या में चरणों में सफल होने की गारंटी दी जाती है।
सामान्यतः,लॉक-फ्री एल्गोरिदम चार चरणों में चल सकता है: अपने स्वयं के ऑपरेशन को पूरा करना,अवरोधक ऑपरेशन में सहायता करना,बाधा डालने वाले ऑपरेशन को रद्द करना और प्रतीक्षा करना। समवर्ती सहायता और गर्भपात की संभावना से खुद का ऑपरेशन पूरा करना जटिल है, यह हमेशा पूरा करने का सबसे तेज़ रास्ता है।
कब सहायता करनी है, कब रद्द करनी है या बाधा उत्पन्न होने पर प्रतीक्षा करनी है, इस बारे में निर्णय लेनाविवाद प्रबंधक का उत्तरदायित्व है। यह बहुत सरल हो सकता है (उच्च प्राथमिकता वाले संचालन में सहायता करें, कम प्राथमिकता वाले को निरस्त करें), या उत्तम थ्रूपुट प्राप्त करने के लिए अधिक अनुकूलित हो सकता है, या प्राथमिकता वाले संचालन की विलंबता को कम कर सकता है।
सही समवर्ती सहायता सामान्यतः लॉक-फ्री एल्गोरिदम का सबसे जटिल हिस्सा है, और अधिकांशतः निष्पादित करने के लिए बहुत महंगा होता है: न केवल सहायक थ्रेड धीमा हो जाता है, बल्कि साझा मेमोरी के यांत्रिकी के लिए धन्यवाद, सहायता की जा रही थ्रेड भी धीमी हो जाएगी , यदि यह अभी भी चल रहा है।
बाधा-मुक्ति
बाधा-मुक्ति सबसे कमजोर प्राकृतिक गैर-अवरोधक प्रगति गारंटी है।एल्गोरिथम बाधा-मुक्त होता है यदि किसी भी बिंदु पर, अलगाव में निष्पादितएकल थ्रेड (अर्थात्, सभी अवरोधक थ्रेड्स को निलंबित कर दिया जाता है) चरणों कीसीमित संख्या के लिए अपना ऑपरेशन पूरा करेगा।[15]सभी लॉक-फ्री एल्गोरिदम बाधा-मुक्त हैं।
बाधा-मुक्ति केवल यह मांग करती है कि किसी भी आंशिक रूप से पूर्ण किए गए ऑपरेशन को निरस्त किया जा सकता है और किए गए परिवर्तन वापस ले लिए जा सकते हैं। समवर्ती सहायता को छोड़ने से अधिकांशतः अधिक सरल एल्गोरिदम हो सकते हैं जो मान्य करने में आसान होते हैं। सिस्टम को लगातार livelock|live-locking से रोकनाकंटेंशन मैनेजर का काम है।
कुछ बाधा-मुक्त एल्गोरिदम डेटा संरचना में स्थिरता मार्करों कीजोड़ी का उपयोग करते हैं। डेटा संरचना को पढ़ने वाली प्रक्रियाएं पहलेसंगति मार्कर को पढ़ती हैं, फिर संबंधित डेटा कोआंतरिक बफर में पढ़ती हैं, फिर अन्य मार्कर को पढ़ती हैं, और फिर मार्करों की तुलना करती हैं। यदि दो मार्कर समान हैं तो डेटा सुसंगत है। डेटा संरचना को अद्यतन करने वाली किसी अन्य प्रक्रिया द्वारा रीड बाधित होने पर मार्कर गैर-समान हो सकते हैं। ऐसी स्थिति में, प्रक्रिया डेटा को आंतरिक बफ़र में छोड़ देती है और पुनः प्रयास करती है।
यह भी देखें
- गतिरोध
- जावा समवर्ती मानचित्र # लॉक-फ्री परमाणुता
- जीवंतता
- ताला (कंप्यूटर विज्ञान)
- आपसी बहिष्कार
- प्राथमिकता उलटा
- संसाधन भुखमरी
संदर्भ
- ↑ Göetz, Brian; Peierls, Tim; Bloch, Joshua; Bowbeer, Joseph; Holmes, David; Lea, Doug (2006). व्यवहार में जावा संगामिति. Upper Saddle River, NJ: Addison-Wesley. p. 41. ISBN 9780321349606.
- ↑ 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.
- ↑ 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.
- ↑ 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".
- ↑ 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.
- ↑ 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.
- ↑ libcds - C++ library of lock-free containers and safe memory reclamation schema
- ↑ liblfds - A library of lock-free data structures, written in C
- ↑ Concurrency Kit - A C library for non-blocking system design and implementation
- ↑ हर्ब सटर। "लॉक-फ्री कोड: सुरक्षा की झूठी भावना". Archived from the original on 2015-09-01.
- ↑ हर्ब सटर। "लॉक-फ्री कोड लिखना: एक सही कतार". Archived from the original on 2008-12-05.
- ↑ Herb Sutter. "Writing a Generalized Concurrent Queue".
- ↑ Herb Sutter. "The Trouble With Locks".
- ↑ Bruce Dawson. "ARM and Lock-Free Programming".
- ↑ 15.0 15.1 Anthony Williams. "Safety: off: How not to shoot yourself in the foot with C++ atomics". 2015. p. 20.
- ↑ 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.
- ↑ 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.
- ↑ 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.
- ↑ 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.
- ↑ 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.
- ↑ 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.
