CompareExchange

CompareExchange, commonly known as compare-and-swap (CAS), is an atomic operation used in concurrent programming. It compares the value stored at a memory location with an expected value and, if they are equal, replaces the stored value with a new one. The operation is indivisible: it either succeeds and updates the value, or fails and leaves the memory unchanged. Depending on the language or API, the function may report success as a boolean, or return the observed value prior to the attempt.

CAS is a cornerstone of lock-free synchronization. It enables threads to coordinate updates to shared state without using mutexes, which can reduce contention and improve scalability in multi-threaded programs. Typical use cases include updating pointers to shared data structures, implementing reference counting, and constructing lock-free stacks, queues, or counters.

Memory ordering is an important aspect of CompareExchange. Many platforms distinguish between strong and weak variants of CAS. A strong CAS guarantees that a successful update will occur if the current value matches the expected one, while a weak CAS may fail spuriously even when the values match. Weak CAS is often used inside loops to reduce contention. Memory ordering semantics define visibility and ordering constraints for the operation, ensuring consistent behavior across threads.

A common challenge is the ABA problem: the value at the location may change from A to B and back to A, misleading a CAS that only checks for equality. Mitigations include version tagging or adding additional hazard pointers or epoch-based reclamation techniques.

Common implementations include C11 atomic_compare_exchange and related functions, C++ std::atomic<T>::compare_exchange_weak/strong, Java AtomicReference.compareAndSet, and .NET Interlocked.CompareExchange. Across languages, CAS remains a primary tool for building robust, scalable concurrent data structures.