5.2.26 · D1std - atomic — lock-free operations
Jab do workers memory ka ek hi box ek saath change karte hain, unke steps aapas mein ulajh jaate hain aur ek change chupke se gayab ho jaati hai. std::atomic ek promise hai ki us box par change ek uninterruptible blink mein hota hai, aur jab ek worker kehta hai "done," doosra worker jo "done" sunta hai woh us se pehle pack ki gayi har cheez bhi dekhta hai.
Is page par assume kiya gaya hai ki aap kuch nahi jaante. Parent note (topic) padhne se pehle, aapko kuch ideas ki zaroorat hai. Hum inhe ek-ek karke build karte hain, har ek agले ka raasta kholega.
Ek memory cell computer mein ek labelled box hai jo ek number hold karta hai. Label uska address hai; andar ka number uski value hai. Reading = andar dekhna bina badlav kiye. Writing = number ko replace karna.
School ke lockers ki ek row imagine karo. Har locker par ek number paint hai (address) aur andar ek note hai (value).
Topic ko ye kyun chahiye: atomics jo kuch bhi karte hain woh sab ek box ke baare mein hai jisme do log haath daalte hain. Agar aap box imagine nahi kar sakte, toh "shared variable" sirf words hain.
Ek thread execution ki ek independent line hai: ek worker jo apni instructions ki list ek-ek karke chala raha hai. Do threads ek saath chalte hain, lekin woh kisi bhi point par ruk sakte hain — operating system decide karta hai kab.
Intuition Tasveer: do haath, ek lockerDo workers ko imagine karo, har ek apni checklist follow kar raha hai, lekin dono ko ek hi locker kholne ki permission hai. Khatre ki baat ye nahi hai ki woh share karte hain — khatre ki baat ye hai ki koi bhi doosre ke kaam karte waqt beech mein freeze ho sakta hai.
Parent note ki saari problem is liye exist karti hai kyunki ek thread apne chhote steps ke beech mein pause ho sakta hai. Threads kaise create hote hain, ye jaanne ke liye std::thread and std::async dekhein.
counter++ ek line ka jhooth hai
C++ ki ek line kai CPU steps chhupaati hai. CPU seedha locker mein add nahi kar sakta — usse ye karna padta hai:
load : locker ki value ko ek chhoti fast slot (register ) mein copy karo.register ke andar 1 add karo .
store : register ki value ko wapas locker mein copy karo.
Ek register CPU core ke andar ek chhoti, ultra-fast storage slot hai. Har thread ke core ke apne registers hote hain, isliye ek thread register mein jo rakhta hai woh doosre ko tab tak dikhai nahi deta jab tak woh memory mein wapas store nahi ho jaata.
Topic ko ye kyun chahiye: "lost update" bug inhi teen steps ke beech ki gap mein rehta hai. Agar aap sochte hain counter++ ek step hai, toh bug samajhna naamumkin hai.
Definition Read-Modify-Write (RMW)Ek read-modify-write koi bhi operation hai jo ek value padhta hai, jo usne padha tha uske basis par badalta hai, phir wapas likhta hai. x++, x += 5, x = x * 2 sab RMW hain.
Intuition Do RMWs aapas mein kyun takraate hainDono threads 5 load karte hain . Dono apne private registers mein 1 add karte hain → dono ke paas 6 hai. Dono 6 store karte hain . Do increments hue, lekin locker sirf ek se aage badha. Ek update overwrite ho gaya — "lost."
Figure follow karo: red timeline dikhata hai Thread B 5 load kar raha hai jabki Thread A mid-flight hai . Yahi interleaving dushman hai. Ek atomic RMW steps 1–2–3 ko ek indivisible blink banata hai taaki koi beech mein na ghus sake.
Atomic (Greek atomos se, "kaat na sake") matlab hai ek operation jise doosre threads ya toh pura ho chuka hai ya shuru nahi hua — kabhi beech mein nahi pakda jaata. Koi visible in-between state nahi hai.
load → (pause) → add → (pause) → store ki jagah, ek atomic RMW ek hi motion mein ek grab-count-replace hai. Koi thread iske dauran peek nahi kar sakta, isliye koi update lost nahi ho sakta.
Topic ko ye kyun chahiye: std::atomic<T> bilkul wahi tool hai jo 3-step RMW ko ek uncuttable step mein badalta hai.
Definition Mutex (mutual exclusion)Ek mutex ek software padlock hai. Kisi thread ko shared box ko chhoone se pehle ise lock karna padta hai aur baad mein unlock karna padta hai. Jab tak lock laga hai, har doosra thread jo andar aana chahta hai use line mein wait karna padta hai.
Intuition Hum prefer kyun nahi karteMutex sahi hai lekin waiting ka cost aata hai: agar lock-holder OS dwara pause ho jaata hai, toh baaki sab ruk jaate hain. Mutex and Lock dekhein. Atomics ka poora point yahi hai ki correctness milein is padlock aur uski waiting ke bina .
Lock-free matlab hai operation kabhi OS mutex pakde bina khatam hota hai, aur ye guarantee deta hai system-wide progress : kisi bhi moment par, kam se kam ek thread aage badh raha hai. Ye promise nahi karta ki har thread aage badhta hai — ek badkismat thread apna CAS retry baar baar haar sakta hai aur starve ho sakta hai jabki doosre succeed karte hain.
Intuition Teen non-blocking progress guaranteesYe weakest se strongest tak ranked hain — inhe kisko progress ki guarantee milegi, us baare mein promises ki tarah padho:
Obstruction-free (sabse weak): ek thread tab khatam hota hai jab woh akele kaafi der tak chale (koi interference nahi). Doosre use abort aur retry kara sakte hain.Lock-free (middle): koi na koi thread hamesha progress karta hai, isliye system kabhi freeze nahi hota — lekin individuals starve ho sakte hain.Wait-free (sabse strong): har thread apne bounded number of steps mein khatam hota hai, chahe doosre kuch bhi karein. Koi starvation possible nahi.
Topic ko ye kyun chahiye: "lock-free operations" literally title hai. Yahi payoff hai — padlock ki waiting ke bina atomicity — lekin aapko pata hona chahiye ki ye "koi thread kabhi wait nahi karta" ke barabar nahi hai (woh wait-free hai).
Ek cache memory ki ek chhoti fast copy hai jo har CPU core ke paas rakhi jaati hai. Cores apni cache copy ko slow main memory se zyada prefer karte hain.
Definition Char MESI statesEk core jo cache line copy rakhta hai woh chaar mein se ek state se tagged hoti hai — naam MESI inhi chaar letters se hai:
Modified (M) : is core ki copy badli hui hai aur sirf yehi valid copy hai; main memory stale hai.Exclusive (E) : is core ke paas sirf ek cached copy hai, unchanged aur memory se match kar rahi hai. Yeh freely likh sakta hai (silently M ban jaata hai).Shared (S) : kai cores ek read-only identical copy rakhte hain.Invalid (I) : ye copy stale/unusable hai — use karne se pehle re-fetch karna zaroori hai.
Intuition Atomic RMW MESI mein kaise move karta haiAtomic increment karne ke liye, ek core ko write karne ki zaroorat hai, jiske liye line M ya E state mein chahiye — yani woh akela owner hona chahiye. Agar koi aur core ise S ya M mein rakhe, toh likhne wala core ek invalidate broadcast karta hai: har doosri copy I par flip ho jaati hai, ownership transfer hoti hai, aur tabhi RMW aage badhta hai. Kyunki poora load-modify-store tab hota hai jab ye ek core exclusive ownership rakhta hai, koi aur core beech mein nahi ghus sakta — yahi hardware hume software lock ke bina atomicity deta hai.
Cache Coherency MESI aur False Sharing dekhein. Topic ko ye kyun chahiye: ye exclusive-ownership grab (invalidations se guard ki gayi E/M state) woh mechanism hai jisse hardware software lock ke bina atomicity provide karta hai.
Definition Compare-And-SwapCompare-And-Swap ek single atomic instruction hai jiska matlab hai: "meri nayi value tabhi likhna agar box abhi bhi wahi value rakhta hai jo maine expect ki thi — warna mujhe batao woh abhi kya rakhta hai."
Intuition "Compare" phir "swap" kyunCAS optimistic hai: value padho, apna change compute karo, phir sirf tabhi swap karo agar beech mein kisine touch nahi kiya . Agar kisine kiya, toh compare fail ho jaata hai, aap fresh value jaante hain, aur retry karte hain. Yahi retry loop har lock-free structure ka dil hai. Compare-And-Swap dekhein.
Memory order woh rule hai jo control karta hai ki atomic operation ke aas-paas doosre writes kab visible hote hain. Atomicity torn values rok ti hai; memory order uske aas-paas ke writes ki visibility aur sequencing control karta hai.
Definition C++ memory orders ka poora setstd::atomic operations inme se ek accept karte hain, cheapest/weakest se safest/strongest tak:
==memory_order_relaxed==: sirf atomicity — aas-paas ki memory ka koi ordering nahi. Ek pure counter ke liye use karo jis par kisi ki ordering depend nahi karti.
==memory_order_acquire== (ek load par): koi bhi read/write jo iske baad likhi hai woh iske pehle reorder nahi ho sakti. Yeh matching release ko "subscribe" karta hai.
==memory_order_release== (ek store par): koi bhi read/write jo iske pehle likhi hai woh iske baad reorder nahi ho sakti. Yeh pehle ke saare writes "publish" karta hai.
==memory_order_acq_rel==: ek single RMW (jaise fetch_add) ke liye jo dono load aur store hai — yeh read half par acquire aur write half par release ek saath karta hai.
==memory_order_consume==: ek rarely-used, weaker acquire jo sirf loaded value par data-dependent cheezein order karta hai. Practice mein compilers ise acquire mein promote karte hain; isse "avoid karo jab tak expert na ho" samjho.
==memory_order_seq_cst== (default ): sequential consistency — sare threads ke saare seq_cst operations ek single global total order share karte hain. Sabse safe, reason karne mein sabse aasaan, aur yahi milta hai agar aap koi order argument pass nahi karte.
Ek release store ek box bandh karke upar "DONE" note rakhne jaisa hai: jo kuch bhi aapne pack kiya woh note se pehle guarantee ke saath andar hai. Ek acquire load us note ko padhne jaisa hai: ek baar jab aap "DONE" dekhte hain, toh aap andar ki sab cheez bhi dekhte hain. Yeh acquire/release handshake C++ Memory Model (C++) se defined hai.
Common mistake Default free nahi haiDefault seq_cst safest hai lekin aksar slowest bhi (yeh extra CPU fences force kar sakta hai). relaxed par jaana tabhi sahi hai jab kisi doosre variable ki visibility is op ki ordering par depend na kare — jaise ek standalone hit counter.
Topic ko ye kyun chahiye: threads mein correctness ke liye dono atomicity (§5) aur ordering (yeh) chahiye. Ek doosre ke bina bhi bugs aa sakte hain.
Map ko neeche se upar padho: upar ke ideas raw building blocks hain, aur har arrow ka matlab hai "samajhne ke liye zaroori hai." Ek memory cell aur ek thread apne private register ke saath aapko teen-step read-modify-write dete hain, jis ki interleaving lost-update bug karti hai. Woh bug atomic (indivisible) operation ka idea force karta hai. Atomicity, mutex padlock se bachne ki chahat ke saath, aur cache/MESI ownership se possible hoke, lock-free operation aur compare-and-swap gate deta hai. Ant mein atomicity memory order ke saath cross-thread visibility ke liye pair hoti hai. Ye saare arrows std::atomic topic node par converge karte hain — woh parent note jise aap padhne ki taiyaari kar rahe hain.
Khud ko test karo — sirf jawab dene ke baad reveal karo.
Memory cell mein kya store hota hai, aur use kya label karta hai? Andar ek value (ek number); ek address use label karta hai.
Do threads simple code par bhi kyun collide kar sakte hain? OS ek thread ko ek line ke tiny machine steps ke beech pause kar sakta hai.
counter++ ke andar chhupe teen steps kaun se hain?register mein load karo, 1 add karo, memory mein wapas store karo.
Register kya hai aur ise kaun dekh sakta hai? CPU core ke andar ek chhota fast slot; us core ke liye private jab tak wapas store nahi hota.
Read-modify-write define karo aur ek example do. Ek op jo padhta hai, jo padha uske basis par badalta hai, phir wapas likhta hai — jaise x++.
"Atomic" intermediate states ke baare mein kya guarantee karta hai? Koi bhi visible nahi; op ya toh pura ho chuka ya shuru nahi hua dikhai deta hai.
Mutex kaun sa cost add karta hai jise atomics avoid karne ki koshish karte hain? Dusre thread ke lock rakhte waqt line mein wait karna.
Lock-free kaun si progress guarantee karta hai, aur kya nahi karta? Koi na koi thread hamesha progress karta hai (system-wide); yeh kisi individual thread ko starve hone se nahi rokta.
Obstruction-free, lock-free, wait-free ko weakest se strongest rank karo. obstruction-free < lock-free < wait-free (wait-free har thread ke apne steps bound karta hai).
Char MESI states ke naam batao. Modified, Exclusive, Shared, Invalid.
Kaun si MESI state(s) core ko likhne deti hain, aur wahan pahunchne ke liye kya broadcast karta hai? Modified ya Exclusive; woh ek invalidate broadcast karta hai taaki doosri copies Invalid ban jaayein.
Jab box ab expected nahi rakhta toh CAS kya karta hai? Woh nahi likhta; current value ko expected mein load karta hai aur false return karta hai.
C++ ke chhe memory orders kaun se hain, aur default kaun sa hai? relaxed, consume, acquire, release, acq_rel, seq_cst — default seq_cst hai.
Memory order kya control karta hai jo atomicity akele nahi karta? Threads ke beech aas-paas ke non-atomic writes ki visibility aur ordering.
