Atomicity and Ordering Are Separate Guarantees in the C Memory Model

Two threads increment a shared integer, each doing its share of the work, and the final value falls short of the expected total. No optimisation flag fixes this, because the fault is not in the code generation: counter++ is a read, an addition, and a write, and two threads can interleave between the read and the write so that one update is silently overwritten. Declaring the object atomic removes that failure completely. No interleaving can observe a half-finished increment, and no increment is lost.

That is only half of what an atomic object buys, and the other half is easier to miss. A producer fills a buffer and then sets a flag; a consumer spins on the flag and then reads the buffer. The flag can be atomic, the writes to it can be indivisible, and the consumer can still read an empty buffer. Indivisibility constrains one memory location at a time. It says nothing about the order in which two different locations become visible to another thread, and the C and C++ memory models keep those two properties in separate clauses. Code that treats an atomic type as a complete answer to a shared-memory problem is code that compiles, runs, and is wrong.

Lost updates are a problem of indivisibility

A read-modify-write on a shared location is not one operation at the machine level. The load brings the current value into a register, the arithmetic happens in the register, and the store writes the result back. Between the load and the store the location is unguarded, so a second thread can perform its own load from the same old value and store its own result on top of the first. Two increments, one net change.

Atomicity means the whole sequence is indivisible: some total order exists over all the modifications, every modification is visible to every thread, and no thread observes an intermediate state. Processors provide this with different machinery. On x86-64 an atomic fetch-and-add compiles to a single instruction carrying the lock prefix, which asserts the bus lock or, more commonly, takes exclusive ownership of the cache line for the duration. On Arm and POWER the same operation is a loop: a load-linked instruction reads the location and arms a monitor, the arithmetic runs, and a store-conditional attempts to write; the store fails if any other write to that line intervened, in which case the loop retries. The retry loop is not an implementation detail of the language. It leaks into the semantics, which is why the standard exposes both a weak and a strong form of compare-and-exchange, discussed in Compare-and-Swap and the Retry Loop.

Hardware also gives more atomicity than the language does. Intel’s manuals guarantee that naturally aligned accesses of certain sizes within a cache line are performed atomically, and 64 bytes is the common cache line size. None of that helps a program written against the C abstract machine, because the standard grants atomicity only to objects declared with _Atomic. Reading a plain object while another thread writes it is a data race regardless of what the instruction happens to do.

Visibility is a problem of ordering

The second failure has nothing to do with interleaving. Suppose one thread executes data[0] = 42; and then ready = 1;, and another thread waits for ready and then reads data[0]. If the two statements are ordinary stores, three separate mechanisms can reorder them.

The compiler may. It sees no dependency between the two stores and no reason to preserve their order, so it may emit them in the other sequence, or keep data[0] in a register and write it much later. The processor may. x86-64 orders stores to stores, but a weakly ordered core such as Arm or POWER is free to make the second store visible before the first. And even with both of those behaving, the reader’s own loads can be satisfied from a stale copy: a core’s load may be serviced from its own cache, or issued speculatively before the branch that tested ready has resolved.

The result is a reader that observes the flag set and the payload absent. Making ready atomic does not repair this. An atomic store guarantees that the flag’s own value moves from 0 to 1 indivisibly; it does not say that the plain store to data[0] happened before it.

Sequenced-before, synchronizes-with, happens-before

The C standard defines three relations, and almost every correct use of atomics is an argument about the third one built from the first two.

Sequenced-before is the within-thread relation: one evaluation precedes another in the abstract execution of a single thread, including the ordering imposed by full expressions and sequence points.

Synchronizes-with is the cross-thread relation, and it is created only by specific pairs of operations. A store to an atomic object with release semantics synchronizes with a load of that same object with acquire semantics that reads the value stored, or a value from the release sequence headed by that store. An atomic read-modify-write can carry both, and a fence can participate in a related rule described in Acquire and Release: What Each Ordering Forbids.

Happens-before is the transitive closure of sequenced-before and synchronizes-with. It is the only relation that grants visibility. If evaluation A happens-before evaluation B, then A’s effects are visible to B.

