4.1 Compare-and-Swap (CAS)

1. What CAS Is

CAS (Compare-and-Swap) is an atomic operation: compare the current value in memory with an expected value, and replace it with a new value only when they match.

The original note used the following code to describe CAS semantics:

int cas(long *addr, long old, long new)
{
    /* Executes atomically. */
    if(*addr != old)
        return 0;
    *addr = new;
    return 1;
}

This is semantic pseudocode. The “compare + write” in ordinary C code does not automatically become atomic; real CAS must be guaranteed by CPU atomic instructions and atomic APIs provided by the language/runtime.

It can be understood as: check whether the current value at addr is old; if they are equal, atomically try to change it to new and return success, otherwise return failure.

2. Why CAS Is Needed

It is used in multithreaded programming to implement atomic compare-and-swap without exposing an intermediate state to other threads, and is commonly used to implement atomic variables and lock-free algorithms.

Whether to retry after CAS fails is determined by the specific algorithm; CAS itself is not a complete lock-free algorithm.

3. CAS Problems

3.1. ABA

If a value goes through A → B → A, CAS that only compares the final value may still think it “has not changed.” This is the ABA problem.

A common approach is to add a version number to the state, or to combine pointer-based lock-free structures with safe memory reclamation.

4. CAS Implementation

CAS is usually based on atomic read-modify-write instructions provided by the CPU and wrapped by language atomic APIs.

Different languages may also require callers to choose a corresponding memory order; this is additional semantics of the atomic API and does not change the core CAS concept originally recorded here.

5. References

• Compare-and-swap - Wikipedia