std - atomic — lock-free operations: Worked examples

The scenario matrix

Before any code, let us list every kind of situation atomics can throw at you. Think of it as a checklist — if we work one example per row, you will never meet an unseen case.

Cell	Scenario class	The core question it tests
A	Simple RMW, no cross-variable dependence	Does `fetch_add` fix lost updates? Is `relaxed` enough?
B	RMW that is not a built-in op (custom function)	Can we still be atomic via a CAS retry loop?
C	High-contention limiting case	What happens as the number of retries grows? Does progress still hold?
D	Cross-variable visibility (publish/subscribe)	Why do we need acquire/release, not `relaxed`?
E	The `a = a + 1` degenerate trap	Why is an "obvious" atomic line not one atomic op?
F	Zero / boundary inputs (empty pop, single winner)	What if the structure is empty, or two threads both try at once?
G	Real-world word problem	Ticket-booking seat allocation — one seat, many buyers
H	Exam-style twist	`weak` spurious failure & the "ABA" surprise

We now fill all eight cells.

Cell A — simple atomic counter

Worked example Two threads, 100 000 increments each (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: guess the final value before reading on. Plain int gave "often less than 200000". What does fetch_add give?

Step 1 — count the increments. Total operations = $2 \times 100000 = 200000$ . Why this step? Each fetch_add(1) adds exactly one, indivisibly, so the answer is just how many were issued.

Step 2 — argue no update is lost. fetch_add is a single hardware RMW (read-modify-write, LOCK XADD). No thread can read the value between another thread's load and store. Why this step? This is exactly the property plain counter++ lacked (it was load–add–store in three separate pieces).

Step 3 — justify relaxed. We care only that the count is right, not that this counter is ordered relative to any other variable. Why this step? relaxed keeps atomicity (never dropped) but skips the expensive cross-variable ordering. It is the cheapest correct choice here.

Verify: $200000$ increments, each $+ 1$ , from $0$ → final $= 200000$ , exactly. No interleaving can subtract anything because each op is indivisible. ✓

Cell B — custom RMW via a CAS loop

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

Suppose we want $a \leftarrow 2 a + 1$ atomically, but there is no fetch_double_plus_one. Start value $a = 5$ , one thread applies it once.

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: what is a after the loop, and how many CAS attempts succeed?

Step 1 — read the old value. old = 5. Why this step? CAS needs to know what we think the value is, so it can detect if someone changed it.

Step 2 — compute the new value. $2 \times 5 + 1 = 11$ . Why this step? We prepare desired outside the atomic write; the write itself only commits if nobody interfered.

Step 3 — the CAS commits. No other thread here, so a == old (5) is still true → CAS writes $11$ , returns true, loop exits after 1 iteration. Why this step? This is the "some thread wins → progress" guarantee. With one thread, it wins immediately.

Step 4 — why relaxed here. This value stands alone; no other variable's visibility hangs off it, so we drop ordering and keep only atomicity. Had we written no order, the default seq_cst would be correct but needlessly expensive. Why this step? Naming the order makes explicit what would otherwise be a hidden seq_cst default.

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

Below is the same loop drawn as a flow: read → compute → CAS commits, with the single-thread "no contention → immediate win" path highlighted in amber. Follow the white arrows left-to-right, then down into the success box.

Figure — std - atomic — lock-free operations

Cell C — high contention limiting behaviour

Worked example Three threads racing one CAS-loop counter (Cell C)

Three threads each want to run +1 on the same value once, all via a CAS loop, all arriving at the same instant. 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: what final value? And in the worst case, how many total CAS attempts (successes + failures) happen across all threads?

Step 1 — final value is deterministic. Whatever the order of winning, each thread lands exactly one +1. Final $= 0 + 3 = 3$ . Why this step? Correctness (the value) never depends on contention — only performance does. relaxed is safe: the count is self-contained.

Step 2 — count successes. Exactly one success per thread ⇒ $3$ successful CAS. Why this step? A success is the moment a thread's +1 is committed; there are three +1s.

Step 3 — count worst-case failures. Order the winners 1st, 2nd, 3rd. The 1st wins immediately (0 failures). The 2nd was holding a stale old, fails once, refreshes, wins (1 failure). The 3rd fails behind both earlier winners: $2$ failures. Worst-case failures $= 0 + 1 + 2 = 3$ . Why this step? This shows lock-free ≠ wait-free: a thread can spin. Total attempts $= 3 successes + 3 failures = 6$ .

Verify: final $= 3$ ; worst-case total attempts $= 3 + \frac{3 ( 3 - 1 )}{2} = 3 + 3 = 6$ . The failure count is the arithmetic series $0 + 1 + \dots + (n - 1) = \frac{n ( n - 1 )}{2}$ for $n = 3$ . ✓

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

Worked example Producer publishes data, consumer reads it (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: with correct orders, what does the consumer read for data? What could it read with relaxed?

Step 1 — producer seals the package. release on the store pins data = 42 to happen before ready becomes visible. Why this step? Release means "no write before me may slip after me" — the 42 is inside the sealed box.

Step 2 — consumer opens after receiving. acquire on the load means once it sees ready == true, all writes the producer did before its release are also visible. Why this step? This forms the synchronizes-with edge. See the memory model.

Step 3 — the guaranteed read. Consumer reads data == 42. Why this step? The acquire/release pair is a one-way gate; data cannot still be $0$ .

Verify: correct orders ⇒ data == 42 guaranteed. With relaxed on both, the compiler/CPU may let the consumer see ready == true while data is still 0 — a real, non-deterministic bug. The number itself is 42 whenever the guarantee holds. ✓

The figure below draws this as a one-way gate between two threads: the amber synchronizes-with arrow is the only channel, and everything the producer wrote above its release is forced across it before the consumer's acquire lets execution proceed. Read the producer column top-down, cross the amber arrow, then read the consumer column.

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

Worked example Why "atomic + obvious code" still loses updates (Cell E)

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

Forecast: is the final value guaranteed to be 2 000 000?

Step 1 — decompose the line. a = a + 1 is int tmp = a.load(); a.store(tmp + 1); — two atomic ops with a gap between them. Why this step? Only member functions/overloaded operators are single atomic ops; a general expression is not.

Step 2 — show the interleave. Thread A loads 5, Thread B loads 5, both store 6. One increment vanishes — exactly the plain-int bug, resurrected. Why this step? Atomicity of each op does not chain into atomicity of the pair.

Step 3 — the fix. Use a.fetch_add(1) or ++a (member operator), which is one RMW. Why this step? One indivisible instruction closes the gap.

Verify: fetch_add/++a version → exactly $2 \times 1000000 = 2000000$ . The a = a + 1 version → not guaranteed 2000000 (can be less). ✓

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

Worked example Lock-free stack: push and the 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)) {}
}