A data race is then defined precisely: two accesses to the same memory location, at least one of them a write, at least one of them not atomic, and no happens-before relation between them. A program containing a data race has undefined behaviour. This is not a formality. Because the compiler is allowed to assume no race exists, it may hoist a load of a plain flag out of a loop, cache it in a register, and turn while (!done) ; into an infinite loop even though another thread does eventually store to done. That transformation is legal, and it is the reason a busy-wait on a plain variable is not merely inefficient but meaningless.

Publishing with a release store

The canonical repair is a release store paired with an acquire load. The release store orders every preceding memory operation in the thread before the store becomes visible; the acquire load orders every following operation after it.

#include <stdatomic.h>
#include <stdbool.h>

struct payload { int a; int b; };

static struct payload *slot;
static atomic_bool ready;

static void publish(struct payload *p)
{
    slot = p;                                    /* plain store, ordered by what follows */
    atomic_store_explicit(&ready, true, memory_order_release);
}

static struct payload *consume(void)
{
    if (!atomic_load_explicit(&ready, memory_order_acquire))
        return NULL;
    return slot;                                 /* the acquire ordered this load after the flag */
}

The store to slot is not atomic and needs no atomic type. What makes the consumer’s read safe is that the release store to ready synchronizes with the acquire load, and the acquire load happens-before the read of slot. The happens-before chain is what removes the race; the atomicity of the flag is incidental, contributing only the guarantee that the consumer never reads a half-written bool.

The same code with memory_order_relaxed on both sides is a race. Relaxed provides atomicity and nothing else: the store to ready still cannot be split, but it carries no ordering, so the store to slot may become visible after it, and the consumer’s read of slot has no happens-before relation to the producer’s write.

What the orderings cost, per architecture

The strength of an ordering is a constraint on the hardware, and hardware that already provides the constraint charges nothing for it.

On x86-64, the processor model is total store order, which preserves load-to-load, load-to-store and store-to-store ordering and permits only a load to be satisfied before an older store to a different location drains. Consequently an acquire load and a release store both compile to ordinary mov instructions; the only cost is a compiler barrier preventing the optimiser from moving code across them. A sequentially consistent store is the expensive one, because it must prevent the store-buffer case, and the compiler emits a locked exchange or a fence instruction.

On Armv8-A the same three operations are distinct instructions. Acquire and release have dedicated forms that carry the ordering in the instruction, and sequential consistency additionally requires a barrier in positions where the acquire/release pair alone does not produce a single total order. The gap between relaxed and sequentially consistent is therefore much wider on weakly ordered cores than on x86, and code tuned on x86 tends to underestimate it.

The axis is strength against cost, and the cost is paid per operation, on the critical path. The temptation is to mark everything sequentially consistent and stop thinking. That is a defensible default for correctness, since it is the ordering the plain atomic_load and atomic_store forms use, and it is the only one that is easy to reason about without a formal model. It is not free on any architecture that is not x86, and a publication that needs only visibility of one location does not require it.

Where the model stops helping

volatile is not an alternative. It prevents the compiler from eliding or fusing accesses, which makes it correct for memory-mapped device registers and for variables shared with a signal handler, and it provides no atomicity and no cross-thread ordering. A volatile flag shared between threads is still a data race.

Atomic types are not guaranteed to be lock-free. The standard provides atomic_is_lock_free and the ATOMIC_LLONG_LOCK_FREE style macros, and a 64-bit atomic on a 32-bit target may be implemented with an internal lock. Only atomic_flag is required to be lock-free; every other type is reported at run time or through the macros, which may say “sometimes” or “never” for a given size. That matters in two places: inside a signal handler, where taking a lock can deadlock against the interrupted thread, and in code that assumes a lock-free algorithm cannot block.

Atomicity also does not extend to aggregates. A load or store of an atomic struct is indivisible in the abstract machine, so an implementation that cannot cover the whole object with one lock-free instruction has to protect it with a lock, and the lock-free query on that type reports the truth. Plain multi-word objects have the opposite problem: a reader can see the low half of one value and the high half of another. On a 32-bit target, a plain 64-bit integer has exactly this tearing problem, which is why the standard’s atomic types are the only portable way to share it.

The model’s remaining sharp edge is that it describes executions, not intentions. Two accesses either have a happens-before relation or the program is undefined, and there is no partial credit for a race that almost always works. What an implementation must do to establish that relation is a hardware question as much as a language one, and the answer differs by architecture.