The CAS Operation: Atomic Compare-and-Swap

In the landscape of concurrent programming, one atomic operation stands as the universal foundation upon which virtually all modern synchronization is built: Compare-and-Swap (CAS). This seemingly simple operation—compare a memory location to an expected value, and if they match, swap in a new value, all atomically—is the cornerstone of lock-free data structures, non-blocking algorithms, and high-performance concurrent systems.

From the Java AtomicInteger you use in everyday programming to the Linux kernel's spinlock implementations, from database transaction managers to garbage collectors, CAS is the hidden workhorse that makes concurrent software possible. Understanding CAS deeply—its semantics, its guarantees, its limitations, and its proper use—is essential knowledge for any systems programmer.

This page provides a rigorous, comprehensive treatment of the CAS operation itself. We will dissect its semantics, explore its hardware implementation across architectures, analyze memory ordering implications, and establish the formal foundation for reasoning about CAS-based algorithms.

Compare-and-Swap (CAS), also known as Compare-and-Exchange (CMPXCHG) on x86 architectures, is an atomic instruction that performs a conditional update of a memory location. The operation takes three operands:

1. Address: A pointer to the memory location to be modified
2. Expected Value: The value we expect to find at that location
3. New Value: The value to write if the expectation matches

Semantic Definition

The CAS operation executes the following logic atomically (as a single, indivisible operation):

CAS(address, expected, new_value):
    if (*address == expected):
        *address = new_value
        return true   // Success: value was as expected, now updated
    else:
        return false  // Failure: value was different, not modified

The critical property is atomicity: the entire compare-and-conditional-swap sequence occurs as one indivisible unit. No other operation on any processor can observe the memory location in an intermediate state (i.e., after the comparison but before the swap).

Why CAS is Fundamental

CAS is consensus number ∞ in the theory of concurrent objects, meaning it can solve the consensus problem for any number of processes. This theoretical property translates to practical power: CAS can implement any concurrent data structure that is possible to implement, making it a universal synchronization primitive.

In contrast, simpler atomic operations like Test-and-Set (TAS) have consensus number 2—they can only solve consensus for two processes. This is why CAS has become the dominant atomic primitive in modern architectures:

• Intel x86/x64: CMPXCHG, CMPXCHG8B, CMPXCHG16B
• ARM: LDREX/STREX (load-exclusive/store-exclusive pairs), CAS in ARMv8.1+
• RISC-V: LR/SC (load-reserved/store-conditional)
• PowerPC: lwarx/stwcx. (load-word-and-reserve-indexed / store-word-conditional-indexed)

Every modern processor architecture provides some form of CAS or equivalent functionality, making CAS-based algorithms portable across platforms.

To appreciate CAS, we must understand how it differs from—and surpasses—other atomic operations. Let's compare CAS with the simpler atomic primitives.

Test-and-Set (TAS)

Test-and-Set atomically reads a memory location and sets it to 1 (or true), returning the previous value.

TAS(address):
    old = *address
    *address = 1
    return old

TAS is simpler than CAS but less powerful:

• TAS always writes 1, regardless of the current value
• TAS cannot conditionally update based on current state
• TAS has consensus number 2 (only works for 2-process mutual exclusion)

Fetch-and-Add (FAA)

Fetch-and-Add atomically reads a value and adds a delta to it, returning the previous value.

FAA(address, delta):
    old = *address
    *address = old + delta
    return old

FAA is useful for counters but cannot implement general synchronization:

• FAA always succeeds (unconditional)
• FAA cannot be used for conditional state transitions
• FAA also has consensus number 2

Why CAS is Superior

The Power of Conditional Updates

The key advantage of CAS is its conditional nature. CAS only modifies the memory location if it currently holds a specific expected value. This conditionality enables a powerful programming pattern:

1. Read the current state
2. Compute the desired new state based on the current state
3. Attempt to atomically transition from current to new using CAS
4. Retry if someone else changed the state in the meantime

This pattern—called optimistic concurrency control—allows multiple threads to make progress without blocking each other, as long as they don't actually conflict. In low-contention scenarios, this dramatically outperforms lock-based approaches.

With TAS or FAA, we cannot implement this pattern because the modification is unconditional. We must know in advance what value to write, independent of the current state. CAS allows the decision to depend on the current state, enabling rich state machines and complex data structures.

Understanding how CAS is implemented in hardware demystifies its behavior and explains its performance characteristics. Different processor architectures implement CAS through different mechanisms, but all provide the same fundamental guarantee of atomicity.

x86/x64: The CMPXCHG Instruction

On Intel and AMD processors, CAS is implemented via the CMPXCHG family of instructions:

