vault

Compare-and-Swap and Load-Linked Store-Conditional

16 min read

Compare-and-Swap and Load-Linked Store-Conditional

Compare-and-swap (CAS) and load-linked/store-conditional (LL/SC) are the two hardware primitives on which essentially all lock-free software is built. Both are atomic read-modify-write (RMW) operations — a single indivisible step that reads a memory word and conditionally writes it back — but they express the “conditional” differently. CAS names an expected value: it writes the new value only if the location still holds exactly what the caller last saw. LL/SC splits the operation into two instructions — a load that registers a reservation on the address, and a store that succeeds only if nothing has touched that address since the load. Their theoretical significance was pinned down by Maurice Herlihy’s Wait-Free Synchronization (ACM TOPLAS, Jan 1991, pp. 124–149): both sit at the very top of the consensus hierarchy with consensus number ∞, meaning either one is universal — from it alone you can build a wait-free implementation of any concurrent object. Weaker primitives such as test-and-set and fetch-and-add cannot.

This is the theory note for the atomic RMW primitives. For the concrete kernel implementation see Compare-and-Swap and cmpxchg in the Kernel; for the Go runtime’s exposure of these see Atomic Operations in Go. The trap that CAS-but-not-LL/SC falls into is covered in The ABA Problem; the progress guarantees these primitives enable are defined in Lock-Free Wait-Free and Obstruction-Free.

Mental Model

Think of an atomic RMW as a hardware-enforced tiny critical section that spans exactly one memory word for exactly one instruction (or one LL–SC pair). Within it, the read and the conditional write cannot be split by any other core — the cache-coherence protocol guarantees that while the operation is in flight, no other core observes or modifies the word. That single indivisible gate is what lets many threads cooperate on shared state without a lock: instead of excluding others up front, each thread does its work speculatively and then tries to commit through the gate, retrying if it was beaten.

flowchart TD
  subgraph CAS["CAS: name the expected value"]
    A1["old = load(p)"] --> A2["new = f(old)"]
    A2 --> A3{"CAS(p, old, new)<br/>atomic: does *p still == old?"}
    A3 -->|"yes → store new, return success"| A4["committed"]
    A3 -->|"no → leave *p, return current"| A1
  end
  subgraph LLSC["LL/SC: reserve, then store-conditional"]
    B1["old = LL(p)<br/>register reservation on p"] --> B2["new = f(old)"]
    B2 --> B3{"SC(p, new)<br/>reservation still valid?"}
    B3 -->|"yes → store new, return 1"| B4["committed"]
    B3 -->|"no → do NOT store, return 0"| B1
  end

Two ways to express a conditional atomic write. What it shows: CAS decides whether to commit by comparing a value (does the word still equal the snapshot?); LL/SC decides by checking a reservation (has this address been touched at all since the load?). The insight to take: the two are almost interchangeable in software — both wrap in a retry loop — but they fail for different reasons. CAS is fooled if the value was changed and changed back (the ABA problem); LL/SC is not, because its reservation is broken by any intervening write, but it pays for this with spurious failures where the store-conditional can fail even when nothing logically conflicted.

The read-modify-write family

A plain x = x + 1 is three separate machine steps — load, add, store — and any of them can interleave with another thread, so two increments can both read the same old value and one update is lost (Wikipedia: read-modify-write). An RMW instruction collapses read-and-conditional-write into one atomic unit that no other core can interrupt. The classical members, in ascending order of power, are:

  • test-and-set (TAS) — atomically set a bit to 1 and return its old value. The primitive behind the simplest spinlock.
  • fetch-and-add (FAA) — atomically add an increment to a word and return the old value (Wikipedia: fetch-and-add). On x86 this is LOCK XADD. It underlies ticket locks and lock-free counters.
  • swap / exchange (XCHG) — atomically write a new value and return the old.
  • compare-and-swap (CAS) and load-linked/store-conditional (LL/SC) — the two conditional RMWs that are the subject of this note.

On a coherent multiprocessor the atomicity is realized by the cache-coherence protocol: the core acquires the target cache line in an exclusive/modified state and holds it for the duration of the RMW, so no other core can read-then-write the same line concurrently. On x86 this is signaled by the LOCK prefix, which on modern chips locks the cache line (not the whole memory bus) for the operation (Wikipedia: CAS).

Compare-and-swap

