std - atomic — lock-free operations: Exercises — Hinglish deep dive

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

Shuru karne se pehle, ek picture jo aap baar baar reference karoge: "lost update" actually kaisa dikhta hai jab do threads interleave karte hain.

Figure — std - atomic — lock-free operations

Figure s01 — walkthrough. Isse black time arrow ke saath left se right padho. Top row (magenta) Thread A hai; bottom row (violet) Thread B hai. Har box counter++ ka ek machine step hai: load, add, store. Order notice karo: A 5 load karta hai, B bhi 5 load karta hai A ke kuch store karne se pehle, dono 6 compute karte hain, aur dono 6 store karte hain. Orange line kehti hai shared counter kabhi 6 se bahar nahi jaata, aur red X us increment ko mark karta hai jo gayab ho gaya. Yahi woh RMW gap hai jiske baare mein har exercise neeche hai — ya toh hum us gap ko band karte hain (atomic RMW / CAS) ya hum sochte hain kab woh pehle se band hai.

Level 1 — Recognition

Goal: kya aap sahi tool ko naam de sakte ho aur vocabulary spot kar sakte ho?

Exercise 1.1

In teen statements mein se kaun se atomic hain jab a std::atomic<int> hai?

a.fetch_add(1);      // (A)
a = a + 1;           // (B)
++a;                 // (C)

Recall Solution 1.1

WHAT: (A) aur (C) atomic hain; (B) ek single atomic operation nahi hai. WHY:

a.fetch_add(1) ek member function hai → ek indivisible read-modify-write (RMW). (Order seq_cst default hota hai kyunki koi diya nahi.) ✅
++a atomic<int>::operator++ call karta hai, jo internally ek RMW karta hai. ✅
a = a + 1 expand hota hai: a ka ek atomic load, phir ek register mein +1, phir a mein ek atomic store. Do alag atomic ops. Doosra thread inke beech slip kar sakta hai → lost update (exactly figure s01). ❌ Answer: A aur C.

Exercise 1.2

Us memory order ka naam batao jiska matlab hai: "sirf atomic counter correctness — kisi bhi doosri variable pe koi ordering guarantee nahi."

Recall Solution 1.2

memory_order_relaxed. Yeh guarantee karta hai ki is atomic pe operation indivisible hai, lekin surrounding reads/writes of other memory pe koi ordering constraint nahi lagata. (Contrast karo default seq_cst se, jo aapko milta hai agar aap koi argument pass nahi karte.)

Exercise 1.3

std::atomic<T>::is_always_lock_free true hai. Yeh aapko kya bataata hai, aur a.is_lock_free() se yeh alag kaise hai?

Recall Solution 1.3

is_always_lock_free ek compile-time constant hai: yeh type har target pe lock-free hai jis pe yeh program run kar sakta hai. Aap isse static_assert mein use kar sakte ho.
a.is_lock_free() is particular object ke liye is machine pe ek runtime query hai (alignment/size matter kar sakta hai). Agar is_always_lock_free true hai, toh is_lock_free() bhi guaranteed true hai.

Level 2 — Application

Goal: ek chhote task pe primitives ko sahi use karo.

Exercise 2.1

Neeche counter ek shared object hai, ek baar declare kiya gaya aur dono threads ko visible (e.g. ek global, ya reference se captured) — memory mein sirf ek counter hai, per thread ek nahi. Dono threads loop chalate hain. counter ki final value kya hai, aur relaxed yahan acceptable kyun hai?

std::atomic<int> counter{0};   // EK shared object, dono threads ISHE touch karte hain
// dono threads mein se har ek yeh loop chalata hai:
for (int i = 0; i < 100000; ++i)
    counter.fetch_add(1, std::memory_order_relaxed);

Recall Solution 2.1

Answer: exactly 200000. WHY yeh genuinely shared hai (aur isliye ek real race target hai): agar har thread ka apna local counter hota, toh koi cross-thread interaction hi nahi hota aur question trivial hota. Exercise ka point yahi hai ki dono threads same memory location ko increment karte hain — yahi woh jagah hai jahan figure-s01 wala lost-update race ek plain int ke saath hota. Kyunki hum atomic fetch_add use karte hain, race defeat ho jaata hai. WHY value: fetch_add ek atomic RMW hai, isliye koi bhi increment kabhi lost nahi hota — $2 \times 100000$ increments mein se har ek land karta hai. $2 \times 100000 = 200000$ . WHY relaxed theek hai: hum sirf care karte hain ki count sahi ho, kisi doosri variable ke relative is counter ko order karne ke baare mein nahi. Atomicity (no torn/lost updates) har memory order ke under preserve rehti hai; relaxed sirf cross-variable ordering drop karta hai jo hum yahan use nahi karte — sabse sasta correct choice. (Note karo default seq_cst hota; humne consciously downgrade kiya.)

