ThinkerQAQ

NOTE

6.4 Compare-and-Set (CAS)

Atomic compare-and-set as a read-modify-write primitive, retry loops, contention, ABA, and when lock-free does not mean contention-free.

JavaCreated Updated 1 min readhistorical

This is a historical learning note and may contain outdated or incomplete understanding.

1. CAS

Compare-and-set atomically performs the conceptual operation:

if current == expected:
    current = update
    success
else:
    fail

The compare and update form one atomic read-modify-write operation.

2. Retry Loop

CAS is often used in a loop:

for (;;) {
    int old = value.get();
    int next = old + 1;
    if (value.compareAndSet(old, next)) break;
}

Under contention, failed threads retry instead of blocking on a mutex.

3. Lock-Free Is Not Free

CAS avoids lock ownership/blocking in many algorithms, but heavy contention can cause repeated failed retries and cache-line bouncing.

A lock can outperform CAS under some workloads.

4. ABA

If a value changes A → B → A, a CAS that only compares the final value cannot tell that an intervening change occurred.

Solutions include version/stamp fields (AtomicStampedReference), immutable nodes, or algorithm-specific reclamation/versioning.

5. Java APIs

Modern Java exposes atomics through java.util.concurrent.atomic and lower-level VarHandle APIs. The JVM maps operations to target-specific atomic instructions and memory-ordering semantics.

  1. Concurrency Programming (6): Atomic Implementation — From Runtime to CPU

    Follows Java AtomicInteger, Go sync/atomic, and CPython's internal atomic operations to see how Atomic RMW reaches the compiler, runtime, and CPU.

  2. Concurrency Programming (5): Atomics — Atomicity, Visibility, and Ordering at the Language Level

    Continues with counter and ready to explain the atomicity, visibility, and ordering guarantees of atomic operations, then compares the public semantics in Java, Go, and CPython.

  3. Concurrency Programming (4): Mutex Implementation — From Runtime to CPU

    Follows the real implementation paths of Java synchronized, Go sync.Mutex, and CPython threading.Lock to see how mutexes use atomic operations, memory ordering, waiting, and wakeup.