Compare-and-swap

Compare- and- swap ( CAS, English for compare and swap ) instructions are used in computer science to implement locking and synchronization operations. A memory location is compared with a predetermined value, and overwritten according to a new value. At the return value must be read whether the exchange was performed.

The CAS instruction is an atomic operation of the CPU, that is, their sequence can not and must not be interrupted by any other operation. On Intel x86 and Itanium processors, this is the cmpxchg instruction.

Other atomic CPU instructions, which can be used in a similar manner, such as test-and- set, and fetch- and-add. On RISC architectures, this operation is usually as Load-Link/Store-Conditional ( LL / SC) implemented since the RISC philosophy does not allow combined read-modify -write instructions. LL / SC has a somewhat narrower semantics, since it can detect also non- changing accesses to the referenced memory location.

Application

CAS is to implement Lockingobjekten, such as semaphores and mutexes, and use of concurrent data structures objects.

A simple mutex scheme ( mutual exclusion ) can be implemented using a simple memory location that is shared by multiple processes or threads by CAS. Want a thread in a critical section enter, he tries by CAS atomically 0 ( mutex unlocked ) be replaced by a 1. CAS was successful, that is, a 1 could be written to the memory location of the thread has exclusive access to the protected resources. All other CAS operations on the memory location fail, so that the respective active threads are waiting or have to relinquish control to the process management of the operating system. Such a fast mutex scheme in which the involvement of the operating system is reduced to a minimum, for example, as futex (fast userspace mutex ) implemented in the Linux operating system.

Concurrent data structure objects can be implemented, for example, with the Read- Copy- Update scheme. Here, the read access is always allowed; Write accesses are performed first on a partial copy of the data structure, which is then atomically hooked back into the original structure.

In a classic paper, Maurice Herlihy showed in 1991 that CAS instructions belong to a class of synchronization objects, which allows the implementation of wait - free, concurrent data structure objects ( wait- free concurrent data object) for an unlimited number of concurrent processes.

Implementation

Since the uninterrupted flow of operation must be guaranteed, the CAS instruction must be implemented at the hardware level. The following pseudo code is an illustration.

Atomic operation << >> CompareAndSwap function (memory- spot, old, new) {      then if * your agency == old          * your body: = new          return true      else          return false } Because memory is manipulated, a method must be implemented in memory- coupled multiprocessor (SMP) systems, which ensures the consistency of the memory and the CPU caches on each processor boundaries (see cache coherency ).