std - atomic — lock-free operations: Worked examples

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

Scenario matrix

Kisi bhi code se pehle, aao list karte hain har tarah ki situation jo atomics aap par throw kar sakti hai. Ise ek checklist samjho — agar hum ek example per row karte hain, toh aap kabhi koi unseen case nahi dekhenge.

Cell	Scenario class	Woh core question jo yeh test karta hai
A	Simple RMW, koi cross-variable dependence nahi	Kya `fetch_add` lost updates fix karta hai? Kya `relaxed` kaafi hai?
B	RMW jo built-in op nahi hai (custom function)	Kya hum phir bhi CAS retry loop se atomic ho sakte hain?
C	High-contention limiting case	Jaise retries badhti hain kya hota hai? Kya progress phir bhi milti hai?
D	Cross-variable visibility (publish/subscribe)	Hume acquire/release kyun chahiye, `relaxed` nahi?
E	`a = a + 1` degenerate trap	Ek "obvious" atomic line ek atomic op kyun nahi hai?
F	Zero / boundary inputs (empty pop, single winner)	Kya hoga agar structure empty ho, ya do threads ek saath try karein?
G	Real-world word problem	Ticket-booking seat allocation — ek seat, bahut saare buyers
H	Exam-style twist	`weak` spurious failure aur "ABA" surprise

Ab hum sare aath cells fill karte hain.

Cell A — simple atomic counter

Worked example Do threads, 100 000 increments har ek (Cell A)

std::atomic<int> counter{0};
// each of 2 threads:
for (int i = 0; i < 100000; ++i)
    counter.fetch_add(1, std::memory_order_relaxed);

Forecast: aage padhne se pehle final value guess karo. Plain int ne "often less than 200000" diya tha. fetch_add kya deta hai?

Step 1 — increments count karo. Total operations = $2 \times 100000 = 200000$ . Yeh step kyun? Har fetch_add(1) exactly ek add karta hai, indivisibly, toh answer sirf kitne issue hue hai.

Step 2 — argue karo ki koi update lost nahi hoga. fetch_add ek single hardware RMW hai (read-modify-write, LOCK XADD). Koi thread ek doosre thread ke load aur store ke beech value read nahi kar sakta. Yeh step kyun? Yahi woh property hai jo plain counter++ mein nahi thi (woh load–add–store teen alag pieces mein tha).

Step 3 — relaxed justify karo. Hume sirf yeh chahiye ki count sahi ho, na ki yeh counter kisi aur variable ke relative order mein ho. Yeh step kyun? relaxed atomicity rakhta hai (kabhi drop nahi hota) lekin expensive cross-variable ordering skip karta hai. Yeh yahan sabse sasta correct choice hai.

Verify: $200000$ increments, har ek $+ 1$ , $0$ se → final $= 200000$ , exactly. Koi bhi interleaving kuch subtract nahi kar sakta kyunki har op indivisible hai. ✓

Cell B — custom RMW via a CAS loop

Worked example Atomically double-then-add-one (Cell B)

Maano hum chahte hain $a \leftarrow 2 a + 1$ atomically, lekin koi fetch_double_plus_one nahi hai. Start value $a = 5$ , ek thread ise ek baar apply karta hai.

std::atomic<int> a{5};
int old = a.load(std::memory_order_relaxed);
// one order used for BOTH success and failure paths:
while (!a.compare_exchange_weak(old, 2*old + 1,
                                std::memory_order_relaxed)) { /* old refreshed */ }

Forecast: loop ke baad a kya hai, aur kitne CAS attempts succeed karte hain?

Step 1 — old value padhon. old = 5. Yeh step kyun? CAS ko jaanna chahiye hum kya sochte hain value hai, taaki pata chale kisi ne ise change kiya ya nahi.

Step 2 — new value compute karo. $2 \times 5 + 1 = 11$ . Yeh step kyun? Hum desired atomic write ke bahar prepare karte hain; write khud sirf tab commit hota hai jab koi interfere na kiya ho.

Step 3 — CAS commit karta hai. Koi doosra thread nahi hai, toh a == old (5) abhi bhi true hai → CAS $11$ likhta hai, true return karta hai, loop 1 iteration ke baad exit karta hai. Yeh step kyun? Yeh "koi thread jeetta hai → progress" guarantee hai. Ek thread ke saath, woh immediately jeetta hai.

Step 4 — relaxed yahan kyun. Yeh value akele khadi hai; kisi doosre variable ki visibility iske upar nahi hai, toh hum ordering drop karte hain aur sirf atomicity rakhte hain. Agar hum koi bhi order nahi likhte, toh default seq_cst sahi hota par unnecessarily expensive. Yeh step kyun? Order ka naam lena yeh explicit karta hai jo warna ek hidden seq_cst default hota.

