Worked examples — Atomic operations and CAS

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

Shuru karne se pehle, ek promise: har symbol earn kiya hua hai. Aao vocabulary ko ek picture ke saath fix karte hain.

Figure dekho: mailbox mein ek value hai, tumhare haath mein do cards hain — ek expected card aur ek new card. CAS tumhare expected card ko andar ki cheez se compare karta hai. Match hua → naya card swap in karta hai. Mismatch hua → haath hata deta hai aur real value bata deta hai taaki tum dobara try kar sako.

Hum memory contents ko $\ast addr$ likhenge, jo padhte hain "us address par stored value" (star matlab "box ke andar dekho"). Toh $\ast addr=10$ matlab box mein abhi 10 hai.

The scenario matrix

Har CAS story inhi cells mein se kisi ek mein aati hai. Neeche ke examples us cell ke saath labelled hain jo woh hit karte hain, aur mil ke yeh sab cover karte hain.

Example A — CAS pehli baar mein succeed karta hai

Forecast: return value aur final box contents guess karo aage padhne se pehle.

1. Current value padho. $\ast addr=42$. Yeh step kyun? CAS internally $\ast addr$ ko $exp$ se compare karta hai; reason karne ke liye humein $\ast addr$ pata hona chahiye.
2. $exp$ ko $\ast addr$ se compare karo. Kya $exp=42$ aur $\ast addr=42$ barabar hain? Haan. Yeh step kyun? Yahi equality hai jo CAS ka poora decision hai.
3. $new$ swap in karo. Kyunki match hua, $\ast addr\leftarrow 99$ aur CAS true return karta hai. Yeh step kyun? Matching guess CAS ka likhne ka licence hai.

Verify: final $\ast addr=99$, return $=$ true. Sanity check: ek hi thread, koi interference nahi, toh bilkul naturally guess hold kiya.

Example B — CAS ek baar fail karta hai, phir retry karke jeet jaata hai

void atomic_increment(int* counter) {
    int old_val, new_val;
    do {
        old_val = *counter;
        new_val = old_val + 1;
    } while (!CAS(counter, old_val, new_val));
}

Forecast: Thread 1 kitni baar CAS call karta hai, aur dono threads finish hone ke baad final value kya hai?

1. Attempt 1 — read. Thread 1 $old\_val=5$ padhta hai, $new\_val=6$ compute karta hai. Yeh step kyun? Jis value ko modify karna hai uska snapshot lena zaroori hai.
2. Interleave. Thread 2 pehle run karta hai, $\text{CAS}(counter,5,6)$ karta hai → success. Ab $\ast counter=6$. Yeh step kyun? Yahi woh race hai jo hum stress-test kar rahe hain — box Thread 1 ke pair tale badal gaya.
3. Attempt 1 — CAS. Thread 1 $\text{CAS}(counter,5,6)$ call karta hai. Lekin $\ast counter=6\ne 5$. False return karta hai. Loop dobara chalta hai. Yeh step kyun? Thread 1 ka guess (5) ab stale hai; strong CAS ka false yahaan genuine mismatch matlab hai — woh sahi se Thread 2 ka kaam chhopne se mana karta hai.
4. Attempt 2 — read. Thread 1 dobara $old\_val=6$ padhta hai, $new\_val=7$ compute karta hai. Yeh step kyun? Fresh read = fresh, sahi guess.
5. Attempt 2 — CAS. $\text{CAS}(counter,6,7)$ → success. $\ast counter=7$.

Verify: 5 se shuru karke do increments → $5+1+1=7$ hona chahiye. Final value 7 ✓ — koi update lost nahi hua, yahi toh poora point hai. Thread 1 ne CAS do baar call kiya. lost-update bug se compare karo jahan dono threads 6 likhte.

Example C — CAS jo fail karna chahiye (only-if update)

Forecast: true ya false? Box change hoga?

1. Compare. $exp=0$ vs $\ast addr=1$. Barabar nahi. Yeh step kyun? Programmer chahta hai write sirf state 0 se ho; mismatch matlab precondition meet nahi hui.
2. No write. CAS $\ast addr=1$ ko untouched rakhta hai aur false return karta hai. Yeh step kyun? Yahan CAS ek guarded write hai — guard fail ho gaya, toh kuch nahi hota. Bilkul aise hi test-and-set spinlocks held lock ko stomp karne se bachti hain.

Verify: box 1 par unchanged, return false. Sanity: strong CAS ke saath false definitively matlab hai "condition meet nahi hui" (koi spurious jhooth nahi). Caller decide karta hai retry karun, wait karun, ya abort karun.

Example D — Fetch-And-Add derive karna, aur return-old subtlety

int fetch_and_add(int* addr, int delta) {
    int old_val, new_val;
    do {
        old_val = *addr;
        new_val = old_val + delta;
    } while (!CAS(addr, old_val, new_val));
    return old_val;   // OLD value, not new!
}

Forecast: returned value aur final box value — dono alag hain; dono predict karo.