Exercise 2.2

Is broken increment ko safe rewrite karo, jitna ho sake utna kam badlaav karo:

std::atomic<int> a{0};
a = a + 5;   // chahte hain 5 atomically add karo

Recall Solution 2.2

a.fetch_add(5);   // single atomic RMW: PURANI value return karta hai (order defaults to seq_cst)

WHY: a = a + 5 load-then-store hai (do ops, inke beech ek race window). fetch_add(5) load-add-store ko ek indivisible unit ke roop mein perform karta hai — koi window nahi.

Exercise 2.3

Neeche producer/consumer flag mein, dono blanks mein kaun se memory orders jaate hain taaki assert kabhi na fire kare?

std::atomic<bool> ready{false};
int data = 0;
// producer
data = 42;
ready.store(true, /* ??? */);
// consumer
while (!ready.load(/* ??? */)) {}
assert(data == 42);

Recall Solution 2.3

Producer store → std::memory_order_release. Consumer load → std::memory_order_acquire. WHY: release store "package seal karta hai": iske pehle ki har write (including data = 42) pin ho jaati hai flag visible hone se pehle happen karne ke liye. Acquire load "package kholta hai": ek baar jab yeh true dekhta hai, yeh guaranteed hai ki release se pehle seal ki gayi har cheez bhi dikhai degi. Woh pair ek synchronizes-with edge banata hai (dekho figure s02). Kisi bhi side pe relaxed ke saath, data abhi bhi 0 read ho sakta hai. (Blanks khali chhod dena seq_cst default dega — yahan bhi correct, bas zaroori se stronger/slower.)

Figure s02 — walkthrough. Magenta box (data = 42) aur orange box (store(true, release)) producer ke do steps hain; dashed magenta arrow dikhata hai ki release se pehle ki har cheez package mein sealed hai. Thick navy vertical arrow synchronizes-with edge hai: yeh sirf tab fire hota hai jab consumer ka orange load(acquire)==true released value observe karta hai. Ek baar woh edge exist kare, right side ka violet box (sees data==42) guaranteed hai. Kisi bhi colour ka order kill karo (use relaxed banao) aur navy edge gayab ho jaata hai — consumer tab stale data == 0 read kar sakta hai.

Level 3 — Analysis

Goal: samajhna ki code race kyun karta hai, spin kyun karta hai, ya slow kyun hai.

Exercise 3.1

Is CAS-based increment ko do threads ke liye trace karo jo dono old = 5 read karte hain. Exactly dikhao kaun se compare_exchange_weak calls succeed karte hain aur kaun se fail, aur final value.

std::atomic<int> a{5};
// har thread ek baar chalta hai:
int old = a.load();
while (!a.compare_exchange_weak(old, old + 1)) { /* old refreshed */ }

Recall Solution 3.1

Dono old = 5 read karte hain. Mano thread A apna CAS pehle chalata hai.

A: compare_exchange_weak(old=5, 6) → a 5 hai == expected → a = 6 set karta hai, true return karta hai. A exit karta hai.
B: compare_exchange_weak(old=5, 6) → a ab 6 hai != expected 5 → fail karta hai, aur current value 6 ko old mein likhta hai. Loop condition !false hai... wait: CAS ne false return kiya, toh !false == true → loop body refreshed old = 6 ke saath phir chalta hai.
B retry: compare_exchange_weak(old=6, 7) → a 6 hai == expected → a = 7 set karta hai, true return karta hai. B exit karta hai.

Final value: 7. Koi update lost nahi: A ne +1 apply kiya (5→6), B ne +1 apply kiya (6→7). Yeh optimistic concurrency hai: assume karo koi conflict nahi, write time pe verify karo, loser retry karo. (Yeh CAS calls orders omit karte hain → seq_cst default.)

Exercise 3.2

Ek colleague compare_exchange_strong ek retry loop ke andar use karta hai aur complain karta hai ki yeh ARM pe _weak se thoda slower hai. Kya unka _strong use karna galat hai? Trade-off kya hai?

Recall Solution 3.2

Galat nahi, lekin ek loop ke andar sub-optimal hai.

