Compare-and-Swap (CAS)

A Compare-and-Swap operation performs three actions as a single, indivisible atomic unit:

• Reads the current value from a shared memory location.
• Compares this value to an expected value provided by the calling thread.
• Conditionally writes a new value only if the comparison succeeds.

This atomicity is guaranteed by the hardware (e.g., via a CPU instruction like CMPXCHG on x86) and prevents the classic lost update problem that occurs when interleaved reads and writes from multiple threads corrupt shared state.

CAS enables lock-free (and often wait-free) algorithms. Unlike a mutex, which suspends (blocks) a thread if the lock is held, a thread using CAS in a loop continually retries the operation without being descheduled by the OS.

Key advantages:

• Avoids deadlock: No holding of locks, eliminating circular wait conditions.
• Improves scalability: Under contention, threads make progress via retries rather than blocking, which is costly with many threads.
• Priority inversion resistance: A high-priority thread is not blocked indefinitely by a low-priority thread holding a lock.

It is the primary primitive for building non-blocking stacks, queues, and reference-counting systems like std::shared_ptr.

The ABA problem is a classic challenge when using CAS. It occurs when a location's value changes from A to B and back to A between the time a thread reads it and attempts the CAS. The CAS will succeed, but the state of the shared data structure may have changed invalidly.

Example: A thread reads the head pointer A of a lock-free stack. Another thread pops A, deallocates it, allocates a new node that coincidentally has the same address A, and pushes it. The first thread's CAS (expected=A, new=X) succeeds, corrupting the stack.

Common solutions:

• Tagged pointers: Use a spare bits (a version counter or tag) alongside the pointer. The combined value changes even if the address repeats.
• Hazard pointers: Track which pointers are in use to prevent premature reclamation.

CAS is implemented directly in CPU instruction sets and exposed through high-level language intrinsics and libraries.

Hardware Instructions:

• x86/x86-64: CMPXCHG (compare and exchange), CMPXCHG8B, CMPXCHG16B.
• ARM: LDREX/STREX (Load-Exclusive/Store-Exclusive) instruction pair.
• RISC-V: LR.W/SC.W (Load-Reserved/Store-Conditional).

Language & Library APIs:

• C/C++: std::atomic_compare_exchange_strong and _weak in <atomic>.
• Java: java.util.concurrent.atomic.AtomicInteger.compareAndSet().
• Rust: AtomicPtr::compare_exchange in std::sync::atomic.

These abstractions allow developers to write portable lock-free code without writing assembly.

A CAS operation is not just an atomic update; it also acts as a memory barrier or fence, enforcing ordering constraints on memory operations around it. This is critical for correctness in weak memory models (like those of ARM and PowerPC).

When a CAS succeeds, it typically has release semantics for the write, making prior writes visible to other threads. It also has acquire semantics for the read, ensuring subsequent reads by this thread see the latest data.

Example in C++: std::atomic<int> val; int expected = val.load(std::memory_order_relaxed); do { // ... compute newVal ... } while (!val.compare_exchange_weak(expected, newVal, std::memory_order_acq_rel, std::memory_order_acquire));

The chosen memory orders (acq_rel for success, acquire for failure) prevent dangerous reordering of instructions around the CAS loop.

CAS is one of several atomic Read-Modify-Write (RMW) operations. Understanding its relation to others clarifies its use cases.

• Fetch-and-Add (FAA): Atomically adds a value and returns the old value. Ideal for uncontended counters. Simpler than CAS for increment/decrement but cannot implement complex conditional updates.
• Load-Linked / Store-Conditional (LL/SC): A more flexible pair of instructions used in ARM/RISC-V. LL loads a value and monitors the address. A subsequent SC succeeds only if no other store occurred to that address. This can avoid the ABA problem more naturally but may suffer from spurious failures.
• Test-and-Set (TAS): An older primitive that atomically sets a bit and returns its old value. Used to build simple locks (spinlocks) but is less versatile for complex lock-free structures compared to CAS.

CAS provides a powerful balance of flexibility and widespread hardware support, making it the default choice for most non-blocking algorithm designs.

Atomic operations are indivisible read-modify-write instructions that complete without interruption from other threads. They are the hardware foundation for CAS and other synchronization primitives.

• Key Property: Guarantees that the operation appears to execute instantaneously from the perspective of other threads.
• Hardware Support: Implemented via CPU instructions like LOCK CMPXCHG (x86) or LDREX/STREX (ARM).
• Common Types: Includes operations like fetch-and-add, swap, and compare-and-swap. They are used to build higher-level constructs like spinlocks and lock-free data structures.

A lock-free algorithm is a non-blocking concurrent algorithm that guarantees system-wide progress. At least one thread will complete its operation in a finite number of steps, regardless of the state or speed of other threads.

• Progress Guarantee: Prevents deadlock and priority inversion. Threads may starve individually, but the system as a whole advances.
• Implementation Basis: Typically built using atomic operations like CAS to manage state transitions.
• Example: A lock-free queue uses CAS to atomically update the head or tail pointer, allowing concurrent enqueue and dequeue operations without a global mutex.

A memory barrier or memory fence is a type of instruction that enforces ordering constraints on memory operations issued before and after the barrier. It is crucial for correct synchronization in systems with weak memory consistency models.

• Function: Prevents the compiler and CPU from reordering loads and stores across the barrier, ensuring visibility of writes to other threads.
• Relation to CAS: CAS operations typically imply a full memory barrier, ensuring the atomic update is globally visible. Weaker forms (e.g., compare_exchange_weak in C++) may allow more reordering for performance.
• Types: Includes acquire (subsequent reads cannot move before the barrier), release (prior writes cannot move after the barrier), and full barriers.

The ABA problem is a classic challenge in lock-free programming where a location's value changes from A to B and back to A between a thread's read and its CAS attempt, causing the CAS to succeed incorrectly.

• Cause: The CAS only checks for value equality, not for whether the value is the same instance of A. This can break algorithms that rely on pointer stability.
• Mitigation Strategies:
  • Tagged Pointers: Use a spare bits in the pointer (e.g., a version counter or tag) that is incremented on each update. The CAS checks both the pointer and the tag.
  • Hazard Pointers: Track pointers that are in use to prevent reclamation and reuse.
• Impact: A key consideration when designing CAS-based data structures like stacks and queues.

A mutex is a synchronization primitive that enforces mutual exclusion, allowing only one thread at a time to execute a critical section of code or access a shared resource.

• Blocking Primitive: Threads attempting to acquire a held mutex are put to sleep (blocked), requiring OS context switches.
• Contrast with CAS: Mutexes are a higher-level, blocking construct. CAS is a low-level, non-blocking operation used to implement mutexes (e.g., a spinlock).
• Trade-off: Mutexes simplify programming but can lead to deadlock, priority inversion, and overhead from blocking. CAS-based algorithms are more complex but avoid these issues for fine-grained operations.

A wait-free algorithm is the strongest non-blocking progress guarantee, where every thread is guaranteed to complete its operation in a bounded number of steps, independent of the actions of other threads.

• Stronger than Lock-Free: While lock-free guarantees some thread progresses, wait-free guarantees every thread progresses. This prevents starvation.
• Implementation Complexity: Wait-free algorithms are significantly more complex to design and prove correct than lock-free ones. They often require threads to help complete other threads' operations.
• Relation to CAS: CAS can be used in wait-free constructions, but achieving wait-freedom typically requires more sophisticated coordination, such as helping protocols and careful memory management to bound retry loops.