स्पिनलॉक
सॉफ्टवेयर इंजीनियरिंग में, एक स्पिनलॉक एक लॉक (कंप्यूटर साइंस) है जो एक थ्रेड (कंप्यूटर साइंस) का कारण बनता है जो बार-बार जांच कर रहा है कि लॉक उपलब्ध है या नहीं। चूँकि थ्रेड सक्रिय रहता है लेकिन कोई उपयोगी कार्य नहीं कर रहा है, ऐसे लॉक का उपयोग एक प्रकार का व्यस्त प्रतीक्षा है। एक बार अधिग्रहित होने के बाद, स्पिनलॉक सामान्यतः तब तक आयोजित किए जाते हैं जब तक कि वे स्पष्ट रूप से जारी नहीं हो जाते हैं, चूंकि कुछ कार्यान्वयनों में वे स्वचालित रूप से जारी हो सकते हैं यदि थ्रेड पर प्रतीक्षा की जा रही है (जिस पर ताला लगा है) ब्लॉक हो जाता है या सो जाता है।
क्योंकि वे ऑपरेटिंग सिस्टम निर्धारण (कंप्यूटिंग) या संदर्भ स्विचिंग से ओवरहेड से बचते हैं, अगर थ्रेड (कंप्यूटर साइंस) केवल छोटी अवधि के लिए अवरुद्ध होने की संभावना है तो स्पिनलॉक्स कुशल होते हैं। इस कारण से, ऑपरेटिंग सिस्टम कर्नेल|ऑपरेटिंग-सिस्टम कर्नेल अधिकांशतः स्पिनलॉक का उपयोग करते हैं। चूंकि, यदि लंबे समय तक रखा जाए तो स्पिनलॉक बेकार हो जाते हैं, क्योंकि वे अन्य थ्रेड्स को चलने से रोक सकते हैं और पुनर्निर्धारण की आवश्यकता होती है। एक थ्रेड जितना अधिक समय तक लॉक रखता है, उतना ही अधिक जोखिम होता है कि लॉक को होल्ड करते समय ओएस शेड्यूलर द्वारा थ्रेड को बाधित किया जाएगा। यदि ऐसा होता है, तो अन्य थ्रेड घूमते रह जाएंगे (बार-बार लॉक प्राप्त करने का प्रयास कर रहे हैं), जबकि लॉक को पकड़ने वाला थ्रेड इसे जारी करने की दिशा में प्रगति नहीं कर रहा है। परिणाम एक अनिश्चितकालीन स्थगन है जब तक कि लॉक को पकड़ने वाला धागा समाप्त नहीं हो सकता और इसे जारी नहीं कर सकता। यह सिंगल-प्रोसेसर सिस्टम पर विशेष रूप से सच है, जहां एक ही प्राथमिकता के प्रत्येक वेटिंग थ्रेड को अपनी क्वांटम (आवंटित समय जहां एक थ्रेड चल सकता है) को बर्बाद करने की संभावना है, जब तक कि लॉक को रखने वाले थ्रेड को समाप्त नहीं किया जाता है।
स्पिनलॉक्स को सही ढंग से कार्यान्वित करना चुनौतीपूर्ण है क्योंकि प्रोग्रामर को लॉक तक एक साथ पहुंच की संभावना को ध्यान में रखना चाहिए, जो दौड़ की स्थिति पैदा कर सकता है। सामान्यतः, ऐसा कार्यान्वयन केवल विशेष सभा की भाषा | असेंबली-लैंग्वेज निर्देशों के साथ ही संभव है, जैसे परमाणु संचालन परीक्षण और सेट संचालन और प्रोग्रामिंग भाषाओं में आसानी से लागू नहीं किया जा सकता है जो वास्तव में परमाणु संचालन का समर्थन नहीं करते हैं।[1] इस तरह के संचालन के बिना आर्किटेक्चर पर, या यदि उच्च स्तरीय भाषा कार्यान्वयन की आवश्यकता होती है, तो गैर-परमाणु लॉकिंग एल्गोरिदम का उपयोग किया जा सकता है, उदा। पीटरसन का एल्गोरिदम। चूंकि, इस तरह के कार्यान्वयन के लिए स्पिनलॉक की तुलना में अधिक स्मृति की आवश्यकता हो सकती है, अनलॉक करने के बाद प्रगति की अनुमति देने के लिए धीमी हो, और उच्च-स्तरीय भाषा में कार्यान्वयन योग्य न हो, यदि आउट-ऑफ-ऑर्डर निष्पादन की अनुमति है।
उदाहरण कार्यान्वयन
स्पिनलॉक को लागू करने के लिए निम्न उदाहरण x86 असेंबली भाषा का उपयोग करता है। यह किसी भी Intel 80386 अनुरूप प्रोसेसर पर काम करेगा। <वाक्यविन्यास प्रकाश लैंग = nasm>
- इंटेल सिंटैक्स
बंद:; ताला चर। 1 = लॉक, 0 = अनलॉक।
डीडी 0
स्पिन_लॉक:
मूव ईएक्स, 1; EAX रजिस्टर को 1 पर सेट करें।
एक्ससीजी ईएक्स, [लॉक]; EAX रजिस्टर को परमाणु रूप से स्वैप करें
; ताला चर।
; यह हमेशा 1 को लॉक करने के लिए स्टोर करेगा
; EAX रजिस्टर में पिछला मान।
टेस्ट ईएक्स, ईएक्स; EAX को स्वयं के साथ टेस्ट करें। अन्य बातों के अतिरिक्त, यह होगा
; यदि EAX 0 है तो प्रोसेसर का जीरो फ्लैग सेट करें।
; यदि ईएक्स 0 है, तो लॉक अनलॉक किया गया था और
; हमने इसे अभी बंद कर दिया है।
; अन्यथा, ईएक्स 1 है और हमने लॉक हासिल नहीं किया है।
जेएनजेड स्पिन_लॉक; अगर जीरो फ्लैग है तो MOV निर्देश पर वापस जाएं
; सेट नहीं; ताला पहले बंद था, और इसलिए
; हमें तब तक स्पिन करने की जरूरत है जब तक कि यह अनलॉक न हो जाए।
रिट; लॉक प्राप्त कर लिया गया है, कॉलिंग पर वापस लौटें
; समारोह।
spin_unlock:
एक्सोर ईएक्स, ईएक्स; EAX रजिस्टर को 0 पर सेट करें।
एक्ससीजी ईएक्स, [लॉक]; EAX रजिस्टर को परमाणु रूप से स्वैप करें
; ताला चर।
रिट; ताला प्रकाशित हो चुकी है।.
</वाक्यविन्यास हाइलाइट>
महत्वपूर्ण अनुकूलन
उपरोक्त सरल कार्यान्वयन x86 आर्किटेक्चर का उपयोग कर सभी CPU पर काम करता है। चूंकि, कई प्रदर्शन अनुकूलन संभव हैं:
x86 आर्किटेक्चर के बाद के कार्यान्वयन पर, spin_unlock धीरे-धीरे लॉक किए गए XCHG के अतिरिक्त अनलॉक किए गए MOV का सुरक्षित रूप से उपयोग कर सकता है। यह सूक्ष्म मेमोरी ऑर्डरिंग नियमों के कारण है जो इसका समर्थन करते हैं, भले ही MOV पूर्ण मेमोरी बैरियर नहीं है। चूंकि, कुछ प्रोसेसर (कुछ सिरिक्स प्रोसेसर, इंटेल पेंटियम प्रो के कुछ संशोधन (बग के कारण), और पहले के पेंटियम (ब्रांड) और i486 सममित मल्टीप्रोसेसिंग सिस्टम) गलत काम करेंगे और लॉक द्वारा संरक्षित डेटा दूषित हो सकता है। अधिकांश गैर-x86 आर्किटेक्चर पर, स्पष्ट स्मृति बाधा या परमाणु निर्देश (उदाहरण के अनुसार) का उपयोग किया जाना चाहिए। कुछ प्रणालियों पर, जैसे IA-64, विशेष अनलॉक निर्देश हैं जो आवश्यक मेमोरी क्रम प्रदान करते हैं।
इंटर-सीपीयू बस (कंप्यूटिंग) को कम करने के लिए, लॉक प्राप्त करने का प्रयास करने वाले कोड को कुछ भी लिखने की कोशिश किए बिना पढ़ने को लूप करना चाहिए जब तक कि यह एक परिवर्तित मान नहीं पढ़ता। MESI कैशिंग प्रोटोकॉल के कारण, यह कैश लाइन को लॉक के लिए साझा करने का कारण बनता है; तब उल्लेखनीय रूप से कोई बस यातायात नहीं होता है जबकि सीपीयू लॉक की प्रतीक्षा करता है। यह ऑप्टिमाइज़ेशन उन सभी CPU आर्किटेक्चर पर प्रभावी है जिनके पास प्रति CPU कैश है, क्योंकि MESI इतना व्यापक है। हाइपर-थ्रेडिंग सीपीयू पर, के साथ रुकना rep nop कोर को संकेत देकर अतिरिक्त प्रदर्शन देता है कि यह दूसरे थ्रेड पर काम कर सकता है जबकि लॉक स्पिन प्रतीक्षा कर रहा है।[2] लेन-देन तुल्यकालन एक्सटेंशन और अन्य हार्डवेयर लेन-देन स्मृति इंस्ट्रक्शन सेट ज्यादातर मामलों में लॉक को बदलने के लिए काम करते हैं। चूंकि लॉकबैक के रूप में अभी भी ताले की आवश्यकता है, लेकिन उनके पास प्रोसेसर को परमाणु संचालन के पूरे ब्लॉक को संभालने के द्वारा प्रदर्शन में काफी सुधार करने की क्षमता है। यह सुविधा कुछ म्यूटेक्स कार्यान्वयनों में अंतर्निहित है, उदाहरण के लिए glibc में। X86 में हार्डवेयर लॉक एलिसन (HLE) TSE का एक कमजोर लेकिन पीछे की ओर अनुरूप संस्करण है, और हम इसे बिना किसी अनुकूलता खोए लॉकिंग के लिए यहां उपयोग कर सकते हैं। इस विशेष मामले में, प्रोसेसर तब तक लॉक नहीं करना चुन सकता है जब तक कि दो धागे वास्तव में एक दूसरे के साथ संघर्ष न करें।[3]
परीक्षण का एक सरल संस्करण उपयोग कर सकता है cmpxchg x86 पर निर्देश, या __sync_bool_compare_and_swap कई यूनिक्स कंपाइलर्स में निर्मित।
लागू किए गए ऑप्टिमाइज़ेशन के साथ, एक नमूना ऐसा दिखाई देगा: <वाक्यविन्यास प्रकाश लैंग = nasm>
- सी में
- जबकि (!
स्पिन_लॉक:
मूव ईसीएक्स, 1; ईसीएक्स रजिस्टर को 1 पर सेट करें।
पुन: प्रयास करें:
एक्सोर ईएक्स, ईएक्स; EAX को ज़ीरो आउट करें, क्योंकि cmpxchg EAX से तुलना करता है।
XACQUIRE लॉक cmpxchg [लॉक], ecx
; परमाणु रूप से निर्णय लें: यदि लॉक शून्य है, तो इसे ईसीएक्स लिखें।
; XACQUIRE प्रोसेसर को संकेत देता है कि हम एक लॉक प्राप्त कर रहे हैं।
जेई आउट; यदि हमने इसे लॉक कर दिया है (पुराना मान EAX: 0 के बराबर है), तो वापस लौटें।
रोकना:
मूव ईएक्स, [लॉक]; ईएक्स में बंद पढ़ें।
टेस्ट ईएक्स, ईएक्स; पहले की तरह शून्य-परीक्षण करें।
जे जेड पुनः प्रयास करें; यदि यह शून्य है, तो हम पुनः प्रयास कर सकते हैं।
प्रतिनिधि नोप; सीपीयू को बताएं कि हम स्पिनलूप में इंतजार कर रहे हैं, तो यह हो सकता है
; अब दूसरे धागे पर काम करो। विराम के रूप में भी लिखा गया है।
जेएमपी विराम; चेक-पॉज़ करते रहें।
बाहर:
रिट; सब कुछ कर दिया।
spin_unlock:
XRELEASE मूव [लॉक], 0; मान लें कि मेमोरी ऑर्डरिंग नियम लागू होते हैं, तो रिलीज़ करें
; लॉक रिलीज़ हिंट के साथ लॉक वेरिएबल।
रिट; ताला प्रकाशित हो चुकी है।.
</वाक्यविन्यास हाइलाइट>
MESI प्रोटोकॉल का उपयोग करने वाले किसी भी बहु-प्रोसेसर सिस्टम पर, ऐसा टेस्ट-एंड-टेस्ट-एंड-सेट लॉक (टीटीएएस) सरल टेस्ट-एंड-सेट लॉक (टीएएस) दृष्टिकोण से काफी बेहतर प्रदर्शन करता है।[4] बड़ी संख्या में प्रोसेसर के साथ, लॉक को फिर से जांचने से पहले रैंडम घातीय बैकऑफ़ देरी जोड़ना TTAS से भी बेहतर प्रदर्शन करता है।[4][5] कुछ मल्टी-कोर प्रोसेसर में एक शक्ति-सचेत स्पिन-लॉक निर्देश होता है जो प्रोसेसर को सोने के लिए रखता है, फिर लॉक मुक्त होने के बाद अगले चक्र पर इसे जगाता है। इस तरह के निर्देशों का उपयोग करने वाला एक स्पिन-लॉक अधिक कुशल है और बैक-ऑफ लूप के साथ या उसके बिना स्पिन लॉक की तुलना में कम ऊर्जा का उपयोग करता है।[6]
विकल्प
स्पिनलॉक का प्राथमिक नुकसान यह है कि लॉक प्राप्त करने के लिए प्रतीक्षा (ऑपरेटिंग सिस्टम) करते समय, यह उस समय को बर्बाद करता है जो उत्पादक रूप से कहीं और खर्च किया जा सकता है। इससे बचने के दो तरीके हैं:
- लॉक हासिल न करें। कई स्थितियों में डेटा संरचनाओं को डिजाइन करना संभव है जो गैर-अवरुद्ध सिंक्रनाइज़ेशन, उदा। प्रति-थ्रेड या प्रति-सीपीयू डेटा का उपयोग करके और व्यवधानों को अक्षम करके।
- प्रतीक्षा करते समय संदर्भ एक अलग थ्रेड पर स्विच करें। इसमें सामान्यतः वर्तमान थ्रेड को लॉक की प्रतीक्षा कर रहे थ्रेड्स की कतार में संलग्न करना सम्मिलित है, इसके बाद किसी अन्य थ्रेड पर स्विच करना जो कुछ उपयोगी कार्य करने के लिए तैयार है। इस योजना का लाभ यह भी है कि यह गारंटी देता है कि संसाधनों की भुखमरी तब तक नहीं होती है जब तक कि सभी धागे अंततः उन ताले को छोड़ देते हैं जो वे प्राप्त करते हैं और शेड्यूलिंग निर्णय किए जा सकते हैं कि किस धागे को पहले प्रगति करनी चाहिए। स्पिनलॉक जो कभी भी स्विचिंग की आवश्यकता नहीं होती है, रीयल-टाइम ऑपरेटिंग सिस्टम द्वारा प्रयोग करने योग्य होती है। रीयल-टाइम ऑपरेटिंग सिस्टम, कभी-कभी कच्चे स्पिनलॉक्स कहलाते हैं।[7]
अधिकांश ऑपरेटिंग सिस्टम (सोलारिस (ऑपरेटिंग सिस्टम), Mac OS X और फ्रीबीएसडी सहित) एडाप्टिव आपसी बहिष्कार नामक हाइब्रिड दृष्टिकोण का उपयोग करते हैं। वर्तमान में चल रहे थ्रेड द्वारा लॉक किए गए संसाधन तक पहुँचने का प्रयास करते समय स्पिनलॉक का उपयोग करने का विचार है, लेकिन यदि थ्रेड (कंप्यूटिंग) वर्तमान में नहीं चल रहा है तो सोने के लिए। (बाद वाला हमेशा सिंगल-प्रोसेसर सिस्टम पर होता है।)[8] OpenBSD ने स्पिनलॉक्स को टिकट ताला से बदलने का प्रयास किया, जिसने FIFO (कंप्यूटिंग और इलेक्ट्रॉनिक्स) को लागू किया। पहले-में-पहले-बाहर व्यवहार, चूंकि इसके परिणामस्वरूप कर्नेल में अधिक CPU उपयोग हुआ और फ़ायर्फ़ॉक्स जैसे बड़े अनुप्रयोग, बहुत धीमे हो गए।[9][10]
यह भी देखें
- तुल्यकालन (कंप्यूटर विज्ञान)
- व्यस्त स्पिन
- गतिरोध
- सीक्लॉक
- टिकट लॉक
संदर्भ
- ↑ Silberschatz, Abraham; Galvin, Peter B. (1994). ऑपरेटिंग सिस्टम अवधारणाओं (Fourth ed.). Addison-Wesley. pp. 176–179. ISBN 0-201-59292-4.
- ↑ "जीसीसी - x86 spinlock cmpxchg का उपयोग कर". Stack Overflow.
- ↑ "आर्म आर्किटेक्चर में नई तकनीकें" (PDF). Archived (PDF) from the original on 2019-04-02. Retrieved 2019-09-26.
- ↑ 4.0 4.1 Maurice Herlihy and Nir Shavit. "The Art of Multiprocessor Programming". "Spin Locks and Contention".
- ↑ "Boost.Fiber Tuning: Exponential back-off".
- ↑ John Goodacre and Andrew N. Sloss. "Parallelism and the ARM Instruction Set Architecture". p. 47.
- ↑ Jonathan Corbet (9 December 2009). "स्पिनलॉक नामकरण का समाधान किया गया". LWN.net. Archived from the original on 7 May 2013. Retrieved 14 May 2013.
- ↑ Silberschatz, Abraham; Galvin, Peter B. (1994). ऑपरेटिंग सिस्टम अवधारणाओं (Fourth ed.). Addison-Wesley. p. 198. ISBN 0-201-59292-4.
- ↑ Ted Unangst (2013-06-01). "src/lib/libpthread/thread.c - संस्करण 1.71". Archived from the original on 2021-02-27. Retrieved 2022-01-25.
- ↑ Ted Unangst (2016-05-06). "वेबकिट में लॉकिंग पर tedu टिप्पणी - Lobsters".
इस पेज में लापता आंतरिक लिंक की सूची
- ताला (कंप्यूटर विज्ञान)
- प्रतीक्षा में व्यस्त
- धागा (कंप्यूटर विज्ञान)
- संसाधन भुखमरी
- प्रतीक्षा करें (ऑपरेटिंग सिस्टम)
- रुकावट डालना
- गैर-अवरुद्ध तुल्यकालन
- FreeBSD
- फीफो (कंप्यूटिंग और इलेक्ट्रॉनिक्स)
- व्यस्त चक्कर
बाहरी संबंध
- pthread_spin_lock documentation from The Open Group Base Specifications Issue 6, IEEE Std 1003.1, 2004 Edition
- Variety of spinlock Implementations from Concurrency Kit
- Article "User-Level Spin Locks - Threads, Processes & IPC" by Gert Boddaert
- Article Spin Lock Example in Java
- Paper "The Performance of Spin Lock Alternatives for Shared-Memory Multiprocessors" by Thomas E. Anderson
- Paper "Algorithms for Scalable Synchronization on Shared-Memory Multiprocessors" by John M. Mellor-Crummey and Michael L. Scott. This paper received the 2006 Dijkstra Prize in Distributed Computing.
- Spin-Wait Lock by Jeffrey Richter
- Austria C++ SpinLock Class Reference
- Interlocked Variable Access(Windows)
- Operating Systems: Three Easy Pieces (Chapter: Locks)
