Editing Compare-and-swap (section)

==Implementations==
Compare-and-swap (and compare-and-swap-double) has been an integral part of the [[System/370|IBM 370]] (and all successor) architectures since 1970. The operating systems that run on these architectures make extensive use of this instruction to facilitate process (i.e., system and user tasks) and processor (i.e., central processors) [[parallel computing|parallelism]] while eliminating, to the greatest degree possible, the "disabled [[spinlock]]s" which had been employed in earlier IBM operating systems. Similarly, the use of [[test-and-set]] was also eliminated. In these operating systems, new units of work may be instantiated "globally", into the global service priority list, or "locally", into the local service priority list, by the execution of a single compare-and-swap instruction. This substantially improved the responsiveness of these operating systems.

In the [[x86]] (since [[80486]]) and [[Itanium]] architectures this is implemented as the '''compare and exchange''' ('''CMPXCHG''') instruction (on a multiprocessor the {{mono|LOCK}} prefix must be used).

As of 2013, most [[multiprocessor]] architectures support CAS in hardware, and the compare-and-swap operation is the most popular [[synchronization primitive]] for implementing both lock-based and non-blocking [[concurrent data structure]]s.<ref name="dice" />

The atomic counter and atomic bitmask operations in the Linux kernel typically use a compare-and-swap instruction in their implementation.
The [[SPARC|SPARC-V8]] and [[PA-RISC]] architectures are two of the very few recent architectures that do not support CAS in hardware; the Linux port to these architectures uses a [[spinlock]].<ref>David S. Miller.
[https://www.kernel.org/doc/Documentation/atomic_ops.txt "Semantics and Behavior of Atomic and Bitmask Operations, for Linux port maintainers"] {{Webarchive|url=https://web.archive.org/web/20120320111533/http://www.kernel.org/doc/Documentation/atomic_ops.txt |date=2012-03-20}}.</ref>

===Implementation in C===
Many C compilers support using compare-and-swap either with the [[C11 (C standard revision)|C11]] <code><stdatomic.h></code> functions,<ref>{{Cite web |title=atomic_compare_exchange_weak, atomic_compare_exchange_strong, atomic_compare_exchange_weak_explicit, atomic_compare_exchange_strong_explicit |url=https://en.cppreference.com/w/c/atomic/atomic_compare_exchange |access-date= |website=en.cppreference.com}}</ref> or some non-standard C extension of that particular C compiler,<ref>[https://gcc.gnu.org/onlinedocs/gcc-4.3.5/gcc/Atomic-Builtins.html "GNU C Extensions to the C Language Family: Built-in functions for atomic memory access"]</ref> 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:

<syntaxhighlight lang="cpp">
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;
}
</syntaxhighlight>

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

For example, an election protocol can be implemented such that every process checks the result of <code>compare_and_swap</code> against its own PID (= newval). The winning process finds the <code>compare_and_swap</code> 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:

<syntaxhighlight lang="cpp">
bool compare_and_swap(int *accum, int *dest, int newval)
{
    if (*accum == *dest) {
        *dest = newval;
        return true;
    } else {
        *accum = *dest;
        return false;
    }
}
</syntaxhighlight>