Visual walkthrough — std - atomic — lock-free operations

This is the visual companion to the parent note. If a word here feels unexplained, it is built on this page — start at Step 1.

Step 1 — What is a "shared variable", really?

WHAT. Two threads, one box in memory called counter. A "thread" is just an independent worker running its own instructions; both workers can reach into the same box.

WHY start here. Before we can talk about a race, we must agree that the danger only exists when two workers touch one box. If each had its own box, nothing could go wrong. So the whole problem lives in the word shared.

PICTURE. Two chalk stick-figures (threads) each with an arrow pointing at the same yellow box. That single shared box is the entire battlefield.

Step 2 — Unfolding counter++ into three moves

WHAT. The innocent-looking counter++ is not one action. The CPU cannot add to memory by wishing; it must:

$\underset{\text{copy box}\to \text{register}}{\underbrace{\text{load}}}⟶\underset{\text{work in register}}{\underbrace{\text{add }1}}⟶\underset{\text{register}\to \text{box}}{\underbrace{\text{store}}}$

• load — reads the box's value into a tiny fast scratchpad inside the core called a register.
• add 1 — the arithmetic happens only in the register, not in the box.
• store — writes the register's new value back into the box.

WHY unfold it. The bug is invisible until you see the three sub-steps. The gap between load and store is where a second thread sneaks in. A three-move sequence like this is called a read-modify-write (RMW).

PICTURE. A single timeline with three chalk beads — load, add, store — and a bracket underneath labelling the whole thing "one RMW = three separate moments".

Step 3 — Watching the lost update happen

WHAT. Now interleave two threads, A and B, both doing the three moves. Both load the box while it still holds 5. Both compute 6. Both store 6.

WHY this exact interleaving. It is the simplest bad schedule — no exotic timing needed. Two increments were intended (5 → 7), but the box ends at 6. One increment evaporated. This is the "lost update" the parent note warns about, shown as motion.

PICTURE. Two parallel timelines. Watch the pink arrow: B's load reads 5 after A's load but before A's store, so B never sees A's 6. Both stores land on 6.

Step 4 — The fix in hardware: hold the cache line

WHAT. Memory does not travel byte-by-byte; the core pulls a whole chunk — a cache line (typically 64 bytes) — into its private cache. The magic instruction (x86 LOCK XADD) says to the coherency protocol: "give me exclusive ownership of this line and don't let anyone else touch it until my load-add-store finishes."

WHY this closes the gap. In Step 3 the bug lived in the gap. Exclusive ownership means no other core can load between our load and our store — the gap is sealed. One instruction, atomic by hardware, no software lock. That is lock-free.

PICTURE. The shared box now sits inside a chalk-outlined cache line. Thread A holds a glowing "exclusive" padlock-of-ownership over the whole line; Thread B's arrow is stopped at the boundary with a red bar until A is done.

Step 5 — The universal primitive: Compare-And-Swap

WHAT. Not every RMW has a dedicated instruction (there is no LOCK XSTACKPUSH). So the CPU offers one general atomic gate — compare-exchange — from which any RMW is built:

Term by term:

• $a$ — the shared atomic box.
• $\text{expected}$ — the value we believe is in the box (our last reading).
• $\text{desired}$ — the value we want to write, only if our belief is still true.
• return true — we won; the box is now desired.
• return false — someone changed a; CAS refreshes expected with the real current value so we can retry.

WHY CAS and not a plain store. A plain store overwrites blindly — that is exactly the Step 3 bug. CAS writes only if nothing changed since we looked. That single conditional test-and-set is enough to build every lock-free structure. See Compare-And-Swap for the full theory.

PICTURE. A gate: our expected key is compared against the box's real lock. Match → gate opens, desired flows in (true). Mismatch → gate stays shut, and the box's true value is copied back into our expected slot (false).

Step 6 — The CAS retry loop (optimistic concurrency)

WHAT. Wrap CAS in a loop so a losing thread simply tries again:

T old = a.load();                                   // read
while (!a.compare_exchange_weak(old, f(old))) { }   // try; on fail, old is refreshed

• old — snapshot of the box.
• f(old) — the new value we want (e.g. old + 1, or a new stack head).
• compare_exchange_weak — writes f(old) only if the box still equals old; otherwise it puts the fresh value into old and we loop.

WHY a loop guarantees progress. Every time a thread fails, it failed because another thread succeeded. So the system as a whole always moves forward — that is the definition of lock-free. This is optimistic concurrency: assume no conflict, verify at write time, retry only on the rare clash.

PICTURE. A flow: read → compute → CAS. Green edge "success" exits; pink edge "someone changed it" loops back with old refreshed. Under low contention the loop runs once.

Step 7 — Degenerate & edge cases you must not skip

WHAT / WHY — walk every corner:

1. Single thread. No sharing → no race. fetch_add still works but the atomicity is unused overhead; a plain int would be correct here. (Step 1's battlefield is empty.)
2. counter = counter + 1 on an atomic. This is a load then a store — two atomic ops with a gap between them — so the Step 3 bug returns. Only fetch_add / ++counter (the member operator) is one RMW.
3. High contention. Many threads → the CAS loop of Step 6 may spin many times; a Mutex and Lock can sometimes win. Lock-free is not automatically faster — measure.
4. Not actually lock-free. For a big T, the library may fall back to an internal lock. Check with a.is_lock_free() or std::atomic<T>::is_always_lock_free.

PICTURE. Four small chalk panels: (1) lone figure, no conflict; (2) atomic box with a reopened gap between load and store; (3) a crowd of figures all spinning on one gate; (4) a box wearing a hidden padlock stamped "not lock-free".

Step 8 — Why relaxed order is enough here (and when it is not)

WHAT. In fetch_add(1, memory_order_relaxed) we drop all cross-variable ordering and keep only atomicity.

WHY it is safe for a counter. We only care that the count is correct, not that it is ordered relative to other variables. Atomicity (Step 4) is preserved regardless of order — memory order only controls visibility of surrounding writes, which a pure counter has none of. So relaxed is the cheapest correct choice.

WHEN it breaks. If another variable's visibility depends on this op (the producer/consumer flag in the parent), you need release/acquire. A counter that also signals readiness is no longer "just a counter".

PICTURE. Left: a lone counter — the "ordering gate" is greyed out, only the atomic core glows (relaxed is fine). Right: a counter paired with a data write — now a release/acquire gate must connect the two threads.

The one-picture summary

Everything on one board: the three-move RMW, the sealed cache line that makes it atomic, and the CAS retry loop that generalises it — the two engines of every lock-free algorithm.

Recall checks: