Understanding Compare‑And‑Swap (CAS), Its Mechanisms, and Common Pitfalls

CAS (compare‑and‑swap) is a lock‑free atomic algorithm that maps to the hardware cmpxchg instruction, ensuring that a memory location is updated only when its current value matches an expected value, thus providing atomicity without kernel‑mode transitions.

The operation takes three parameters: V (the current value), E (the expected value), and N (the new value). If V == E , the CPU atomically writes N to the memory location; otherwise, no change occurs.

CPU hardware guarantees atomicity via two mechanisms:

Bus lock : the CPU asserts a LOCK# signal on the system bus, blocking other CPUs from accessing the bus until the operation completes.

Cache lock : the CPU locks the cache line containing the target variable; cache‑coherence protocols detect modifications and invalidate other CPUs' cached copies, preventing simultaneous updates.

Despite its advantages over traditional locks (no blocking, no context switches, no deadlock), CAS has several drawbacks:

It can only guarantee atomicity for a single shared variable.

Spin‑based implementations may waste CPU cycles during long spin periods.

The ABA problem : a value may change from A to B and back to A, making a CAS check falsely succeed.

A typical Java spin‑lock built on CAS uses an AtomicInteger as the lock flag. The code below demonstrates the lock, tryLock, and unlock methods:

public class SpinLock {
    // lockValue default 1 (free)
    private AtomicInteger lockValue = new AtomicInteger(1);

    // spin to acquire lock
    public void lock() {
        while (!tryLock()) {
            // busy‑wait
        }
    }

    // try to acquire lock: expect 1, set to 0
    public boolean tryLock() {
        return lockValue.compareAndSet(1, 0);
    }

    // release lock: expect 0, set to 1
    public void unLock() {
        if (!lockValue.compareAndSet(0, 1)) {
            throw new RuntimeException("Release lock failed");
        }
    }
}

In this implementation, tryLock succeeds only for the thread that sees the expected value, while other threads keep spinning until the lock becomes free.

The ABA issue can be mitigated by attaching a version stamp to the value. Each update increments the version, turning the sequence A→B→A into 1A→2B→3A. Java provides AtomicStampedReference to handle such stamped references.

Understanding CAS, its underlying hardware guarantees, and its limitations is essential for designing high‑performance concurrent algorithms and for answering interview questions on lock‑free programming.