एटॉमिक्स में

एटॉमिक्स के बारे में

एक अकेला इंस्ट्रक्शन देखने में एक अविभाज्य काम लग सकता है, जबकि वह असल में ऐसा है ही नहीं। मेमोरी में रखी किसी वैल्यू में पाँच जोड़ने को ही लीजिए:

add qword [rel counter], 5

अंदर ही अंदर, प्रोसेसर के पास सीधे मेमोरी में जोड़ने का कोई तरीका नहीं होता। इसलिए वह इस एक इंस्ट्रक्शन को तीन छोटे चरणों में तोड़ देता है, जिन्हें माइक्रो-ऑपरेशन कहते हैं:

1. मेमोरी से मौजूदा वैल्यू पढ़ना;
2. उस वैल्यू को रजिस्टर में बदलना, यानी उसमें पाँच जोड़ना;
3. नतीजे को वापस लिखना।

mov rax, qword [rel counter] ; 1. load the current value
add rax, 5                   ; 2. add five
mov qword [rel counter], rax ; 3. store the result back

यह एक आम पैटर्न है जिसे रीड-मॉडिफ़ाई-राइट (RMW) कहते हैं।

ध्यान दीजिए कि पढ़ना (या लोड करना) और लिखना (या स्टोर करना) दो अलग-अलग घटनाएँ हैं, इसलिए इनके बीच समय का एक अंतराल रहता है। हमें यह आम तौर पर दिखता नहीं, क्योंकि सिंगल कोर पर हर इंस्ट्रक्शन की गारंटी होती है कि अगला इंस्ट्रक्शन चलने से पहले वह अपना असर पूरा कर देगा। इसलिए वह अंतराल अदृश्य रहता है और add एक ही इकाई की तरह व्यवहार करता है।

लेकिन आज के CPU शायद ही कभी सिंगल-कोर होते हैं, और ऐप्लिकेशन अक्सर एक साथ कई कोर पर चलते हैं, बिना किसी तय क्रम के। जब कई कोर ठीक एक ही पल में चल रहे हों, तो कोई दूसरा कोर इस अंतराल के भीतर counter को पढ़ या लिख सकता है, इस कोर के लोड के बाद और उसके स्टोर से पहले। दो थ्रेड एक ही पुरानी वैल्यू लोड करते हैं, दोनों पाँच जोड़ते हैं, और दोनों अपना नतीजा स्टोर करते हैं। जोड़ तो दो बार हुए, पर वैल्यू सिर्फ पाँच बढ़ी। एक अपडेट चुपचाप खो गया।

इसे डेटा रेस कहते हैं, और मल्टी-थ्रेडेड कोड में यह एक आम समस्या है।

हर वैल्यू इस तरह खुली नहीं होती। हर थ्रेड के अपने रजिस्टर और अपना स्टैक होता है, इसलिए रजिस्टर में रखी वैल्यू, या थ्रेड के स्टैक पर रखा कोई लोकल वेरिएबल, सिर्फ उसी थ्रेड का होता है और उसमें रेस नहीं हो सकती। सुरक्षा सिर्फ उसी मेमोरी को चाहिए जिसे थ्रेड आपस में साझा करते हैं, जैसे ऊपर का counter।

x86-64 में इस समस्या को हल करने के लिए कुछ इंस्ट्रक्शन हैं, जो एक इंस्ट्रक्शन को अविभाज्य बना देते हैं। ऐसा इंस्ट्रक्शन एक ही इकाई की तरह व्यवहार करता है, सिर्फ उस कोर के लिए नहीं जो उसे चला रहा है, बल्कि हर दूसरे कोर के लिए भी। जो काम एक साथ जुड़ा रहता है, जिसे कोई दूसरा कोर बीच से नहीं तोड़ सकता, उसे एटॉमिक कहते हैं।

एटॉमिक एक्सचेंज

xchg इंस्ट्रक्शन दो ऑपरेंड की जगहें बदल देता है। गंतव्य ऑपरेंड उस पुरानी वैल्यू के बराबर हो जाता है जो स्रोत ऑपरेंड में थी, और स्रोत ऑपरेंड उस पुरानी वैल्यू के बराबर हो जाता है जो गंतव्य ऑपरेंड में थी। सोचने में इसे दो mov इंस्ट्रक्शन मान सकते हैं जो एक ही साथ हो रहे हों।

आम तौर पर इसका इस्तेमाल दो रजिस्टर ऑपरेंड के साथ, या एक मेमोरी ऑपरेंड और एक रजिस्टर ऑपरेंड के साथ किया जा सकता है:

