Hardware Memory Models: Reordering, Store Buffers, Cache Coherence and Sequential Consistency

Version note: The code in this post was built and run with .NET 10 (C# 14); tests use xUnit v3 4.0.3. The outputs were taken on ARM64; statements about x64 are based on Intel's software developer's manual and the .NET memory model spec, with no measurement on x64.

Guess First

In Bookstore, the online bookstore used as the shared example across this site's series, two threads share two int fields that start at 0. The first thread writes X = 1, then reads Y. The second writes Y = 1, then reads X. No lock, no volatile, plain field access. Can both threads read 0? On paper both threads write before they read; whoever reads first, at least one of them seems bound to see the other's 1.

Second question: the ordering service writes the order total first, then raises a "ready" flag. The shipping thread reads the total once it sees the flag. Can it see the flag as 1 and the total as 0? I ran both experiments 10 million times each on ARM64. Write down a guess before looking at the numbers; afterwards we will talk about why the same code behaves differently on your x64 machine running Windows.

In the third post we saw Peterson's algorithm break even with volatile and passed over the reason in one sentence: "the sequential consistency assumption". In this post we unpack that sentence.

Sequential Consistency: The Programmer's Intuition

In his 1979 paper "How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs", Leslie Lamport defined a criterion for a multiprocessor computer to count as correct. In our own words: the memory operations of all threads must look as if they were placed in one single order, and in that order each thread's operations must appear in the order of its own program. If you can explain an execution as the steps of the threads being shuffled like a deck of cards and laid out one after another, that execution is sequentially consistent.

The interleavings in the first post were exactly this model: we placed the steps of two threads side by side in every possible order. In this model the answer to the opening question is clear. The first step has to be either X = 1 or Y = 1; whichever comes first, one of the two later reads sees that 1. There is no order in which both threads read 0.

What Lamport's paper really says is this: optimizations that make a single processor faster can break this intuition once several processors work together. None of today's CPUs give sequential consistency by default. To see why, let's look at the experiment.

The Store Buffering Litmus Test

The tiny programs used to study memory models are called litmus tests: two or three threads, a few memory operations each, and the question "is this outcome possible?". The opening question is known in the literature as store buffering, or SB. As in every post, I added a new folder to the lab project, Hardware/:

// Two shared ints, 128 bytes apart so they never share a cache line
[StructLayout(LayoutKind.Explicit, Size = 256)]
public struct Cells
{
    [FieldOffset(0)] public int X;
    [FieldOffset(128)] public int Y;
}

// Store buffering (SB): write your own cell, then read the other one
public sealed class StoreBufferingPlain : LitmusTest
{
    public override string Name => "SB plain";

    [MethodImpl(MethodImplOptions.NoInlining | MethodImplOptions.AggressiveOptimization)]
    public override int Thread0()
    {
        Shared.X = 1;
        return Shared.Y;
    }

    [MethodImpl(MethodImplOptions.NoInlining | MethodImplOptions.AggressiveOptimization)]
    public override int Thread1()
    {
        Shared.Y = 1;
        return Shared.X;
    }
}

With AggressiveOptimization the methods are compiled straight to optimized code, so every run measures the same machine code and the intermediate stages of tiered compilation do not blur the result. To make the two threads really run these two lines at the same time, LitmusRunner uses a third thread as a coordinator: every round it resets the cells, bumps the round number both workers are waiting for, and counts the values they read once both are done.

for (int round = 1; round <= rounds; round++)
{
    test.Reset();
    Volatile.Write(ref _done, 0);
    Volatile.Write(ref _go, round); // both workers wait for this value
    while (Volatile.Read(ref _done) != 2) { }
    outcomes[_r0, _r1]++;
}

I also added two variants of the same test: StoreBufferingVolatile, which does the reads and writes with Volatile.Read/Volatile.Write, and StoreBufferingFenced, which puts Interlocked.MemoryBarrier() between the write and the read.

dotnet run -c Release --project src/Bookstore.ConcurrencyLab -- litmus-sb 10000000

SB plain                 r0=0,r1=0: 5,314,715  0,1:     4,874  1,0: 4,680,409  1,1:         2  (1972 ms)
SB Volatile.Read/Write   r0=0,r1=0:    11,272  0,1:    10,957  1,0: 4,638,867  1,1: 5,338,904  (2172 ms)
SB full fence            r0=0,r1=0:         0  0,1:    12,402  1,0: 5,466,604  1,1: 4,520,994  (2074 ms)

With plain access both threads read 0 in 5,314,715 of 10 million rounds; the most frequent outcome is the one sequential consistency calls impossible. In the Volatile version the number dropped to 11,272 but did not reach zero. With a full fence it is zero. A second run gave different numbers (5,557,821 with plain access, 62,894 with Volatile), and the fenced version was 0 again.

The cause is the store buffer. When a core writes to memory, the write can reach the cache only after the core takes ownership of the cache line, and if the line sits in another core that can take tens of nanoseconds. Instead of waiting, the core parks the write in a small store buffer in front of it and moves on. If the next instruction reads from another address, the read is served from the cache right away. Because the write is still in the buffer, the other core cannot see it. When both cores do this at the same time, both read the other's old value, 0. A core can read its own write from the buffer (store forwarding), so from a single thread's point of view nothing breaks.

Where Reordering Comes From: Hardware and the JIT

A read overtaking an earlier write is a reordering from the programmer's point of view. It has three sources: the store buffer, out-of-order execution and the compiler. In .NET the compiler side is the JIT, and the memory model spec states plainly that ordinary reads and writes may be reordered, by code generation as well as by the hardware, as long as the result seen by a single thread stays the same.

To check that the 0,0 outcome in our experiment comes from the hardware and not from the JIT, I looked at the generated code. The DOTNET_JitDisasm environment variable prints the assembly of the named methods to the console ($env:DOTNET_JitDisasm="Thread0" in PowerShell, DOTNET_JitDisasm=Thread0 in front of the command in bash):

DOTNET_JitDisasm=Thread0 dotnet run -c Release --project src/Bookstore.ConcurrencyLab -- litmus-sb 1

; StoreBufferingPlain:Thread0
mov     w1, #1
str     w1, [x0, #0x08]
ldr     w0, [x0, #0x88]
; StoreBufferingVolatile:Thread0
mov     w1, #1
stlur   w1, [x0, #0x08]
ldapur  w0, [x0, #0x88]
; StoreBufferingFenced:Thread0
mov     w1, #1
str     w1, [x0, #0x08]
dmb     ish
ldr     w0, [x0, #0x88]

These are the relevant lines of the output. The JIT left the instructions in program order: first str (the write), then ldr (the read). The swap happens entirely in the hardware. In the Volatile version the write becomes stlur (a release store) and the read becomes ldapur (an acquire load). Release stops the write from overtaking the operations before it; acquire stops the read from falling behind the operations after it. Neither keeps the order "write first, then read". That is why the Volatile version also produced 0,0. The dmb ish in the fenced version is a full barrier: later memory operations cannot start before all earlier ones complete, so the read waits until the store buffer drains.

This also makes clear why Peterson broke in the third post: the read "the other side's flag is down" ran while the write "I raised my flag" was still waiting in the store buffer. The rules for volatile and fences in .NET are the topic of the next post.

Cache Coherence and Memory Consistency Are Different Things

A common mix-up at this point is the thought "CPU caches are coherent, so whatever one core writes the other sees". In the multi-core post of the How Computers Work series we covered the MESI protocol and how cache lines move between cores. Coherence is a guarantee about a single address: writes to the same address are seen by all cores in the same order. Consistency is about the order in which operations on different addresses become visible relative to each other.

I measured coherence separately. One thread writes 1 to 50 million in order to the same field, three threads keep reading that field and count whether they ever see a value smaller than their previous read:

dotnet run -c Release --project src/Bookstore.ConcurrencyLab -- coherence 50000000

writes=50,000,000 reads=172,760,742 saw the value go back=0

In 172 million reads the value never went back once. I used Volatile.Read for the reads, but only so the JIT cannot merge consecutive reads into one; the ordering guarantee on a single address comes from coherence. The .NET memory model spec lists this as a hardware property it expects from every supported platform. So the problem in the store buffering test is not cache inconsistency: every address is consistent with itself, the problem is the order of two different addresses relative to each other. The coherence protocol does not arrange that order at all, and the store buffer is a layer that sits in front of coherence and acts before it.

x86-TSO and ARM64: The Message Passing Test

Hardware architectures move away from sequential consistency to different degrees. The x86 family's model is known in the literature as x86-TSO, where TSO stands for Total Store Order. According to the memory ordering section in volume 3 of the Intel SDM, Intel's software developer's manual, in this model reads are not reordered with other reads, writes are not reordered with other writes, and a write does not overtake an earlier read either. The only reordering allowed is a read moving ahead of an earlier write to a different address. That is exactly what the store buffer does. So the 0,0 outcome of the SB test is allowed on x64 as well.

ARM64's model is much weaker: almost any pair of independent reads and writes to different addresses may be reordered. AWS's Graviton technical guide says this plainly: Arm is weakly ordered while x86 is a variant of TSO, and code that relies on TSO may be missing the barriers it needs. The litmus test that shows the difference best is message passing, or MP, the second opening question:

// Message passing (MP): X = order total, Y = "ready" flag
public override int Thread0()
{
    Shared.X = 1; // total
    Shared.Y = 1; // ready
    return 0;
}

public override int Thread1()
{
    int ready = Shared.Y;
    int total = Shared.X;
    return ready * 2 + total;
}

dotnet run -c Release --project src/Bookstore.ConcurrencyLab -- litmus-mp 10000000

MP plain                 ready=1,total=1:     57,615  ready=0:  3,650,600  ready=1,total=0: 6,291,785  (1899 ms)
MP Volatile.Read/Write   ready=1,total=1:      2,729  ready=0:  9,997,271  ready=1,total=0:       0  (2215 ms)

With plain access, in 6,291,785 of 10 million rounds the shipping thread saw the flag raised but the total as 0. The ordering service's code writes the total before the flag, and the two str instructions are in that order in the JIT output too. ARM64 changed either the order in which the writes became visible or the order of the two ldr instructions on the reading side; both are allowed on this architecture. Writing the flag with Volatile.Write and reading it with Volatile.Read brought this outcome down to zero. This test is exactly the case release/acquire solves: the release write guarantees that the total becomes visible before the flag, and the acquire read guarantees that the total is read after the flag.

The x64 column is not a measurement; it lists the outcomes the manual allows and forbids. If you run this program on your x64 machine with Windows, according to the manual you should see 0,0 in the SB rows and never see flag 1, total 0 in the plain MP version. Note the words "forbidden by the hardware": the .NET spec allows the JIT to reorder plain reads and writes. Today's x64 JIT may not swap these two lines, but that is not a guarantee the language gives.

Fences: Getting the Order Back

A fence (or barrier) is how you tell the hardware "order matters here". On ARM64 the dmb ish instruction is a full barrier for all cores; on x64 mfence or a lock-prefixed instruction does the same job, and according to the Intel SDM locked instructions are not reordered with reads and writes. In .NET you do not write these directly: Interlocked.MemoryBarrier(), every Interlocked method and entering and leaving a lock are abstractions for which the runtime picks the right instruction for the platform.

A fence has a cost: it makes the core wait until the store buffer drains. Our experiment does not show the difference, because the real cost of each round is synchronizing the threads (all three runs take about 2 seconds). In a tight loop, however, a fence in every iteration brings a measurable slowdown. That is the reason memory models exist: the hardware vendor chooses the fast default behaviour, and code that really needs ordering asks for it explicitly.

The difference between release/acquire and a full fence follows from this. For "write the data, then raise the flag" cases such as message passing, release/acquire is enough and cheap on ARM64 (stlur/ldapur). For "write my intent, then read the other side's" cases such as store buffering (algorithms like Peterson and Dekker), a full fence is required.

In Production

A test that passes on your x64 machine can break on ARM64, and ARM64 is no longer a remote possibility. AWS Graviton, Azure's Cobalt 100 based virtual machines (generally available since October 2024) and Windows on Arm devices are common places where .NET code runs on ARM64. When you build your container image multi-arch and deploy it to ARM64 nodes, an MP-style bug you have never seen on x64 can show up. AWS's guide gives the same warning and adds an important note: code that uses the language's own lock and synchronization abstractions does not notice the difference. The problem is in code written without locks that relies on x86 behaviour.

So if you have a lock-free flag, a cache refresh mechanism you wrote yourself, or code that hands data between two threads through a "ready" field, run a stress test on an ARM64 runner in CI as well. Seeing zero failures on x64 is no proof for this kind of code; in the MP test the x64 hardware already forbids the outcome, so a test running on x64 can never catch this bug.

Keep the lab conditions in mind when you measure. In our experiment the numbers are high because both threads are released at the same moment in every round. In a real application the same bad ordering may show up once in millions of requests; being rare does not make it harmless, it only makes debugging harder.

Common Pitfalls

Testing on x86 and deploying to ARM64. An MP-style bug never shows on x64 hardware; on ARM64 it showed in more than half of the rounds in our experiment. Prove the correctness of lock-free code with memory model rules, not with measurements.

"Guaranteeing" ordering with Thread.Sleep. Saying "write the total, raise the flag 10 ms later" gives no thread any visibility order; it only makes the bug rarer. Ordering comes only from release/acquire, fences or locks.

Taking coherence for consistency. Coherent caches keep the order of the values of a single address. Coherence says nothing about the order between two different fields.

Believing Volatile keeps every order. In the SB test the Volatile version made both threads read 0 in 11,272 of 10 million rounds. Release/acquire does not keep the order of a read that follows a write.

A Small Experiment

★☆☆ Run the litmus-sb and litmus-mp commands on your own machine. If you are on x64, check that the "ready=1,total=0" count of the plain MP version stays at 0 while the plain SB version shows 0,0, and compare with the x64 column of the table.

★★☆ Change FieldOffset(128) in the Cells struct to FieldOffset(4), putting both fields on the same cache line. How did the SB and MP results change? Explain the change in terms of the store buffer and cache line ownership.

★★★ Add the load buffering (LB) test: each thread first reads the other's cell, then writes 1 to its own. Is it possible under sequential consistency for both threads to read 1? The ARM64 model allows it; can you see it on your machine? If you cannot, explain why that does not mean "not allowed".

In this post we looked at the guarantees the hardware gives and saw that x64 and ARM64 run the same code in different orders. How does a language give the same meaning on every piece of hardware it runs on? In the next post of the series we move to the .NET memory model: happens-before, acquire/release, what volatile really means, double-checked locking, and why the JIT can make a loop run forever.