Exercises — Memory model — happens-before, acquire-release semantics

• relaxed → neither (atomicity only, no ordering of other memory).
• acquire → upward (a load; nothing after it may float above it).
• release → downward (a store; nothing before it may sink below it).
• acq_rel → both (used on a read-modify-write like fetch_add).
• seq_cst → both + a single global total order all seq_cst ops agree on.

The figure below draws this: on the left, a release store with a yellow "floor" line — blue arrows for earlier ops point down toward it, and a dashed pink arrow with an X shows an earlier op is forbidden to sink below. On the right, an acquire load with a yellow "ceiling" line — blue arrows for later ops point up toward it, and a dashed pink X shows a later op is forbidden to float above.

It is a data race: same memory location, at least one write, no happens-before ordering. Consequence: undefined behavior — the standard promises nothing at all, not even a "reasonable" garbage value.

Only if the acquire-load actually reads the value the release-store wrote (or a later value in that store's release sequence — the chain defined in the vocabulary list above and proved in exercise L5.2 later on this page). No matching value read ⇒ no sw edge ⇒ no hb.

r can only be 7.

• (1) is sb (2) — same thread, and release forbids (1) sinking below (2).
• (2) sw (3) — the acquire-load exits the loop only after reading true, the value the release-store wrote.
• (3) is sb (4).
• Transitive chain: $(1)\stackrel{hb}{\to }(2)\stackrel{hb}{\to }(3)\stackrel{hb}{\to }(4)$, so (1) hb (4). Thread 2 sees the write data = 7. No other value is possible.

With no sw edge, data is a non-atomic location touched by two threads with no happens-before ordering — that is a data race, which is undefined behavior. Strictly, the standard permits anything: the program may read 0, read 7, read a torn/garbage value, crash, or optimize the whole loop away. The intuitive, non-adversarial outcome people expect is 0 or 7: relaxed gives atomicity only, so the loop can see ready == true before the write to data is visible, yielding a stale 0. But do not mistake "0 or 7" for a guarantee — once it is UB, "0 or 7" is only the friendliest possibility, not a bound the standard promises.

Yes, relaxed is enough. total is always 3.

Part A — no increment is lost (even without ordering other memory). Each fetch_add is an atomic read-modify-write. Atomicity plus modification-order consistency (all writes to a single atomic form one total order everyone agrees on) guarantee each RMW reads the immediately preceding value in that order and adds one. Three RMWs on the same atomic therefore produce the values 1, 2, 3 in some order — none can overwrite another. We need no ordering of other memory here, so relaxed is correct and cheapest.

Part B — why the final relaxed load sees all three (the join() hb chain). The load is relaxed, so on its own it carries no acquire barrier. What saves us is std::thread::join(): the standard specifies that the completion of a thread synchronizes-with the return of the join() that waits on it. That is a genuine sw edge — the same kind of edge acquire/release builds, but supplied for free by join(). Trace it for one worker thread T1:

1. cnt.fetch_add(1) in T1 is sb the end of T1's execution (program order — it is the last thing T1 does).
2. The end of T1 sw the return of T1.join() in main (the join rule above).
3. T1.join() returning is sb cnt.load(...) in main (program order in main — we join before we load).
4. Transitivity: fetch_add (T1) hb load (main). Same argument for T2 and T3.

So all three increments happen-before the load, and by the visibility guarantee the load observes every one of them → 3. The relaxed tag on the load is irrelevant because join() already provided the ordering — this is exactly the "which two events need ordering, and what edge supplies it?" question, answered by join() rather than by acquire.

Because the write payload = 99 is after the release-store in program order. Release is a downward barrier: it keeps operations that come before it from sinking below. It does nothing for operations after it. So (B) is not published by (A); the consumer's acquire inherits everything before (A), which does not include (B). Bug: signal was raised before the data was written. Order is inverted. Fix: write the payload first, then release:

payload = 99;
ready.store(true, std::memory_order_release);

Under acquire/release: ==yes, x == 0 && y == 0 is possible==. Each thread stores to a different atomic; no value travels between the two threads, so no sw edge forms. Acquire/release orders memory only along a synchronizes-with chain — there is none here, so the two stores can appear un-ordered to each other. Under seq_cst: no. seq_cst forces a single global total order S on all seq_cst ops. In S one store is first; the thread whose load comes after that store in S must see 1. So both reading 0 is impossible. This is the Dekker / store-buffer scenario.

The figure below shows why: each thread's store lands first in its own store buffer (a per-core queue) and is not yet globally visible, so each thread reads the other flag as still 0, giving (0, 0). seq_cst outlaws this by forcing one global order that flushes a store first.

No. An hb edge needs both halves: a release-store and an acquire-load reading it. A relaxed load creates no acquire side, so no sw edge forms even if it reads 1. data is therefore unordered — data race, UB. Fix: make the load std::memory_order_acquire. A release with no matching acquire is like raising a flag no one is allowed to look at.

std::atomic<bool> held{false};
 
void lock() {
    while (held.exchange(true, std::memory_order_acquire))
        ; // spin
}
void unlock() {
    held.store(false, std::memory_order_release);
}

• lock() uses exchange with acquire: once we win the lock (old value was false), the acquire is an upward barrier so the critical section's reads/writes cannot float above the lock. This mirrors a mutex: acquire on lock.
• unlock() uses release: a downward barrier so all critical-section writes are published before held becomes false. The next thread's acquiring exchange reads that false→ builds the sw edge → sees our work.

Important classification note: this spinlock is a blocking synchronization mechanism, not a lock-free data structure. Under the standard definition, lock-free means the system as a whole makes progress even if any thread is suspended; a spinlock fails that — if the lock-holder is descheduled while holding held == true, every waiter spins forever. What is genuinely lock-free is the underlying atomic `exchange` primitive we built the lock from. Study true lock-free algorithms under lock-free programming patterns.

int data = 0;
std::atomic<bool> ready{false};
 
// Producer
data = 42;
std::atomic_thread_fence(std::memory_order_release);  // (F1)
ready.store(true, std::memory_order_relaxed);
 
// Consumer
while (!ready.load(std::memory_order_relaxed)) ;
std::atomic_thread_fence(std::memory_order_acquire);  // (F2)
assert(data == 42);

• (F1) release fence sits before the relaxed store: it keeps data = 42 from sinking past the store. The store publishes.
• (F2) acquire fence sits after the relaxed load succeeds: it keeps assert(data) from floating above the load.
• The release-fence-then-store pairs with load-then-acquire-fence to build the same hb edge. See thread fences. It is equivalent to tagged release/acquire but decouples the barrier from the atomic op.

Use ==std::memory_order_seq_cst==. acq_rel only orders memory along a synchronizes-with chain between a matched store/load pair. When you have independent atomics and need every thread to agree on one global sequence of events (the IRIW situation of L3.2), acquire/release is too weak — different observers can see different orders. seq_cst adds a single global total order S covering all seq_cst operations, so every consumer agrees. See sequential consistency. The cost: extra fences, usually slower.

A data race requires two accesses to the same location, ≥1 write, with no hb ordering. Here access (1) writes data, access (4) reads data.

• (1) sb (2): program order in Thread 1.
• (2) sw (3): release-store read by the acquire-load that exits the loop.
• (3) sb (4): program order in Thread 2. Happens-before is the transitive closure of sb ∪ sw. Chaining: (1) hb (2), (2) hb (3), (3) hb (4) ⇒ (1) hb (4) by transitivity. Since (1) hb (4), the two conflicting accesses are ordered, so by definition there is no data race. ∎

Yes. This is the proof promised in the vocabulary list at the top of the page. The rule is: an acquire-load synchronizes-with a release-store if it reads the stored value or any value later in that release-store's release sequence. The release sequence is headed by the release-store and continued by read-modify-write operations on the same atomic (fetch_add here) — even relaxed ones. So reading 2 (produced by an RMW chained onto the release-store) still inherits the producer's prior work. This is precisely why RMWs may be relaxed inside such chains.

No. A single-threaded program can never observe its own reordering. Here is the full reasoning:

1. Within one thread, sequenced-before fully orders every dependent access. Program order defines sb between successive evaluations, and sb is exactly the ordering the language exposes to that thread.
2. The as-if rule constrains all reordering. The compiler and CPU may reorder or eliminate instructions, but only if the program's observable behavior (I/O, volatile accesses, and the final values of objects) is identical to running strictly in program order. See the as-if rule and, at the hardware level, out-of-order execution and store buffers — the CPU tracks data dependencies and retires results as if in order.
3. Therefore any reordering that a single thread could detect is forbidden. If reordering A and B would change what this thread reads or outputs, it is illegal; if it would not, the thread cannot tell it happened. Either way the thread observes program-order results.
4. Memory-model subtleties are strictly a cross-thread phenomenon. They appear only because one thread's sb does not reach into another thread — there is no sb edge across threads, so you must build sw edges (via acquire/release) by hand. With a single thread there is nothing to synchronize with, so happens-before collapses to plain program order and the whole question of visibility disappears.

Conclusion: reordering is invisible to a lone thread by construction; the memory model only becomes observable once a second thread reads what the first wrote.

Both stores write 1. Loads read either the initial 0 or the store's 1. Candidate pairs: (0,0), (0,1), (1,0), (1,1). Under seq_cst there is a total order S of the four operations. Whichever store comes last in S is preceded by the other store; the thread that loads after that earliest store in S must observe 1. Formally, at least one load sees 1, ruling out (0,0). The three surviving outcomes (0,1), (1,0), (1,1) are all reachable. So exactly 3 of the 4 combinations are possible under seq_cst.