Compare-and-Swap: The Atomic Primitive Behind Lock-Free Programming
Compare-and-swap gave processors an atomic conditional update primitive powerful enough to build lock-free algorithms and, in theory, solve consensus for any number of threads.
Concurrent updates need a moment that cannot be split
Suppose two threads both read the same shared value, compute replacements and then write. If the read-check-write sequence can be interleaved, one thread may overwrite the other’s work. Atomic read-modify-write instructions solve this by making a compound state transition appear indivisible to competing processors.
Compare-and-swap, commonly abbreviated CAS, became one of the most important such primitives because it makes the update conditional on the memory still containing the value the caller previously observed.
CAS turns optimism into a retry loop
A thread reads a value, computes a desired replacement and asks the processor to install it only if the old value is unchanged. Failure means another thread won the race, so the operation can reload and try again.
IBM System/370 made compare-and-swap a machine instruction
IBM documentation for the System/370 lineage describes a Compare and Swap instruction that compares a register value with memory and conditionally replaces memory as one atomic operation. Current IBM language documentation still exposes built-ins whose implementation relies on the System/370 CS instruction.[1]
The instruction was designed for multiprocessor synchronization, where software needed a reliable way to update shared words without a conventional lock around every operation.
Conditional update is more expressive than test-and-set
Test-and-set is excellent for acquiring a simple lock. CAS can encode a wider range of state transitions because the expected old value is supplied by the caller rather than fixed to one lock state.
Lock-free algorithms use CAS to protect state transitions rather than code regions
Traditional mutexes protect a critical section: one thread owns the lock while it executes several ordinary operations. Lock-free algorithms instead attempt atomic updates to shared data structures so that some operation can continue even when another thread is delayed.
This can avoid deadlock and reduce convoying, but it moves complexity into the data-structure algorithm. Correctness must account for retries, memory reclamation, ABA effects and the memory-ordering rules around the atomic instruction.
Herlihy showed that CAS has unusual theoretical power
Maurice Herlihy’s 1991 wait-free synchronization paper classified synchronization primitives by consensus number. In that hierarchy, compare-and-swap has infinite consensus number, meaning it can solve consensus for any finite number of processes in the model used by the paper.[2]
This result gave CAS a theoretical significance beyond its practical use. It is not merely a faster lock instruction; it is a universal primitive for constructing wait-free shared objects under the relevant assumptions.
Consensus number separates superficially similar atomics
Operations such as test-and-set and fetch-and-add are useful but have lower consensus power in Herlihy’s hierarchy. CAS therefore occupies a special place in the theory of concurrent objects.
Linearizability supplied the correctness condition for concurrent objects
Herlihy and Jeannette Wing’s 1990 paper defined linearizability as the illusion that each concurrent operation takes effect at one instantaneous point between invocation and response.[3]
CAS-based data structures are often designed around a successful CAS as that linearization point. The machine instruction supplies an atomic moment; the proof explains why that moment corresponds to the abstract operation the programmer intended.
Practical lock-free structures turned the primitive into a systems technique
Michael and Scott’s nonblocking queue showed how CAS could support a practical concurrent FIFO queue without using a single global mutex for every enqueue and dequeue.[4] The algorithm became highly influential in concurrent data-structure design.
Such algorithms also reveal the costs of lock-free programming: a short primitive can support sophisticated progress guarantees, but the surrounding pointer and memory-management logic can be substantially more difficult than conventional locked code.
The ABA problem exposes the limits of comparing only a value
A location can change from A to B and back to A between a read and a CAS. The equality test succeeds even though the state changed in between. Tagged pointers, version counters and safe reclamation schemes are common responses.
Modern languages expose CAS through standardized atomic APIs
The C++ atomic library provides compare-exchange operations with explicit memory-order parameters, allowing portable software to request conditional atomic updates while specifying ordering constraints.[5]
This is a striking historical path: a hardware primitive introduced for multiprocessors became part of mainstream language standards, where it serves as the foundation for lock-free containers, reference counters, runtimes and synchronization libraries.
Why compare-and-swap belongs in the concurrency canon
CAS connects hardware, theory and software unusually cleanly. IBM supplied an atomic conditional instruction; Herlihy showed the primitive’s consensus power; Herlihy and Wing supplied a correctness framework; practical algorithms demonstrated how it could replace locks in real data structures.[1][2][3][4]
The primitive’s lasting importance lies in what it enables: optimistic concurrency in which threads proceed independently and coordinate at precisely defined atomic state transitions rather than holding a lock across an entire code region.
Works Cited
- 01
- 02
- 03
- 04
- 05cppreference — std::atomic compare_exchange operations en.cppreference.com
CodeHistory is a living archive. Citations document the evidence used for this edition; later evidence may refine the account.
Submit a research lead