Verify: $2 (5) + 1 = 11$ ; iterations $= 1$ . ✓

Neeche wahi loop ek flow ke roop mein draw hai: read → compute → CAS commits, single-thread "no contention → immediate win" path amber mein highlighted hai. White arrows left-to-right follow karo, phir success box mein neeche jaao.

Figure — std - atomic — lock-free operations

Cell C — high contention limiting behaviour

Worked example Teen threads ek CAS-loop counter par race kar rahe hain (Cell C)

Teen threads mein se har ek ek baar same value par +1 karna chahta hai, sab CAS loop se, sab ek hi waqt aa rahe hain. Start $a = 0$ .

// each thread, memory_order named explicitly (else default = seq_cst):
int old = a.load(std::memory_order_relaxed);
while(!a.compare_exchange_weak(old, old + 1,
                               std::memory_order_relaxed)) {}

Forecast: final value kya hai? Aur worst case mein, sab threads mein total kitne CAS attempts (successes + failures) hote hain?

Step 1 — final value deterministic hai. Winning ka order kuch bhi ho, har thread exactly ek +1 land karta hai. Final $= 0 + 3 = 3$ . Yeh step kyun? Correctness (value) kabhi contention par depend nahi karti — sirf performance karta hai. relaxed safe hai: count self-contained hai.

Step 2 — successes count karo. Har thread ka exactly ek success ⇒ $3$ successful CAS. Yeh step kyun? Ek success woh moment hai jab thread ka +1 commit hota hai; teen +1s hain.

Step 3 — worst-case failures count karo. Winners ko 1st, 2nd, 3rd order karo. 1st immediately jeetta hai (0 failures). 2nd ke paas stale old tha, ek baar fail karta hai, refresh karta hai, jeeta hai (1 failure). 3rd dono pehle winners ke peechhe fail karta hai: $2$ failures. Worst-case failures $= 0 + 1 + 2 = 3$ . Yeh step kyun? Yeh dikhata hai lock-free ≠ wait-free: ek thread spin kar sakta hai. Total attempts $= 3 successes + 3 failures = 6$ .

Verify: final $= 3$ ; worst-case total attempts $= 3 + \frac{3 ( 3 - 1 )}{2} = 3 + 3 = 6$ . Failure count arithmetic series hai $0 + 1 + \dots + (n - 1) = \frac{n ( n - 1 )}{2}$ $n = 3$ ke liye. ✓

Cell D — cross-variable visibility (acquire/release)

Worked example Producer data publish karta hai, consumer padhta hai (Cell D)

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

Forecast: sahi orders ke saath, consumer data ke liye kya padhega? relaxed ke saath kya padh sakta hai?

Step 1 — producer package seal karta hai. ready par release store, data = 42 ko ready visible hone se pehle pin karta hai. Yeh step kyun? Release matlab "mere pehle ka koi write mere baad slip nahi ho sakta" — 42 sealed box ke andar hai.

Step 2 — consumer receive karne ke baad kholta hai. Load par acquire matlab ek baar jab consumer ready == true dekhta hai, producer ne apne release se pehle ki saari writes bhi visible hain. Yeh step kyun? Yeh synchronizes-with edge banata hai. Dekho memory model.

Step 3 — guaranteed read. Consumer data == 42 padhta hai. Yeh step kyun? Acquire/release pair ek one-way gate hai; data abhi bhi $0$ nahi ho sakta.

Verify: sahi orders ⇒ data == 42 guaranteed. Dono par relaxed se, compiler/CPU consumer ko ready == true dikhane de sakta hai jabki data abhi bhi 0 ho — ek real, non-deterministic bug. Jab bhi guarantee hold karti hai, number khud 42 hai. ✓

Neeche ka figure ise do threads ke beech ek one-way gate ki tarah draw karta hai: amber synchronizes-with arrow ek hi channel hai, aur producer ne apne release ke upar jo bhi likha woh sab iske through force hota hai consumer ke acquire se pehle jo execution proceed karne deta hai. Producer column top-down padhon, amber arrow cross karo, phir consumer column padhon.

Cell E — `a = a + 1` degenerate trap

Worked example "Atomic + obvious code" phir bhi updates kyun khota hai (Cell E)

std::atomic<int> a{0};
// two threads each do 1 million times:
a = a + 1;   // LOOKS atomic — it is NOT

Forecast: kya final value guaranteed 2 000 000 hai?

Step 1 — line decompose karo. a = a + 1 hai int tmp = a.load(); a.store(tmp + 1); — do atomic ops jinke beech gap hai. Yeh step kyun? Sirf member functions/overloaded operators single atomic ops hain; ek general expression nahi hota.