Two threads push 10 and 20 onto an initially empty stack. Forecast: after both pushes, how many nodes, and what is head->v?

Step 1 — the zero/degenerate case. Initially head == nullptr. The first n->next is nullptr — a valid, non-crashing starting point. Why this step? We must check the empty case: CAS against nullptr still works; there is nothing to trip over.

Step 2 — the single-winner boundary. If both threads read head == nullptr at once, only one CAS succeeds (say pushes 10). The loser's CAS fails, refreshes n->next to the new head (the 10-node), retries, succeeds. Why this step? CAS guarantees exactly one winner per round — the boundary "both try simultaneously" resolves cleanly.

Step 3 — why the success order MUST be release. The new Node{v, ...} writes to n->v and n->next before the CAS publishes n into head. A popping thread does an acquire load of head, then dereferences the node. If our success CAS were relaxed, those field writes could be reordered after the pointer became visible — a popper would read uninitialized v/next. release pins the initialization before publication, matching the popper's acquire. Why this step? This is the load-bearing edge case: pointer visible ⇒ its contents must already be visible. Failure path stays relaxed because a failed CAS publishes nothing.

Step 4 — count the result. Two successful pushes ⇒ 2 nodes. The last pusher's node is on top, so head->v = the value pushed last. Why this step? Push prepends, so top = whichever won last (10 or 20).

