Foundations — Atomic operations and CAS

Before you can read the parent note, you must be fluent in a small pile of words and squiggles it uses without pausing to explain. We build them one at a time, each on top of the last. Nobody here is assumed to know what a pointer, a race, or a *addr means — we start from a shelf of numbered boxes.

1. Memory as a wall of numbered boxes

Look at the figure. The gray row is memory. The number under each box (0, 1, 2, …) is its address — it never changes. The number inside a box is its value — this can change. This one distinction (address vs. value) is the source of almost every confusion later, so hold it firmly.

Why the topic needs this: atomic operations always act on one specific box. The whole game is "who gets to change the number inside this box, and when."

2. The pointer *addr — an arrow to a box

Two symbols, two jobs:

• addr — the arrow itself (which box).
• *addr — following the arrow to read/write the number in that box.

In the figure the orange arrow is addr; it holds the number 200, so it points at box 200. Writing *addr = 7 means "put 7 into the box the arrow points at." Writing *addr = *addr + 1 means "read box 200, add one, put the result back into box 200."

Why the topic needs this: CAS's first argument is always a pointer (CAS(addr, ...)). It must know which box to guard before it can guard it.

3. Read-Modify-Write (RMW) — the three-step move

counter = counter + 1 looks like one line, but the CPU does:

1. R — read the number in the box (say 10),
2. M — compute 10 + 1 = 11,
3. W — write 11 back into the box.

Why the topic needs this: the entire danger the parent note opens with lives in the gaps between R, M, and W. If those three steps are not glued together, a second worker can sneak in.

4. Threads — many hands, one wall

Picture two hands reaching for the same box. Nothing stops both from grabbing it — unless the hardware provides a rule. That rule is what atomics give us.

5. Interleaving and the race window

Follow the time axis (left → right) in the figure. Both threads read 10 before either writes. Both compute 11. Both write 11. Two increments happened but the counter only moved by one — a lost update. The dashed red region between a thread's Read and its Write is the race condition window: the gap where another thread's write can poison your assumption.

Why the topic needs this: the parent note's opening story ("expected 12, got 11") is this figure.

6. The math notation ←, =, and cases {

The parent note writes formulas like $\ast addr\leftarrow new$. These arrows and braces are not scary — here is each one.

So the parent's CAS formula $\text{CAS}(addr,expected,new)⟹\{\begin{array}{ll}\ast addr\leftarrow new,& \text{if }\ast addr=expected\\ \text{no change},& \text{if }\ast addr\ne expected\end{array}$ now reads in plain English: "Look at the box. Compare its value to expected. If they match, assign new into the box. Otherwise, leave it alone." The $\ne$ symbol just means "not equal."

Why the topic needs this: every atomic primitive in the parent (Fetch-And-Add, Test-And-Set, Swap, CAS) is written with exactly these three symbols.

7. true/false and the retry loop

The figure shows the loop as a cycle: read → compute → attempt. A green exit leaves the loop on success; a red arrow curls back on failure. This is the skeleton of every lock-free algorithm you'll meet in Lock-Free Data Structures.

Why the topic needs this: without the retry loop, a single CAS failure would lose your work. The loop is what turns "detect interference" into "handle interference."

8. Cache lines and coherence — where atomicity physically happens

You don't need the full protocol yet (that's a later dive) — just know that "locking one cache line" is how the hardware provides the zero-width window from §5, and it's cheaper than freezing the whole bus.

9. Instruction reordering — why memory barriers exist

The parent's tags ${\text{CAS}}_{acquire}$, ${\text{CAS}}_{release}$, ${\text{CAS}}_{seq\_cst}$ are just three strengths of this fence, glued onto the CAS. You only need to know that a fence exists for D1; strengths come later.

Prerequisite map

Read it top-down: numbered boxes and threads are the ground floor; the race window forces the need for atomicity; atomicity plus the math notation and the retry loop combine into CAS; cache lines and barriers explain how it all works on real silicon.

Equipment checklist

Cover the right side and answer aloud. If any stalls you, reread that section before opening the parent note.