इस प्रश्न को सी # टैग से पूछना, लेकिन यदि यह संभव है, तो यह किसी भी भाषा में संभव होना चाहिए।क्या एक लॉक (प्रतीक्षा) मुफ्त दोगुनी लिंक सूची संभव है?
क्या कोई प्रतीक्षा लॉकिंग प्रदान करने के लिए इंटरलाक्ड ऑपरेशंस का उपयोग करके दोगुनी लिंक्ड सूची को कार्यान्वित करना संभव है? मैं बिना इंतजार किए, सम्मिलित करना, निकालना और साफ़ करना चाहता हूं।
एक साधारण Google खोज कई लॉक-मुक्त दोगुनी लिंक्ड सूची कागजात प्रकट करेगी।
हालांकि, वे परमाणु सीएएस (तुलना और स्वैप) पर आधारित हैं।
पता नहीं कैसे परमाणु सी # में परिचालन कर रहे हैं, लेकिन इस वेबसाइट के अनुसार
http://www.albahari.com/threading/part4.aspx
सी # संचालन केवल पढ़ने और एक 32bit क्षेत्र लिखने के लिए परमाणु होने की गारंटी है। सीएएस का कोई जिक्र नहीं।
सी # (.NET) बिल्कुल परमाणु तुलना-और-स्वैप है। इसे Interlocked.CompareExchange कहा जाता है। http://msdn.microsoft.com/en-us/library/system.threading.interlocked.compareexchange.aspx – Cheeso
@ चेसो, फिर उस मामले में, यह संभव है। – Unknown
इसका उपयोग बहु-थ्रेडेड उपयोगकर्ता-इंटरफ़ेस को लागू करने के लिए किया जा सकता है - कोई भी एकल यूआई थ्रेड नहीं। – luvieere
मुझे विश्वास नहीं है कि यह संभव है, क्योंकि आपको एक शॉट में कई संदर्भ सेट करना पड़ रहा है, और इंटरलॉक ऑपरेशन उनकी शक्ति में सीमित हैं।
उदाहरण के लिए, ऐड ऑपरेशन लें - यदि आप ए और सी के बीच नोड बी डाल रहे हैं, तो आपको बी-> अगला, बी-> पिछला, ए-> अगला, और सी-> एक में सेट करना होगा परमाणु ऑपरेशन। इंटरलाक्ड इसे संभाल नहीं सकता है। प्रीसेटिंग बी के तत्व भी मदद नहीं करते हैं, क्योंकि जब आप "बी" तैयार करते हैं तो एक और थ्रेड डालने का निर्णय ले सकता है।
मैं इस मामले में लॉकिंग को जितना संभव हो उतना दोगुना करने पर अधिक ध्यान केंद्रित करता हूं, इसे खत्म करने की कोशिश नहीं करता।
"लॉकिंग को यथासंभव ठीक से प्राप्त करना" - जो इसे धीमा कर सकता है, क्योंकि एप्लिकेशन के मैक्रो-व्यवहार के आधार पर कई छोटे ताले निकालने की लागत से बचने के समय से अधिक महत्वपूर्ण हो सकता है। –
अच्छा बिंदु, ईरविकियर। प्रोफाइलिंग लाभ होगा –
यह उत्तर गलत है। संदिग्ध लिंक्ड सूचियां लागू की गई हैं। कुंजी यह है कि बैक पॉइंटर हमेशा अद्यतित नहीं होता है और इसलिए जब आप पीछे की तरफ जाते हैं, तो आपको कुछ अतिरिक्त काम करना पड़ता है। –
मैं कहूंगा कि उत्तर बहुत गहराई से योग्य है "हाँ, यह संभव है, लेकिन कठिन"। जो भी आप पूछ रहे हैं उसे लागू करने के लिए, आपको मूल रूप से ऐसा कुछ चाहिए जो संचालन को संकलित करने के लिए एक साथ टकराव सुनिश्चित करेगा; इस प्रकार, उस उद्देश्य के लिए सामान्य कार्यान्वयन करना बहुत मुश्किल होगा, और इसमें अभी भी कुछ महत्वपूर्ण सीमाएं होंगी। सटीक आवश्यकताओं के अनुरूप एक विशिष्ट कार्यान्वयन बनाने के लिए शायद यह आसान होगा, और फिर भी, यह किसी भी माध्यम से "सरल" नहीं होगा।
"कुछ ऐसा जो कुछ भी टकराव सुनिश्चित करने के लिए संचालन को संकलित करेगा" - इसका क्या अर्थ है? –
इस बारे में सोचें कि आधुनिक सीपीयू उच्च निर्देश थ्रुपुट प्राप्त करने के लिए एक कोर पर एकाधिक निष्पादन इकाइयों का उपयोग कैसे करते हैं; निष्पादन इकाइयों के साथ निर्देशों की बातचीत गैर-परस्पर निर्भर होने के लिए की जाती है, और सूक्ष्म निर्देशों को अंतःस्थापित किया जाता है ताकि किसी ऑर्डर-निर्भर संचालन को संरक्षित किया जा सके। यह मूल रूप से एक संकलन ऑपरेशन है। –
यह एक बहुत ही गैर-मुद्दा है क्योंकि अधिकांश भाषाएं "मेमोरी बाrier" की आपूर्ति करती हैं जो संकलक और सीपीयू दोनों को इसके आगे पढ़ने/लिखने के संचालन को स्थानांतरित करने से रोकती है, ताकि आप सुनिश्चित कर सकें कि यह संचालन को पुनर्व्यवस्थित नहीं करता है इस तरह से आप अमान्य हैं कि आप कोड हैं। (यही कारण है कि सी/सी ++ में अस्थिर कीवर्ड का आविष्कार किया गया था, हालांकि अस्थिर केवल अन्य अस्थिर चर के खिलाफ यह सुनिश्चित करता है, इसलिए स्मृति बाधाओं का परिचय)। –
यहां एक paper है जो लॉक मुक्त दोगुनी लिंक वाली सूची का वर्णन करता है।
हम एक समवर्ती Deque कि सुलभ संबंध तोड़ना-समानांतर है और परमाणु पुरातन जो आधुनिक कंप्यूटर सिस्टम में उपलब्ध हैं का उपयोग करता है के लिए एक कुशल और व्यावहारिक ताला मुक्त कार्यान्वयन प्रस्तुत करते हैं। इससे पहले deques की जाना जाता ताला मुक्त एल्गोरिदम या तो गैर उपलब्ध परमाणु तुल्यकालन पुरातन पर आधारित हैं, केवल कार्यक्षमता के एक सबसेट को लागू, या नहीं बनाया गया है के लिए संबंध तोड़ना तक पहुँचता है। हमारा एल्गोरिदम एक दोगुना लिंक्ड सूची पर आधारित है, और केवल एकल-शब्द तुलना और स्वैप ...
रॉस Bencina वास्तव में कुछ अच्छे लिंक मैं सिर्फ numerious कागजात और स्रोत कोड excamples के साथ पाया है की आवश्यकता है "Some notes on lock-free and wait-free algorithms" के लिए।
मुझे विश्वास है कि, AFAIK, * सभी * दोगुनी-लिंक्ड सूचियां (और वास्तव में, यह सभी एकल-लिंक्ड सूचियां भी हो सकती हैं) जीसी की आवश्यकता होती है। –
मेरा मानना है कि वालोइस की 1995 की एकल-लिंक्ड सूची में जीसी की आवश्यकता नहीं है - मुझे हालांकि पेपर पढ़ने की जरूरत है। –
वालोइस पेपर लॉक फ्री मेमोरी प्रबंधन सुनिश्चित करने के लिए संदर्भ गिनती का उपयोग करता है। संदर्भ संख्या नोड पर वैश्विक पॉइंटर्स की संख्या का प्रतिनिधित्व करती है। इसके अतिरिक्त प्रत्येक थ्रेड पॉइंटर्स की एक खतरनाक सूची को नोड्स में रखता है जो वर्तमान में उपयोग कर रहा है। यदि कोई थ्रेड अपनी खतरनाक सूची से पॉइंटर को हटाना चाहता है जिसमें 0 की संदर्भ संख्या है, तो यह देखने के लिए कि क्या कोई अभी भी इसका उपयोग कर रहा है, उसे किसी अन्य थ्रेड की खतरनाक सूचियों को स्कैन करना है, और केवल इसे हटाएं। किसी भी ताले के बिना खतरनाक सूचियों को सुरक्षित रूप से स्कैन करने में शामिल कुछ चालें हैं। – JanKanis
एफडब्ल्यूआईडब्ल्यू, .NET 4.0 एक समवर्ती लिंक्डलिस्ट जोड़ रहा है, जो सिस्टम में थ्रेडसेफ दोगुनी जुड़ी सूची है।संग्रह। कॉनकुरेंट नेमस्पेस। आप documentation या blog post इसे वर्णित कर सकते हैं।
किसी भी माध्यम से थ्रेडसेफ का मतलब ताला रहित नहीं है। अच्छे शोध के लिए –
फुटनोट पढ़ें - वे VS2010
के अंतिम रिलीज वैसे आप वास्तव में इसे कैसे करना नहीं कहा है करने से पहले 4.0 से ConcurrentLinkedList खींचने के लिए योजना है। लेकिन, बशर्ते आप सी # में परमाणु सीएएस कर सकें, यह पूरी तरह से संभव है।
असल में मैं अभी सी ++ में एक दोगुनी लिंक्ड प्रतीक्षा मुक्त सूची के कार्यान्वयन के माध्यम से काम कर रहा हूं।
यहां पेपर का वर्णन करने वाला पेपर है। http://www.cse.chalmers.se/~tsigas/papers/Haakan-Thesis.pdf
और एक प्रस्तुति जो आपको कुछ सुराग भी प्रदान कर सकती है। http://www.ida.liu.se/~chrke/courses/MULTI/slides/Lock-Free_DoublyLinkedList.pdf
हां यह संभव है, यहां सी ++ में एसटीएल की तरह Lock-Free Doubly-Linked List का मेरा कार्यान्वयन है।
Sample code that spawns threads to randomly perform ops on a list
यह एक 64-बिट तुलना और स्वैप ए.बी.ए. मुद्दों के बिना काम करने के लिए की आवश्यकता है। यह सूची केवल lock-free memory manager की वजह से संभव है।
benchmarks on page 12 देखें। विवाद की वृद्धि के रूप में धागे की संख्या के साथ रैखिक रूप से सूची तराजू का प्रदर्शन। एल्गोरिदम विवादित पहुंच के लिए समांतरता का समर्थन करता है, इसलिए सूची आकार बढ़ने से विवाद कम हो सकता है।
अधिकांश आर्किटेक्चर पर सभी कॉपी करने योग्य डेटा संरचनाओं के लिए लॉक मुक्त एल्गोरिदम लिखना संभव है [1]। लेकिन कुशल लोगों को लिखना मुश्किल है।
मैंने .NET के लिए lock-free doubly linked list by Håkan Sundell and Philippas Tsigas में implementation लिखा था। ध्यान दें, कि यह अवधारणा के कारण परमाणु पॉपलिफ्ट का समर्थन नहीं करता है।
[1]: Maurice Herlihy: Impossibility and universality results for wait-freesynchronization (1988)
मुक्त ताला और इंतजार मुक्त अलग हैं .... ताला मुक्त कुछ सूत्र, प्रगति कर सकते हैं मुक्त साधन सभी धागे प्रक्रिया कर सकते हैं इंतजार का मतलब है। – user997112