Verify: node count $= 2$ ; empty→push→push never dereferences nullptr because CAS reads nullptr as a plain value, not a pointer to follow. Top value is whichever won last (10 or 20), both valid, and its fields are guaranteed initialized thanks to the release. ✓

Cell G — real-world word problem: one seat, many buyers

Worked example Ticket booking — 1 seat, 4 threads try to book it (Cell G)

A concert has 1 seat left. Four booking threads each try to claim it. Model the seat as available/taken:

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: how many threads succeed? How many try_book calls return false?

Step 1 — model with CAS. "Book only if still free" is exactly compare (free?) and swap (to taken). Why this step? CAS is the natural tool: it atomically checks the pre-condition and commits in one step, so no two buyers can both see "free".

Step 2 — exactly one winner. The first thread finds taken == false, swaps to true, returns true. The other three now find taken == true, so expected (which was false) ≠ actual → CAS returns false. Why this step? _strong is right here — this is a single, non-looped check, so no spurious-failure allowance is needed.

Step 3 — why keep seq_cst. Booking touches money and audit logs; a single global total order of "who booked when" is worth the cost, so we keep the default rather than relaxing it. Why this step? It shows the default is deliberately chosen, not forgotten.

Step 4 — tally. Successes $= 1$ , failures $= 4 - 1 = 3$ . Why this step? One seat can be sold once; three buyers are correctly rejected — no double-booking.

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

Cell H — exam twist: spurious failure & the ABA surprise

Worked example

weak fails "for no reason" — is the count wrong? (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; }

Suppose the CPU makes compare_exchange_weak fail spuriously twice, even though a is still 7, then succeeds. Forecast: what is final a, and does the spurious failure corrupt the result?

Step 1 — what a spurious failure does. weak may return false even when a == old. On failure it reloads old from a (still 7). Why this step? This is by design — cheaper on some CPUs (e.g. LL/SC architectures). The loop is meant to absorb it. Note weak is only safe inside a loop; naming relaxed keeps the (self-contained) value cheap.

Step 2 — the loop retries. old is refreshed to 7 (unchanged), we recompute old + 1 = 8, try again. After 2 spurious fails, the 3rd attempt commits. Why this step? Because the value never actually changed, each retry recomputes the same desired value — no drift.

Step 3 — result & attempt count. Final a = 8. attempts (failures counted) $= 2$ ; total CAS calls $= 3$ . Why this step? Spurious failure costs time, never correctness. Using _strong here would remove the spurious fails but is slower in loops.

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

Recall Quick self-test: name the cell

A fetch_add(1, relaxed) counter is correct because... ::: each op is one indivisible RMW; relaxed keeps atomicity, only cross-variable ordering is dropped (Cell A). Worst-case CAS failures for $n$ colliding threads ::: $\frac{n ( n - 1 )}{2}$ , quadratic — lock-free is not wait-free (Cell C). Why is a = a + 1 on an atomic still buggy? ::: it is load-then-store (two ops with a gap), not one RMW; use fetch_add/++a (Cell E). In a lock-free push, why must the successful CAS be a release-store? ::: so the new node's fields (v, next) are published before the head pointer becomes visible; else a popper reads uninitialized data (Cell F). One seat, four buyers, how many succeed? ::: exactly one; CAS gives a single winner (Cell G). Does a spurious weak failure change the final value? ::: no — only costs extra loop iterations; correctness is untouched (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

Worst-case number of failed CAS attempts for n threads colliding on one loop?

The arithmetic series 0+1+...+(n-1) = n(n-1)/2, showing lock-free is not wait-free.

In the ticket-booking (one seat, four buyers) example, why use compare_exchange_strong not weak?

It is a single non-looped check, so we must not tolerate spurious failures; strong never fails spuriously.

What is the ABA problem?

CAS compares values not history; if a value goes A to B back to A, CAS wrongly succeeds. Fix with version tags or hazard pointers.

Why must the successful CAS in a lock-free stack push use memory_order_release?

To publish the new node's initialized fields before the head pointer is visible, so an acquiring popper never reads uninitialized data.