1. Read. $old\_val=10$. Yeh step kyun? Pre-increment value chahiye, compute karne ke liye bhi aur return karne ke liye bhi.
2. Compute. $new\_val=old\_val+\Delta =10+3=13$. Yeh step kyun? Arithmetic bahar karo atomic step se, taaki atomic part sirf ek sasta compare-swap rahe.
3. CAS. $\text{CAS}(addr,10,13)$ → success (no contention). $\ast addr=13$.
4. Return. $old\_val=10$ return karo. Yeh step kyun? Fetch-and-add ka contract hai "mujhe apne add se pehle wali value do." Yahi isko unique indices distribute karne ke liye useful banata hai — har caller ko ek alag old value milti hai.

Verify: 10 return karta hai, box 13 ho jaata hai. Check: $\text{return}+\Delta =10+3=13=\ast addr$ ✓. Yahi invariant hai $new=old+\Delta$.

Example E — Degenerate inputs

Forecast: kya E1 kuch change karta hai? Kya E2 NULL dereference karke crash hoga?

E1 — zero delta:

1. Compute. $new\_val=7+0=7$. Yeh step kyun? $\Delta =0$ addition ka identity hai — new equals old.
2. CAS. $\text{CAS}(addr,7,7)$ succeed karta hai (7 equals 7), 7 ke upar 7 likhta hai (no-op write). Yeh step kyun? CAS phir bhi succeed karta hai; bas same value likhta hai. Return $7$ hai.

Verify E1: 7 return karta hai, box 7 rehta hai. Zero-delta fetch-and-add ek valid atomic read hai — ek legitimate idiom.

E2 — empty stack se pop:

Node* pop() {
    Node* old_top;
    Node* new_top;
    do {
        old_top = stack_top;
        if (old_top == NULL) return NULL;   // guard FIRST
        new_top = old_top->next;
    } while (!CAS(&stack_top, old_top, new_top));
    return old_top;
}

1. Top padho. $old\_top=\text{NULL}$. Yeh step kyun? Kuch bhi touch karne se pehle snapshot lo.
2. Guard. Kyunki $old\_top$ NULL hai, turant NULL return karo — kabhi bhi NULL dereference mat karo. Yeh step kyun? Guard skip karne se NULL->next hoga, crash. Har real lock-free structure mein yeh degenerate check zaroori hai.

Verify E2: NULL return karta hai, koi dereference nahi, koi CAS attempt nahi. Empty-stack ka sahi behaviour.

Example F — Limiting behaviour: high contention & livelock

Forecast: kya CAS loop deadlock karta hai, livelock karta hai, ya sirf slow ho jaata hai?

1. No deadlock. Har instant mein kam se kam ek thread ka CAS succeed karta hai (jiski guess current value se match kare). Yeh step kyun? CAS lock-free hai: system-wide progress guaranteed hai kyunki failing CAS matlab hai kisi aur ne progress kiya.
2. Lekin starvation possible hai. Ek specific unlucky thread races haarta raha sakta hai aur indefinitely retry karta raha sakta hai — us thread ke liye livelock hai, system ke liye nahi. Yeh step kyun? Lock-freedom guarantee karta hai koi ek thread progress kare, har thread nahi. Fairness ke liye extra kaam chahiye (dekho Lock-Free Data Structures).
3. Throughput saturate hota hai. Har successful CAS doosre sab cores par cache line invalidate karta hai (dekho Cache Coherence Protocols), toh zyada threads → zyada coherence traffic → line "ping-pong" karta hai. Throughput plateau ho jaata hai aur drop bhi ho sakta hai. Yeh step kyun? Limiting cost cache-line bouncing hai, CPU arithmetic nahi.

Verify: limiting case reasoning — $N$ total increments ke saath final value hamesha $\text{start}+N$ hogi chahe interleaving kuch bhi ho; correctness kabhi nahi todti, sirf speed. E.g. start $0$, $N=1000$ threads har ek +1 baar → final $1000$.

Example G — ABA trap fire karta hai

Forecast: Thread 1 ka CAS — succeed karta hai? Kya woh success correct hai?

1. T1 padhta hai. $old\_top=A$, plan karta hai $new\_top=A\text{->}next=B$. Phir T1 preempt ho jaata hai. Yeh step kyun? T1 ka guess "top A hai, next B hai" ab time mein freeze ho gaya hai.
2. T2 A pop karta hai. $stack\_top\to B\to \text{NULL}$. Node $A$ free ho jaata hai.
3. T2 B pop karta hai. $stack\_top=\text{NULL}$. Node $B$ free ho jaata hai.
4. T2 A wapas push karta hai (memory allocator ne freed block reuse kiya). $stack\_top\to A\to \text{NULL}$. Yeh step kyun? Pointer value $A$ wapas aa gayi, lekin $A\text{->}next$ ab NULL hai, $B$ nahi.
5. T1 CAS resume karta hai. $\text{CAS}(\&stack\_top,A,B)$. Current top hai $A$, toh strong CAS succeed karta hai — aur $stack\_top=B$ set kar deta hai. Yeh step kyun? Disaster: $B$ step 3 mein freed tha. Stack ab reclaimed memory point kar raha hai. Dhyan rakho yeh spurious failure issue nahi hai — CAS ne bilkul wahi kiya jo strong CAS promise karta hai; flaw yeh hai ki value-equality identity-equality nahi hoti.

