Atomic Read-Modify-Write and the Mutual Exclusion Problem

A critical section is a region of code that must not execute in two threads at the same time. The requirement is easy to state and, at first sight, easy to satisfy: each thread looks at the other thread’s flag, enters if it is clear, and raises its own flag on the way in. The scheme fails. It fails not because of a coding mistake but because a load followed by a store is two events, and between them anything may happen. Every mutual exclusion primitive in an operating system rests on an instruction that makes the pair one event.

Two flags that both threads see as clear

Written in C11 atomics, the naive protocol looks like this:

/* Incorrect: the check and the set are separate steps. */
static atomic_int flag[2];

static void enter(int self)
{
    int other = 1 - self;
    while (atomic_load_explicit(&flag[other], memory_order_seq_cst))
        ;                       /* wait until the other side leaves */
    atomic_store_explicit(&flag[self], 1, memory_order_seq_cst);
}

static void leave(int self)
{
    atomic_store_explicit(&flag[self], 0, memory_order_seq_cst);
}

Each individual operation is atomic. The protocol built from them is not. Thread A reads flag[1] and finds 0. Thread B reads flag[0] and finds 0. Both then store 1 into their own flag and enter, and the critical section holds two threads. Making each access sequentially consistent does not help: the bad interleaving is a legal sequentially consistent execution, since both loads can precede both stores in a consistent global order.

Dijkstra’s 1965 solution, and the later Dekker and Peterson algorithms, escape by adding a second shared variable that breaks the symmetry, a turn or a victim field, so that at least one of the two threads must observe the other’s intent. Those algorithms are correct only under sequential consistency, which is why they are taught as history rather than used. On a machine that buffers stores or reorders a load ahead of a store to a different address, the proof no longer applies, and the code needs fences on every path to restore the assumption. The alternative is to stop trying to build mutual exclusion out of ordinary loads and stores and to ask the hardware for a single operation that reads and writes without an interval between.

What “atomic” means at the coherence layer

An atomic read-modify-write is one instruction whose read and write are indivisible with respect to every other core on the machine. Three implementation families exist, and the differences matter for what the programmer must handle.

x86 uses the LOCK prefix on instructions such as XCHG, CMPXCHG, and ADD. On processors from the P6 family onward the prefix does not lock the system bus; the core acquires the target cache line exclusively for the duration of the instruction and keeps it in the modified state of the coherence protocol, so no other core can read or write the line until the instruction retires. The bus lock remains as a fallback for operations that cannot be handled that way, notably a locked access that crosses a cache-line or page boundary, and taking one is expensive precisely because it suspends the other cores’ traffic. The XCHG instruction with a memory operand is atomic by definition, without a prefix, which is why it is the natural primitive for a test-and-set lock.

Arm and RISC-V instead expose a pair: a load that establishes an exclusive claim and a store that succeeds only if the claim still holds. On AArch64 these are LDXR and STXR, with LDREX and STREX as the AArch32 spelling; the load marks the address in a per-core exclusive monitor, and the store returns a status register value of zero on success and nonzero on failure. The monitor is cleared by any write to the line from any core, by an exception, and by a context switch, so a STXR can fail even when no competing thread touched the variable. RISC-V provides the same shape as lr.w/sc.w, and additionally provides true atomic memory operations such as amoswap.w that behave like the x86 instructions.

The pair design has a property worth naming: it is immune to the ABA problem, because the store checks a claim rather than a value. A compare-and-swap cannot distinguish “unchanged since the load” from “changed away and back”. For a lock whose state alternates between zero and one, that distinction is usually harmless; for a pointer in a lock-free list it is not, which is the subject of lock-free reclamation and the ABA problem.

A lock from one instruction

The smallest correct lock is a single word with two states, plus an instruction that tests and sets it in one step.

#include <stdatomic.h>

typedef struct {
    atomic_flag held;           /* ATOMIC_FLAG_INIT is the unlocked state */
} spinlock_t;

static void lock(spinlock_t *l)
{
    while (atomic_flag_test_and_set_explicit(&l->held,
                                             memory_order_acquire))
        ;                       /* keep trying until the flag was clear */
}

static void unlock(spinlock_t *l)
{
    atomic_flag_clear_explicit(&l->held, memory_order_release);
}

