Visual walkthrough — std - atomic — lock-free operations

5.2.26 · D2 · Coding › C++ Programming › std - atomic — lock-free operations

Yeh parent note ka visual companion hai. Agar yahan koi word unexplained lagta hai, toh woh isi page par bana hai — Step 1 se shuru karo.

Step 1 — "Shared variable" asal mein hota kya hai?

WHAT. Do threads, memory mein ek box jiska naam counter hai. Ek "thread" sirf ek independent worker hai jo apni instructions chalata hai; dono workers ek hi box mein reach kar sakte hain.

WHY yahan se shuru karein. Race ki baat karne se pehle, humein agree karna hoga ki danger tab hi hoti hai jab do workers ek box ko touch karte hain. Agar har ek ka apna box hota, toh kuch bhi galat nahi ho sakta. Toh poora problem shared shabd mein rehta hai.

PICTURE. Do chalk stick-figures (threads) jismein se har ek ka arrow ek hi yellow box ki taraf point kar raha hai. Woh single shared box hi poora battlefield hai.

Step 2 — counter++ ko teen moves mein unfold karna

WHAT. Yeh innocent-looking counter++ ek action nahi hai. CPU memory mein wish karke add nahi kar sakta; use karna padta hai:

$\underset{\text{copy box}\to \text{register}}{\underbrace{\text{load}}}⟶\underset{\text{work in register}}{\underbrace{\text{add }1}}⟶\underset{\text{register}\to \text{box}}{\underbrace{\text{store}}}$

• load — box ki value ko core ke andar ek chhoti fast scratchpad mein copy karta hai jise register kehte hain.
• add 1 — arithmetic sirf register mein hoti hai, box mein nahi.
• store — register ki nayi value wapas box mein likhta hai.

WHY unfold karein. Bug tab tak invisible hai jab tak aap teen sub-steps nahi dekhte. Load aur store ke beech ka gap hi woh jagah hai jahan doosra thread sneaks in karta hai. Teen-move sequence ko read-modify-write (RMW) kaha jaata hai.

PICTURE. Ek single timeline jismein teen chalk beads hain — load, add, store — aur neeche ek bracket hai jo poori cheez ko "one RMW = three separate moments" label karta hai.

Step 3 — Lost update hote dekhna

WHAT. Ab do threads A aur B ko interleave karo, dono teen moves kar rahe hain. Dono box ko load karte hain jab woh abhi bhi 5 hold kar raha hai. Dono 6 compute karte hain. Dono 6 store karte hain.

WHY exactly yeh interleaving. Yeh sabse simple bad schedule hai — koi exotic timing ki zaroorat nahi. Do increments intended the (5 → 7), lekin box 6 par khatam hota hai. Ek increment evaporate ho gaya. Yeh woh "lost update" hai jiske baare mein parent note warn karta hai, motion mein dikhaya gaya hai.

PICTURE. Do parallel timelines. Pink arrow dekho: B ka load A ke load ke baad lekin A ke store ke pehle 5 read karta hai, isliye B kabhi A ka 6 nahi dekhta. Dono stores 6 par land karte hain.

Step 4 — Hardware mein fix: cache line ko hold karo

WHAT. Memory byte-by-byte travel nahi karti; core poora chunk pull karta hai — ek cache line (typically 64 bytes) — apne private cache mein. Magic instruction (x86 LOCK XADD) coherency protocol ko kehta hai: "mujhe is line ki exclusive ownership do aur kisi aur ko tab tak touch mat karne do jab tak mera load-add-store finish nahi ho jaata."

WHY yeh gap close karta hai. Step 3 mein bug gap mein rehta tha. Exclusive ownership ka matlab hai koi doosra core hamare load aur store ke beech load nahi kar sakta — gap sealed ho gaya. Ek instruction, hardware se atomic, koi software lock nahi. Yahi lock-free hai.

PICTURE. Shared box ab ek chalk-outlined cache line ke andar baitha hai. Thread A poori line par ek glowing "exclusive" padlock-of-ownership hold kiye hua hai; Thread B ka arrow boundary par ek red bar se roka gaya hai jab tak A done nahi ho jaata.

Step 5 — Universal primitive: Compare-And-Swap

WHAT. Har RMW ka dedicated instruction nahi hota (koi LOCK XSTACKPUSH nahi hai). Toh CPU ek general atomic gate offer karta hai — compare-exchange — jisse koi bhi RMW build kiya ja sakta hai:

Term by term:

• $a$ — shared atomic box.
• $\text{expected}$ — woh value jo hum sochte hain box mein hai (hamari last reading).
• $\text{desired}$ — woh value jo hum likhna chahte hain, tabhi jab hamara belief abhi bhi sach ho.
• return true — hum jeet gaye; box ab desired hai.
• return false — kisi ne a badal diya; CAS expected ko real current value se refresh karta hai taaki hum retry kar sakein.

