Exercises — Memory consistency models

• Coherence = single address. All cores must agree on the order of writes to one cell. See Cache Coherence.
• Consistency = across addresses. It governs how ops to different cells are ordered relative to one another. Coherence is necessary but weaker; consistency is the global rulebook.

Only S→L (an earlier Store may be bypassed by a later Load). Reason: the store sits in the per-core FIFO store buffer and drains later, while the load completes now. Mnemonic: "Stores Look Late."

False. volatile only stops the compiler from caching a value in a register; it emits no hardware fence and gives no cross-thread ordering. For that you need std::atomic with an ordering (see C++ Memory Model (acquire-release)).

• (a) SC: No. SC enforces every pair, including S→L. So S1 ${<}_m$ L2 and S3 ${<}_m$ L4. r1==0 needs L2 ${<}_m$ S3; r2==0 needs L4 ${<}_m$ S1. Chain them: $S1{<}_{m}L2{<}_{m}S3{<}_{m}L4{<}_{m}S1$ — a cycle, impossible. Forbidden.
• (b) TSO: Yes. TSO drops S→L. Both stores sit in store buffers; both loads read the stale 0 from memory before either store drains. Outcome r1==r2==0 is legal on x86.

No fence needed on TSO. The producer's two stores are S→S, which TSO preserves, so data=42 becomes globally visible before flag=1. The consumer's L3→L4 is L→L, also preserved. Once L3 sees flag==1, data is already 42. (On weak hardware this would need fences — see L3.2.)

Legal. Edges forced:

• Program order: $S1{<}_{m}L2$, $S3{<}_{m}L4$.
• r1==1 (L2 read the new y) ⇒ $S3{<}_{m}L2$.
• r2==0 (L4 read the old x) ⇒ $L4{<}_{m}S1$. Now try to find a cycle. One valid total order: $S3,L4,S1,L2$. Check: $S3{<}_{m}L4$ ✅ (po), $S1{<}_{m}L2$ ✅ (po), $S3{<}_{m}L2$ ✅, $L4{<}_{m}S1$ ✅. No cycle ⇒ allowed. A single acyclic ordering witnessing all edges = a legal SC execution.

This outcome means C3 sees x-write first, C4 sees y-write first — the two writes observed in opposite orders.

• (a) SC/TSO: No. Both guarantee a single total store order. If in that one order $x=1$ precedes $y=1$, every reader that sees $y=1$ must also see $x=1$. C4 seeing r3=1,r4=0 contradicts C3 seeing r1=1,r2=0.
• (b) POWER/ARM: Yes. These are non-multi-copy-atomic: a write can reach different cores at different times. No global store order is imposed, so the two readers legally disagree. (See Out-of-Order Execution for why propagation is not simultaneous.)

Two fences, one per core:

• Producer — a release fence between S1 and S2: data = 42; RELEASE_FENCE; flag = 1; Role: forces S1 (data) to be globally visible before S2 (flag). Recovers S→S at exactly the point that matters.
• Consumer — an acquire fence after L3: while(flag==0){}; ACQUIRE_FENCE; r = data; Role: forbids L4 (read data) from floating above L3 (read flag). Recovers L→L. Together they form an acquire–release pair (C++ Memory Model (acquire-release)): everything before the release on Core 1 is visible after the matching acquire on Core 2. Cheaper than making the whole program SC.

Insert one fence per core between the store and the load: x = 1; MFENCE; r1 = y; and y = 1; MFENCE; r2 = x; MFENCE (or any LOCK-prefixed atomic) drains the store buffer, restoring the S→L ordering TSO dropped. Now S1 ${<}_m$ L2 and S3 ${<}_m$ L4 hold ⇒ the same cycle argument as SC forbids the double-zero. No coherence change and no lock is needed — just the two fences.

Protocol (uses one full flag as the acquire-release handshake):

Producer:            Consumer:
  buf = item           while(load_acquire(full)==0){}
  store_release(full,1)  x = buf
                         store_release(full,0)   // reclaim slot

Proof the consumer never sees stale buf:

1. store_release(full,1) guarantees every write before it (here buf=item) is visible to any core that performs the matching load_acquire(full) and sees the value 1. — release semantics.
2. The consumer's load_acquire(full) observing 1 therefore synchronizes-with the producer's release. — acquire semantics.
3. Consequently x = buf (which is after the acquire in program order, and acquire forbids later loads from hoisting above it) reads the value the producer wrote. ∎
4. Coherence (single-address agreement, Cache Coherence) guarantees the full flag itself is seen consistently, so the spin-wait terminates once. Consistency handles the cross-address ordering between full and buf.

Judgment: correct and cheap — exactly one acquire and one release fence on the hot path, nothing global. This is strictly weaker (thus faster) than making the whole region SC, yet sufficient.

Falsifier = the SB test (L2.1). TSO's single relaxation, S→L, makes r1==0 && r2==0 observable on real x86 — an outcome SC forbids. So TSO is not SC; the difference is exactly the store-buffer bypass. Fix: MFENCE between each core's store and load (as in L4.2) drains the buffer and forbids the double-zero. Conclusion: "TSO ≈ SC" is false precisely for the S→L pair, and that pair is not an academic curiosity — it is the everyday Dekker/mutex-flag hazard.

The universal legality test for any outcome ::: build the memory-order graph from program-order + read-from edges, then check for a cycle; a cycle means the outcome is forbidden.