गैर-अवरुद्ध एल्गोरिदम
कंप्यूटर विज्ञान में,कलन विधि को गैर-अवरुद्ध कहा जाता है यदि किसी थ्रेड (कंप्यूटिंग) की विफलता या निर्धारण (कंप्यूटिंग) किसी अन्य थ्रेड की विफलता या निलंबन का कारण नहीं बन सकती है।[1] कुछ कार्यों के लिए, यह एल्गोरिदम पारंपरिक लॉक (कंप्यूटर विज्ञान) के लिएउपयोगी विकल्प प्रदान करते हैं।गैर-अवरुद्ध एल्गोरिथम लॉक-फ्री है यदि सिस्टम-वाइड रिसोर्स भुखमरी की गारंटी है, और प्रति-थ्रेड प्रगति की गारंटी होने पर प्रतीक्षा-मुक्त है। 2003 में बाधा-मुक्ति की प्रारंभिक तक गैर-अवरुद्ध को साहित्य में लॉक-फ्री के पर्याय के रूप में उपयोग किया गया था।[2] नॉन-ब्लॉकिंग शब्द का पारंपरिक रूप से दूरसंचार नेटवर्क का वर्णन करने के लिए उपयोग किया जाता था जो उपस्तिथ कॉल को फिर से व्यवस्थित किए बिना रिले केसेट के माध्यम सेकनेक्शन को रूट कर सकता था (Clos नेटवर्क देखें)। इसके अतिरिक्त, यदि टेलीफोन एक्सचेंज दोषपूर्ण नहीं है, तो यह हमेशा कनेक्शन बना सकता है (न्यूनतम स्पैनिंग स्विच को अनब्लॉक करना देखें)।
प्रेरणा
बहु-थ्रेडेड प्रोग्रामिंग के लिए पारंपरिक दृष्टिकोण साझा संसाधन (कंप्यूटर विज्ञान) तक पहुंच को सिंक्रनाइज़ करने के लिए लॉक (कंप्यूटर विज्ञान) का उपयोग करना है। पारस्परिक बहिष्करण, सेमाफोर (प्रोग्रामिंग), और महत्वपूर्ण खंड जैसे सिंक्रनाइज़ेशन प्रिमिटिव्स सभी तंत्र हैं जिनके द्वाराप्रोग्रामर यह सुनिश्चित कर सकता है कि कोड के कुछ खंड समवर्ती रूप से निष्पादित नहीं होते हैं, यदि ऐसा करने से साझा मेमोरी संरचना दूषित हो जाती है। यदिथ्रेड किसी अन्य थ्रेड द्वारा पहले से रखे गए लॉक को प्राप्त करने का प्रयास करता है, तो लॉक मुक्त होने तक थ्रेड ब्लॉक हो जाएगा।
किसी थ्रेड को ब्लॉक करना कई कारणों से अवांछनीय हो सकता है।स्पष्ट कारण यह है कि जब थ्रेड अवरुद्ध होता है, तो यह कुछ भी पूरा नहीं कर सकता है: यदि अवरुद्ध थ्रेड उच्च-प्राथमिकता या रीयल-टाइम कंप्यूटिंग | रीयल-टाइम कार्य कर रहा था, तो इसकी प्रगति को रोकना बेहद अवांछनीय होगा।
अन्य समस्याएं कम स्पष्ट हैं। उदाहरण के लिए, तालों के बीच कुछ अंतःक्रियाएं गतिरोध, 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 से रोकनाकंटेंशन मैनेजर का काम है।
कुछ बाधा-मुक्त एल्गोरिदम डेटा संरचना में स्थिरता मार्करों कीजोड़ी का उपयोग करते हैं। डेटा संरचना को पढ़ने वाली प्रक्रियाएं पहलेसंगति मार्कर को पढ़ती हैं, फिर संबंधित डेटा कोआंतरिक बफर में पढ़ती हैं, फिर अन्य मार्कर को पढ़ती हैं, और फिर मार्करों की तुलना करती हैं। यदि दो मार्कर समान हैं तो डेटा सुसंगत है। डेटा संरचना को अद्यतन करने वाली किसी अन्य प्रक्रिया द्वारा रीड बाधित होने पर मार्कर गैर-समान हो सकते हैं। ऐसी स्थिति में, प्रक्रिया डेटा को आंतरिक बफ़र में छोड़ देती है और पुनः प्रयास करती है।
यह भी देखें
- गतिरोध
- जावा समवर्ती मानचित्र # लॉक-फ्री परमाणुता
- जीवंतता
- ताला (कंप्यूटर विज्ञान)
- आपसी बहिष्कार
- प्राथमिकता उलटा
- संसाधन भुखमरी
संदर्भ
- ↑ 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.
