Atomic operations and CAS: Exercises — Hinglish deep dive

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

Shuru karne se pehle, ek shared vocabulary reminder taaki koi symbol bina explanation ke use na ho:

Inme se kaun si operation typical hardware par atomic hai, aur kaun si race-prone read-modify-write hai? (a) x = 5; (single aligned 32-bit store) (b) counter++; (c) CAS(&p, old, new) (d) total += array[i];

Recall Solution

Atomic: (a) aur (c). Not atomic: (b) aur (d).

(a) Ek single aligned store of a machine word atomic hai — koi dusra thread ise half-written nahi dekh sakta.
(b) counter++ load → add → store mein compile hota hai: three alag steps hain jinke beech race window hoti hai.
(c) CAS ek single hardware primitive hai, atomic by definition.
(d) += bhi load → add → store hai, (b) jaise hi race window. Atomic operations ki count: 2.

Exercise 1.2

CAS ko $CAS (a dd r, e x p ec t e d, n e w)$ call kiya jaata hai. Agar *addr = 7 hai, toh CAS(addr, 4, 9) memory ke saath kya karta hai aur kya return karta hai?

Recall Solution

Stored value $7$ hai lekin $e x p ec t e d = 4$ hai. Kyunki $7 \neq = 4$ , compare fail hota hai: memory $7$ par hi rehti hai aur CAS false return karta hai. Return = false, memory unchanged (still 7).

Level 2 — Application

Exercise 2.1

atomic_increment ko $10$ se shuru hote counter par trace karo, jahan CAS doosri attempt par succeed karta hai (kisi dusre thread ne tumhare read aur CAS ke beech counter ko $11$ kar diya). Har old_val, new_val, aur CAS result list karo. Final counter value kya hai?

Recall Solution

old_val = *counter        // read 10
new_val = old_val + 1      // 11
CAS(counter, 10, 11)       // FAILS: counter ab 11 hai, 10 nahi
old_val = *counter         // re-read 11
new_val = old_val + 1      // 12
CAS(counter, 11, 12)       // SUCCEEDS: counter 11 tha

Attempt 1: old_val=10, new_val=11, CAS → false
Attempt 2: old_val=11, new_val=12, CAS → true
Final counter = 12. (Interfering thread ke increment ne ise 11 kiya, hamare ne 12 — koi update lost nahi hua.)

Exercise 2.2

fetch_and_add(addr, delta) use karke jo add se pehle ki value return karta hai: agar *addr = 100 hai aur do threads fetch_and_add(addr, 5) aur fetch_and_add(addr, 3) run karte hain, toh *addr ki final value kya hai, aur kaun se do return values possible hain (dono orderings list karo)?

Recall Solution

Fetch-and-add atomic hai, isliye dono adds order ke bawajood compose ho jaate hain. Final value = $100 + 5 + 3 = 108$ . Return values order par depend karte hain:

Agar +5 pehle run kare: yeh $100$ return karta hai, +3 $105$ return karta hai.
Agar +3 pehle run kare: yeh $100$ return karta hai, +5 $103$ return karta hai. Exactly ek thread hamesha $100$ dekhta hai; doosra partially-updated value dekhta hai. Final = 108 dono cases mein.

Level 3 — Analysis

Exercise 3.1

Ek spinlock test_and_set use karta hai, jo atomically $1$ likhta hai aur old value return karta hai. Lock "free" hoti hai jab word $0$ ho. Acquire loop likho aur explain karo: kaunsi old value matlab "maine lock li"? Figure dekho.

Recall Solution

void acquire(int* lock) {
    while (test_and_set(lock) == 1) {
        // spin: old value 1 tha => lock already held thi
    }
    // old value 0 tha => yeh free thi, aur humne ise 1 kar diya: hum owner hain
}

Tumhe lock tab mili jab test_and_set $0$ return kare. $0$ return karna matlab word free tha aur tumne ise same indivisible step mein $1$ par flip kar diya. $1$ return karna matlab kisi ke paas already thi; tum spin karte raho. Dekho Spinlocks and Mutexes.

Exercise 3.2

Neeche ek lock-free pop trace hai. Exact line identify karo jahan ABA problem strike karta hai aur kyun CAS galat succeed karta hai.

Initial: stack_top -> A -> B -> NULL
T1: old_top = A
T1: new_top = A.next = B
    [T1 preempted]
T2: pop A          (stack_top = B)
T2: pop B          (stack_top = NULL)
T2: push A         (stack_top = A, reusing freed node A)
T1: CAS(&stack_top, A, B)   <-- ???

Recall Solution

Final CAS galat succeed karta hai. T1 ka expected = A hai aur stack_top ek baar phir A hai, isliye pointer comparison match karta hai — lekin structure neeche change ho gayi. T1 stack_top = B set karta hai, lekin $B$ already T2 ke dwara pop aur free ho chuka tha. Result: stack_top freed memory ko point karta hai → corruption. Root cause: CAS pointer value compare karta hai, object identity nahi. Pointer $A$ par wapas aa gaya ("A → B → A" sequence), isliye CAS nahi bata sakta ki sab kuch move ho gaya. Fix ABA Problem Solutions aur Exercise 4.1 mein.

Level 4 — Synthesis

Exercise 4.1

