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

From Vigyanwiki
No edit summary
No edit summary
 
(5 intermediate revisions by 4 users not shown)
Line 1: Line 1:
{{Short description|Algorithm in a thread whose failure cannot cause another thread to fail}}
{{Short description|Algorithm in a thread whose failure cannot cause another thread to fail}}
{{Distinguish|गैर-अवरुद्ध I/O}}
{{Distinguish|गैर-अवरुद्ध आई/ओ}}


[[कंप्यूटर विज्ञान]] में,[[कलन विधि]] को गैर-अवरुद्ध कहा जाता है यदि किसी [[थ्रेड (कंप्यूटिंग)]] की विफलता या [[ निर्धारण (कंप्यूटिंग) ]] किसी अन्य थ्रेड की विफलता या निलंबन का कारण नहीं बन सकता है।<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 नेटवर्क देखें)। इसके अतिरिक्त, यदि टेलीफोन एक्सचेंज "दोषपूर्ण नहीं होता है, तब यह हमेशा कनेक्शन बना सकता है" (न्यूनतम स्पैनिंग स्विच को अनअवरुद्ध करना देखें)।
सामान्यतः गैर-अवरुद्धिंग शब्द का पारंपरिक रूप से [[दूरसंचार नेटवर्क]] का वर्णन करने के लिए उपयोग किया जाता था, जो "उपस्तिथ कॉल को फिर से व्यवस्थित किए बिना" रिले के समूह के माध्यम से कनेक्शन को रूट कर सकता था (क्लोस नेटवर्क देखें)। इसके अतिरिक्त, यदि टेलीफोन रूपांतरण "दोषपूर्ण नहीं होता है, तब यह हमेशा कनेक्शन बना सकता है" (न्यूनतम स्पैनिंग स्विच को अनअवरुद्ध करना देखें)।