Verify: CAS true return kiya (pointer match hua) phir bhi result corrupt hai. Bug yeh hai ki CAS pointer ke bits compare karta hai, object ki identity nahi. Yahi ABA problem hai.

Example H — ABA version counter se fix kiya

Forecast: kya T1 ka CAS is baar succeed karta hai?

1. T1 padhta hai. $old=\{A,7\}$, plan karta hai $new=\{B,8\}$. Preempted. Yeh step kyun? T1 read time par dono pointer aur version capture karta hai.
2. T2 A pop karta hai → $\{B,8\}$. B pop karta hai → $\{\text{NULL},9\}$. A push karta hai → $\{A,10\}$. Yeh step kyun? Teen successful modifications ne version teen baar bump kiya: $7\to 10$.
3. T1 CAS resume karta hai. $\text{CAS}(\&stack\_top,\{A,7\},\{B,8\})$. Current $\{A,10\}$ hai. Pointer match karta hai, lekin $version10\ne 7$ → CAS fail karta hai. Yeh step kyun? Version ek "generation stamp" ki tarah kaam karta hai. Pointer wapas $A$ par aa gaya, lekin duniya aage badh gayi aur stamp prove karta hai.
4. T1 retry karta hai $\{A,10\}$ ki fresh read ke saath — ab safe hai.

Verify: CAS false return karta hai, corruption avoid ho jaati hai. Versions ka sanity check: 3 modifications ⇒ version exactly 3 se badha, $7+3=10\ne 7$. Iske liye double-width CAS chahiye (x86 par 128-bit: CMPXCHG16B). Dekho Memory Barriers ki version write aur pointer write ek indivisible unit kyun honi chahiye.

Example I — Real-world word problem: ticket dispenser

Forecast: teen seat numbers aur final counter.

1. Request 1. fetch_and_add(counter,1) old value $100$ return karta hai; counter → $101$. Yeh step kyun? Fetch-and-add pre-increment value return karta hai — wahi assigned seat hai, uniqueness guarantee karta hai.
2. Request 2. fetch_and_add(counter,1) $101$ return karta hai; counter → $102$. Yeh step kyun? Interleaving chahe kuch bhi ho, atomicity ensure karti hai ki do requests same old value nahi padh saktiं — har caller ek distinct snapshot dekhta hai, toh koi seat do baar nahi milti.
3. Request 3. fetch_and_add(counter,1) $102$ return karta hai; counter → $103$. Yeh step kyun? Teesra caller bhi apna unique pre-increment value pata hai, teen distinct seats ka batch complete karta hai.

Verify: seats assigned $\{100,101,102\}$ — sab distinct ✓. Final counter $=100+3=103$ ✓ (start $+$ number of requests). Koi double-booking nahi, koi locks nahi. Isliye fetch-and-add ID/seat generation ke liye go-to primitive hai.

Example J — Exam twist: weak vs strong CAS (spurious failure)

Forecast: bug hai, ya legal behaviour?

1. Mechanism pehchano. ARM/RISC-V par, CAS Load-Link / Store-Conditional se bana hai. SC fail ho sakta hai kyunki reservation ek unrelated event se break ho gayi (interrupt, context switch, same cache line ka koi aur access). Yeh step kyun? Parent note ka LL/SC section key hai: SC "fail hota hai agar reservation break ho," aur reservation value se completely unrelated reasons se break ho sakti hai — yahi bilkul woh spurious failure hai jo page ke top par define ki gayi.
2. Weak CAS woh spurious failure forward karta hai. ${\text{CAS}}_{weak}$ false return kar sakta hai tab bhi jab $\ast addr=exp$. Yeh legal aur documented behaviour hai, hardware fault nahi. Yeh step kyun? Spurious failure expose karna compiler ko ek single LL/SC pair (fast) emit karne deta hai instead of internal retry loop ke.
3. Strong CAS isko hide karta hai. ${\text{CAS}}_{strong}$ internally retry karta hai toh sirf genuine value mismatch par false return karta hai — lekin inner loop ka cost aata hai. Isliye is page par har earlier example ne strong CAS assume kiya: unka "false hamesha real mismatch matlab" reasoning sirf strong variant ke liye hold karta hai. Yeh step kyun? Weak choose karo ek loop mein jo tum already retry karte ho (increment, push); strong choose karo one-shot conditional update ke liye (Example C).

Verify: $\ast addr$ unchanged ke saath false return karna weak CAS ke liye correct hai — bug nahi. Programmer ka outer loop simply retry karta hai: agli iteration mein $\ast addr$ phir bhi $5$ padhta hai, guess still match karta hai, aur (assuming koi aur spurious break nahi) increment land karta hai $5\to 6$. Strong CAS jaisa hi final result, e.g. box $6$ par khatam hota hai. Yeh trade-off memory ordering semantics se juda hai.