Exercise 3.2 ko version counter (tagged pointer) se fix karo. Stacked value ek pair $⟨ pt r, v er ⟩$ hai aur double-width CAS ko dono fields match karni chahiye. Suppose T1 ne $⟨ A, 7 ⟩$ read kiya. A→B→A recycling ke dauran, T2 ne 3 modifications kiye (pop, pop, push). Jab T1 finally CAS run karta hai toh stack_top pe kaun sa version hoga, aur kya T1 ka CAS succeed karega?

Recall Solution

Har modification version ko $1$ se increment karta hai:

start: $⟨ A, 7 ⟩$
pop A ke baad: $⟨ B, 8 ⟩$
pop B ke baad: $⟨ NULL, 9 ⟩$
push A ke baad: $⟨ A, 10 ⟩$

T1 ka CAS expected = ⟨A, 7⟩ use karta hai. Current $⟨ A, 10 ⟩$ hai. Pointer match karta hai ( $A = A$ ) lekin $7 \neq = 10$ , isliye double-width CAS fail hota hai — exactly jo hum chahte hain. Final version = 10; T1 ka CAS fail hota hai aur woh safely retry karta hai. ABA defeat ho gaya.

Exercise 4.2

swap(addr, new) (unconditionally new store karo, old value return karo) sirf CAS ka loop mein use karke derive karo. Prove karo ki yeh contention na hone par exactly ek CAS ke saath hamesha terminate karta hai.

Recall Solution

int swap(int* addr, int new) {
    int old_val;
    do {
        old_val = *addr;               // current read karo
    } while (!CAS(addr, old_val, new));// new install karo sirf tab agar unchanged ho
    return old_val;
}

No contention: hum old_val read karte hain, aur CAS se pehle kuch bhi *addr modify nahi karta, isliye *addr == old_val abhi bhi hold karta hai. CAS pehli attempt par succeed karta hai → exactly ek CAS, phir hum old_val return karte hain. Contention ke saath, har failure matlab kisi aur ne write kiya, isliye hum re-read aur retry karte hain; har retry mein koi thread progress karta hai (lock-freedom). Dekho Lock-Free Data Structures.

Level 5 — Mastery

Exercise 5.1

Ek ARM/RISC-V machine par tumhare paas CAS ki jagah LL/SC hai. LL(addr) load karta hai aur reservation set karta hai; SC(addr, val) store karta hai aur success par $1$ return karta hai, $0$ agar reservation kisi bhi intervening write se break ho gayi. Ek line mein explain karo ki LL/SC Exercise 3.2 ke A→B→A scenario mein ABA se immune kyun hai, bina kisi version counter ke. Phir LL/SC ke upar CAS implement karo.

Recall Solution

Immunity: SC fail hota hai agar LL ke baad address par koi bhi write hui ho — chahe woh same value restore karne wali write ho. Isliye A→B→A sequence reservation break karta hai aur SC $0$ return karta hai, unlike CAS jo sirf final bits compare karta hai. (Caveat: hardware spuriously reservations lose kar sakta hai, isliye LL/SC hamesha retry loop mein rehta hai.)

bool CAS(int* addr, int expected, int new) {
    int cur = LL(addr);          // load + reserve
    if (cur != expected)
        return false;            // value differ karti hai, give up
    return SC(addr, new) == 1;   // store sirf tab agar reservation intact ho
}

Agar SC $0$ return kare (reservation broken), CAS false return karta hai, CAS semantics match karte hue. Dekho Memory Barriers ordering fences ke liye jo usually iske saath pair hote hain.

Exercise 5.2

Ek counter $N$ threads dwara increment kiya jaata hai, har ek CAS loop via $K$ successful atomic increments karta hai. Final counter value aur minimum total CAS executions (successful + failed) ka lower bound do sabhi threads mein. Dono $N = 4$ , $K = 1000$ ke liye compute karo.

Recall Solution

Final value: har increment exactly ek baar land karta hai (CAS lost updates se guard karta hai), isliye final $= N \cdot K = 4 \cdot 1000 = 4000$ . Minimum total CAS executions: best case mein zero contention hai — har CAS pehli try mein succeed karta hai — isliye $N \cdot K$ successful increments mein se har ek exactly ek CAS cost karta hai. Minimum $= N \cdot K = 4000$ . (Failures sirf isme add hote hain; count contention ke under bahut zyada ho sakti hai, lekin $4000$ se kabhi kam nahi.) Answers: final = 4000, minimum total CAS = 4000.

Recall Self-test cloze

Ek atomic op completely and indivisibly execute hoti hai, isliye koi thread partially-completed state nahi dekhta. CAS true sirf tab return karta hai jab *addr expected ke barabar ho. ABA problem CAS ko fool karta hai kyunki yeh pointer value compare karta hai object identity nahi. Version counters ABA ko defeat karte hain CAS ko both pointer aur version match karne par force karke. LL/SC ABA-immune hai kyunki SC any intervening write par fail karta hai, sirf value mismatch par nahi.

Exercises — Atomic operations and CAS

Level 1 — Recognition

Exercise 1.1

Exercise 1.2

Level 2 — Application

Exercise 2.1

Exercise 2.2

Level 3 — Analysis

Exercise 3.1

Exercise 3.2

Level 4 — Synthesis

Exercise 4.1

Exercise 4.2

Level 5 — Mastery

Exercise 5.1

Exercise 5.2