mov  eax, 1
xchg dword [rdi], eax ; [rdi] = 1, eax = the old value of [rdi]
mov ecx, 2
mov edx, 3
xchg edx, ecx         ; edx = 2, ecx = 3

जब इसका इस्तेमाल किसी मेमोरी ऑपरेंड के साथ होता है, तो xchg हमेशा एटॉमिक होता है। प्रोसेसर उतनी देर के लिए उस जगह पर लॉक लगा देता है। यही तरीका lock प्रीफिक्स दूसरे इंस्ट्रक्शनों के लिए इस्तेमाल करता है, जिसकी चर्चा आगे है।

लॉक प्रीफिक्स

x86-64 में किसी इंस्ट्रक्शन को एटॉमिक बनाने का सबसे आम तरीका है उसके आगे lock प्रीफिक्स लगाना। यह पढ़ने, बदलने और लिखने को एक अविभाज्य चरण में जोड़ देता है। इसका मतलब है कि पूरी प्रक्रिया के दौरान वह कोर उस मेमोरी पर अकेले का अधिकार रखता है, इसलिए बीच में कोई दूसरा कोर उस जगह को पढ़ या लिख नहीं सकता।

lock add qword [rel counter], 5 ; the read, the modify, and the write are one step

lock सिर्फ तभी काम करता है जब गंतव्य मेमोरी हो, और सिर्फ उन्हीं इंस्ट्रक्शनों पर जो उस मेमोरी को पढ़ते-बदलते-लिखते हैं:

1. अंकगणितीय ऑपरेशन, जैसे add, sub, inc, dec, neg;
2. बिटवाइज़ ऑपरेशन, जैसे and, or, xor, not;
3. बिट ऑपरेशन bts, btr, btc;
4. कुछ और खास इंस्ट्रक्शन, जैसे xadd और cmpxchg, जिनकी चर्चा आगे है।

किसी और इंस्ट्रक्शन पर, जैसे सादे mov पर, यह प्रीफिक्स मान्य नहीं होता और प्रोसेसर अमान्य-ऑपकोड फॉल्ट उठा देता है। अकेले लोड या अकेले स्टोर को किसी प्रीफिक्स की ज़रूरत नहीं होती: प्राकृतिक रूप से अलाइन्ड एक्सेस अपने आप ही एटॉमिक होता है।

एटॉमिक बिट ऑपरेशन

जिन इंस्ट्रक्शनों पर लॉक लगाया जा सकता है, उनमें बिट टेस्ट इस दस्तावेज़ के अंत में आने वाले स्पिनलॉक के साथ अच्छी तरह जुड़ जाते हैं। bts, btr और btc में से हर एक किसी चुने हुए बिट को कैरी फ्लैग में कॉपी करता है और फिर उसे सेट, क्लियर या पलट देता है। lock प्रीफिक्स के साथ यह एक-बिट का रीड-मॉडिफ़ाई-राइट बन जाता है: बिट एटॉमिक रूप से बदलता है, और CF बताता है कि पहले वह क्या था।

    lock bts qword [rdi], 0 ; set bit 0; CF = the bit's previous value
    setc al                 ; al = 1 when the bit was already set

अगर सेट करते समय पता चले कि बिट पहले से सेट है, तो मतलब किसी दूसरे थ्रेड ने उसे पहले पा लिया। यह उसी फ्लैग पर दावा करने का एक-बिट वाला रूप है, जो xchg पूरे वर्ड के लिए करता है।

एक्सचेंज और ऐड

सादा lock add मेमोरी को अपडेट करता है, पर पुरानी वैल्यू फेंक देता है। अक्सर पुरानी वैल्यू ही चाहिए होती है, जैसे हर थ्रेड को एक अलग टिकट नंबर देना हो।

xadd इंस्ट्रक्शन (x यानी एक्सचेंज) जोड़ते समय पिछली वैल्यू लौटा देता है। यह जोड़ को गंतव्य में लिखता है और गंतव्य की मूल वैल्यू को स्रोत रजिस्टर में छोड़ देता है।

mov  rax, 1
lock xadd qword [rdi], rax ; [rdi] = [rdi] + rax = [rdi] + 1
                           ; rax = the old value of [rdi]

lock प्रीफिक्स के साथ यह एटॉमिक फ़ेच-एंड-ऐड बन जाता है। एक ही काउंटर पर कई थ्रेड इसे चलाएँ, तो हर कॉल एक अलग पुरानी वैल्यू लौटाती है।

lock add की तरह, काउंटर अंत में ठीक कॉलों की उतनी ही संख्या तक पहुँचता है। लेकिन lock add से अलग, यहाँ बीच की हर वैल्यू भी लौटाई जाती है, हर कॉल करने वाले को एक।