• CMPXCHG — Compare and exchange for 8, 16, or 32-bit operands
• CMPXCHG8B — Compare and exchange 8 bytes (64 bits)
• CMPXCHG16B — Compare and exchange 16 bytes (128 bits, x64 only)

The instruction works as follows:

; CMPXCHG destination, source
; Implicit operand: EAX (or RAX for 64-bit) holds expected value

CMPXCHG [memory], new_value
; If [memory] == EAX:
;     [memory] = new_value
;     ZF = 1 (zero flag set, indicating success)
; Else:
;     EAX = [memory]  (load actual value into EAX)
;     ZF = 0 (zero flag clear, indicating failure)

The LOCK Prefix

For multi-processor systems, CMPXCHG must be preceded by the LOCK prefix to ensure atomicity across all CPUs:

LOCK CMPXCHG [global_var], ebx

The LOCK prefix instructs the processor to:

1. Assert the bus lock or use cache-locking protocols (MESI)
2. Ensure exclusive access to the cache line containing the memory location
3. Prevent other processors from accessing that cache line during the operation
4. Issue memory barriers to prevent memory reordering around the instruction

ARM: Load-Exclusive / Store-Exclusive (LL/SC)

ARM processors (prior to ARMv8.1) use a different approach called Load-Link/Store-Conditional (LL/SC), implemented as LDREX (Load Exclusive) and STREX (Store Exclusive):

1. LDREX: Reads the value and sets an exclusive monitor on the address
2. STREX: Attempts to write; succeeds only if the exclusive monitor is still valid

The exclusive monitor is invalidated if any other processor writes to the same cache line, or if certain events occur (interrupts, context switches). This provides atomicity without an explicit lock.

LDREX/STREX vs CMPXCHG

Cache Coherence and CAS

Modern multi-processor systems maintain cache coherence using protocols like MESI (Modified, Exclusive, Shared, Invalid). Understanding how CAS interacts with cache coherence explains its performance characteristics:

1. Before CAS: The processor must acquire the cache line in Exclusive or Modified state
2. During CAS: Other processors' copies of the cache line are invalidated
3. After CAS: The modified cache line is in Modified state, visible to other processors on-demand

This cache coherence activity is the primary source of CAS overhead in high-contention scenarios. When multiple processors contend for the same variable, cache lines bounce between processors, creating significant traffic on the memory bus or interconnect.

Memory Ordering Guarantees

Atomic CAS operations provide sequentially consistent semantics on most platforms:

• Full memory barrier: On x86, LOCK-prefixed instructions act as full memory barriers, preventing reordering of memory operations around them
• Acquire-release semantics: CAS typically provides at least acquire semantics on success (all subsequent reads see writes before the CAS) and release semantics (all prior writes are visible to other threads seeing the CAS)

This makes CAS ideal for implementing synchronization primitives that require memory visibility guarantees.

Modern programming languages provide high-level abstractions for CAS operations, hiding the architecture-specific details while exposing the essential semantics. Understanding these APIs is crucial for writing portable concurrent code.

C/C++: The Atomic Library

C11 and C++11 introduced standardized atomic operations, including CAS:

#include <stdatomic.h>  // C11
// or
#include <atomic>        // C++11

The primary CAS functions are:

• atomic_compare_exchange_strong: Never fails spuriously
• atomic_compare_exchange_weak: May fail spuriously, but can be more efficient in loops

Java: AtomicInteger and VarHandle

Java provides atomic classes since JDK 1.5 and more flexible atomic operations via VarHandle since JDK 9:

CAS is not without pitfalls. The most famous is the ABA problem, a subtle bug that can occur when a value changes from A to B and back to A between a read and a subsequent CAS operation.

The Problem Illustrated

Consider a lock-free stack implemented with CAS:

1. Thread 1 reads top = A (pointing to node A)
2. Thread 1 is suspended
3. Thread 2 pops A, pops B, pushes A back (perhaps a recycled node)
4. Thread 1 resumes, performs CAS(top, A, C)
5. CAS succeeds because top is still A!

But the stack structure has changed—perhaps B is now leaked, or the new A points to invalid memory. The CAS succeeded because it cannot detect that the value was modified and restored.

Solutions to the ABA Problem

Several techniques address the ABA problem:

1. Tagged Pointers (Version Counting)

Augment each pointer with a version counter. The CAS operates on the combined pointer+counter, and the counter is incremented on every modification. The ABA scenario now has A₁ → B → A₂, where A₁ ≠ A₂.

2. Double-Wide CAS (DCAS/CMPXCHG16B)

Use 128-bit CAS to atomically compare-and-swap both a pointer and a counter. x86-64's CMPXCHG16B supports this.

3. Hazard Pointers

Threads announce which nodes they're accessing. Other threads skip reclamation of announced nodes. Ensures nodes aren't recycled while in use.

4. Epoch-Based Reclamation

