Compare-and-Swap
Subject: Computer and Technology noun /kəmˈpɛr ənd ˈswɑːp/ 1 definition
- concurrency-control
- computer-architecture
- systems-programming
- operating-systems
-
Definition (noun)
Entry #345 · UpdatedCompare-and-Swap (CAS) is an atomic synchronization instruction used in concurrent programming to update shared state without acquiring mutual-exclusion locks. The operation accepts three inputs—a target memory location, an expected current value, and a desired new value—and atomically writes the new value only when the location still holds the expected value. If a competing thread alters the location before the check completes, the write is aborted and the caller receives a failure signal (or the observed current value) so it can reload and retry in a CAS loop. By relying on hardware-enforced atomicity rather than operating system scheduling, CAS serves as the foundation for lock-free data structures and optimistic synchronization, though it requires extra safeguards against the ABA problem and loses efficiency under intense write contention.
Common Forms
Single-Word Hardware CAS: Atomically compares and swaps one machine word (typically 32 or 64 bits) directly through processor instructions such as x86
LOCK CMPXCHGor ARMv8.1 LSECAS.Double-Width CAS (DWCAS): Operates atomically across two contiguous machine words (such as 128 bits via x86-64
LOCK CMPXCHG16B), allowing a pointer to be paired with a monotonic version tag to prevent the ABA problem.Strong and Weak Language Primitives: Standard-library APIs—such as C++
compare_exchange_strongvs.compare_exchange_weakor JavaAtomicReference.compareAndSet—distinguish guaranteed match-success operations from weak variants that permit spurious failures on Load-Linked/Store-Conditional (LL/SC) architectures.Distributed Conditional Writes: Applies CAS semantics beyond CPU memory in key-value stores and coordination systems (such as etcd transactions, ZooKeeper versions, or DynamoDB conditional puts) by gating mutations on a matching revision number or stored value.
Example
Two worker threads share a lock-free Java
AtomicLongrequest counter currently holding42, and both read42before invokingcounter.compareAndSet(42L, 43L). Thread A's CPU executesLOCK CMPXCHGfirst to advance the counter to43, while Thread B's call observes43instead of42, returnsfalse, reloads43, and retries withcompareAndSet(43L, 44L)so neither increment is lost.