Atomic operations and CAS: Visual walkthrough — Hinglish deep dive

6.1.9 · D2 · Hardware › Parallelism & Multicore › Atomic operations and CAS

Pehli line se pehle, teen plain-word definitions taaki koi bhi symbol unexplained na rahe:

Step 1 — Desk draw karo: ek box, do workers

KYA. Hum scene set karte hain. Ek memory box jiska naam counter hai jisme number $10$ hai. Do threads, unhe T1 (burnt orange) aur T2 (deep teal) kaho, dono counter = counter + 1 karna chahte hain. Correct final answer $12$ hai.

KYUN. Tum race tab tak spot nahi kar sakte jab tak dono timelines ko side by side dekh nahi sakte. Time neeche ki taraf flow karta hai; har thread ke actions uski apni vertical line par dots hain.

PICTURE. Box middle mein baitha hai. Har worker ka ek arrow andar read karne ke liye aur ek arrow bahar write karne ke liye hai. Abhi kuch hua nahi — yeh time zero hai.

Step 2 — Timelines ko interleave karo: the lost update

KYA. Ab hum T1 ke teen motions aur T2 ke teen motions ko same clock par rakhte hain, lekin operating system ko unhe badly interleave karne dete hain: T2 T1 ke read aur T1 ke write ke beech ghus jaata hai.

KYUN. Yahi poori bimari hai. Kyunki $R$ aur $W$ alag hain, doosra worker stale value $10$ read kar sakta hai pehle worker ke $11$ wapas likhne se pehle. Dono $11$ compute karte hain. Dono $11$ likhte hain. Ek increment gum ho gayi.

PICTURE. Numbered clock ticks follow karo. Red "!" exactly woh instant mark karta hai jab damage avoid nahi ho sakta — woh moment jab T2 $10$ read karta hai jab T1 abhi bhi use hold kar raha hai.

$T1 reads 10 \to T2 reads (stale!) 10 \to T1 writes W (11) \to T2 overwrites W (11)$

Pehla $10$ — woh jo T1 ne dekha.
Doosra $10$ — woh jo T2 ne dekha kyunki T1 ne abhi write nahi kiya tha. Yahi staleness bug hai.
Dono $W (11)$ — do workers same answer install karte hain; doosra pehle wale ko flatten kar deta hai.

Step 3 — Atomic weapon introduce karo: CAS as a challenge coin

KYA. Hum woh single hardware instruction define karte hain jise use karne ki humein permission hai.