स्रोत कोई भी जनरल-परपस रजिस्टर हो सकता है, और ऑपरेंड की चौड़ाई एक बाइट से लेकर एक क्वाडवर्ड तक हो सकती है। कोई ऋणात्मक वैल्यू जोड़ने से वही इंस्ट्रक्शन फ़ेच-एंड-सब्ट्रैक्ट बन जाता है।

कम्पेयर और एक्सचेंज

xadd जोड़ता है और xchg के ऊपर लिख देता है, पर इनमें से कोई भी नई वैल्यू को मौजूदा वैल्यू पर निर्भर नहीं बना सकता, और यह भी तय नहीं कर सकता कि वह तभी लगे जब नीचे कुछ बदला न हो। ऐसा शर्त के साथ होने वाला अपडेट cmpxchg यानी कम्पेयर-एंड-एक्सचेंज देता है, और यह इन सबमें सबसे व्यापक प्रिमिटिव है।

cmpxchg dest, src rax को अंतर्निहित एक्युमुलेटर की तरह इस्तेमाल करता है और उसकी तुलना dest से करता है:

• अगर dest == rax, तो dest = src और ZF = 1।
• अगर dest != rax, तो rax = dest और ZF = 0।

एक्युमुलेटर ऑपरेंड के आकार के साथ बदलता है: एक बाइट के लिए al, और बड़े रूपों के लिए ax, eax और rax।

ध्यान दीजिए कि dest तभी अपडेट होता है जब वह उस अपेक्षित वैल्यू के बराबर हो जो पहले rax में लोड की गई थी। यह बराबरी पक्का करती है कि dest में अब भी वही वैल्यू है जिससे नई वैल्यू निकाली गई थी, इसलिए पुरानी पढ़ाई पर टिका कोई अपडेट कभी लागू नहीं होता। यही cmpxchg को एटॉमिक अपडेट की बुनियादी इकाई बनाता है, जिसे कम्पेयर-एंड-स्वैप (CAS) भी कहते हैं:

    mov rax, qword [rdi]          ; rax = the value we expect to find
.retry:
    lea rcx, [rax + 10]           ; rcx = the new value we want to install
    lock cmpxchg qword [rdi], rcx ; if [rdi] still equals rax, store rcx and set ZF
                                  ; otherwise reload rax with the current value, clear ZF
    jnz  .retry                   ; ZF is cleared, so another thread won the race. Recompute and retry

यह रिट्राई लूप लॉक-फ्री अपडेट का दिल है। पढ़ने और कम्पेयर-एंड-एक्सचेंज के बीच का अंतराल ठीक वही समय है जब कोई दूसरा थ्रेड बीच में आ सकता है, और cmpxchg पुरानी पढ़ाई से निकली वैल्यू को स्टोर करने से मना करके उस पर पकड़ बना लेता है।

एक बारीक बात जानने लायक है। cmpxchg यह जाँचता है कि वैल्यू वही है जो पढ़ी गई थी, यह नहीं कि उस जगह को छुआ ही नहीं गया। अगर अंतराल के भीतर कोई दूसरा थ्रेड वैल्यू को A से B और फिर A पर ले आए, तो एक्सचेंज फिर भी सफल हो जाता है, भले ही अंदर सब कुछ बदल चुका हो।

किसी सादे काउंटर के लिए यह नुकसानदेह नहीं है, क्योंकि बराबर गिनती उतनी ही अच्छी गिनती होती है। लेकिन किसी लॉक-फ्री ऐरे के सिरे पर रखे मेमोरी एड्रेस के लिए यह ठीक नहीं है, क्योंकि वही एड्रेस अब कहीं और ले जा सकता है। इसे ABA समस्या कहते हैं।

इस समस्या का आम हल यह है कि वैल्यू के साथ कोई स्टैम्प जोड़ दिया जाए, जैसे कोई काउंटर जो सिर्फ बढ़ता ही रहता है। चूँकि स्टैम्प सिर्फ आगे बढ़ता है, मिलता हुआ स्टैम्प साबित करता है कि बीच में उस जगह को छुआ नहीं गया, सिर्फ यह नहीं कि वह वैसी ही दिखती है।

लेकिन मल्टी-थ्रेडेड वातावरण में यह काम तभी करेगा जब मेमोरी एड्रेस और उसका स्टैम्प दोनों एक साथ अपडेट हों। चूँकि x86-64 में मेमोरी एड्रेस एक पूरा क्वाडवर्ड होता है, सिर्फ cmpxchg से उसे और साथ में किसी दूसरी वैल्यू को एक ही बार में अपडेट नहीं किया जा सकता।

