Atomic operations and CAS: Visual walkthrough — Hardware deep dive

Before line one, three plain-word definitions so no symbol is unearned:

Step 1 — Draw the desk: one box, two workers

WHAT. We set the scene. One memory box named counter holding the number $10$ . Two threads, call them T1 (burnt orange) and T2 (deep teal), each want to do counter = counter + 1. The correct final answer is $12$ .

WHY. You cannot spot a race until you can see both timelines side by side. Time flows downward; each thread's actions are dots on its own vertical line.

PICTURE. The box sits in the middle. Each worker has an arrow reaching in to read and an arrow reaching out to write. Nothing has happened yet — this is time zero.

Step 2 — Interleave the timelines: the lost update

WHAT. We now place T1's three motions and T2's three motions on the same clock, but let the operating system interleave them badly: T2 sneaks in between T1's read and T1's write.

WHY. This is the whole disease. Because $R$ and $W$ are separate, another worker can read the stale value $10$ before the first worker has written $11$ back. Both compute $11$ . Both write $11$ . One increment vanished.

PICTURE. Follow the numbered clock ticks. The red "!" marks the exact instant the damage becomes unavoidable — the moment T2 reads $10$ while T1 is still holding it.

$T1 reads 10 \to T2 reads (stale!) 10 \to T1 writes W (11) \to T2 overwrites W (11)$

The first $10$ — what T1 saw.
The second $10$ — what T2 saw because T1 had not written yet. This staleness is the bug.
Both $W (11)$ — two workers install the same answer; the second flattens the first.

Step 3 — Introduce the atomic weapon: CAS as a challenge coin

WHAT. We define the single hardware instruction we are allowed to use.

