स्पिनलॉक
सॉफ्टवेयर इंजीनियरिंग में, स्पिनलॉक एक लॉक (कंप्यूटर साइंस) है जो एक थ्रेड (कंप्यूटर साइंस) का कारण बनता है जो बार-बार जांच कर रहा है कि लॉक उपलब्ध है या नहीं। चूँकि थ्रेड सक्रिय रहता है लेकिन कोई उपयोगी कार्य नहीं कर रहा है, ऐसे लॉक का उपयोग एक प्रकार का व्यस्त प्रतीक्षा है। एक बार अधिग्रहित होने के बाद, स्पिनलॉक सामान्यतः तब तक आयोजित किए जाते हैं जब तक कि वे स्पष्ट रूप से जारी नहीं हो जाते हैं, चूंकि कुछ कार्यान्वयनों में वे स्वचालित रूप से जारी हो सकते हैं यदि थ्रेड पर प्रतीक्षा की जा रही है (जिस पर ताला लगा है) ब्लॉक हो जाता है या सो जाता है।
क्योंकि वे ऑपरेटिंग सिस्टम निर्धारण (कंप्यूटिंग) या संदर्भ स्विचिंग से ओवरहेड से बचते हैं, यदि थ्रेड (कंप्यूटर साइंस) केवल छोटी अवधि के लिए अवरुद्ध होने की संभावना है तो स्पिनलॉक्स कुशल होते हैं। इस कारण से, ऑपरेटिंग सिस्टम कर्नेल|ऑपरेटिंग-सिस्टम कर्नेल अधिकांशतः स्पिनलॉक का उपयोग करते हैं। चूंकि, यदि लंबे समय तक रखा जाए तो स्पिनलॉक व्यर्थ हो जाते हैं, क्योंकि वे अन्य थ्रेड्स को चलने से रोक सकते हैं और पुनर्निर्धारण की आवश्यकता होती है। एक थ्रेड जितना अधिक समय तक लॉक रखता है, उतना ही अधिक जोखिम होता है कि लॉक को होल्ड करते समय ओएस शेड्यूलर द्वारा थ्रेड को बाधित किया जाएगा। यदि ऐसा होता है, तो अन्य थ्रेड घूमते रह जाएंगे (बार-बार लॉक प्राप्त करने का प्रयास कर रहे हैं), जबकि लॉक को पकड़ने वाला थ्रेड इसे जारी करने की दिशा में प्रगति नहीं कर रहा है। परिणाम एक अनिश्चितकालीन स्थगन है जब तक कि लॉक को पकड़ने वाला धागा खत्म नहीं हो सकता और इसे जारी नहीं कर सकता। यह सिंगल-प्रोसेसर सिस्टम पर विशेष रूप से सच है, जहां एक ही प्राथमिकता के प्रत्येक वेटिंग थ्रेड को अपनी क्वांटम (आवंटित समय जहां एक थ्रेड चल सकता है) को बर्बाद करने की संभावना है, जब तक कि लॉक को रखने वाले थ्रेड को खत्म नहीं किया जाता है।
स्पिनलॉक्स को सही ढंग से कार्यान्वित करना चुनौतीपूर्ण है क्योंकि प्रोग्रामर को लॉक तक एक साथ पहुंच की संभावना को ध्यान में रखना चाहिए, जो दौड़ की स्थिति पैदा कर सकता है। सामान्यतः, ऐसा कार्यान्वयन केवल विशेष सभा की भाषा | असेंबली-लैंग्वेज निर्देशों के साथ ही संभव है, जैसे परमाणु संचालन परीक्षण और सेट संचालन और प्रोग्रामिंग भाषाओं में आसानी से लागू नहीं किया जा सकता है जो वास्तव में परमाणु संचालन का समर्थन नहीं करते हैं।[1] इस तरह के संचालन के बिना आर्किटेक्चर पर, या यदि उच्च स्तरीय भाषा कार्यान्वयन की आवश्यकता होती है, तो गैर-परमाणु लॉकिंग एल्गोरिदम का उपयोग किया जा सकता है, उदाहरण के लिए पीटरसन का एल्गोरिदम। चूंकि, इस तरह के कार्यान्वयन के लिए स्पिनलॉक की तुलना में अधिक स्मृति की आवश्यकता हो सकती है, अनलॉक करने के बाद प्रगति की अनुमति देने के लिए धीमी हो, और उच्च-स्तरीय भाषा में कार्यान्वयन योग्य न हो, यदि आउट-ऑफ-ऑर्डर निष्पादन की अनुमति है।
उदाहरण कार्यान्वयन
स्पिनलॉक को लागू करने के लिए निम्न उदाहरण x86 असेंबली भाषा का उपयोग करता है। यह किसी भी Intel 80386 संगत प्रोसेसर पर काम करेगा।
; Intel syntax
locked: ; The lock variable. 1 = locked, 0 = unlocked.
dd 0
spin_lock:
mov eax, 1 ; Set the EAX register to 1.
xchg eax, [locked] ; Atomically swap the EAX register with
; the lock variable.
; This will always store 1 to the lock, leaving
; the previous value in the EAX register.
test eax, eax ; Test EAX with itself. Among other things, this will
; set the processor's Zero Flag if EAX is 0.
; If EAX is 0, then the lock was unlocked and
; we just locked it.
; Otherwise, EAX is 1 and we didn't acquire the lock.
jnz spin_lock ; Jump back to the MOV instruction if the Zero Flag is
; not set; the lock was previously locked, and so
; we need to spin until it becomes unlocked.
ret ; The lock has been acquired, return to the calling
; function.
spin_unlock:
xor eax, eax ; Set the EAX register to 0.
xchg eax, [locked] ; Atomically swap the EAX register with
; the lock variable.
ret ; The lock has been released.
महत्वपूर्ण अनुकूलन
उपरोक्त सरल कार्यान्वयन x86 आर्किटेक्चर का उपयोग कर सभी सेंट्रल प्रोसेसिंग यूनिट पर काम करता है। चूंकि, कई प्रदर्शन अनुकूलन संभव हैं:
x86 आर्किटेक्चर के बाद के कार्यान्वयन पर, स्पिन अनलॉक धीरे-धीरे लॉक किए गए एक्ससीएचजी के अतिरिक्त अनलॉक किए गए एमओवी का सुरक्षित रूप से उपयोग कर सकता है। यह सूक्ष्म मेमोरी ऑर्डरिंग नियमों के कारण है जो इसका समर्थन करते हैं,? एमओवी पूर्ण मेमोरी बैरियर नहीं है। चूंकि, कुछ प्रोसेसर (कुछ सिरिक्स प्रोसेसर,? पेंटियम प्रो के कुछ संशोधन (बग के कारण), और पहले के पेंटियम (ब्रांड) और i486 सममित मल्टीप्रोसेसिंग सिस्टम) गलत काम करेंगे और लॉक द्वारा संरक्षित डेटा दूषित हो सकता है। अधिकांश गैर-x86 आर्किटेक्चर पर, स्पष्ट स्मृति बाधा या परमाणु निर्देश (उदाहरण के अनुसार) का उपयोग किया जाना चाहिए। कुछ प्रणालियों पर, जैसे IA-64, विशेष अनलॉक निर्देश हैं जो आवश्यक मेमोरी क्रम प्रदान करते हैं।
इंटर-सीपीयू बस (कंप्यूटिंग) को कम करने के लिए, लॉक प्राप्त करने का प्रयास करने वाले कोड को कुछ भी लिखने के प्रयास किए बिना पढ़ने को लूप करना चाहिए जब तक कि यह एक परिवर्तित मान नहीं पढ़ता। MESI कैशिंग प्रोटोकॉल के कारण, यह कैश लाइन को लॉक के लिए साझा करने का कारण बनता है; तब उल्लेखनीय रूप से कोई बस यातायात नहीं होता है जबकि सीपीयू लॉक की प्रतीक्षा करता है। यह ऑप्टिमाइज़ेशन उन सभी सेंट्रल प्रोसेसिंग यूनिट आर्किटेक्चर पर प्रभावी है जिनके पास प्रति सेंट्रल प्रोसेसिंग यूनिट कैश है, क्योंकि एमईएसआई इतना व्यापक है। हाइपर-थ्रेडिंग सीपीयू पर, के साथ रुकना repnop कोर को संकेत देकर अतिरिक्त प्रदर्शन देता है कि यह दूसरे थ्रेड पर काम कर सकता है जबकि लॉक स्पिन प्रतीक्षा कर रहा है।[2] लेन-देन तुल्यकालन एक्सटेंशन और अन्य हार्डवेयर लेन-देन स्मृति इंस्ट्रक्शन सेट अधिकांश स्थितियों में लॉक को बदलने के लिए काम करते हैं। चूंकि लॉकबैक के रूप में अभी भी ताले की आवश्यकता है, लेकिन उनके पास प्रोसेसर को परमाणु संचालन के पूरे ब्लॉक को संभालने के द्वारा प्रदर्शन में काफी सुधार करने की क्षमता है। यह सुविधा कुछ म्यूटेक्स कार्यान्वयनों में अंतर्निहित है, उदाहरण के लिए glibc में। X86 में हार्डवेयर लॉक एलिसन (उच्च परत इकाई) ट्रांसमिसिबल स्पॉन्गॉर्मॉर्म एन्सेफैलोपैथी का एक कमजोर लेकिन पीछे की ओर अनुरूप संस्करण है, और हम इसे बिना किसी अनुकूलता खोए लॉकिंग के लिए यहां उपयोग कर सकते हैं। इस विशेष मामले में, प्रोसेसर तब तक लॉक नहीं करना चुन सकता है जब तक कि दो धागे वास्तव में एक दूसरे के साथ संघर्ष न करें।[3]
परीक्षण का एक सरल संस्करण उपयोग कर सकता है cmpxchg x86 पर निर्देश, या __sync_bool_compare_and_swap कई यूनिक्स कंपाइलर्स में निर्मित।
लागू किए गए ऑप्टिमाइज़ेशन के साथ, एक उदाहरण ऐसा दिखाई देगा:
; In C: while(!__sync_bool_compare_and_swap(&locked, 0, 1)) while(locked) __builtin_ia32_pause();
spin_lock:
mov ecx, 1 ; Set the ECX register to 1.
retry:
xor eax, eax ; Zero out EAX, because cmpxchg compares against EAX.
XACQUIRE lock cmpxchg [locked], ecx
; atomically decide: if locked is zero, write ECX to it.
; XACQUIRE hints to the processor that we are acquiring a lock.
je out ; If we locked it (old value equal to EAX: 0), return.
pause:
mov eax, [locked] ; Read locked into EAX.
test eax, eax ; Perform the zero-test as before.
jz retry ; If it's zero, we can retry.
rep nop ; Tell the CPU that we are waiting in a spinloop, so it can
; work on the other thread now. Also written as the "pause".
jmp pause ; Keep check-pausing.
out:
ret ; All done.
spin_unlock:
XRELEASE mov [locked], 0 ; Assuming the memory ordering rules apply, release the
; lock variable with a "lock release" hint.
ret ; The lock has been released.
संशोधित अनन्य साझा और अमान्य प्रोटोकॉल का उपयोग करने वाले किसी भी बहु-प्रोसेसर सिस्टम पर,
ऐसा टेस्ट-एंड-टेस्ट-एंड-सेट लॉक (टीटीएएस) सरल टेस्ट-एंड-सेट लॉक (टीएएस) दृष्टिकोण से काफी बेहतर प्रदर्शन करता है।[4]
बड़ी संख्या में प्रोसेसर के साथ,
लॉक को फिर से जांचने से पहले रैंडम घातीय बैकऑफ़ देरी जोड़ना विश्वसनीय टोकन प्रमाणीकरण सेवा से भी बेहतर प्रदर्शन करता है।[4][5]
कुछ मल्टी-कोर प्रोसेसर में एक शक्ति-सचेत स्पिन-लॉक निर्देश होता है जो प्रोसेसर को सोने के लिए रखता है, फिर लॉक मुक्त होने के बाद अगले चक्र पर इसे जगाता है। इस तरह के निर्देशों का उपयोग करने वाला एक स्पिन-लॉक अधिक कुशल है और बैक-ऑफ लूप के साथ या उसके बिना स्पिन लॉक की तुलना में कम ऊर्जा का उपयोग करता है।[6]
विकल्प
स्पिनलॉक का प्राथमिक हानि यह है कि लॉक प्राप्त करने के लिए प्रतीक्षा (ऑपरेटिंग सिस्टम) करते समय, यह उस समय को तबाह करता है जो उत्पादक रूप से कहीं और खर्च किया जा सकता है। इससे बचने के दो तरीके हैं:
- लॉक हासिल न करें। कई स्थितियों में डेटा संरचनाओं को डिजाइन करना संभव है जो गैर-अवरुद्ध सिंक्रनाइज़ेशन, उदा। प्रति-थ्रेड या प्रति-सेंट्रल प्रोसेसिंग यूनिट डेटा का उपयोग करके और व्यवधानों को अक्षम करके।
- प्रतीक्षा करते समय संदर्भ एक अलग थ्रेड पर स्विच करें। इसमें सामान्यतः वर्तमान थ्रेड को लॉक की प्रतीक्षा कर रहे थ्रेड्स की कतार में संलग्न करना सम्मिलित है, इसके बाद किसी अन्य थ्रेड पर स्विच करना जो कुछ उपयोगी कार्य करने के लिए तैयार है। इस योजना का लाभ यह भी है कि यह गारंटी देता है कि संसाधनों की भुखमरी तब तक नहीं होती है जब तक कि सभी धागे अंततः उन ताले को छोड़ देते हैं जो वे प्राप्त करते हैं और शेड्यूलिंग निर्णय किए जा सकते हैं कि किस धागे को पहले प्रगति करनी चाहिए। स्पिनलॉक जो कभी भी स्विचिंग की आवश्यकता नहीं होती है, रीयल-टाइम ऑपरेटिंग सिस्टम द्वारा प्रयोग करने योग्य होती है। रीयल-टाइम ऑपरेटिंग सिस्टम, कभी-कभी कच्चे स्पिनलॉक्स कहलाते हैं।[7]
अधिकांश ऑपरेटिंग सिस्टम (सोलारिस (ऑपरेटिंग सिस्टम), Mac OS X और फ्रीबीएसडी सहित) एडाप्टिव आपसी बहिष्कार नामक हाइब्रिड दृष्टिकोण का उपयोग करते हैं। वर्तमान में चल रहे थ्रेड द्वारा लॉक किए गए संसाधन तक पहुँचने का प्रयास करते समय स्पिनलॉक का उपयोग करने का विचार है, लेकिन यदि थ्रेड (कंप्यूटिंग) वर्तमान में नहीं चल रहा है तो सोने के लिए। (बाद वाला हमेशा सिंगल-प्रोसेसर सिस्टम पर होता है।)[8]
OpenBSD ने स्पिनलॉक्स को टिकट ताला से बदलने का प्रयास किया, जिसने फीफो (कंप्यूटिंग और इलेक्ट्रॉनिक्स) को लागू किया। पहले-में-पहले-बाहर व्यवहार, चूंकि इसके परिणामस्वरूप कर्नेल में अधिक सेंट्रल प्रोसेसिंग यूनिटउपयोग हुआ और फ़ायर्फ़ॉक्स जैसे बड़े अनुप्रयोग, बहुत धीमे हो गए।[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".
बाहरी संबंध
- 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)