== प्रेरणा ==
== प्रेरणा ==
Line 25: Line 25:
</ref>
</ref>
== कार्यान्वयन ==
== कार्यान्वयन ==
सामान्यतः कुछ अपवादों के साथ, गैर-अवरुद्ध एल्गोरिदम [[परमाणु पठन-संशोधित-लेखन आदिम]] का उपयोग करते हैं जो हार्डवेयर को प्रदान करना चाहिए, जिनमें से सबसे उल्लेखनीय तुलना और स्वैप (सीएएस) है। इन प्रिमिटिव्स पर मानक इंटरफेस का उपयोग करके क्रिटिकल सेक्शन लगभग हमेशा प्रयुक्त किए जाते हैं (सामान्य स्थिति में, इन प्रिमिटिव्स के साथ प्रयुक्त होने पर भी क्रिटिकल सेक्शन अवरुद्ध हो जाते है)। सन्न 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>
सामान्यतः कुछ अपवादों के साथ, गैर-अवरुद्ध एल्गोरिदम [[परमाणु पठन-संशोधित-लेखन आदिम]] का उपयोग करते हैं जो हार्डवेयर को प्रदान करना चाहिए, जिनमें से सबसे उल्लेखनीय तुलना और स्वैप (सीएएस) है। इन प्रिमिटिव्स पर मानक इंटरफेस का उपयोग करके क्रिटिकल सेक्शन लगभग हमेशा प्रयुक्त किए जाते हैं (सामान्य स्थिति में, इन प्रिमिटिव्स के साथ प्रयुक्त होने पर भी आलोचनात्मक सेक्शन अवरुद्ध हो जाते है)। सन्न 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 63: Line 63:
सामान्यतः अनेक पेपरों ने प्रतीक्षा-मुक्त एल्गोरिथम बनाने की कठिनाई की जांच की है। उदाहरण के लिए, यह दिखाया गया है<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 केबी तक) खर्च करना व्यावहारिक प्रणालियों के लिए अधिक महंगा नहीं माना जाता है (सामान्यतः राशि) तार्किक रूप से आवश्यक स्टोर शब्द होता है, अतः कैश लाइन पर शारीरिक रूप से कैस ऑपरेशंस टकराएंगे और एलएल / एससी ऑपरेशंसही एक्सक्लूसिव रिजर्वेशन ग्रेन्युल में टकराएंगे, इसलिए भौतिक रूप से '''आवश्यक स्टोर की मात्रा ज्यादा होता है)।'''
अधिकाशतः व्यवहार में यह निचली सीमाएं वास्तविक बाधा नहीं प्रस्तुत करती हैं जिससे कि साझा मेमोरी में स्टोर प्रति थ्रेड के कैश लाइन या अनन्य आरक्षण ग्रेन्युल (एआरएम पर 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> लॉक-मुक्त वाले से प्रतीक्षा-मुक्त डेटा संरचना उत्पन्न करने के लिए स्वचालित तंत्र प्रदान किया। इस प्रकार, प्रतीक्षा-मुक्त कार्यान्वयन अब अनेक डेटा-संरचनाओं के लिए उपलब्ध होता हैं।


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


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


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


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


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


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


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


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


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


== यह भी देखें ==
== यह भी देखें ==
* गतिरोध
* गतिरोध
* जावा समवर्ती मानचित्र # लॉक-मुक्त परमाणुता
* जावा समवर्ती मानचित्र
* [[जीवंतता]]
* [[जीवंतता]]
* ताला (कंप्यूटर विज्ञान)
* लॉक (कंप्यूटर विज्ञान)
* आपसी बहिष्कार
* आपसी बहिष्कार
* प्राथमिकता उलटा
* प्राथमिकता उलटा
Line 106: Line 104:
* [http://tutorials.jenkov.com/java-concurrency/non-blocking-algorithms.html Non-blocking Algorithms]
* [http://tutorials.jenkov.com/java-concurrency/non-blocking-algorithms.html Non-blocking Algorithms]


{{DEFAULTSORT:Non-Blocking Algorithm}}[[Category: तादात्म्य]] [[Category: समरूपता नियंत्रण]] [[Category: समवर्ती नियंत्रण एल्गोरिदम]]
{{DEFAULTSORT:Non-Blocking Algorithm}}


 
[[Category:Articles with hatnote templates targeting a nonexistent page|Non-Blocking Algorithm]]
 
[[Category:Created On 26/05/2023|Non-Blocking Algorithm]]
[[Category: Machine Translated Page]]
[[Category:Lua-based templates|Non-Blocking Algorithm]]
[[Category:Created On 26/05/2023]]
[[Category:Machine Translated Page|Non-Blocking Algorithm]]
[[Category:Pages with script errors|Non-Blocking Algorithm]]
[[Category:Templates Vigyan Ready|Non-Blocking Algorithm]]
[[Category:Templates that add a tracking category|Non-Blocking Algorithm]]
[[Category:Templates that generate short descriptions|Non-Blocking Algorithm]]
[[Category:Templates using TemplateData|Non-Blocking Algorithm]]
[[Category:तादात्म्य|Non-Blocking Algorithm]]
[[Category:समरूपता नियंत्रण|Non-Blocking Algorithm]]
[[Category:समवर्ती नियंत्रण एल्गोरिदम|Non-Blocking Algorithm]]

Latest revision as of 14:53, 12 June 2023

Not to be confused with गैर-अवरुद्ध आई/ओ.

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

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

प्रेरणा

Main article: अवरुद्ध की हानियाँ

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

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

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

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

प्रदर्शन को उत्तम बनाने के लिए लॉक-मुक्त डेटा संरचना का उपयोग किया जा सकता है। इस प्रकार लॉक-मुक्त डेटा संरचना सीरियल निष्पादन के अतिरिक्त समानांतर निष्पादन में बिताए गए समय की मात्रा को बढ़ाती है, अतः मल्टी-कोर प्रोसेसर पर प्रदर्शन में सुधार करती है, जिससे कि साझा डेटा संरचना तक पहुंच को सुसंगत रहने के लिए क्रमबद्ध करने की आवश्यकता नहीं होती है।[4]

कार्यान्वयन

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

स्टैक (डेटा संरचना), कतार (डेटा संरचना), सेट (कंप्यूटर विज्ञान) और हैश तालिका जैसी बुनियादी डेटा संरचनाएँ प्रदान करने में अधिक शोध किया गया है। यह प्रोग्राम को सरलता से थ्रेड्स के मध्य अतुल्यकालिक रूप से डेटा का आदान-प्रदान करने की अनुमति देते हैं।

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

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

सामान्यतः अनेक पुस्तकालय आंतरिक रूप से लॉक-मुक्त तविधियों का उपयोग करते हैं,[7][8][9] लॉक-मुक्त कोड लिखने में कठिनाई होती है जो सही होती है।[10][11][12][13]

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

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

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

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

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

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

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

लॉक-मुक्ति

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

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

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

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

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

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

बाधा-मुक्ति

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

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

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

यह भी देखें

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

संदर्भ

  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=184647’