compare_exchange_weak spuriously fail ho sakta hai (failure report kare jab bhi a == expected ho), kyunki kuch architectures pe yeh LL/SC — load-linked / store-conditional — naam ke cheaper instruction pair pe map hota hai. Load-linked ek location read karta hai aur use watched mark karta hai; store-conditional wapas tabhi likhta hai jab tab se kuch uss location ko touch na kiya ho, warna fail karta hai. Woh "fail if disturbed" check tab bhi trip kar sakta hai jab value unchanged lagti hai (e.g. ek unrelated cache event), yahi spurious failure hai. Ek loop mein aap waise bhi retry karte ho, toh ek spurious failure ek extra harmless iteration ka cost karta hai.
compare_exchange_strong koi spurious failure guarantee nahi karta, lekin unhi LL/SC architectures pe internally ek retry loop add karna padta hai → extra kaam. Rule: loops ke andar _weak, ek single non-looped check ke liye _strong.

Exercise 3.3

Bahut zyada contention ke under, ek lock-free CAS counter measure kiya gaya aur woh std::mutex-guarded counter se slower nikla. Explain karo kaise ek "lock-free" structure ek lock se haar sakta hai.

Recall Solution 3.3

Lock-free ≠ wait-free ≠ always faster. Lock-free guarantee karta hai ki koi thread har step progress karta hai, yeh nahi ki har thread karta hai. Heavy contention ke under bahut se threads ke CAS calls baar baar fail aur retry karte hain — har failed CAS ek wasted round-trip hai jo cache line ko cores ke beech bounce bhi karta hai (coherency traffic, dekho Cache Coherency MESI). Ek mutex, iske contrast mein, losers ko park kar deta hai isliye sirf ek core line ko touch karta hai aur koi spin-storm nahi hoti. Takeaway: lock-free low–medium contention pe shine karta hai; hamesha measure karo. Dekho False Sharing bhi ek related slowdown ke liye jab unrelated atomics ek cache line share karte hain.

Level 4 — Synthesis

Goal: ek chhota correct lock-free routine build karo.

Exercise 4.1

Ek lock-free stack push complete karo. Blanks fill karo, CAS ke liye sensible memory orders choose karo, aur loop ko justify karo.

struct Node { int v; Node* next; };
std::atomic<Node*> head{nullptr};
void push(int v){
    Node* n = new Node{v, /* ??? */};
    while(!head.compare_exchange_weak(/* ??? */, /* ??? */)) {}
}

Recall Solution 4.1

void push(int v){
    Node* n = new Node{v, head.load(std::memory_order_relaxed)};
    while(!head.compare_exchange_weak(
              n->next, n,
              std::memory_order_release,   // success: n aur jo kuch humne isme likha use publish karo
              std::memory_order_relaxed))  // failure: pure re-read, koi ordering ki zaroorat nahi
    {}
}

WHY CAS (n->next, n): expected = n->next (woh head jiske peeche hum sochte hain hain), desired = n (hamara node). CAS n ko new head ke roop mein tabhi install karta hai jab head abhi bhi n->next ke barabar ho. Agar kisi doosre thread ne beech mein push kiya, CAS fail karta hai aur new head ko n->next mein likhta hai — toh n automatically fresh head ke peeche re-link ho jaata hai, aur hum retry karte hain. Koi mutex nahi, koi blocking nahi (CAS timeline ke liye figure s03 dekho).

WHY yeh memory orders (yeh exercise ka point hai): two-argument form hume alag success order aur failure order choose karne deta hai.

Success = release. Jab CAS succeed karta hai yeh n ko publish karta hai (ek store). Hum chahte hain ki *n ka initialization (v aur next) kisi bhi thread ko visible ho jo baad mein head ko load(acquire) kare aur hamara node dereference kare — isliye hume winning store pe release semantics chahiye. acq_rel bhi kaam karta agar kisi reader/popper ko is same op pe acquire karna hota, lekin push sirf likhta hai, isliye plain release minimum correct choice hai.
Failure = relaxed. Ek failed CAS ek pure load hai jo sirf n->next refresh karta hai; downstream kuch bhi ise order karne pe depend nahi karta, isliye relaxed sabse sasta hai. (Yaad karo: failure order kabhi release nahi ho sakta.)
Orders completely omit karna dono paths pe seq_cst default karta — correct, lekin yahan zaroori se heavier.

CRITICAL edge case — yeh toy push safe hai, lekin pop NAHI, ABA problem ki wajah se. push sirf add karta hai, isliye jo head pointer woh CAS karta hai woh hamesha ek valid comparison hai. Danger pop mein aata hai:

