Concurrency at the Silicon Level: Cache Coherence and Memory Barriers

Multithreaded code operates under an assumption that doesn’t hold at the hardware level: that multiple cores share a single, consistent view of memory. They don’t. Each core has its own private L1 and L2 caches, and writes from one core are not immediately visible to others. The hardware works hard to maintain an illusion of consistency, but the mechanisms it uses introduce subtle ordering behaviors that, if ignored, produce race conditions that no amount of code review will catch.

To write correct lock-free code, or to understand why a mutex works at all, you need a model of what the hardware is actually doing.

The Cache Hierarchy Problem

Physical RAM access takes 60–100 nanoseconds — hundreds of clock cycles at modern frequencies. Without caching, a 4 GHz core would stall waiting for memory the vast majority of the time. So each core has its own L1 cache (latency: ~4 cycles), L2 cache (~12 cycles), and shares an L3 with other cores (~40 cycles). RAM is the last resort.

The consequence: when Thread A on Core 0 writes a variable, that write goes to Core 0’s L1 cache. Thread B on Core 1 has its own copy of the same cache line. Core 1 doesn’t automatically see Core 0’s write. Without coordination, you have two cores with divergent views of the same memory address.

This is the cache coherence problem.

The MESI Protocol

The dominant solution on x86 is the MESI protocol, a state machine that every cache line participates in. Each 64-byte cache line is tagged with one of four states:

• Modified (M): This core has written to the line. Its copy is the authoritative version — RAM and all other caches are stale.
• Exclusive (E): This core holds the only cached copy, and it matches RAM. No write has occurred.
• Shared (S): Multiple cores have this line cached. All copies match RAM. The line is effectively read-only until ownership is acquired.
• Invalid (I): This cache line’s data is stale and must not be read.

Write Invalidation

When Core 0 wants to write to a line currently in Shared state (held by both Core 0 and Core 1), it can’t just overwrite its copy. It needs exclusive ownership first.

Core 0 broadcasts an RFO (Request for Ownership) message. Core 1’s coherence hardware receives it, transitions its copy of that line to Invalid, and sends an acknowledgment. Only after Core 0 has collected all acknowledgments does it transition to Modified and complete the write.

One important clarification on the mechanism: the “bus snooping” model — where every core watches a shared bus — is accurate for older or simpler designs. Modern multi-core and multi-socket processors use directory-based coherence instead, with a directory structure (often embedded in the L3 or memory controller) that tracks which cores hold which lines. This avoids the scalability problems of broadcasting to every core on every write, but the MESI state semantics remain the same from a programmer’s perspective.

Store Buffers and Invalidate Queues

The protocol above has a latency problem. Waiting for RFO acknowledgments from all cores before completing a write can take dozens to hundreds of cycles. Stalling the pipeline on every write would eliminate most of the benefit of out-of-order execution.

The hardware introduces two queues to decouple this:

Store Buffer: When a core executes a write, the write goes into a small, fast store buffer rather than directly to the cache. The core sends the RFO, continues executing subsequent instructions, and the cache update happens when the acknowledgment arrives and the store buffer drains. The core can read its own pending stores from the store buffer (store-to-load forwarding), so its own subsequent loads see the write — but other cores can’t see it yet.

Invalidate Queue: When a core receives an invalidation message for one of its cache lines, it doesn’t necessarily process it immediately. It queues the invalidation, sends an acknowledgment to the requesting core, and processes the actual state change later. This means a core can acknowledge “I’ve invalidated that line” before it has actually done so. A subsequent load from that core may still read the (not-yet-invalidated) stale data.

Both of these are deliberate performance optimizations. Both of them break the intuition that writes are immediately globally visible.

The Litmus Test: Store-Load Reordering on x86

x86 uses a memory model called Total Store Order (TSO). It provides stronger guarantees than most architectures: stores from a single core are seen by other cores in program order, and loads are not reordered with earlier loads. But one reordering is permitted: a load can be satisfied from the store buffer before a preceding store has drained to cache.

