Read-Modify-Write Atomicity and the Ordering It Carries

An atomic read-modify-write is a single memory operation that reads a location, computes a new value from the old one, and writes it back, with the guarantee that no other operation to that location occurs between the read and the write. That guarantee cannot be assembled from a load and a store, no matter how carefully they are ordered, because the gap between them is a window in which another processor can act. Everything else about atomics follows from how the hardware closes that window.

The closing mechanism is the interesting part, and it has a direct effect on cost and on the ordering that comes along for free.

Why load-then-store is not an increment

The failure is easy to state. Two threads execute a non-atomic increment of a shared counter, which compiles to a load, an add, and a store. Both loads read the same old value, both compute the same new value, both store it, and the counter has advanced by one instead of two. Every individual access is atomic and coherent: each load returned a value that some store produced, each store wrote a well-formed value, and the per-location order is a valid serialisation of the two stores. Coherence is satisfied and the program is wrong.

The missing property is atomicity of the pair, which is a requirement on the sequence of accesses, not on any single one. Coherence constrains individual accesses and cannot express it. The memory model constrains ordering between accesses and cannot express it either, since the two accesses are ordered by program order and the reordering is done by the other thread’s interleaving, not by this thread’s.

This is why atomics are a distinct category of operation rather than a pattern built from ordinary ones. The hardware provides operations that are atomic across the read and the write, and no amount of fencing or ordering makes a load-store pair equivalent to one.

How the window is closed in hardware

Three implementation strategies appear, with different costs.

Bus locking. The oldest and simplest: the processor asserts a lock signal that prevents any other processor from using the interconnect for the duration of the read-modify-write. It works on any topology with a shared bus and it serialises all memory traffic, not just traffic to the locked location. On a machine with many cores, the cost is severe because unrelated accesses are blocked. The x86 LOCK prefix originated this way, and early implementations used it literally.

Cache-line locking. The modern approach on coherent machines: the processor acquires the line in an exclusive state, performs the read-modify-write in its own cache, and releases exclusivity afterwards. Other processors that want the line stall on the coherence protocol rather than on a bus signal, and accesses to other lines proceed normally. The cost is one coherence transaction for ownership plus the invalidations of any other sharers. This is why an atomic operation on a contended line is expensive while an atomic operation on a private line is cheap: the contention is the cost, not the atomicity.

Load-linked / store-conditional. The RISC approach, used on Arm, MIPS, and PowerPC. A load-linked reads the location and registers a reservation on it. A store-conditional writes the new value only if the reservation is still valid, meaning no other write to that line has occurred since the load-linked; otherwise it fails and writes nothing. The software retries the whole sequence on failure.

The third approach is notable because it moves the atomicity into a pair of instructions with an explicit failure path. The retry loop is visible in the code, which makes the contention behaviour explicit: under heavy contention, the loop can spin many times, and each iteration costs a load-linked and a failed store-conditional. It also means the atomicity is not a hardware guarantee on a single instruction but a software protocol over two, and the protocol must be written correctly.

#include <stdatomic.h>

/* A compare-and-swap loop: the failed exchange is the normal path. */
int atomic_inc(_Atomic int *p) {
    int old = atomic_load_explicit(p, memory_order_relaxed);
    int neu = old + 1;
    while (!atomic_compare_exchange_weak_explicit(
               p, &old, neu, memory_order_relaxed, memory_order_relaxed)) {
        /* old now holds the value we raced with; recompute */
        neu = old + 1;
    }
    return neu;
}

The important detail is that the failure of the exchange is not an error. It is the normal outcome under contention, and the loop is the mechanism, not a fallback. Code that treats a failed exchange as exceptional, or that performs side effects inside the loop body beyond the memory update, breaks the protocol. On implementations built from a load-linked / store-conditional pair, the restriction is sharper still, because the conditional store is permitted to fail spuriously: the loop body must be idempotent apart from the memory update itself, and it must not contain another load-linked on a different address, which would overwrite the reservation.

Compare-and-swap as the general primitive

Most lock-free algorithms are built on compare-and-swap rather than on an increment, because compare-and-swap can express any update that is a function of the observed value. The operation reads the location, compares it to an expected value, and writes a new value only if they match, reporting whether it succeeded. On x86 this is CMPXCHG with the LOCK prefix; on Arm it is a load-linked / store-conditional pair plus a comparison.