Thread 1 head = A read karta hai, plan karta hai head ko A se A->next (ise B kaho) pe CAS karne ka.
Thread 1 ruk jaata hai. Beech mein doosra thread A pop karta hai, B pop karta hai, phir A wapas push karta hai. head phir A hai — lekin A->next ab kahin aur point karta hai, aur B free ho sakta hai.
Thread 1 jaagta hai, uska CAS head == A dekhta hai (A→B→A sequence unchanged lagta tha!) aur succeed karta hai — stale/freed B install karta hai. Corruption.

Yeh ABA problem hai: CAS values compare karta hai, aur ek value change hone ke baad A pe wapas aa sakti hai, isliye "unchanged value" ≠ "untouched". Safe reclamation zaroori hai taaki freed nodes reuse na hon (ya reused addresses same logical node na samjhe jayein). Standard fixes:

Tagged/versioned pointers — pointer word mein ek counter pack karo; har push/pop tag bump karta hai, isliye tag 7 wala A ≠ tag 9 wala A, aur CAS inhe distinguish karta hai.
Hazard pointers — har thread un pointers ko publish karta hai jinhein woh dereference karne wala hai; ek node tabhi actually free hota hai jab koi hazard pointer use reference na kare.
RCU / epoch-based reclamation — freeing tab tak defer karo jab tak un saare readers ne aage move na kar liya ho jo potentially pointer hold kar sakte the.

Is exercise ke liye push-only code correct hai; bas yaad rakho ki real lock-free stack with pop zaroor ABA aur reclamation address kare.

Figure s03 — walkthrough. Yeh push ke liye CAS timeline hai (contrast karo s01 se, jo ek broken counter dikhata tha). Magenta row Thread A hai jo node nA push kar raha hai; violet row Thread B hai jo node nB push kar raha hai. Dono same head H load karte hain, isliye dono apna next = H set karte hain. A ka compare_exchange_weak(nA->next=H, nA) pehle chalta hai: head abhi bhi H ke barabar hai → succeeds (orange check), head ab nA hai. B ka CAS (nB->next=H, nB) ab head == nA != H paata hai → fails (red X), aur navy arrow dikhata hai CAS nB->next ko current head nA se refresh karta hai. B retry karta hai (nB->next=nA, nB) → succeeds. Koi node lost nahi, koi mutex nahi — exactly s01 wala racy gap, lekin compare-and-swap se band kiya gaya.

Exercise 4.2

Ek lock-free multiply_by likho: ek atomic<int> a ko factor k se atomically multiply karo. Koi fetch_mul nahi hai. CAS use karo.

Recall Solution 4.2

void multiply_by(std::atomic<int>& a, int k){
    int old = a.load(std::memory_order_relaxed);
    while(!a.compare_exchange_weak(old, old * k,
                                   std::memory_order_relaxed)) {
        /* old current value pe refresh ho gaya → old*k recompute karo */
    }
}

WHY yeh pattern: koi bhi RMW a ← f(a) bina hardware instruction ke CAS retry loop ban jaata hai: old read karo, f(old) compute karo, CAS karo. Agar kisi ne a change kiya, CAS old refresh karta hai aur hum old * k recompute karte hain. Eventually ek thread jeetta hai → lock-free progress. Yeh parent note se universal recipe hai. Ek order yahan kyun kaam karta hai: single relaxed argument success order ko relaxed set karta hai aur ek relaxed failure order derive karta hai — theek hai, kyunki is counter mein koi cross-variable ordering dependency nahi. Agar a doosra data guard karta toh aap success ko release/acq_rel pe raise karte. Check: a=3 se start karo, multiply_by(a,4) 12 deta hai; phir multiply_by(a,5) 60 deta hai.

Level 5 — Mastery

Goal: design aur judge karo — orders choose karo, correctness prove karo, subtle traps se bacho.

Exercise 5.1

Ek atomic<bool> se bana ek spin-lock. lock aur unlock ke liye memory orders choose karo taaki critical section sahi protected ho, aur explain karo kyun weaker orders isse break kardete.

std::atomic<bool> flag{false};
void lock(){   while(flag.exchange(true, /* ??? */)); }   // busy-wait
void unlock(){ flag.store(false, /* ??? */); }

Recall Solution 5.1

void lock(){   while(flag.exchange(true, std::memory_order_acquire)); }
void unlock(){ flag.store(false, std::memory_order_release); }