\begin{cases} \texttt{*addr} \leftarrow \texttt{new}, & \text{return } \textbf{true} \quad \text{if } \texttt{*addr} = \texttt{exp}\\[4pt] \text{leave box alone}, & \text{return } \textbf{false} \quad \text{if } \texttt{*addr} \neq \texttt{exp} \end{cases}$$ Term by term: - $\texttt{addr}$ — *woh* box jis par hum bet laga rahe hain (`counter` ka address). - $\texttt{exp}$ — woh value jo hum expect karte hain ki abhi bhi wahan ho. Yeh hamara claim hai "jab se maine read kiya, kisi ne touch nahi kiya." - $\texttt{new}$ — woh value jo hum install karna chahte hain agar hamara claim sahi ho. - Poora comparison-and-write ==indivisibly== hota hai — koi bhi worker compare aur swap ke beech nahi ghus sakta. **KYUN *yeh* tool aur plain write kyun nahi?** Plain write unconditional hai — woh jo bhi wahan hai use stomp kar deta hai. CAS ek *conditional* write hai: yeh tabhi fire karta hai **agar reality abhi bhi tumhari expectation se match karti ho**. Woh ek word "if" hi hai jo ek worker ko *detect* karne deta hai ki kisi ne interfere kiya, instead of unhe blindly clobber karne ke. **PICTURE.** Ek challenge coin ki tarah socho. Tum guard ko woh coin dikhate ho jo tumhe `exp` mein expect hai. Agar woh table par rakhe coin (`*addr`) se match karta hai, swap hota hai aur tumhe **true** milta hai. Agar kisi ne table coin already swap kar diya, koi swap nahi, tumhe **false** milta hai — aur important baat, tum *jaante* ho. ![[deepdives/dd-hardware-6.1.09-d2-s03.png]] --- ## Step 4 — Successful CAS: hamari expectation sahi nikli **KYA.** T1 CAS ke saath poora recipe karta hai: $10$ read karo, $11$ compute karo, phir $\text{CAS}(\texttt{counter}, 10, 11)$. Kisi ne interfere nahi kiya, toh `*counter` abhi bhi $10$ hai, `exp` $=10$ se match karta hai, swap fire hota hai. **KYUN.** Yeh happy path hai — woh case jahan loop jo hum banane wale hain exactly ek baar chalega. Hume success clearly dekhna chahiye pehle is par complication add karne se. **PICTURE.** Green check mark karta hai ki compare succeed hua ($10 = 10$); arrow dikhata hai $11$ likha ja raha hai; CAS **true** return karta hai. ![[deepdives/dd-hardware-6.1.09-d2-s04.png]] $$\text{CAS}(\texttt{counter},\ \underbrace{10}_{\texttt{exp}=\ \texttt{*counter}},\ \underbrace{11}_{\texttt{new}}) = \textbf{true} \quad\Rightarrow\quad \texttt{counter}=11$$ --- ## Step 5 — Failing CAS: expectation toot gayi, aur yeh ACHHA kyun hai **KYA.** Ab Step 2 ki buri interleaving ko replay karo, lekin CAS ke saath. T1 ne $10$ read kiya. T1 ke CAS se pehle, T2 puri increment karta hai, toh `counter` ab $11$ hai. T1 $\text{CAS}(\texttt{counter}, 10, 11)$ fire karta hai. Lekin `*counter` $11$ hai $\neq 10 =$ `exp`. **Koi swap nahi. False return karta hai.** **KYUN.** Step 2 mein plain write ne yahan T2 ka kaam silently destroy kar diya tha. CAS iski bajaye *refuse* karta hai aur collision *report* karta hai. Lost update ek **detected** update ban jaata hai. Detection aadhi ladai hai — doosri aadhi (Step 6) retry karna hai. **PICTURE.** Red cross mark karta hai ki compare fail hua ($10 \neq 11$); box $11$ par untouched raha; CAS **false** return karta hai. Notice karo T2 ka increment survive karta hai. ![[deepdives/dd-hardware-6.1.09-d2-s05.png]] $$\text{CAS}(\texttt{counter},\ \underbrace{10}_{\texttt{exp (stale!)}},\ 11) = \textbf{false} \quad\Rightarrow\quad \texttt{counter still }=11,\ \text{T1 must retry}$$ --- ## Step 6 — Loop close karo: fresh eyes ke saath retry **KYA.** Hum read-compute-CAS ko ek `do … while (!CAS(...))` mein wrap karte hain. Failure par, hum wapas loop karte hain, ab-current value **re-read** karte hain, recompute karte hain, aur phir try karte hain. ```c void atomic_increment(int* counter) { int old_val, new_val; do { old_val = *counter; // (a) re-read fresh each time new_val = old_val + 1; // (b) recompute from fresh value } while (!CAS(counter, old_val, new_val)); // (c) gamble; retry if false } ``` **HAR LINE KYUN?** - `(a)` retry par re-reading *mandatory* hai — Step 5 ne dikhaya ki purana `old_val` ab ek jhooth hai. Fresh read = honest `exp`. - `(b)` recompute karo taaki `new_val` *current* reality par build ho, stale wali par nahi. - `(c)` `!CAS` matlab "loop karo jab tak swap fail ho." Success loop exit karta hai; failure humein `(a)` par wapas spin karta hai. **PICTURE.** T1 ka doosra lap: woh $11$ re-read karta hai, $12$ compute karta hai, aur $\text{CAS}(\texttt{counter}, 11, 12)$ ab match karta hai → **true** → final answer $12$. Lost update *theek* ho gaya bina ek bhi lock ke. ![[deepdives/dd-hardware-6.1.09-d2-s06.png]] > [!intuition] Yeh kabhi kyun sleep nahi karta aur kabhi deadlock kyun nahi hota > Ek [[Spinlocks and Mutexes|lock]] haarne walo ko *wait* karwata hai. CAS loop haarne walo ko *fresh data ke saath turant retry* karwata hai. Koi na koi hamesha har round mein progress karta hai — woh "koi na koi hamesha jeetta hai" property hi hai jise [[Lock-Free Data Structures|lock-free]] kehte hain. --- ## Step 7 — Degenerate cases jo tumhe phir bhi survive karne chahiye **KYA.** Har case, spell out kiya gaya taaki koi scenario tumhe surprise na kare: | Case | Kya hota hai | Loop behaviour | |------|--------------|----------------| | **No contention** (ek thread) | pehla CAS `exp` se match karta hai | exactly ek baar chalta hai, jaise Step 4 | | **Contention** (Step 5) | CAS ek baar fail, re-reads, jeet jaata hai | 2+ laps, *ek* winner ke liye hamesha terminate hota hai | | **Heavy contention** (N threads) | bahut failures | phir bhi exactly *ek* winner per round → system hamesha progress karta hai | | **A→B→A trap** | value `exp` par wapas aa jaati hai change hone ke baad | CAS galat succeed karta hai — neeche dekho | **KYUN aakhri row special hai.** CAS *values* compare karta hai, *history* nahi. Agar `counter` (ya ek pointer) $A \to B \to A$ jaata hai, toh final $A$ tumhare `exp` se match karta hai aur CAS fire hoti hai — even though world tumhare neeche badal gayi thi. Yahi ==ABA problem== hai. **PICTURE.** Left: normal failure, CAS correctly false kehta hai. Right: ABA sneak — value $A$ par cycle back kar gayi, toh CAS **true** kehta hai lekin tum stale structure par act kar rahe ho. Fix hai ek ==version counter==: value ke saath ek monotonically increasing tag pair karo, aur *pair* par CAS karo, taaki $A_{\text{v3}} \neq A_{\text{v1}}$. ![[deepdives/dd-hardware-6.1.09-d2-s07.png]] > [!recall]- Exactly kab plain CAS loop break karta hai? > Plain value-only CAS loop precisely tab unsafe hai jab ek value tumhare read aur tumhare CAS ke beech ==pehle dekhi gayi state mein wapas aa sake== (A→B→A). Fix ::: value ke saath ek version counter pair karo (tagged pointer / double-width CAS) taaki same values alag histories ke saath equal na compare karein. Dekho [[ABA Problem Solutions]]. --- ## Ek picture mein summary Upar sab kuch compress kiya: ek decision loop. Fresh read karo → compute karo → CAS. Agar **true**, done. Agar **false**, kisi ne interfere kiya, wapas loop karo aur phir read karo. Koi locks nahi, koi waiting nahi, har round mein ek guaranteed winner. ![[deepdives/dd-hardware-6.1.09-d2-s08.png]] ```mermaid flowchart TD A["read old_val from box"] --> B["new_val = f of old_val"] B --> C["CAS box old_val new_val"] C -->|"true = I won"| D["done"] C -->|"false = interfered"| A ``` > [!recall]- Feynman retelling — plain words mein bolo > Do workers ek number share karte hain. Bug: worker one 10 uthata hai, aur uske 11 wapas likhne se pehle, worker two bhi 10 uthata hai — ab dono 11 likhte hain aur ek increment *lost* ho jaati hai, kyunki reading aur writing alag motions hain inke beech gap ke saath. > > CAS ise ek *conditional* write hokar fix karta hai. Tum hardware ko bolta ho: "is box ko 11 se swap karo, lekin **tabhi** jab woh abhi bhi woh 10 hold kar raha ho jo maine dekha tha." Ek indivisible tick mein hardware check karta hai aur swap karta hai. Agar abhi bhi 10 hold kar raha tha → done. Agar kisi ne use badal diya → CAS refuse karta hai aur tumhe *false* bolta hai, toh ab tum *jaante* ho ki tumhare saath interfere kiya gaya, instead of silently clobber kiye bina. > > Yeh jaante hue ki tum fail ho gaye, tum bas **fir se read karte** ho (fresh value), recompute karte ho, aur ek baar aur try karte ho. Tab tak loop karo jab tak jeeto. Kyunki har round mein exactly ek worker ka CAS match karta hai, koi na koi hamesha progress karta hai — koi locks nahi, koi waiting nahi. > > Ek gotcha: CAS sirf *value* dekhta hai, uski *history* nahi. Agar value wander away kare aur same number par wapas aaye (A→B→A), CAS fool ho jaata hai ki kuch nahi badla. Cure yeh hai ki value par ek version counter staple karo taaki "same number, baad mein time mein" ab equal na lage. > [!mnemonic] Loop chaar beats mein > **R**ead fresh · **C**ompute · **C**AS · **R**etry-if-false. Aur trap ke liye: **A**lways **B**e **A**ware of the value that came back. Related depth: [[Memory Consistency Models]] · [[Memory Barriers]] · [[Cache Coherence Protocols]] govern karte hain ki *kab* doosre threads tumhara winning swap dekhte hain.