एक डबल-विड्थ इंस्ट्रक्शन भी है, जिसे cmpxchg16b कहते हैं। यह अर्थ में cmpxchg जैसा ही है, पर एक साथ 16 बाइट पर काम करता है और उस स्थिति में इस्तेमाल किया जा सकता है। इसका कोई स्रोत ऑपरेंड नहीं होता; इसके बजाय यह rcx:rbx को बदली वैल्यू की तरह इस्तेमाल करता है। इसका एकमात्र ऑपरेंड 16 बाइट पर अलाइन्ड मेमोरी लोकेशन होती है। यह इंस्ट्रक्शन एक्युमुलेटर की तरह सिर्फ rax के बजाय rdx:rax इस्तेमाल करता है।

मेमोरी ऑर्डरिंग

अब तक का हर ऑपरेशन सिर्फ एक जगह को छूता रहा है। जब थ्रेड एक से ज़्यादा जगहों के ज़रिए आपस में तालमेल बिठाते हैं, तो एक नया सवाल उठता है: एक थ्रेड की लिखाई दूसरे को किस क्रम में दिखती है। इस सवाल का जवाब प्रोसेसर की मेमोरी ऑर्डरिंग देती है।

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

x86-64 सादे लोड और स्टोर के बीच मजबूत मेमोरी ऑर्डरिंग बनाए रखता है, इसलिए हर कोर पर:

1. किसी लोड को उसके बाद वाले लोड के बाद नहीं खिसकाया जाता;
2. किसी स्टोर को उसके बाद वाले स्टोर के बाद नहीं खिसकाया जाता;
3. किसी लोड को उसके बाद वाले स्टोर के बाद नहीं खिसकाया जाता।

सिर्फ एक ही तरह की अदला-बदली संभव है: कोई स्टोर किसी अलग एड्रेस के बाद वाले लोड के बाद पूरा होता दिखे।

lock प्रीफिक्स वाला इंस्ट्रक्शन, या मेमोरी ऑपरेंड वाला xchg, एक पूरा बैरियर होता है: उसके आर-पार कुछ भी किसी भी दिशा में खिसकता नहीं दिखता। इसीलिए ज़्यादातर स्थितियों में पूरी ऑर्डरिंग पक्की करने के लिए यही काफी होते हैं।

बची हुई इस एक अदला-बदली के पीछे का तंत्र स्टोर बफर है। आगे बढ़ते रहने के लिए कोर हर स्टोर को उस बफर में रख देता है और आगे वाले इंस्ट्रक्शनों को चलने देता है, तब तक जब तक स्टोर उस मेमोरी तक नहीं पहुँचता जिसे दूसरे कोर देख सकते हैं। इसलिए किसी लिखाई के बाद किसी दूसरी जगह की पढ़ाई क्रम से बाहर दिख सकती है: लिखाई अब भी बफर में पड़ी रह सकती है, जबकि बाद वाली पढ़ाई आगे बढ़ चुकी होती है। इस मॉडल को, जिसमें उस लिखो-फिर-पढ़ो की खाई के अलावा सब क्रम में रहता है, टोटल स्टोर ऑर्डर कहते हैं।

यही एक खाई लिखो-फिर-जाँचो वाले हैंडशेक को तोड़ने के लिए काफी है। अगर दो थ्रेड अपना-अपना फ्लैग लिखकर दूसरे का फ्लैग पढ़ें, तो दोनों पढ़ाइयाँ बिना सेट मिल सकती हैं, क्योंकि तब तक कोई भी स्टोर अपने स्टोर बफर से बाहर नहीं निकला। mfence इंस्ट्रक्शन स्टोर बफर को खाली करके यह खाई भर देता है: उससे पहले की हर लिखाई, उसके बाद की किसी भी पढ़ाई से पहले दिखने लगती है।

    mov dword [rdi], 1    ; publish: this thread is ready
    mfence                ; the store above must land before the load below
    mov eax, dword [rsi]  ; observe whether the other thread is ready

दो और छोटे बैरियर भी हैं:

• sfence लिखाइयों का आपस में क्रम तय करता है और मुख्य रूप से स्ट्रीमिंग, नॉन-टेम्पोरल स्टोर के साथ मायने रखता है;
• lfence पढ़ाइयों का क्रम तय करता है।

ऊपर बताए गए आम एटॉमिक पैटर्न के लिए lock प्रीफिक्स वाले इंस्ट्रक्शन पहले से पूरी ऑर्डरिंग लिए होते हैं, इसलिए कोई साफ़ बैरियर सिर्फ ऐसे हैंडशेक के लिए चाहिए जो ऊपर की तरह सादे स्टोर और लोड से बना हो।