CAS takes three arguments — an address p, an expected value old, and a new value — and does, indivisibly: read *p; if it equals old, store new; return either a boolean (succeeded?) or the value actually found. Herlihy, Luchangco and Moir give the compact definition: a CAS(a, e, n) stores n and reports success only “if the value currently stored at address a matches the expected value e” (Herlihy–Luchangco–Moir 2003). Because the read-compare-store is one atomic step, a successful CAS is a proof: the location held exactly old for the whole operation and now holds new.

CAS first appeared as the CS/CDS (compare-and-swap / compare-double-and-swap) instructions on the IBM System/370 in the 1970s, introduced specifically to let multiprocessor operating-system code coordinate without disabling interrupts (Wikipedia: CAS). On x86 it is the CMPXCHG instruction, present since the 80486, which requires the LOCK prefix to be atomic across cores.

The CAS-loop idiom

CAS on its own is just a conditional store; the pattern that makes it useful is the retry loop. To atomically apply a function f to a shared word:

uint64_t old, new;
do {
    old = atomic_load(p);   // 1. snapshot the current value
    new = f(old);           // 2. compute the update privately (no lock held)
} while (!CAS(p, old, new)); // 3. commit iff *p is still the snapshot; else retry

Line 1 takes a snapshot. Line 2 does the real work on a private copy — this can be arbitrary computation, but it must be idempotent and side-effect-free, because it may run many times. Line 3 is the atomic gate: if some other thread committed between the load and here, *p no longer equals old, the CAS fails, and the loop re-reads the fresh value and tries again. The only serialized point is the single CAS instruction, so an uncontended update is nearly free and contention degrades into extra loop iterations rather than into blocking. Researchers found that adding exponential backoff between failed attempts materially improves throughput under high contention, because it thins out the storm of colliding CAS attempts (Wikipedia: CAS).

Weak and strong CAS

Language-level CAS comes in two flavors, most visibly in C++‘s std::atomic: compare_exchange_strong and compare_exchange_weak. The weak form is permitted to fail spuriously — to report failure and leave the value untouched even when *p did equal old. This concession exists precisely because on LL/SC hardware (below) a value-comparing CAS is synthesized from an LL/SC pair that can itself fail spuriously; forcing the strong (never-spurious) semantics there would require an extra inner loop. The rule of thumb: use the weak form when you are already inside a retry loop (a spurious failure just costs one more cheap iteration), and the strong form when a single decisive attempt is wanted.

Uncertain

Verify: the exact wording of the C++ standard’s compare_exchange_weak/strong spurious-failure contract. Reason: cppreference returned HTTP 403 during this task, so the claim rests on the LL/SC spurious-failure mechanism (verified below) rather than the C++ spec text itself. To resolve: read [atomics.types.operations] in a current C++ working draft. #uncertain

Double-width CAS and the ABA problem

CAS’s blind spot is that it compares values, not history: if the word goes A → B → A between the snapshot and the CAS, the CAS succeeds as if nothing happened, even though the state it referred to may be stale (a freed-and-reallocated node, say). This is the ABA problem, treated in depth in The ABA Problem. The standard hardware fix is a double-width CAS that swaps a pointer and an adjacent monotonic counter in one atomic step: pack (pointer, tag) into a double word and increment tag on every update, so an A → B → A cycle changes the tag and the CAS correctly fails (Wikipedia: CAS). x86 provides CMPXCHG8B (64-bit compare-exchange, since the Pentium) and CMPXCHG16B (128-bit, on x86-64) exactly for this.

Load-linked / store-conditional

LL/SC splits the conditional RMW across two instructions. Load-linked (also load-reserved or load-and-reserve) reads the word at an address and, as a side effect, registers a reservation on that address in the core. A later store-conditional to the same address stores the new value only if no update has occurred to that location since the load-linked, and reports whether it stored (Wikipedia: LL/SC). The decisive property: the store-conditional fails if the address was written even if the value was written back to what it was — so LL/SC is inherently immune to the ABA problem, because it keys on “was this address touched?” rather than “does this value match?”

The reservation and spurious failures