The classic demonstration uses two shared variables, $X = 0$ and $Y = 0$, and two threads:

Thread A (Core 0):

mov [X], 1    ; store 1 to X
mov eax, [Y]  ; load Y

Thread B (Core 1):

mov [Y], 1    ; store 1 to Y
mov ebx, [X]  ; load X

Intuitively, it seems like at least one of eax or ebx must be 1: whichever thread’s store executed first would be visible to the other’s subsequent load. But on real x86 hardware, both can read 0.

The sequence: Core 0 stores 1 to X into its store buffer and immediately proceeds to load Y from cache (still 0 — Core 1’s store is in Core 1’s store buffer). Core 1 does the same in parallel. Both loads complete before either store buffer drains. The result: eax = 0, ebx = 0.

This is not a bug. It is documented behavior in the Intel and AMD architecture manuals. The x86 TSO model explicitly permits this specific reordering. Weaker memory models (ARM, RISC-V, POWER) permit additional reorderings: store-store and load-load reorderings that x86 TSO forbids. Code that relies on x86’s relatively strong ordering will break silently when ported to ARM.

Memory Barriers

A memory barrier (or fence) is an instruction that constrains reordering. On x86:

• sfence: All stores before the fence are globally visible before any store after the fence. Relevant primarily for non-temporal (NT) stores that bypass the cache.
• lfence: Serializes loads — all loads before the fence complete before any load after it. Also prevents speculative execution past the fence (relevant for Spectre mitigations).
• mfence: Full barrier. No load or store may be reordered across an mfence in either direction. Forces the store buffer to drain before proceeding.

Inserting mfence between the store and load in the litmus test prevents the reordering:

; Thread A
mov [X], 1
mfence        ; wait for store buffer to drain
mov eax, [Y]  ; now guaranteed to see any store that completed before the fence

With mfence in both threads, the eax = 0, ebx = 0 outcome is impossible.

lock-prefixed instructions (lock cmpxchg, lock xchg) also have full barrier semantics — with one caveat: Intel’s documentation specifies they don’t order non-temporal stores, which is why mfence is occasionally necessary even when using locked instructions in code that mixes NT stores.

False Sharing

Before looking at the spinlock implementation, one practical coherence hazard worth understanding: false sharing.

Cache coherence operates on 64-byte cache lines, not individual variables. If Thread A writes to variable x and Thread B writes to variable y, and both variables happen to occupy the same cache line, the cores will continuously invalidate each other’s copies even though they’re writing to logically independent data. The MESI protocol has no knowledge of variable boundaries — it only sees cache lines.

The fix is alignment:

/* Without padding: x and y likely share a cache line */
struct bad {
    int x;
    int y;
};

/* With padding: each variable occupies its own cache line */
struct good {
    int x;
    char _pad[60];
    int y;
};

Or with C11: alignas(64) int x;. False sharing can cause 10x or worse performance degradation in tight loops and shows up in perf output as elevated cache-line invalidation rates.

volatile Is Not Enough

Before the implementation: a common misconception is that marking a shared variable volatile makes concurrent access safe. It doesn’t.

volatile in C tells the compiler not to optimize away reads and writes to a variable — ensuring every access generates an actual memory instruction rather than being cached in a register. What it does not do is prevent the CPU from reordering those instructions relative to each other, and it provides no atomicity for read-modify-write operations. Using volatile alone for thread synchronization is undefined behavior in C11 and later.

For portable concurrent code, use <stdatomic.h> (C11) or std::atomic<> (C++11). These insert the appropriate barrier instructions for whatever architecture you’re targeting, and the compiler won’t reorder operations across atomic accesses.

The inline assembly spinlock below bypasses the standard library to expose the hardware mechanism directly. It is x86-specific and would need dmb/stlr equivalents on ARM.