WHY lock pe acquire: exchange old value return karta hai; hum tab tak spin karte hain jab tak woh false na ho (humne lock grab kar liya). Acquire ensure karta hai ki critical section ke andar koi bhi read/write lock own karne se pehle reorder na ho — kuch "package early nahi kholta". WHY unlock pe release: release store critical section ke andar ki har write ko pin karta hai flag ke false hone se pehle happen karne ke liye — taaki next thread jo acquire karta hai hamare saare updates dekhe. Saath mein: release → acquire synchronizes-with do threads ke beech. Kisi bhi side pe relaxed critical-section memory ko lock ke andar ya bahar leak karne deta. (Orders omit karna seq_cst default karta — correct lekin zaroori se stricter.) Compare karo ek real Mutex and Lock se, jo yeh aapke liye karta hai.

Exercise 5.2

Aapke paas std::atomic<int> counters[64]; hai jo 8 threads access karte hain (thread t sirf counters[t] touch karta hai). Throughput bahut kharab hai even though koi logical sharing nahi hai. Diagnose aur fix karo.

Recall Solution 5.2

Diagnosis: false sharing. Independent counters jo same 64-byte cache line mein hain woh line ko cores ke beech har atomic write pe bounce karte hain, chahe do threads same counter touch na karen. Coherency protocol (MESI) poori line ko invalidate karta hai, sirf ek byte ko nahi. Dekho False Sharing aur Cache Coherency MESI. Fix: har counter ko apni cache line pe pad/align karo:

struct alignas(64) Padded { std::atomic<int> c{0}; };
Padded counters[64];

Ab har thread ki write ek alag line dirty karti hai → koi cross-core invalidation storm nahi.

Figure s04 — walkthrough. Left side (magenta, "BAD") mein, chaar counters c0..c3 ek single navy-outlined 64-byte cache line ke andar hain. Do red arrows dikhate hain Core 0 c0 likh raha hai aur Core 1 c1 likh raha hai: har write POORI line ko invalidate karta hai, isliye line cores ke beech ping-pong karti hai even though counters logically independent hain — yahi false sharing hai. Right side (violet, "GOOD") mein, har counter alignas(64) mein wrap hai aur apni khud ki navy-outlined line paata hai; orange caption note karta hai ki ab koi cross-core invalidation nahi hai. Same code semantics, bahut better throughput — fix purely is baare mein hai ki bytes kahan rehte hain.

Exercise 5.3

Informally prove karo ki arbitrary RMW ke liye CAS retry loop lock-free hai, yaani system as a whole hamesha progress karta hai. Phir ek cheez batao jo yeh guarantee nahi karta.

Recall Solution 5.3

Progress argument: har iteration mein, ek thread current value old read karta hai, f(old) compute karta hai, aur CAS karta hai. Ek CAS tabhi fail karta hai jab kisi doosre thread ka CAS succeed kiya aur hamari read ke baad value change ki. Isliye har failure doosre thread ki success ki wajah se hoti hai. Isliye kisi bhi run mein, har contended step pe kam se kam ek thread apna operation complete karta hai → poora system kabhi stall nahi karta → definition ke mutabiq lock-free. Yeh kya guarantee nahi karta: wait-freedom. Ek single unlucky thread hamesha CAS pe beat ho sakta hai aur indefinitely retry karta reh sakta hai (us thread ka starvation), even while system as a whole progress karta rehta hai. Lock-free ek system guarantee hai, per-thread nahi.

Recall One-line self-check

fetch_add a = a + 1 se kyun better hai? ::: fetch_add ek single indivisible RMW hai; a = a + 1 ek alag atomic load phir atomic store hai jinke beech ek racy gap hai. relaxed kab safe hai? ::: Jab aapko sirf is atomic ki apni correctness chahiye, kisi doosri variable pe koi ordering dependency nahi. Agar aap koi argument pass nahi karte toh default memory order kya hai? ::: std::memory_order_seq_cst — sabse strong aur sabse slow. Lock-free push CAS ke success path ko kaun sa order use karna chahiye, aur failure path ko? ::: success = release (new node publish karta hai); failure = relaxed (ek pure re-read). ABA problem kya hai? ::: Ek value A→B→A change hoti hai, isliye ek CAS "unchanged" dekhta hai aur succeed karta hai even though state disturb hui thi; tagged pointers, hazard pointers, ya epoch reclamation se fix hota hai. Lock-free vs wait-free? ::: Lock-free = system hamesha progress karta hai; wait-free = har thread bounded steps mein finish karta hai (stronger).