atomic_flag_test_and_set compiles to XCHG on x86 and to a load-exclusive/store-exclusive loop on Arm and RISC-V. The loop is what makes it a lock rather than a single attempt. Mutual exclusion follows from the indivisibility: exactly one of the concurrent attempts observes the old value zero, and only that attempt exits the loop.

The acquire and release annotations are not decoration. Without them the compiler and the hardware are free to move the loads and stores inside the critical section to before the lock acquisition or after the release, which produces a critical section that does not exclude anything. The ordering contract is developed in acquire and release ordering; for now the point is that the atomicity of the flag and the ordering of the surrounding memory are two separate guarantees, and a lock needs both.

There is a practical refinement. A bare test-and-set loop issues a write to the lock word on every iteration, and each write invalidates the line in every other core’s cache. Under contention with many waiters, that traffic is the dominant cost. A test-and-test-and-set loop spins on a plain load, which can be served from a shared cache line, and only attempts the atomic operation once the line appears free. The window between the load and the attempt is a race that the atomic operation resolves, so correctness is unaffected; only the traffic changes.

Progress, starvation, and what the flag cannot promise

The three classical requirements for a mutual exclusion algorithm are mutual exclusion, progress, and bounded waiting. A test-and-set lock satisfies the first two. It does not satisfy the third. The instruction has no notion of arrival order, so a core that loses the race can lose again indefinitely while newer arrivals keep winning. On a lightly loaded machine this is invisible; on a contended one it becomes a latency tail. Restoring order requires a queue rather than a single flag, which is why real kernel locks are ticket locks or linked-list locks, as described in ticket locks and MCS queues.

The cost of the primitive is also worth stating in orders of magnitude. An uncontended atomic read-modify-write on a modern x86 core costs tens of cycles. The same operation on a line owned by another core costs a cache-line transfer, which is on the order of a hundred nanoseconds on a two-socket machine, several hundred cycles. A lock that is acquired and released in a handful of instructions can therefore spend most of its time in the coherence protocol rather than in the critical section.

Alignment and the width of the guarantee

The guarantee covers one naturally aligned quantity no wider than the instruction supports. A word that crosses a cache-line boundary, or a structure that is not aligned to its size, can be touched by two separate coherence transactions, and the atomicity evaporates. The same applies to quantities wider than the widest single instruction: a 16-byte compare-and-swap exists on x86-64 as CMPXCHG16B and requires 16-byte alignment, and a 128-bit atomic on a 64-bit Arm core is only available when the architecture implements the large-system-extensions atomics and the address is aligned to 16 bytes. A 32-bit x86 machine has no single instruction that adds 64 bits atomically, though it does have an 8-byte compare-and-swap in CMPXCHG8B; the 16-byte CMPXCHG16B exists only in 64-bit mode. Armv7 has LDREXD/STREXD. A 64-bit counter on a core without a 64-bit atomic operation is therefore built from a retry loop around a lock or around a wide compare-and-swap rather than from one increment.

This is why atomic types in C11 and C++11 are specified with an alignment requirement at least as large as their size, and why a struct containing an atomic member must not be packed. A packed atomic is not merely slow; it is a data race the compiler cannot detect. The portable rule is that any object shared between threads without a lock must be accessed through an atomic type, and any atomic type must be allowed to impose its alignment.

The cases where the primitive is the wrong tool

Three failure modes follow directly from the nature of the instruction.

A thread that holds a spinlock and is descheduled blocks every other thread for the length of its absence. On a uniprocessor this is a permanent deadlock, since the holder cannot run while a waiter spins. This is why spinlocks in kernels are paired with a rule that preemption is disabled while they are held, and why user-space code should not spin on a lock that a preempted thread may own.

A spinlock also makes no attempt to order waiters by importance, so a high-priority thread can wait behind a low-priority one for an unbounded time. The inversion is a scheduling problem rather than an atomicity problem, treated in priority inversion and inheritance.

Finally, the primitive only covers one word. Any protocol that needs to update two words together, or to wait for a condition rather than for a flag, needs more than an atomic instruction. Waiting without burning a core requires giving the decision to the scheduler, which is what the futex interface does: the atomic instruction is the fast path, and the kernel is the slow path, as covered in futex wait and wake.