Hardware does not track reservations byte-precisely. An implementation registers a reservation set — an implementation-defined span of bytes that at least covers the accessed word (RISC-V “A” extension). Any write to any byte in that set breaks the reservation. Because the set may be as coarse as a whole cache line, a write to an unrelated neighbor can break a reservation — a false conflict. Worse, on most real machines a context switch, an interrupt, another load-linked, or even an unrelated ordinary load or store between the LL and the SC can clear the reservation and make the SC fail even with no genuine conflict at all (Wikipedia: LL/SC). These spurious failures are why all real LL/SC is called weak LL/SC, and why LL/SC code must keep the LL–SC window minimal — no function calls, no memory traffic, ideally just the compute of new.

Architectures

LL/SC is the RMW substrate of essentially every RISC architecture, because it avoids baking a complex compare-and-swap into the pipeline:

  • DEC Alpha — ldl_l / stl_c (the original, and where the name “load-locked” comes from).
  • ARM — LDREX / STREX in ARMv6/v7; LDXR / STXR (and acquire/release variants LDAXR / STLXR) in ARMv8-A. CLREX explicitly clears a reservation.
  • POWER / Power ISA — lwarx / stwcx (load-word-and-reserve / store-word-conditional).
  • MIPS — LL / SC, the instructions that gave the pattern its name.
  • RISC-V — LR.W/LR.D and SC.W/SC.D in the “A” (atomic) extension.

RISC-V’s forward-progress guarantee

RISC-V is unusually explicit about when an LL/SC loop is guaranteed to eventually succeed, which illuminates the general problem. It defines a constrained LR/SC loop: the LR and SC must target the same address and size, and — critically — the code between them must avoid other loads/stores, backward branches, and system instructions (RISC-V “A” extension). For such loops in memory regions with the “LR/SC eventuality property,” the execution environment must guarantee that eventually either this hart’s SC succeeds, or some other hart/device writes the reservation set (RISC-V ISA manual). The ISA forbids extra memory accesses in the window because they could evict cache lines that back the reservation, and permitting them “could impose undue restrictions on … cache and TLB size and associativity.” An LR/SC sequence that violates these rules is unconstrained and “might succeed on some attempts on some implementations, but might never succeed on other implementations.” The lesson generalizes: LL/SC gives ABA-immunity for free, but only guarantees forward progress if you keep the window tiny — which is exactly why C libraries synthesize CAS from LL/SC inside a bounded retry and expose a weak CAS to the programmer.

RISC-V AMOs vs LR/SC

RISC-V also provides single-instruction atomic memory operations (AMOs) — amoadd, amoswap, amoand, amoor, amoxor, amomax, amomin — that load, apply a binary operator, and store back in one instruction (RISC-V “A” extension). AMOs are the fetch-and-add / swap family; they are simpler and often faster than an LR/SC loop but cannot express an arbitrary conditional update, which is what CAS/LL-SC are for.

The consensus hierarchy — why these two are special

The reason CAS and LL/SC matter beyond convenience is Herlihy’s wait-free consensus hierarchy. A wait-free implementation of a concurrent object is one where “any process can complete any operation in a finite number of steps, regardless of the execution speeds on the other processes” (Herlihy 1991). Herlihy asks: given two object types X and Y, can you build a wait-free X using only instances of Y (plus registers)? He answers it with a single numeric invariant.

Each object type has a consensus number: the maximum number of processes that can use it to solve the classic consensus problem wait-free — every process proposes a value, all must agree on one of the proposed values, and the protocol must always terminate. Herlihy proves that an object with consensus number n cannot be used to build a wait-free implementation of any object with a higher consensus number. That is an impossibility result, and it stratifies all primitives:

Consensus numberObjects (per Herlihy 1991, Fig. 1)
1atomic read/write registers
2test-and-set, swap, fetch-and-add, wait-free queue, wait-free stack
2n − 2n-register atomic assignment
∞compare-and-swap, memory-to-memory move and swap, fetch-and-cons, sticky byte, augmented queue

Reading the table top to bottom is a hierarchy of synchronization power. Plain shared memory (registers) has consensus number 1: with only reads and writes you cannot even get two processes to agree wait-free — the bottom of the hierarchy, and the reason “just use a volatile flag” is not enough to build lock-free structures. test-and-set and fetch-and-add climb to 2 — enough for two-process consensus but provably not three, which is why they build spinlocks and counters but not arbitrary lock-free objects.

