CompareandSwap

Compare-and-swap, often abbreviated CAS, is an atomic synchronization primitive used in concurrent programming. It allows a thread to update a shared memory location only if its current value matches an expected value, providing a simple way to implement lock-free data structures and coordination without heavy locking.

Operation: CAS(ptr, expected, new) checks the value at ptr. If it equals expected, CAS sets *ptr to new and returns true, indicating the swap occurred. If the current value differs, CAS leaves the location unchanged and returns false. The operation is atomic, so no interleaving reads or writes can observe a partial result.

Use cases and patterns: CAS is widely used to implement lock-free stacks, queues, and reference counters, as well as to atomically update pointers or indices. CAS often participates in loops known as compare-and-swap loops: repeatedly loading the current value, computing a desired update, and attempting CAS until it succeeds. These loops enable progress without conventional locks, though they can be sensitive to contention and memory ordering.

Hardware and design considerations: CAS is provided by many CPUs (for example, cmpxchg on x86 and similar instructions on other architectures) and exposed in various languages through atomic libraries or the C11/C++11 atomic facilities. Common issues include the ABA problem, where a value changes from A to B and back to A, potentially fooling CAS. Memory ordering, visibility guarantees, and potential livelock or liveliness concerns also influence CAS-based algorithms, often requiring backoff strategies and careful synchronization design.