Memory Models, Atomics, and Lock-Free

The code you write is not the code that executes. Both the compiler and the CPU reorder instructions freely, as long as the reordering is invisible to a single thread. The moment you have two threads, what looks invisible locally becomes catastrophically visible globally.

Compiler example: a store to ready = true may be hoisted above the write to data if the compiler sees no dependency. CPU example: store-buffer forwarding on x86 means a core may read its own recent write before other cores see it; on ARM and POWER, even store order between two cores is not guaranteed.

Why? Performance. Reordering allows out-of-order execution, pipeline saturation, and cache-line prefetching. Modern CPUs can sustain 3–6 instructions per cycle precisely because they're free to reorder.

The implication: you cannot reason about concurrent programs by reading C or Python source. You must think in terms of the memory model the language or hardware guarantees.

Multi-core CPUs use a coherence protocol (MESI or derivatives) to ensure that all cores eventually agree on the value of any single memory address. If core 0 writes x = 5, core 1 will eventually see x = 5 — it will never see a stale value indefinitely.

But coherence ≠ consistency. Coherence is per-variable; consistency is about the order of multiple variables. Consider:

// Thread A (core 0)         // Thread B (core 1)
x = 1;                        y = 1;
int r1 = y;                   int r2 = x;

On x86 it's impossible for both r1 == 0 and r2 == 0. On ARM it's legal — both stores may sit in store buffers while the loads execute. Cache coherence guarantees each write is eventually visible; it does not guarantee the order threads observe each other's writes.

This is the gap a memory model fills: it tells you exactly which orderings are possible.

A happens-before edge ($A \to B$) means: all memory effects of $A$ are visible to $B$ before $B$ executes. Without such an edge, $B$ may see stale values, even on a cache-coherent machine.

Happens-before is established by synchronization events:

• Releasing a mutex HB acquiring the same mutex.
• Writing an atomic with release semantics HB reading it with acquire semantics.
• thread.join() HB everything after the join.
• channel send HB channel receive (in Go).

If thread A writes data, then writes ready = true (release), and thread B reads ready (acquire) and sees true, then B is guaranteed to see A's write to data — even if data is a plain variable.

Without a happens-before edge, the question "does thread B see thread A's write?" has no definite answer. The compiler or CPU may have reordered or cached it away.

In Java, volatile on a field guarantees: (1) writes are not cached in registers, (2) a write happens-before a subsequent read by another thread. In C/C++, volatile only prevents the compiler from eliding reads/writes — it does not generate memory fences or prevent CPU reordering.

Common misconceptions:

The C++ equivalent of Java volatile for concurrency is std::atomic<T> with appropriate memory ordering — not volatile. Using volatile in C++ for thread communication is a bug, not a feature. The compiler is allowed to reorder volatile stores relative to non-volatile ones, and the CPU adds further reordering on top.

An atomic operation completes without any observable intermediate state from another thread. The most powerful atomic primitive is compare-and-swap (CAS):

// Atomically: if (*ptr == expected) { *ptr = desired; return true; } else return false;
bool compare_exchange(T *ptr, T expected, T desired);

CAS is the foundation of most lock-free algorithms. A lock-free counter in C++:

#include <atomic>
std::atomic<int> counter{0};

void increment() {
    int old = counter.load(std::memory_order_relaxed);
    while (!counter.compare_exchange_weak(
               old, old + 1,
               std::memory_order_release,   // success ordering
               std::memory_order_relaxed))  // failure ordering
    {}
    // old is updated by CAS on failure — no spurious retry wasted
}

compare_exchange_weak may fail spuriously (on some architectures it's LL/SC under the hood). The loop retries until the CAS succeeds. This is wait-free in the absence of contention; under high contention, all threads retry simultaneously — a CAS storm.

C++ std::atomic exposes six memory orderings. In practice you use three:

• memory_order_relaxed: no ordering guarantees beyond atomicity. Use for counters where exact order doesn't matter (stats, hit counts).
• memory_order_acquire: no reads/writes in the current thread can be reordered before this load. Pairs with release on the writer side.
• memory_order_release: no reads/writes in the current thread can be reordered after this store. Establishes happens-before to an acquire load that sees this value.
• memory_order_seq_cst (default): full sequential consistency — a global total order over all seq_cst operations across all threads. Safest; most expensive (full fence on some architectures).

The acquire/release pair is the standard idiom for a one-producer, one-consumer channel:

// Producer (thread A)
data.store(42, std::memory_order_relaxed);
ready.store(true, std::memory_order_release);  // publishes data

// Consumer (thread B)
while (!ready.load(std::memory_order_acquire)) {} // sees data after this
use(data.load(std::memory_order_relaxed));          // guaranteed to see 42

CAS checks that the value equals expected. But what if another thread changed the value from A to B and back to A between your load and your CAS? The CAS succeeds even though the world changed — this is the ABA problem.

Example: a lock-free stack. Thread A reads head=A. Thread B pops A, pops B, pushes A back. Thread A's CAS succeeds (head is still A) and sets head to A's old next — which now points to freed memory.

Fixes:

• Tagged pointers / version counters: pack a monotonically increasing version into the pointer (common on 64-bit: use the upper 16 bits). CAS on both pointer and version — B→A will have a different version.
• Hazard pointers: mark pointers in use before loading; defer freeing until no hazard pointer references them.
• Epoch-based reclamation (EBR): threads publish their epoch; memory is freed only when all threads have advanced past the epoch that freed it.

ABA is why lock-free data structures are harder to write correctly than lock-based ones. Prefer battle-tested library implementations.

A release store on thread A synchronizes with an acquire load on thread B, making all of A's prior writes visible to B.

These terms have precise meanings that are often blurred in blog posts:

Most "lock-free" data structures in practice are lock-free but not wait-free: under adversarial scheduling, a single thread could be starved (though not permanently, by the system-level progress guarantee). True wait-freedom requires algorithms like Kogan-Petrank queues — complex and rarely faster in practice.

The practical takeaway: lock-free structures reduce worst-case tail latency and eliminate deadlock, but are not magic. Under low contention a well-written mutex is often faster due to simpler code and better branch prediction.