Step 2 — interleave dikhao. Thread A 5 load karta hai, Thread B 5 load karta hai, dono 6 store karte hain. Ek increment gayab ho jaata hai — exactly wahi plain-int bug, wapas aa gaya. Yeh step kyun? Har op ki atomicity pair ki atomicity mein chain nahi hoti.

Step 3 — fix. a.fetch_add(1) ya ++a (member operator) use karo, jo ek RMW hai. Yeh step kyun? Ek indivisible instruction gap band karta hai.

Verify: fetch_add/++a version → exactly $2 \times 1000000 = 2000000$ . a = a + 1 version → guaranteed nahi 2000000 (kam ho sakta hai). ✓

Cell F — zero / boundary inputs (empty stack, single winner)

Worked example Lock-free stack: push aur empty-pop boundary (Cell F)

struct Node { int v; Node* next; };
std::atomic<Node*> head{nullptr};   // empty stack
void push(int v){
    Node* n = new Node{v, head.load(std::memory_order_relaxed)};
    // success = RELEASE so the new Node's fields publish before head;
    // failure = RELAXED (just a retry, nothing to publish yet):
    while(!head.compare_exchange_weak(n->next, n,
                                      std::memory_order_release,
                                      std::memory_order_relaxed)) {}
}

Do threads 10 aur 20 initially empty stack par push karte hain. Forecast: dono pushes ke baad, kitne nodes hain, aur head->v kya hai?

Step 1 — zero/degenerate case. Initially head == nullptr. Pehla n->next hai nullptr — ek valid, non-crashing starting point. Yeh step kyun? Hume empty case check karna chahiye: nullptr ke against CAS abhi bhi kaam karta hai; kuch bhi trip karne ke liye nahi hai.

Step 2 — single-winner boundary. Agar dono threads ek saath head == nullptr padhein, sirf ek CAS succeed karta hai (maano 10 push karta hai). Haarne wale ka CAS fail karta hai, n->next ko new head (10-node) par refresh karta hai, retry karta hai, succeed karta hai. Yeh step kyun? CAS har round mein exactly ek winner guarantee karta hai — boundary "dono simultaneously try karte hain" cleanly resolve hoti hai.

Step 3 — success order MUST release kyun hona chahiye. new Node{v, ...} n->v aur n->next par CAS ke n ko head mein publish karne se pehle likhta hai. Ek popping thread head ka acquire load karta hai, phir node dereference karta hai. Agar hamara success CAS relaxed hota, toh woh field writes pointer visible hone ke baad reorder ho sakti theen — ek popper uninitialized v/next padh leta. release initialization ko publication se pehle pin karta hai, popper ke acquire se match karta hua. Yeh step kyun? Yeh load-bearing edge case hai: pointer visible ⇒ uske contents already visible hone chahiye. Failure path relaxed rehta hai kyunki failed CAS kuch publish nahi karta.

Step 4 — result count karo. Do successful pushes ⇒ 2 nodes. Last pusher ka node top par hai, toh head->v = woh value jo last push ki gayi. Yeh step kyun? Push prepend karta hai, toh top = jo bhi last jeeta (10 ya 20).

Verify: node count $= 2$ ; empty→push→push kabhi bhi nullptr dereference nahi karta kyunki CAS nullptr ko ek plain value ki tarah padhta hai, pointer follow karne ke liye nahi. Top value jo bhi last jeeta (10 ya 20) hai, dono valid hain, aur uske fields release ki wajah se guaranteed initialized hain. ✓

Cell G — real-world word problem: ek seat, bahut saare buyers

Worked example Ticket booking — 1 seat, 4 threads book karne ki koshish kar rahe hain (Cell G)

Ek concert mein 1 seat bacha hai. Chaar booking threads mein se har ek ise claim karne ki koshish karta hai. Seat ko available/taken ki tarah model karo:

std::atomic<bool> taken{false};
bool try_book(){
    bool expected = false;
    // single non-looped check -> STRONG; seq_cst default kept for a
    // clear global order of who-booked-first (safest for money-handling):
    return taken.compare_exchange_strong(expected, true,
                                          std::memory_order_seq_cst);
}

Forecast: kitne threads succeed karte hain? Kitne try_book calls false return karti hain?

Step 1 — CAS se model karo. "Sirf tab book karo jab abhi free ho" exactly compare (free?) and swap (to taken) hai. Yeh step kyun? CAS natural tool hai: yeh atomically pre-condition check karta hai aur ek step mein commit karta hai, toh do buyers dono "free" nahi dekh sakte.

Step 2 — exactly ek winner. Pehla thread taken == false paata hai, true par swap karta hai, true return karta hai. Baaki teen ab taken == true paate hain, toh expected (jo false tha) ≠ actual → CAS false return karta hai. Yeh step kyun? _strong yahan sahi hai — yeh ek single, non-looped check hai, toh spurious-failure allowance ki zaroorat nahi.

