Memory consistency models: Visual walkthrough — Hardware deep dive

Parent: Memory consistency models · Hinglish: यह Hinglish में पढ़ो →

We assume you have never seen a store buffer, a "reordering", or the arrows S→L. We earn every one.

Step 1 — What "memory" even looks like to two cores

WHAT. Draw the machine. Two little processors (we call each a core — one independent instruction-runner) sitting on top of one shared box of memory. Memory is just a wall of numbered mailboxes; two of them are named x and y, both starting at 0.

WHY start here. Before we can say "the load read a stale value," we must agree on where values live and who can see them. A value is "visible to a core" only once it has reached the shared memory wall — not while it is still sitting inside a core. That distinction is the whole story, so we picture it first.

PICTURE. The two cores in magenta and violet; the shared memory wall in the middle holding x=0, y=0.

Step 2 — The program each core runs (the litmus test)

WHAT. Give each core two instructions. This exact 4-instruction pattern is the Store Buffering test (a.k.a. Dekker).

S_{1} x = 1; L_{2} r1 = y S_{3} y = 1; L_{4} r2 = x

Reading each symbol where it sits:

$S_{1}$ — Core 1's Store: put 1 into mailbox x.
$L_{2}$ — Core 1's Load: copy mailbox y's current value into Core 1's private slot r1.
$S_{3}$ , $L_{4}$ — the mirror image on Core 2: write y, then read x.

WHY these four. Each core writes its own variable, then reads the other's. So each core's answer (r1, r2) is a snapshot of "had the other core's write reached memory yet?" That makes the pair of results a direct probe of ordering.

PICTURE. The two programs side by side, with $S$ (store) tinted orange and $L$ (load) tinted violet, arrows showing which mailbox each touches.

Recall The forecast

Before reading on, predict: can we finish with r1 == 0 and r2 == 0? Naive single-timeline reasoning ::: says no — one store must happen first, so its reader can't miss it.

Step 3 — The naive "one timeline" world (Sequential Consistency)

WHAT. Imagine a single global clock. Every instruction from either core is threaded onto one timeline, and each core's two instructions keep their program order. This is Sequential Consistency (SC).

WHY picture the strong model first. To feel why real hardware surprises us, we first see the world where nothing surprising happens. In SC, a store is globally visible the instant it executes — there is no "inside a core" limbo.

PICTURE. All four ops threaded on one arrow of time. We test the bad outcome and get a loop.

Now the contradiction, symbol by symbol. Write $a <_{m} b$ to mean " $a$ happens before $b$ on the single timeline."

r1 == 0 means Core 1 read y before y was written: $L_{2} <_{m} S_{3}$ .
r2 == 0 means Core 2 read x before x was written: $L_{4} <_{m} S_{1}$ .
Program order forces $S_{1} <_{m} L_{2}$ and $S_{3} <_{m} L_{4}$ .

Chain them:

S_{1} <_{m} L_{2} <_{m} S_{3} <_{m} L_{4} <_{m} S_{1}

Every symbol here is a position on the one timeline; the chain says $S_{1}$ is strictly before itself — impossible. So under SC the double-zero outcome is forbidden. Good — that matches our forecast.

Step 4 — Enter the store buffer (why real hardware differs)

WHAT. Give each core a private store buffer: a small FIFO queue that catches a store the instant the core issues it, lets the core move on immediately, and drains the store into shared memory later.

WHY it exists. Writing all the way to shared memory (through the cache system, see Cache Coherence) is slow. Making the core wait would waste hundreds of cycles. So the core drops its write into this local mailbox-in-waiting and races ahead — classic out-of-order speed hacking.

PICTURE. Each core now has an orange FIFO buffer between it and the memory wall. x=1 is sitting in Core 1's buffer, not yet on the wall.

Step 5 — The bypass: a load overtakes a not-yet-visible store

WHAT. Trace one core. Core 1 executes $S_{1}$ : x=1 drops into its buffer (not the wall). Core 1 immediately runs $L_{2}$ : read y. It looks in its own buffer for y — nothing there (it only wrote x) — so it reads y straight from the wall, which still says 0. So $L_{2}$ completes while $S_{1}$ is still stuck in the buffer.