Nodes are only recycled after all threads have completed any operation that started before the node was removed.

5. Reference Counting

Maintain reference counts on nodes. Nodes are only freed when their reference count reaches zero.

CAS operations interact with the memory model in important ways. Understanding memory ordering is essential for correct concurrent programming, as modern processors and compilers aggressively reorder memory operations for performance.

The Memory Visibility Problem

Without proper memory ordering, changes made by one thread may not be visible to other threads—or may become visible in a surprising order. Consider:

// Thread 1
data = 42;          // (A)
ready = true;       // (B)

// Thread 2
while (!ready);     // (C)
assert(data == 42); // (D) — May fail!

The assertion can fail because:

1. Compiler reordering: The compiler might move (A) after (B) as an optimization
2. CPU reordering: The processor might execute stores out of order
3. Cache visibility: Thread 2 might see ready = true before it sees data = 42

Memory Ordering Semantics

C11/C++11 define several memory orderings:

CAS and Memory Ordering

CAS is a read-modify-write operation, so it touches memory in two ways: it reads the current value and potentially writes a new value. This leads to an interesting question: what memory ordering does a CAS provide?

Default behavior (seq_cst): By default, most languages use sequentially consistent ordering for CAS. This provides the strongest guarantees:

• All threads agree on a total order of all seq_cst operations
• Operations before the CAS (in program order) are visible to threads that see the CAS's effect
• Operations after the CAS see all prior effects from other threads

Custom ordering in C++: C++ allows specifying separate orderings for success and failure cases:

Platform-Specific Behavior

x86/x64: The x86 memory model is relatively strong (Total Store Order). LOCK-prefixed instructions like CMPXCHG act as full memory barriers, preventing any reordering around them. This means even memory_order_relaxed CAS on x86 gets acquire-release semantics "for free".

ARM/RISC-V: These architectures have weaker memory models. Memory barriers must be explicitly generated based on the requested memory order. A relaxed CAS truly provides only atomicity, with separate barrier instructions needed for ordering.

This architectural difference has implications:

• Code relying on x86's strong ordering may break on ARM
• Using proper memory orderings ensures portability
• The C/C++ memory model is designed to be architecture-neutral

While CAS is powerful, it has limitations that affect algorithm design and performance. Understanding these limitations helps in choosing appropriate synchronization strategies.

Single-Word Limitation

Standard CAS operates on a single memory word (typically 32 or 64 bits, or 128 bits with CMPXCHG16B). This creates challenges when atomically updating multiple locations.

The Multi-Word Update Problem:

// Cannot make this atomic with single CAS:
struct Account {
    int balance;
    int last_transaction;
};

// We want: atomically update both balance AND last_transaction
// But CAS can only compare-and-swap one field at a time

Solutions:

• Pack multiple small values into one word (e.g., two 32-bit values into 64 bits)
• Use indirection: point to immutable structures, CAS the pointer
• Use Software Transactional Memory (STM)
• Use Multi-Word CAS implementations (MCAS) built from single CAS
• Use locks when atomic multi-word update is required

Contention and Scalability

CAS performance degrades significantly under high contention:

The Contention Storm:

When many threads compete for the same CAS:

1. All threads read the same value
2. All threads compute new values
3. Only one CAS succeeds
4. All others fail and must retry
5. This repeats, wasting CPU cycles

Cache Line Bouncing:

Every CAS requires exclusive ownership of the cache line. Under contention:

• Cache line constantly moves between cores
• Each CAS requires cache coherence traffic
• Memory bus becomes the bottleneck
• Cores spend more time waiting for cache lines than doing useful work

Mitigation Strategies

Several techniques can reduce CAS contention:

1. Exponential Backoff

When CAS fails, wait before retrying. Increase wait time exponentially on repeated failures:

int backoff = 1;
while (!CAS(...)) {
    for (int i = 0; i < backoff; i++) {
        cpu_pause();  // Yield CPU momentarily
    }
    backoff = min(backoff * 2, MAX_BACKOFF);
}

2. Hierarchical Data Structures

Spread contention across multiple CAS targets. Instead of one central counter, use per-thread or per-shard counters:

// Instead of:
atomic<int> global_counter;  // Massive contention

// Use:
atomic<int> counters[NUM_SHARDS];  // Spread load
int total() {
    int sum = 0;
    for (int i = 0; i < NUM_SHARDS; i++) sum += counters[i];
    return sum;
}

3. Elimination

For operations with inverse (e.g., push/pop), pair threads to cancel out:

• Thread A wants to push X
• Thread B wants to pop
• Instead of both fighting over the stack, A gives X directly to B

4. Combining

Aggregate multiple operations:

• Multiple increment requests are combined into one CAS adding the total
• Reduces contention on the central variable