\begin{cases} \texttt{*addr} \leftarrow \texttt{new}, & \text{return } \textbf{true} \quad \text{if } \texttt{*addr} = \texttt{exp}\\[4pt] \text{leave box alone}, & \text{return } \textbf{false} \quad \text{if } \texttt{*addr} \neq \texttt{exp} \end{cases}$$ Term by term: - $\texttt{addr}$ — *which* box we are gambling on (the address of `counter`). - $\texttt{exp}$ — the value we *expect* to still be there. This is our claim "nobody touched it since I read." - $\texttt{new}$ — the value we want to install if our claim holds. - The whole comparison-and-write happens ==indivisibly== — no worker can slip between the compare and the swap. **WHY *this* tool and not a plain write?** A plain write is unconditional — it stomps whatever is there. CAS is a *conditional* write: it only fires **if reality still matches your expectation**. That single word "if" is what lets a worker *detect* that someone interfered, instead of blindly clobbering them. **PICTURE.** Think of a challenge coin. You show the guard the coin you *expect* (`exp`). If it matches the coin on the table (`*addr`), the swap happens and you get **true**. If someone swapped the table coin already, no swap, you get **false** — and crucially, you *know* it. ![[deepdives/dd-hardware-6.1.09-d2-s03.png]] --- ## Step 4 — The successful CAS: our expectation holds **WHAT.** T1 does the full recipe with CAS: read $10$, compute $11$, then $\text{CAS}(\texttt{counter}, 10, 11)$. No one interfered, so `*counter` is still $10$, matches `exp` $=10$, swap fires. **WHY.** This is the happy path — the case where the loop we are about to build runs exactly once. We must see success cleanly before we complicate it with failure. **PICTURE.** The green check marks the compare succeeding ($10 = 10$); the arrow shows $11$ being written; CAS returns **true**. ![[deepdives/dd-hardware-6.1.09-d2-s04.png]] $$\text{CAS}(\texttt{counter},\ \underbrace{10}_{\texttt{exp}=\ \texttt{*counter}},\ \underbrace{11}_{\texttt{new}}) = \textbf{true} \quad\Rightarrow\quad \texttt{counter}=11$$ --- ## Step 5 — The failing CAS: expectation broken, and why that is GOOD **WHAT.** Now replay Step 2's bad interleaving, but with CAS. T1 read $10$. Before T1's CAS, T2 sneaks a full increment in, so `counter` is now $11$. T1 fires $\text{CAS}(\texttt{counter}, 10, 11)$. But `*counter` is $11 \neq 10 =$ `exp`. **No swap. Returns false.** **WHY.** In Step 2 a plain write here silently destroyed T2's work. CAS instead *refuses* and *reports* the collision. The lost update becomes a **detected** update. Detection is half the battle — the other half (Step 6) is retrying. **PICTURE.** The red cross marks the compare failing ($10 \neq 11$); the box is left untouched at $11$; CAS returns **false**. Notice T2's increment survives. ![[deepdives/dd-hardware-6.1.09-d2-s05.png]] $$\text{CAS}(\texttt{counter},\ \underbrace{10}_{\texttt{exp (stale!)}},\ 11) = \textbf{false} \quad\Rightarrow\quad \texttt{counter still }=11,\ \text{T1 must retry}$$ --- ## Step 6 — Close the loop: retry with fresh eyes **WHAT.** We wrap read-compute-CAS in a `do … while (!CAS(...))`. On failure, we loop back, **re-read** the now-current value, recompute, and try again. ```c void atomic_increment(int* counter) { int old_val, new_val; do { old_val = *counter; // (a) re-read fresh each time new_val = old_val + 1; // (b) recompute from fresh value } while (!CAS(counter, old_val, new_val)); // (c) gamble; retry if false } ``` **WHY each line?** - `(a)` re-reading is *mandatory* on retry — Step 5 showed the old `old_val` is now a lie. Fresh read = honest `exp`. - `(b)` recompute so `new_val` is built on the *current* reality, not the stale one. - `(c)` `!CAS` means "loop while the swap failed." Success exits the loop; failure spins us back to `(a)`. **PICTURE.** T1's second lap: it re-reads $11$, computes $12$, and $\text{CAS}(\texttt{counter}, 11, 12)$ now matches → **true** → final answer $12$. The lost update is *cured* without a single lock. ![[deepdives/dd-hardware-6.1.09-d2-s06.png]] > [!intuition] Why this never sleeps and never deadlocks > A [[Spinlocks and Mutexes|lock]] makes losers *wait*. The CAS loop makes losers *retry immediately with fresh data*. Someone always makes progress on every round — that "someone always wins" property is what [[Lock-Free Data Structures|lock-free]] means. --- ## Step 7 — The degenerate cases you must still survive **WHAT.** Every case, spelled out so no scenario ambushes you: | Case | What happens | Loop behaviour | |------|--------------|----------------| | **No contention** (one thread) | first CAS matches `exp` | runs exactly once, like Step 4 | | **Contention** (Step 5) | CAS fails once, re-reads, wins | 2+ laps, always terminates for *one* winner | | **Heavy contention** (N threads) | many failures | still exactly *one* winner per round → system always progresses | | **The A→B→A trap** | value returns to `exp` after changing | CAS wrongly succeeds — see below | **WHY the last row is special.** CAS compares *values*, not *history*. If `counter` (or a pointer) goes $A \to B \to A$, the final $A$ matches your `exp` and CAS fires — even though the world changed underneath you. This is the ==ABA problem==. **PICTURE.** Left: normal failure, CAS correctly says false. Right: the ABA sneak — the value cycled back to $A$, so CAS says **true** but you are acting on stale structure. The fix is a ==version counter==: pair the value with a monotonically increasing tag, and CAS the *pair*, so $A_{\text{v3}} \neq A_{\text{v1}}$. ![[deepdives/dd-hardware-6.1.09-d2-s07.png]] > [!recall]- When exactly does the plain CAS loop break? > The plain value-only CAS loop is unsafe precisely when a value can ==return to a previously-seen state== between your read and your CAS (A→B→A). Fix ::: pair the value with a version counter (tagged pointer / double-width CAS) so identical values with different histories no longer compare equal. See [[ABA Problem Solutions]]. --- ## The one-picture summary Everything above compressed: a decision loop. Read fresh → compute → CAS. If **true**, done. If **false**, someone interfered, loop back and read again. No locks, no waiting, one guaranteed winner per round. ![[deepdives/dd-hardware-6.1.09-d2-s08.png]] ```mermaid flowchart TD A["read old_val from box"] --> B["new_val = f of old_val"] B --> C["CAS box old_val new_val"] C -->|"true = I won"| D["done"] C -->|"false = interfered"| A ``` > [!recall]- Feynman retelling — say it in plain words > Two workers share one number. The bug: worker one picks up a 10, and before he writes 11 back, worker two also picks up the 10 — now both write 11 and one increment is *lost*, because reading and writing are separate motions with a gap between them. > > CAS fixes this by being a *conditional* write. You tell the hardware: "swap this box to 11, but **only if** it still holds the 10 I saw." In one indivisible tick the hardware checks and swaps. If it still held 10 → done. If somebody changed it → CAS refuses and tells you *false*, so you now *know* you were interfered with, instead of silently clobbering. > > Knowing you failed, you just **read again** (the fresh value), recompute, and try once more. Loop until you win. Because each round exactly one worker's CAS matches, someone always makes progress — no locks, no waiting. > > The one gotcha: CAS only looks at the *value*, not its *history*. If the value wanders away and comes back to the same number (A→B→A), CAS is fooled into thinking nothing changed. The cure is to staple a version counter onto the value so "the same number, later in time" no longer looks equal. > [!mnemonic] The loop in four beats > **R**ead fresh · **C**ompute · **C**AS · **R**etry-if-false. And for the trap: **A**lways **B**e **A**ware of the value that came back. Related depth: [[Memory Consistency Models]] · [[Memory Barriers]] · [[Cache Coherence Protocols]] govern *when* other threads see your winning swap.