WHY this is the crucial move. The load $L_{2}$ has now finished before the store $S_{1}$ became globally visible. From the outside world's view, Core 1's load happened before its store. That is exactly the reordering the parent note names:

S \to L reordering: a S tore may be overtaken by a later L oad.

Each label: S = the buffered store $S_{1}$ ; L = the later load $L_{2}$ ; the arrow " $\to$ " is program order; the whole thing being allowed is TSO's one relaxation (its "one sin").

PICTURE. A violet load-arrow leaping over the orange buffered store, reaching the wall first.

Step 6 — Both cores do it at once ⇒ double zero

WHAT. Run the exact same trick on both cores, interleaved:

x=1 → Core 1's buffer (wall still x=0).
y=1 → Core 2's buffer (wall still y=0).
Core 1 reads y from the wall → r1 = 0.
Core 2 reads x from the wall → r2 = 0.
Later, both buffers drain; the wall finally becomes x=1, y=1 — but the loads already happened.

WHY it works now. In Step 3 the double-zero needed a timeline loop and died. Here there is no single timeline: each store lives in a private buffer, invisible to the other core, at the moment of the reads. The cycle $S_{1} < L_{2} < S_{3} < L_{4} < S_{1}$ never forms because " $<_{m}$ " (a global order of visible events) no longer contains the buffered stores at read-time. The paradox dissolves.

PICTURE. Snapshot of the instant of both loads: both buffers hold a 1, both loads pull 0 off the wall.

Step 7 — The degenerate & edge cases (so nothing surprises you)

WHAT. Walk every remaining outcome and the boundary conditions.

WHY. A contract must cover all inputs. If we only showed the flashy double-zero we'd have hidden three ordinary outcomes and two boundary behaviours.

The four possible result-pairs of the SB test:

`r1`	`r2`	How it happens	Allowed on TSO?
0	1	Core 1 read `y` early; Core 2 read `x` after it drained	✅ (also SC)
1	0	Mirror image of the row above	✅ (also SC)
1	1	Both buffers drained before either load	✅ (also SC)
0	0	Both loads ran while both stores were buffered	✅ TSO only, ❌ SC

Boundary cases:

Buffer drains instantly (empty buffer): behaves exactly like SC — you simply never observe 0,0. So SC is the special case of TSO where stores are never late.
Insert a fence between store and load on each core: `MFENCE` drains the buffer before the load runs, so the buffered store reaches the wall first. The bypass of Step 5 is now forbidden → the 0,0 row disappears. This is the same acquire/release idea C++ and locks use.
Same variable on both sides (x=1; r=x): the load hits its own buffer via store-forwarding and reads 1, never 0. Coherence, not consistency, governs a single address — the buffer can't hide a value from the core that wrote it.

PICTURE. The 2×2 outcome grid; the 0,0 cell glowing, with a fence padlock that greys it out.

The one-picture summary

Everything above, compressed: SC = one honest timeline (no double-zero). TSO = private FIFO buffers let a load bypass a not-yet-visible store (S→L), so both cores can read 0. A fence drains the buffer and restores SC exactly where you need it.

Recall Feynman retelling — the whole walkthrough in plain words

Two kids, Anna and Bob, each have an outbox on their desk and a shared bulletin board on the wall. The rule for each kid alone: do things top-to-bottom. Anna writes "x=1" but instead of walking to the wall she tosses it in her outbox and immediately turns to read whatever's on the wall for "y" — still the old 0. Bob does the mirror. So both read the old 0, and only afterwards do their notes get pinned up. Nobody broke their own top-to-bottom rule, yet an outsider watching the wall sees each kid read before they wrote. That's the store buffer's S→L bypass. If Anna truly needs her write pinned before she reads, she yells "FENCE!" and waits by the wall until her note is up — slow, but now the double-zero can never happen. The memory model is just the posted class rule saying which of these surprises the wall is allowed to show.

Recall Quick self-check

Why can't the SC contradiction cycle form under TSO? ::: Because the buffered stores aren't in the global visible-order at load time, so the chain $S_{1} < L_{2} < S_{3} < L_{4} < S_{1}$ never closes. Which single ordering does TSO relax? ::: S→L (a store may be overtaken by a later load). What does a fence physically do here? ::: Drains the store buffer, forcing the store to become globally visible before the following load runs.