Compare and swap

from Wikipedia, the free encyclopedia

Compare-and-swap ( CAS , English for compare and swap ) instructions are in the computer science used to Locking- and synchronization operations to implement. A memory location is compared with a specified value and, if it matches, is overwritten with a new value. The return value must show whether the exchange has been carried out.

The CAS instruction is an atomic operation of the CPU ; H. its process cannot and must not be interrupted by any other operation. On Intel x86 and Itanium processors, this is the CMPXCHG instruction.

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

application

CAS is used to implement locking objects such as semaphores and mutexes and concurrent data structure objects .

A simple mutex scheme (mutual exclusion) can be implemented via CAS using a simple memory location that is shared by several processes or threads . If a thread wants to enter a critical section , it tries atomically to replace a 0 (mutex unlocked) with a 1 using CAS. If the CAS was successful, i.e. a 1 could be written to the memory location, the thread has exclusive access to the protected resources. All other CAS operations on the storage location fail, so that the respective threads actively wait or hand over control to the process management of the operating system . One such fast mutex scheme, in which the involvement of the operating system is reduced to a minimum, is e.g. B. implemented as Futex (fast userspace mutex) in the Linux operating system.

Concurrent data structure objects can e.g. B. can be implemented with the read-copy-update scheme. Read access is always allowed; Write accesses are initially carried out on a partial copy of the data structure, which is then re-attached atomically to the original structure.

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

implementation

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

<< atomare Operation >>
function CompareAndSwap(speicherstelle, alt, neu) {
    if *speicherstelle == alt then
        *speicherstelle := neu
        return true
    else
        return false
}

Since memory is manipulated, a procedure must be implemented in memory- coupled multiprocessor systems ( SMP ) that guarantees the coherence of the memory and the individual CPU caches across processor boundaries (see cache coherence ).

See also

Individual evidence

  1. ^ Maurice Herlihy: Wait-free synchronization . In: ACM Trans. Program. Long. Syst. . 13, No. 1, January 1991, pp. 124-149. Retrieved May 20, 2007.