Compare-and-swap

As an example use case of compare-and-swap, here is an algorithm for atomically incrementing or decrementing an integer. This is useful in a variety of applications that use counters. The function add performs the action *p ← *p + a, atomically (again denoting pointer indirection by *, as in C) and returns the final value stored in the counter. Unlike in the cas pseudocode above, there is no requirement that any sequence of operations is atomic except for cas.

function add(p: pointer to int, a: int) returns int
    done ← false
    while not done
        value ← *p  // Even this operation doesn't need to be atomic.
        done ← cas(p, value, value + a)

    return value + a

In this algorithm, if the value of *p changes after (or while!) it is fetched and before the CAS does the store, CAS will notice and report this fact, causing the algorithm to retry.[5]

Some CAS-based algorithms are affected by and must handle the problem of a false positive match, or the ABA problem. It is possible that between the time the old value is read and the time CAS is attempted, some other processors or threads change the memory location two or more times such that it acquires a bit pattern which matches the old value. The problem arises if this new bit pattern, which looks exactly like the old value, has a different meaning: for instance, it could be a recycled address, or a wrapped version counter.

A general solution to this is to use a double-length CAS (DCAS). E.g., on a 32-bit system, a 64-bit CAS can be used. The second half is used to hold a counter. The compare part of the operation compares the previously read value of the pointer and the counter, with the current pointer and counter. If they match, the swap occurs - the new value is written - but the new value has an incremented counter. This means that if ABA has occurred, although the pointer value will be the same, the counter is exceedingly unlikely to be the same (for a 32-bit value, a multiple of 2³² operations would have to have occurred, causing the counter to wrap and at that moment, the pointer value would have to also by chance be the same).

An alternative form of this (useful on CPUs which lack DCAS) is to use an index into a freelist, rather than a full pointer, e.g. with a 32-bit CAS, use a 16-bit index and a 16-bit counter. However, the reduced counter lengths begin to make ABA possible at modern CPU speeds.

One simple technique which helps alleviate this problem is to store an ABA counter in each data structure element, rather than using a single ABA counter for the whole data structure.

A more complicated but more effective solution is to implement safe memory reclamation (SMR). This is in effect lock-free garbage collection. The advantage of using SMR is the assurance a given pointer will exist only once at any one time in the data structure, thus the ABA problem is completely solved. (Without SMR, something like a freelist will be in use, to ensure that all data elements can be accessed safely (no memory access violations) even when they are no longer present in the data structure. With SMR, only elements actually currently in the data structure will be accessed).

CAS, and other atomic instructions, are sometimes thought to be unnecessary in uniprocessor systems, because the atomicity of any sequence of instructions can be achieved by disabling interrupts while executing it. However, disabling interrupts has numerous downsides. For example, code that is allowed to do so must be trusted not to be malicious and monopolize the CPU, as well as to be correct and not accidentally hang the machine in an infinite loop or page fault. Further, disabling interrupts is often deemed too expensive to be practical. Thus, even programs only intended to run on uniprocessor machines will benefit from atomic instructions, as in the case of Linux's futexes.

In multiprocessor systems, it is usually impossible to disable interrupts on all processors at the same time. Even if it were possible, two or more processors could be attempting to access the same semaphore's memory at the same time, and thus atomicity would not be achieved. The compare-and-swap instruction allows any processor to atomically test and modify a memory location, preventing such multiple-processor collisions.

On server-grade multi-processor architectures of the 2010s, compare-and-swap is cheap relative to a simple load that is not served from cache. A 2013 paper points out that a CAS is only 1.15 times more expensive than a non-cached load on Intel Xeon (Westmere-EX) and 1.35 times on AMD Opteron (Magny-Cours).[6]

Many C compilers support using compare-and-swap either with the C11 <stdatomic.h> functions,[8] or some non-standard C extension of that particular C compiler,[9] or by calling a function written directly in assembly language using the compare-and-swap instruction.

The following C function shows the basic behavior of a compare-and-swap variant that returns the old value of the specified memory location; however, this version does not provide the crucial guarantees of atomicity that a real compare-and-swap operation would:

int compare_and_swap(int* reg, int oldval, int newval)
{
    ATOMIC();
    int old_reg_val = *reg;
    if (old_reg_val == oldval)
        *reg = newval;
    END_ATOMIC();
    return old_reg_val;
}

old_reg_val is always returned, but it can be tested following the compare_and_swap operation to see if it matches oldval, as it may be different, meaning that another process has managed to succeed in a competing compare_and_swap to change the reg value from oldval.

For example, an election protocol can be implemented such that every process checks the result of compare_and_swap against its own PID (= newval). The winning process finds the compare_and_swap returning the initial non-PID value (e.g., zero). For the losers it will return the winning PID.

This is the logic in the Intel Software Manual Vol 2A:

bool compare_and_swap(int *accum, int *dest, int newval)
{
    if (*accum == *dest) {
        *dest = newval;
        return true;
    } else {
        *accum = *dest;
        return false;
    }
}

• Sundell, Håkan; Tsigas, Philippas. "Lock-Free and Practical Deques using Single-Word Compare-And-Swap" (PDF).
• Valois, John D. Lock-Free Linked Lists Using Compare-and-Swap. Proceedings of the Fourteenth Annual ACM Symposium on Principles of Distributed Computing. CiteSeerX 10.1.1.41.9506.
• Prakash, S.; Lee, Yann Hang; Johnson, T. "A Nonblocking Algorithm for Shared Queues Using Compare-and-Swap". IEEE Transactions on Computers.
• 2003 discussion "Lock-Free using cmpxchg8b..." on Intel x86, with pointers to various papers and source code

• AIX compare_and_swap Kernel Service
• Java package java.util.concurrent.atomic implements 'compareAndSet' in various classes
• .NET Class methods Interlocked::CompareExchange
• Windows API InterlockedCompareExchange