इन गारंटियों के नाम x86 से आगे तक जाते हैं। किसी ऑपरेशन में एक्वायर ऑर्डरिंग तब होती है जब उसके बाद का कोई एक्सेस उससे पहले खिसकता न दिखे, और रिलीज़ ऑर्डरिंग तब जब उससे पहले का कोई एक्सेस उसके बाद खिसकता न दिखे। x86 पर हर लोड एक्वायर है, हर स्टोर रिलीज़ है, और lock प्रीफिक्स वाला इंस्ट्रक्शन या मेमोरी वाला xchg दोनों एक साथ हैं।

स्पिनिंग और pause

जो इंस्ट्रक्शन फ्लैग सेट करते समय उसकी पिछली स्थिति भी लौटा देते हैं, उन्हें टेस्ट-एंड-सेट कहते हैं। इन्हें स्पिनलॉक की बुनियाद बनाया जा सकता है, जो यह पक्का करता है कि कोड के किसी हिस्से पर एक कोर का अकेला अधिकार रहे।

बाइनरी फ्लैग के साथ xchg इंस्ट्रक्शन इस्तेमाल करने वाला पूरा एल्गोरिदम यह है:

1. फ्लैग 0 से शुरू होता है।
2. लॉक लेने के लिए एक कोर फ्लैग की वैल्यू को 1 से बदल देता है।
3. अगर लौटी वैल्यू 1 है, तो इसका मतलब लॉक किसी दूसरे कोर के पास पहले से है। तब यह कोर रुकता है और दोबारा लॉक लेने की कोशिश करता है।
4. अगर लौटी वैल्यू 0 है, तो इसका मतलब लॉक खाली था। xchg ने अब उसे 1 कर दिया है, और दूसरे कोर तब तक रुकेंगे जब तक यह कोर उसे छोड़ न दे।
5. जब यह कोर अपना काम खत्म कर लेता है, तो फ्लैग को 0 कर देना लॉक छोड़ देता है।

acquire:
    mov  eax, 1
    xchg dword [rdi], eax ; try to take the lock; eax = its old value
    test eax, eax
    jnz  .held            ; old value was 1: someone else holds it
    ret                   ; old value was 0: the lock is ours
.held:
    pause                 ; wait before trying again
    jmp  acquire

इंतज़ार वाले लूप में pause इंस्ट्रक्शन इस बात को नहीं बदलता कि कोड क्या गणना करता है। यह प्रोसेसर को संकेत देता है कि यह एक स्पिन-वेट है। तब CPU इंतज़ार कर रहे थ्रेड की बिजली की खपत घटा सकता है और उसी कोर पर चल रहे साथी थ्रेड को मौका दे सकता है। pause के बिना भी स्पिन लूप सही रहता है, बस फिजूल होता है।

ध्यान दीजिए कि टेस्ट-एंड-सेट में xchg जैसा इंस्ट्रक्शन फ्लैग को हर बार सेट कर देता है, भले ही वह पहले से सेट हो। इसका मतलब है कि हर स्पिन में उसे उस मेमोरी पर अकेला अधिकार मिल जाता है, तब भी जब लॉक के अब भी किसी और के पास होने की संभावना हो।

इस एल्गोरिदम का एक रूप भी है, जिसे टेस्ट-एंड-टेस्ट-एंड-सेट कहते हैं। यह पहले फ्लैग को जाँचता (पढ़ता) है कि वह पहले से सेट है या नहीं। फिर टेस्ट-एंड-सेट (यहाँ xchg) की कोशिश तभी करता है जब लॉक खाली दिखे:

acquire:
    mov  eax, 1
    xchg dword [rdi], eax ; try to take the lock
    test eax, eax
    jz   .taken           ; got it
.held:
    pause                 ; wait before trying again
    cmp  dword [rdi], 0   ; watch the lock without writing to it
    jne  .held            ; still held
    jmp  acquire          ; looks free: retry
.taken:
    ret

जब थ्रेड अपना काम पूरा कर लेता है, तो वह mov से सादा 0 स्टोर करके लॉक छोड़ सकता है। mov से ज़्यादा कुछ नहीं चाहिए, क्योंकि x86-64 पर लोड और स्टोर को उनके बाद वाले स्टोर के बाद नहीं खिसकाया जाता। जो स्टोर अपने से पहले के एक्सेस से कभी आगे नहीं निकलता, उसमें रिलीज़ ऑर्डरिंग कही जाती है, और x86 पर हर सादा स्टोर यह लिए होता है।