The cost profile has two regimes that matter for algorithm design.

Under no contention, the operation acquires the line exclusively, performs the update, and continues. The cost is one coherence transaction, and the line typically stays in the core’s cache in an exclusive state, so a subsequent compare-and-swap on the same line is cheap.

Under contention, every successful compare-and-swap invalidates the other cores’ copies, so every other core’s next attempt misses and must reacquire. The result is a ping-pong in which the line moves between cores and each move costs an interconnect round trip. Adding more cores makes it worse, because more cores are competing for the same line and each acquisition invalidates all the others.

This is why lock-free stacks and queues scale poorly under high contention even though they are correct, and why designs use combining, elimination, or per-thread structures when contention is expected. The algorithmic fix is to reduce the number of cores touching one line, not to reduce the number of atomic operations.

The ordering an atomic carries

An atomic read-modify-write with sequentially consistent ordering acts as a full fence, and the reason is structural rather than stipulated. The operation cannot execute until prior operations from the same thread have drained, because it must read the current value and a pending store to that location would change it. It cannot retire until it is globally visible, because its result depends on being the unique modification at that point. Everything after it therefore begins only after it has completed.

That gives three practical consequences.

A lock acquisition needs no fence around it. The atomic operation that takes the lock is the barrier, and the critical section’s accesses are ordered after it by the atomic’s own semantics. This is why a lock cmpxchg sequence in a spinlock is correct without an MFENCE, and why adding one is wasted cycles.

A release of a lock likewise needs no fence. The atomic store that clears the lock word is ordered after the critical section by the atomic’s semantics.

A relaxed atomic carries none of this ordering. It is atomic but not ordered, so it does not constrain the operations around it. This is the useful case: an atomic counter that is only ever incremented and never used to guard data needs atomicity and not ordering, and a relaxed increment avoids the fence cost. The distinction is the same one described in Acquire and Release as One-Way Ordering Constraints, applied to an operation that is already atomic.

The ordering strength is chosen per operation, and mixing them in one algorithm is where bugs appear. A compare-and-swap that publishes a pointer with relaxed ordering does not order the initialisation of the object the pointer refers to, even though the pointer store itself is atomic. The atomicity and the ordering are separate properties, and an operation can have either without the other.

Atomicity across widths and the ABA problem

Two failure modes are worth naming because they are not ordering failures and are not fixed by fences.

Width. The atomic guarantee applies to a single access no wider than the machine’s supported atomic width. A structure whose state does not fit in one word needs either a lock or a double-width compare-and-swap, and the latter is only available on some architectures and only for aligned accesses. A 16-byte compare-and-swap exists on x86-64 with the appropriate feature, and it is not portable. A structure that needs to update two words atomically and has no double-width primitive must use a lock, a seqlock, or an indirection through a single pointer.

ABA. Compare-and-swap compares values, not versions. If a location goes from A to B and back to A between the read and the compare, the compare succeeds and the update proceeds as if nothing happened, even though the intervening change may have invalidated the assumption the algorithm made. The standard remedy is a version counter carried alongside the value, which requires the value and counter to fit in one atomic word, or a tagged pointer that uses otherwise unused address bits. Hazard pointers and epoch-based reclamation solve a related problem, in which a node is freed and a new node is allocated at the same address, and the algorithm cannot tell them apart.

Neither problem is a memory-ordering problem, and neither is solved by a fence. They are consequences of what the atomic primitive can express, and they bound what lock-free algorithms can be built from a single-word compare-and-swap.

What the primitive does not give

An atomic operation guarantees that one location changes indivisibly. It says nothing about two locations changing together, and it says nothing about ordering between two atomics on different locations beyond what their orderings specify. A protocol that must update two words consistently needs a lock, or a design in which one word is the authoritative state and the other is derived.

It also does not guarantee fairness. A compare-and-swap loop can starve under contention, and no hardware primitive promises otherwise. Bounded waiting requires a lock with a queue, which is why lock-free is a statement about progress for the system rather than for any individual thread. The distinction between lock-free, wait-free, and obstruction-free progress is not a memory-model property, but it is the reason atomics alone do not compose into arbitrary concurrent data structures. The coherence traffic that atomics generate is the subject of Cache Coherence Is Per Location, Consistency Is Not, and the propagation guarantees that a released atomic provides to a third thread are Propagation, Cumulativity, and Why Weak Models Need Transitive Visibility.