उद्घाटन रात

अटॉमिक

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

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 हमेशा अटॉमिक होता है।

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

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, जिनके बारे में नीचे बताया गया है।

एक्सचेंज और जोड़ना

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

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

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।

ध्यान दीजिए कि 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 इसे यह करके पकड़ लेता है: वह पुरानी पढ़ी गई वैल्यू से निकाली गई वैल्यू को स्टोर करने से इनकार कर देता है।

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

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

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

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

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

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

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 के बिना भी स्पिन लूप सही रहता है, बस फालतू है।

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