At the top, with consensus number ∞, sits compare-and-swap: it can solve consensus for any number of processes. Herlihy’s universality theorem turns this into a construction: “an object is universal in a system of n processes if and only if it has a consensus number greater than or equal to n” (Herlihy 1991). Because CAS has consensus number ∞, it is universal for any number of processes — there is a mechanical (if not always efficient) construction of a wait-free version of any sequential object type using only CAS. LL/SC is universal for the same reason; in Herlihy’s table it is grouped with the ∞-power primitives. This is the precise sense in which “if your machine has CAS (or LL/SC), it is powerful enough to run any wait-free algorithm” — and machines that offer only registers, test-and-set, or fetch-and-add are provably not.

Uncertain

Verify: Herlihy’s TOPLAS volume/issue number. Reason: the PDF page footer reads “Vol. 11, No. 1” while the widely cited reference is Volume 13, Issue 1 (both agree on Jan 1991, pp. 124–149) — likely an OCR artifact. To resolve: check the ACM Digital Library record. The pagination and year are certain; only the volume digit is in doubt. #uncertain

Failure Modes and Common Misunderstandings

“A successful CAS means the value never changed.” False — it means the value equals old now. If it went A → B → A you get a success on stale state. This is the ABA problem; use LL/SC, a version tag with double-width CAS, or a safe-reclamation scheme (see The ABA Problem, Hazard Pointers).

“LL/SC never fails if there’s no conflict.” False — real LL/SC fails spuriously on context switches, interrupts, unrelated memory traffic, and coarse reservation granules. Code must retry and keep the LL–SC window minimal.

“CAS is lock-free, so my algorithm is lock-free.” Not automatically. A CAS loop is lock-free only if some thread always makes progress; if the loop body is unbounded or if threads can starve, you may have merely obstruction-free or even a livelock. The progress a data structure actually guarantees is a separate question (Lock-Free Wait-Free and Obstruction-Free).

Livelock under contention. Many threads CASing the same hot word can each keep failing and retrying — the system does work but no individual thread finishes promptly. Exponential backoff and combining/queuing (e.g. MCS-style) mitigate this.

Emulating CAS on LL/SC changes semantics. A CAS built from LL/SC can fail spuriously and (unlike true CAS) will not suffer ABA. Portable code should not assume either the strong-CAS or the ABA-prone-CAS behavior; program to compare_exchange_weak in a loop.

Alternatives and When to Choose Them

  • Locks (mutex/spinlock). Simpler to reason about; the right default when the critical section is more than a couple of words or the contention is low. CAS/LL-SC only pay off when you need non-blocking progress or extreme scalability on a tiny piece of state. See Spinlocks versus Blocking Locks.
  • fetch-and-add / atomic counters. When the update is a pure increment or an unconditional swap, prefer FAA/XCHG (or a RISC-V AMO) over a CAS loop: they are single instructions, contention-tolerant, and cannot livelock. They just cannot express a conditional update.
  • Double-width CAS vs LL/SC for ABA. On x86 (no LL/SC) you reach for CMPXCHG16B with a tag; on ARM/RISC-V you can lean on LL/SC’s native ABA-immunity instead. Portable libraries abstract this behind a tagged-pointer or reclamation layer.
  • Transactional memory. Hardware TM (Intel TSX) or software TM lets you make a multi-word region conditionally atomic, which single-word CAS cannot; see Software Transactional Memory. It trades away the simplicity and predictability of single-word RMW.

Production Notes

Every mainstream language’s atomics compile down to these primitives: C11/C++11 atomic_compare_exchange_*, Java’s AtomicReference.compareAndSet / VarHandle, Go’s sync/atomic.CompareAndSwap* (Atomic Operations in Go), and Rust’s AtomicUsize::compare_exchange / compare_exchange_weak all lower to LOCK CMPXCHG on x86 and to an LL/SC retry on ARM/POWER/RISC-V. The Linux kernel’s cmpxchg/try_cmpxchg family (Compare-and-Swap and cmpxchg in the Kernel) is the same story with explicit memory-ordering control. The practical engineering wisdom that recurs in production lock-free code: (1) prefer compare_exchange_weak inside loops so ARM/RISC-V don’t pay a double loop; (2) keep the retry body branch-free and side-effect-free; (3) add backoff on hot words; and (4) never treat CAS success as proof of unchanged history — pair it with tags or hazard pointers when reclaiming memory. Because CAS/LL-SC are universal, the temptation is to build everything lock-free; in practice the universal construction is too slow to use directly, and hand-tuned structures like the Michael–Scott queue are what ship (The Treiber Stack and Michael-Scott Queue).

See Also

Graph View

Backlinks