Step 3 — seq_cst kyun rakho. Booking paise aur audit logs touch karti hai; "kisne kab book kiya" ka ek single global total order cost worth hai, toh hum default ko relax karne ki jagah rakhte hain. Yeh step kyun? Yeh dikhata hai default deliberately chosen hai, bhula nahi gaya.

Step 4 — tally. Successes $= 1$ , failures $= 4 - 1 = 3$ . Yeh step kyun? Ek seat ek baar bik sakti hai; teen buyers sahi se reject ho jaate hain — koi double-booking nahi.

Verify: successes $= 1$ , failures $= 3$ , aur $1 + 3 = 4$ total attempts. ✓

Cell H — exam twist: spurious failure aur ABA surprise

Worked example

weak "bina kisi reason ke" fail hota hai — kya count galat hai? (Cell H)

std::atomic<int> a{7};
int old = a.load(std::memory_order_relaxed);   // old == 7
// weak MAY fail spuriously; relaxed order (self-contained value):
int attempts = 0;
while(!a.compare_exchange_weak(old, old + 1,
                               std::memory_order_relaxed)) { ++attempts; }

Maano CPU compare_exchange_weak ko spuriously do baar fail karta hai, even though a abhi bhi 7 hai, phir succeed karta hai. Forecast: final a kya hai, aur kya spurious failure result corrupt karta hai?

Step 1 — spurious failure kya karta hai. weak false return kar sakta hai even jab a == old ho. Failure par yeh old ko a se reload karta hai (abhi bhi 7). Yeh step kyun? Yeh by design hai — kuch CPUs par sasta (e.g. LL/SC architectures). Loop ise absorb karne ke liye meant hai. Note karo weak sirf loop ke andar safe hai; relaxed naam lena (self-contained) value ko sasta rakhta hai.

Step 2 — loop retry karta hai. old 7 par refresh hota hai (unchanged), hum old + 1 = 8 recompute karte hain, dobara try karte hain. 2 spurious fails ke baad, 3rd attempt commit karta hai. Yeh step kyun? Kyunki value actually kabhi nahi badi, har retry wahi desired value recompute karta hai — koi drift nahi.

Step 3 — result aur attempt count. Final a = 8. attempts (failures counted) $= 2$ ; total CAS calls $= 3$ . Yeh step kyun? Spurious failure sirf time cost karta hai, correctness kabhi nahi. Yahan _strong use karne se spurious fails hat jaate par loops mein slow hota.

Verify: final $= 8$ ; failure count $= 2$ ; total attempts $= 3$ . ✓

Recall Quick self-test: cell ka naam batao

fetch_add(1, relaxed) counter sahi hai kyunki... ::: har op ek indivisible RMW hai; relaxed atomicity rakhta hai, sirf cross-variable ordering drop hoti hai (Cell A). Worst-case CAS failures $n$ colliding threads ke liye ::: $\frac{n ( n - 1 )}{2}$ , quadratic — lock-free wait-free nahi hai (Cell C). a = a + 1 atomic par abhi bhi buggy kyun hai? ::: yeh load-then-store hai (do ops ek gap ke saath), ek RMW nahi; fetch_add/++a use karo (Cell E). Lock-free push mein, successful CAS ko release-store kyun hona chahiye? ::: taaki new node ke fields (v, next) head pointer visible hone se pehle publish hon; warna popper uninitialized data padh le (Cell F). Ek seat, chaar buyers, kitne succeed karte hain? ::: exactly ek; CAS ek single winner deta hai (Cell G). Kya spurious weak failure final value change karta hai? ::: nahi — sirf extra loop iterations ki cost lagti hai; correctness untouched rehti hai (Cell H).

Parent: Hinglish version · Related: Compare-And-Swap · Memory Model (C++) · Cache Coherency MESI · std::thread and std::async · False Sharing · Mutex and Lock

Flashcards

n

threads ek loop par collide karein toh worst-case failed CAS attempts kitne?

Arithmetic series

0 + 1 + \dots + (n - 1) = n (n - 1) /2

, jo dikhata hai lock-free wait-free nahi hai.

Ticket-booking (ek seat, chaar buyers) example mein compare_exchange_strong kyun use karte hain, weak nahi?

Yeh ek single non-looped check hai, toh spurious failures tolerate nahi kar sakte; strong kabhi spuriously fail nahi karta.

ABA problem kya hai?

CAS values compare karta hai history nahi; agar ek value A se B aur wapas A jaaye, CAS galat tarike se succeed karta hai. Fix: version tags ya hazard pointers.

Lock-free stack push mein successful CAS ko memory_order_release kyun use karna chahiye?

Taaki new node ke initialized fields head pointer visible hone se pehle publish hon, taaki acquiring popper kabhi uninitialized data na padhe.