CAS and Atomic Classes: The Bedrock of Non-Blocking Concurrency

CAS (Compare And Swap) is the fundamental primitive of Java concurrency. Whether it's the lock-inflation in synchronized, state management in AQS, or lock-free updates in atomic classes, everything depends on CAS. Understanding CAS is understanding the core of non-blocking concurrency.

1. What is CAS?

At its heart, CAS is a CPU atomic instruction (e.g., CMPXCHG on x86). Its logic is executed as a single, uninterruptible hardware operation:

CAS(Address, ExpectedValue, NewValue)

if (CurrentValueAtAddress == ExpectedValue) {
    UpdateValueAtAddress = NewValue;
    return true; // Success
} else {
    return false; // Failure (another thread intervened)
}

1.1 The Spin Pattern

When a CAS operation fails, the thread typically spins and retries: it re-reads the value, re-calculates the result, and attempts the CAS again.

1.2 CAS (Optimistic) vs. Locks (Pessimistic)

2. The Atomic Family (java.util.concurrent.atomic)

Java provides specialized classes that wrap CAS operations for safe, lock-free updates.

• Primitives: AtomicInteger, AtomicLong. (e.g., incrementAndGet()).
• References: AtomicReference. Atomically updates object pointers.
• Field Updaters: AtomicIntegerFieldUpdater. Uses reflection and CAS to update a volatile field of an existing class without extra memory overhead.

3. The ABA Problem

CAS only checks if the value is the same. It cannot detect if a value was changed from A to B, then back to A.

Why is this a problem? In simple counters, it doesn't matter. But in data structures like Linked Stacks, if a node is popped and pushed back, the reference is the same, but the internal "next" pointers of the structure might have been corrupted.

The Solution: Versioning

AtomicStampedReference adds a Version Stamp. It only updates if both the value AND the version match.

// Logic: If value is "A" AND version is 10, update to "B" and set version to 11
stampedRef.compareAndSet("A", "B", 10, 11);

4. LongAdder: Scaling Under Contention

In high-concurrency scenarios, AtomicLong becomes a bottleneck as hundreds of threads compete (spin) for the same memory address.

LongAdder (introduced in JDK 8) uses Contention Stripping:

1. Low Competition: Updates a base variable directly.
2. High Competition: Threads are hashed to an array of Cells. Each thread updates its own cell.
3. Result Retrieval: The final value is calculated by summing base + all Cells.

Comparison: LongAdder is far faster than AtomicLong for high-throughput counting, but sum() is only "weakly consistent" (giving an approximate snapshot).

Summary of CAS Limitations

1. ABA Problem: Solved via AtomicStampedReference.
2. CPU Spinning: If contention is extremely high, spinning wastes CPU cycles. Switching to a lock might be more efficient.
3. Single Variable Constraint: One CAS can only update one memory location. To update multiple fields atomically, encapsulate them into a single object and use AtomicReference.