WHY CAS na ki plain store. Plain store blindly overwrite karta hai — yahi Step 3 ka bug hai. CAS tabhi likhta hai jab hum ne dekha tab se kuch nahi badla. Woh single conditional test-and-set har lock-free structure build karne ke liye kaafi hai. Poori theory ke liye Compare-And-Swap dekho.

PICTURE. Ek gate: hamari expected key box ke real lock se compare hoti hai. Match → gate khuul jaata hai, desired andar flow karta hai (true). Mismatch → gate band rehta hai, aur box ki sacchi value hamare expected slot mein copy ho jaati hai (false).

Step 6 — CAS retry loop (optimistic concurrency)

WHAT. CAS ko ek loop mein wrap karo taaki haarne wala thread bas dobara try kare:

T old = a.load();                                   // read
while (!a.compare_exchange_weak(old, f(old))) { }   // try; on fail, old is refreshed

• old — box ka snapshot.
• f(old) — woh nayi value jo hum chahte hain (jaise old + 1, ya ek naya stack head).
• compare_exchange_weak — f(old) tabhi likhta hai jab box abhi bhi old ke barabar ho; nahi toh fresh value old mein daal deta hai aur hum loop karte hain.

WHY loop progress guarantee karta hai. Jab bhi koi thread fail karta hai, woh fail hua isliye kyunki doosra thread succeed hua. Toh system as a whole hamesha aage badhta rehta hai — yahi lock-free ki definition hai. Yeh optimistic concurrency hai: assume karo koi conflict nahi, write time par verify karo, sirf rare clash par retry karo.

PICTURE. Ek flow: read → compute → CAS. Green edge "success" exit karta hai; pink edge "kisi ne badal diya" old ko refreshed karke wapas loop karta hai. Low contention ke under loop ek baar chalta hai.

Step 7 — Degenerate & edge cases jo tum skip nahi kar sakte

WHAT / WHY — har corner walk karo:

1. Single thread. Koi sharing nahi → koi race nahi. fetch_add abhi bhi kaam karta hai lekin atomicity unused overhead hai; yahan plain int correct hota. (Step 1 ka battlefield khaali hai.)
2. Atomic par counter = counter + 1. Yeh ek load phir ek store hai — do atomic ops jiske beech gap hai — toh Step 3 ka bug wapas aa jaata hai. Sirf fetch_add / ++counter (member operator) ek RMW hai.
3. High contention. Bahut saare threads → Step 6 ka CAS loop kaafi baar spin kar sakta hai; kabhi kabhi Mutex and Lock jeet sakta hai. Lock-free automatically faster nahi hota — measure karo.
4. Actually lock-free nahi. Bade T ke liye, library internal lock par fall back kar sakti hai. a.is_lock_free() ya std::atomic<T>::is_always_lock_free se check karo.

PICTURE. Char chhote chalk panels: (1) akela figure, koi conflict nahi; (2) atomic box jisme load aur store ke beech reopened gap hai; (3) ek crowd of figures sab ek gate par spinning kar rahe hain; (4) ek box jisme ek chhupa hua padlock laga hai jis par "not lock-free" stamped hai.

Step 8 — Relaxed order yahan kyun kaafi hai (aur kab nahi hota)

WHAT. fetch_add(1, memory_order_relaxed) mein hum cross-variable ordering drop kar dete hain aur sirf atomicity rakhte hain.

WHY counter ke liye yeh safe hai. Humein sirf yeh care hai ki count sahi ho, na ki woh doosre variables ke relative mein ordered ho. Atomicity (Step 4) order ki parwah kiye bina preserve hoti hai — memory order sirf surrounding writes ki visibility control karta hai, jo ek pure counter ki koi nahi hoti. Toh relaxed sabse sasta correct choice hai.

KAB yeh break karta hai. Agar kisi doosre variable ki visibility is op par depend karti hai (parent mein producer/consumer flag), toh tumhe release/acquire chahiye. Ek counter jo readiness signal bhi karta hai woh ab "sirf ek counter" nahi raha.

PICTURE. Left: akela counter — "ordering gate" greyed out hai, sirf atomic core glow kar raha hai (relaxed theek hai). Right: ek counter ek data write ke saath paired hai — ab ek release/acquire gate do threads ko connect karna chahiye.

One-picture summary

Sab kuch ek board par: teen-move RMW, sealed cache line jo use atomic banati hai, aur CAS retry loop jo use generalise karta hai — har lock-free algorithm ke do engines.

Recall checks: