# Compare-and-Swap Compare-and-swap (CAS) is an atomic instruction used in multithreading to achieve synchronization. It compares the contents of a memory location with an expected value and, only if they match, modifies that location to a new value — as a single atomic operation. ## How It Works ```text function cas(memory_location, expected_value, new_value): // This entire block executes atomically if *memory_location == expected_value: *memory_location = new_value return true else: return false ``` ## Use Cases - **Lock-free data structures** — stacks, queues, linked lists without mutexes - **Atomic counters** — incrementing a shared counter without locks - **Implementing spinlocks and mutexes** — CAS is the building block for higher-level synchronization - **Optimistic concurrency control** — read, compute, CAS back; retry on failure ## CAS Loop Pattern Since CAS can fail (another thread modified the value), it's typically used in a retry loop: ```java AtomicInteger counter = new AtomicInteger(0); int oldVal, newVal; do { oldVal = counter.get(); newVal = oldVal + 1; } while (!counter.compareAndSet(oldVal, newVal)); ``` ## The ABA Problem If a value changes from A to B and back to A, CAS succeeds even though the value was modified in between. **Solutions:** - **Double-width CAS** — pair with a version counter (`AtomicStampedReference` in Java) - **Hazard pointers** — track which nodes are in use - **Tagged pointers** — embed a counter in unused pointer bits ## Hardware Support | Architecture | Instruction | |---|---| | x86/x86-64 | `CMPXCHG` | | ARM | `LDXR`/`STXR` (ARMv8+), `LDREX`/`STREX` (ARMv7) | | RISC-V | `LR`/`SC` (LL/SC pair) | | SPARC | `CAS` | Some architectures use Load-Link/Store-Conditional (LL/SC) instead, which naturally avoids ABA at the hardware level. ## CAS vs Locks | CAS (Lock-free) | Locks (Blocking) | |---|---| | No thread is ever blocked | Threads wait for lock holder | | No deadlocks possible | Deadlock risk | | Can livelock (spinning) | No livelock | | Better for low contention | Better for high contention | | More complex algorithms | Simpler to reason about | --- See also: [[Double-Checked Locking]], [[Initialization-on-demand Holder Idiom]]