Implementation: A Spinlock in C with Inline Assembly

#include <stdio.h>
#include <stdint.h>
#include <pthread.h>

/*
 * 0 = unlocked, 1 = locked.
 *
 * Note: 'volatile' here prevents the compiler from hoisting the load out of
 * the spin loop — necessary but not sufficient for correctness. The actual
 * memory ordering is provided by the 'lock' prefix on cmpxchgl.
 */
volatile int global_lock = 0;
int shared_resource = 0;

static void acquire_lock(void)
{
    int expected, result;

    do {
        expected = 0;

        /*
         * lock cmpxchgl: atomically compare global_lock with expected (0).
         * If equal, write desired (1) and set ZF. If not equal, load the
         * current value into EAX and clear ZF.
         *
         * The 'lock' prefix asserts bus ownership for the duration of the
         * read-modify-write, making it indivisible. It also provides
         * acquire-release barrier semantics on x86 for regular (non-NT) memory.
         *
         * The "memory" clobber is a compiler barrier — the compiler may not
         * move memory accesses across this asm block.
         */
        __asm__ __volatile__(
            "lock cmpxchgl %2, %1\n\t"
            "sete %0"
            : "=q"(result), "+m"(global_lock)
            : "r"(1), "a"(expected)
            : "memory"
        );

        if (!result) {
            /*
             * pause: hints to the CPU that this is a spin-wait loop.
             * On HyperThreaded cores, it yields cycles to the sibling thread.
             * It also prevents the CPU from mis-speculating past the loop,
             * reducing the pipeline flush penalty when the lock becomes free.
             */
            __asm__ __volatile__("pause" ::: "memory");
        }

    } while (!result);
}

static void release_lock(void)
{
    /*
     * On x86 TSO, stores are not reordered with earlier stores, so writing
     * 0 to global_lock is sufficient to release after completing the critical
     * section — the critical section's stores will be visible before the
     * lock release store.
     *
     * The compiler barrier prevents the compiler from moving critical-section
     * code after the store. On ARM, this would need a 'stlr' (store-release)
     * instruction or an explicit 'dmb st' fence instead.
     */
    __asm__ __volatile__("" ::: "memory");
    global_lock = 0;
}

static void *worker(void *arg)
{
    (void)arg;
    for (int i = 0; i < 1000000; i++) {
        acquire_lock();
        shared_resource++;
        release_lock();
    }
    return NULL;
}

int main(void)
{
    pthread_t t1, t2;
    pthread_create(&t1, NULL, worker, NULL);
    pthread_create(&t2, NULL, worker, NULL);
    pthread_join(t1, NULL);
    pthread_join(t2, NULL);

    /*
     * With correct synchronization, this must print 2000000.
     * A naive implementation using volatile without atomics would
     * produce a lower number due to lost updates.
     */
    printf("Final value: %d\n", shared_resource);
    return 0;
}

Final value: 2000000

The lock cmpxchgl in acquire_lock does three things simultaneously: reads the current value of global_lock, compares it to 0, and conditionally writes 1 — all as one indivisible operation. No other core can observe the lock in a state between the read and the write. The lock prefix provides the atomicity; the barrier semantics it implies on x86 ensure the critical section’s stores don’t leak out before the lock is acquired, and don’t bleed past the release.

The release_lock is deliberately minimal. On x86, a plain store with a compiler barrier is sufficient because TSO guarantees that stores aren’t reordered with each other. On ARM or POWER, you’d emit an explicit store-release instruction to achieve the same ordering guarantee portably. This asymmetry — strong acquire via lock cmpxchgl, light release via a plain store — is the standard pattern for x86 spinlocks and reflects the specific guarantees x86 TSO provides.

Understanding the hardware model underneath the spinlock is what separates a developer who uses a mutex from one who can implement one correctly, audit a lock-free data structure, or diagnose a coherence-related performance regression.