Skip to main content
Definition Website Computer and Technology

Compare-and-Swap

Subject: Computer and Technology noun /kəmˈpɛr ənd ˈswɑːp/ 1 definition

  1. Definition (noun)

    Entry #345 · Updated

    Compare-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 CMPXCHG or ARMv8.1 LSE CAS.

    • 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_strong vs. compare_exchange_weak or Java AtomicReference.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 AtomicLong request counter currently holding 42, and both read 42 before invoking counter.compareAndSet(42L, 43L). Thread A's CPU executes LOCK CMPXCHG first to advance the counter to 43, while Thread B's call observes 43 instead of 42, returns false, reloads 43, and retries with compareAndSet(43L, 44L) so neither increment is lost.