Exercises — Memory models — sequential consistency, TSO, relaxed

Permitted: Store → Load (a later load may complete before an earlier store becomes globally visible, because the store waits in the store buffer). Forbidden: Store→Store, Load→Load, Load→Store. Why: TSO = SC + one relaxation. The one relaxation is the store buffer, and a store buffer only lets a store slip behind a later load; it never reorders two stores, two loads, or a load ahead of a store.

Class: Relaxed / weak. Real ISAs: ARM and POWER (also RISC-V RVWMO). "Restricted only by per-location coherence" means: the machine still keeps a single agreed order of writes to each individual location, but imposes no cross-location order unless you ask. See Memory Barriers and Fences for how you re-impose order there.

(a) SC — FORBIDDEN. SC means some single total order of all four operations, respecting each thread's program order. For r1 == 0, T1's load of y must come before T2's store y = 1. For r2 == 0, T2's load of x must come before T1's store x = 1. Combined with program order (x=1 before r1=y, and y=1 before r2=x) we get the cycle $(x=1)<(r1=y)<(y=1)<(r2=x)<(x=1),$ a contradiction ($<$ is a strict total order, so nothing can precede itself). Hence (0,0) cannot appear. Look at the red cyclic arrows in the figure below — a total order can have no cycle.

(b) TSO — ALLOWED. x = 1 enters T1's store buffer and is not yet globally visible. T1's r1 = y (a later load) executes immediately via the permitted W→R reordering and reads the still-global y = 0. Symmetrically x = 1 is buffered in... T2 reads global x = 0. Both stores drain later. Outcome (0, 0). This is real x86 behaviour.

TSO — NO, r is always 42. Both operations of T1 are stores, so they are a Store→Store pair, which TSO keeps in order. Both operations of T2 are loads (of flag, then of data), a Load→Load pair, which TSO keeps in order. So if T2 saw flag == 1, the earlier data = 42 is already globally visible ⇒ r == 42. TSO gives "free publication".

Relaxed — YES, r == 0 is possible. Either flag = 1 becomes visible before data = 42 (W→W reorder), or T2's load of data completes before its load of flag (R→R reorder). Nothing ties the two propagations together. See C++ Atomics and memory_order for the release/acquire fix.

Between the store and the load in each thread:

T1:  x = 1;  MFENCE;  r1 = y;
T2:  y = 1;  MFENCE;  r2 = x;

Why: the illegal outcome existed only because the store sat buffered while the load jumped ahead. MFENCE drains the store buffer — x = 1 becomes globally visible — before r1 = y may execute. Now at least one thread's store is visible before the other's load, breaking the cyclic dependence from L2.1. Cost: a global round-trip per fence.

One fence is not enough — you need it in both threads. If only T1 fences, T2's W→R reorder still lets both reads see 0 (T2 stores y=1 to its buffer and reads stale x=0 while T1 hasn't reached the fence yet).

The dangerous pair is flag[i] = true (a store) followed by the read of flag[j] inside the while (a load) — a Store→Load pair, exactly the one TSO reorders. If both threads let their flag[i] store sit buffered and each reads the other's still-false flag[j], both enter the critical section → mutual exclusion violated. This is the SB pattern in disguise.

Fix — insert a full fence after the flag/turn writes and before the spin-read:

flag[i] = true;
turn = j;
MFENCE;                              // or seq_cst fence (defined at top)
while (flag[j] && turn == j) {}      // enter CS

The MFENCE drains the store buffer, so this thread's flag[i] = true is globally visible before it peeks at flag[j]. That removes the store→load slip on both threads (each needs its own fence, exactly like L3.1), so they cannot both read the other's flag as false. See Peterson and Dekker Locks and Happens-before and Synchronizes-with.

std::atomic<int> data{0};
std::atomic<bool> flag{false};
 
// producer T1:
data.store(42, std::memory_order_relaxed);
flag.store(true, std::memory_order_release);
 
// consumer T2:
while (!flag.load(std::memory_order_acquire)) {}
int r = data.load(std::memory_order_relaxed);

Why these: the release store on flag publishes everything sequenced before it in T1 (including the relaxed data = 42). An acquire load that reads that released value establishes a happens-before edge: $(\text{data.store, T1})\stackrel{\text{happens-before}}{\to }(\text{data.load, T2}).$ So r == 42 is guaranteed. data itself only needs relaxed because ordering is carried by the flag's release/acquire, not by data's own order. Using seq_cst everywhere would also work but pays for a global total order you don't need here. See C++ Atomics and memory_order and Lock-free Programming.

This outcome says: T3 thinks x was written before y, while T4 thinks y was written before x.

First, a needed term: a model is multi-copy-atomic if, once any thread other than the writer can see a store, every other thread can see it too — i.e. a store becomes visible to all cores "at the same instant". When this holds there is a single, globally agreed instant per store, so all readers must observe the two stores in the same order.

(a) SC — FORBIDDEN. A single global total order fixes one order for x=1 vs y=1; both readers must agree.

(b) TSO — FORBIDDEN. Step-by-step WHY. In TSO the store buffer is private and local: it can only delay a core's own store past that same core's own later load (the store→load slip). Crucially, when a buffered store finally drains, it drains into the single shared memory — there is exactly one memory that all other cores read from. So the moment T1's x=1 leaves T1's buffer, it is visible to T3 and T4 simultaneously (TSO is multi-copy-atomic for every core except the writing core itself). Therefore the two stores hit shared memory in one definite order, and both T3 and T4 read from that same shared memory: they cannot observe opposite orders. The store buffer explains the SB (0,0) outcome but gives no mechanism for two remote readers to disagree.

(c) Relaxed (ARM/POWER, older) — ALLOWED. These systems are not multi-copy-atomic: a store can propagate to some cores before others via independent cache paths. So x=1 can reach T3 before y=1 does, while y=1 reaches T4 before x=1 does. The readers legitimately disagree. Fix on relaxed: a full/sync barrier (heavier than lwsync) between the two loads in each reader, or seq_cst atomics, restoring a single agreed store order.

SB outcomes are the four tuples $\{(0,0),(0,1),(1,0),(1,1)\}$.

• SC allows $\{(0,1),(1,0),(1,1)\}$ — everything except $(0,0)$.
• TSO allows all four — it adds exactly $(0,0)$ via store→load reordering.
• Relaxed also allows all four (it can never allow fewer; it only relaxes more). So for SB specifically: $S_{\text{SC}}⊊S_{\text{TSO}}=S_{\text{Relaxed}}$. The extra outcome $(0,0)$ is precisely what distinguishes SC from TSO. (For MP, by contrast, TSO $=$ SC and Relaxed is the strictly weaker one — the test determines which boundary you probe.)

T1:  a = 1;  MFENCE;  r1 = b;      // r1==0 means "T2 not here yet"
T2:  b = 1;  MFENCE;  r2 = a;      // r2==0 means "T1 not here yet"

Claim: (r1, r2) = (0, 0) is impossible ⇒ they cannot both think the other is absent. Proof. MFENCE drains each thread's store buffer, so a = 1 is globally visible before T1 loads b, and b = 1 is globally visible before T2 loads a. Suppose r1 == 0: then T1's load of b happened before b = 1 became visible. Because of T1's fence, a = 1 was already globally visible before that load — hence before T2's load of a (which is after b=1, which is after T1's load of b). Therefore T2's load reads a == 1, so r2 == 1 ≠ 0. Symmetric argument if we assume r2 == 0. Hence not both zero. This is exactly the SB fix (L3.1) applied as a handshake — two fences, one per thread, is the minimum (L3.2 showed one is not enough).