Memory Consistency, Atomics and Fences

When two threads share memory, in what order can they see each other's writes? On a simple machine you would expect the order the program wrote them. On real hardware, that's not always what happens: store buffers, out-of-order execution and caches all let memory operations appear reordered to another core. A memory consistency model is the contract that says which orders are allowed, and fences and atomic instructions let software demand more. This article explains the models, shows the classic examples, and uses real RISC-V code for atomics and locks.

13 min read | Intermediate

What You'll Learn

• Explain sequential consistency and why hardware relaxes it
• Work out the outcomes of the store buffering litmus test
• Use RISC-V fences and acquire and release ordering
• Read real atomic instructions and a load-reserved loop

A Question of Order

Cache Coherence Protocols guarantees that all cores agree on the order of writes to any single location. It says nothing about two different locations. Look at this common pattern, in which one thread prepares data and raises a flag:

Surely thread 1 prints 42? On many real machines, without special instructions, it might print 0. If flag becomes visible before data does, thread 1 sees the flag raised and reads old data. Each location is coherent, but the two writes appear in a different order to the second core.

The rules for this are the memory consistency model, sometimes just called the memory model. It is part of the instruction set: a contract saying what values a load may return in a multi-threaded program.

Sequential Consistency

The natural model is sequential consistency (SC), defined by Leslie Lamport in 1979. A multi-threaded run must act as if all the memory operations of all threads were placed in one overall sequence, with each thread's own operations in program order. It's as though the threads take turns at a single memory.

It's easy to reason about, but it is costly. It would forbid a store buffer letting a later load pass an earlier store, and that optimization is one of the most valuable in any fast processor. Hardware that enforced it fully would have to give up much of the performance gained by load and store queues.

Store Buffering: A Litmus Test

A litmus test is a tiny multi-threaded program used to test a memory model. The most famous one has x and y both starting at 0:

Under SC, what can r0 and r1 end up as? One of the stores must come first in the overall order, and its thread's load then comes after. Try every interleaving: you get (0,1), (1,0) or (1,1). But never (0,0): for r0 to be 0, core 0's load must come before core 1's store, and for r1 to be 0, core 1's load must come before core 0's store. Together with program order, that forms a cycle, which is impossible.

Yet (0,0) really does happen on nearly all real processors:

Each store goes into that core's store buffer, and its load goes straight to memory and finds the old value. Neither core sees the other's store until the buffers drain. Each core is correct from its own point of view, and the buffers only delay the visibility of a store.

Relaxed Models

Architectures choose how much reordering to allow:

Total store order (TSO), the x86 model, allows just the first reordering, the one store buffers need. Stores stay in order, so the flag example works on x86 without any special instruction. Relaxed models, such as RISC-V's default RVWMO (RISC-V Weak Memory Ordering) and Arm's, allow all four, unless the program asks otherwise. Note that dependent accesses are still respected, and a single thread always sees its own operations in order. The reordering can be seen only by other threads.

Relaxed models give hardware more freedom: stores can leave the buffer in any order, and loads can run out of order without being tracked and replayed. The price is paid by software, which has to say explicitly where order matters.

Fences

A fence, or memory barrier, is an instruction that orders memory operations around it. On RISC-V, fence names what must come before and what must come after, using r for reads and w for writes. Devices have their own letters, i and o.

fence rw, rw      # all earlier reads and writes before all later ones
fence w, w        # earlier writes before later writes
fence r, rw       # earlier reads before later reads and writes

The flag example becomes correct on RVWMO with two fences:

The writer's fence keeps the data ahead of the flag, and the reader's fence keeps the flag read ahead of the data read. A programmer rarely writes these by hand. In C, _Atomic variables with a memory order, or a mutex, tell the compiler what is needed, and the compiler picks instructions for the target. This is also the reason that volatile is not enough for threads: it stops the compiler from reordering, but not the hardware. Memory-Mapped I/O looks at the device version of the same issue.

Atomic Operations

Multicore Processors and Shared Memory showed that two threads incrementing a counter can lose an update, since load, add and store are three separate steps. An atomic operation does a read-modify-write as one indivisible step. The RISC-V A extension offers two kinds.

Atomic Memory Operations

AMO instructions do a simple operation directly on memory: swap, add, and, or, xor, min, max. A real example is atomic_fetch_add_explicit(&n, 1, memory_order_relaxed), compiled by GCC with -march=rv32ia:

add:
    lui      a5,%hi(n)
    li       a4,1
    addi     a5,a5,%lo(n)
    amoadd.w zero,a4,0(a5)     # add 1 to memory, as one step
    ret

To do this, the core gets the line in Modified state, as in Cache Coherence Protocols, and holds on to it through the whole operation, so no other core can get in between.

Load-Reserved and Store-Conditional

For more complicated updates, there is a pair of instructions. lr.w, load-reserved, reads a word, and marks a reservation on the address. sc.w, store-conditional, writes only if the reservation is still valid, meaning nobody else wrote there. It sets a register to 0 on success. If it failed, the loop tries again. A compare-and-swap built with GCC gives:

    fence    iorw,ow        # order earlier accesses first
1:  lr.w.aq  a0,0(a5)       # load the current value
    bne      a0,a1,2f       # not what we expected? give up
    sc.w.aq  a4,a2,0(a5)    # try to store the new value
    bnez     a4,1b          # another core got in first: retry
2:

The fence and the .aq bits appear because this compare-and-swap asked for the strongest ordering. Unlike a built-in swap, this pattern can build any read-modify-write. RISC-V limits what can sit between the two, to make sure some thread always makes progress.

Acquire and Release

Atomics carry two ordering bits. aq, acquire, means that no later memory operation in this thread may appear before this one. rl, release, means that no earlier one may appear after it. They match the entry and exit of a critical section. A real spin lock from GCC looks like this:

acquire:
    ...
1:  amoswap.w.aq a4,a4,0(a2)    # atomically set the lock to 1, get the old value
    bne          a4,zero,1b     # it was held: try again
    ret

release:
    ...
    fence iorw,ow               # everything earlier completes first
    amoswap.w    zero,zero,0(a5) # then clear the lock
    ret

Acquire ensures the protected accesses don't leak out of the top of the critical section, and release ensures they don't leak out of the bottom. These are cheaper than full fences, since they order only in one direction.

How Hardware Honors the Model

A core that follows a strict model doesn't have to run slowly. It can speculate. A TSO processor runs loads out of order internally, and watches for coherence messages that would reveal the reordering. If a line it has read early is written by another core before the load commits, it replays the load. To other cores, the result looks as if the loads ran in order, though they did not. This trick gives strong ordering at low cost, using the load queue described in Load/Store Queues and Memory Disambiguation.

On a relaxed machine, a fence is often simple: the core stops issuing later memory operations until the earlier ones are done, and drains its store queue. Acquire and release can be handled more cheaply, because each needs only one direction of ordering. The model is therefore a contract about what can be observed. It says nothing about how the hardware must work inside, which leaves designers free to do anything that gives the same visible results.

The compiler is part of this too. It reorders memory accesses for its own reasons, for example moving a load out of a loop. C's atomic types tell the compiler to keep such accesses in order, and they also make it emit the right fences for the target. A thread-safe program is therefore a three-way agreement between the programmer, the compiler and the hardware.

What Atomics Cost

An atomic operation on an uncontended line in the core's own cache takes tens of cycles at most. When several cores compete for it, each operation means moving the line, which costs tens to hundreds of cycles. So a lock that is often contended can stop a program from scaling, whatever the core count. Much effort goes into reducing contention, by using per-thread data, fine-grained locks, or read-mostly schemes.

Fences aren't free either. A full fence drains the store buffer and stops the reordering that gives the core its speed. On a large core, it can take tens of cycles. Code should use the weakest ordering that is correct.

Common Mistakes