Compare-and-swap
From Wikipedia, the free encyclopedia
In computer science, the compare-and-swap CPU instruction ("CAS") is a special instruction that atomically compares the contents of a memory location to a given value and, if they are the same, modifies the contents of that memory location to a given new value. The result of the operation must indicate whether it performed the substitution; this can be done either with a simple boolean response, or by returning the value read from the memory location (not the value written to it).
CAS is used to implement semaphores in multiprocessor systems.
It is also used to implement lock-free and wait-free algorithms in multiprocessor systems, something that Maurice Herlihy (1993) proved cannot be done with only read, write, and test-and-set.
Algorithms built around CAS typically read some key memory location and remember the old value. Based on that old value, they compute some new value. Then they try to swap in the new value using CAS, where the comparison checks for the location still being equal to the old value. If CAS indicates that the attempt has failed, it has to be repeated from the beginning: the location is re-read, a new value is computed and the CAS is tried again.
Some of these algorithms are affected by and must handle the problem of a false positive match, or the ABA problem. It's 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.
CAS, and other atomic instructions, are unnecessary in uniprocessor systems, because the atomicity of any sequence of instructions can be achieved by disabling interrupts while executing it.
However, in multiprocessor systems, it is impossible and undesirable to disable interrupts on all processors at the same time. Even with interrupts disabled, two or more processors could be attempting to access the same semaphore's memory at the same time. The compare-and-swap instruction allows any processor to atomically test and modify a memory location, preventing such multiple processor collisions.
[edit] See also
[edit] External links
- Wait-Free Synchronization by Maurice Herlihy (1993)
- compare_and_swap Kernel Service
- "Lock-Free and Practical Deques using Single-Word Compare-And-Swap" by Håkan Sundell, Philippas Tsigas
- "Fast, Reactive and Lock-free: Multi-word Compare-and-swap Algorithms" by Phuong Ha-Hoai, Philippas Tsigas
- "A Practical Multi-Word Compare-And-Swap Operation" by Timothy L. Harris, Keir Fraser, Ian A. Pratt
- "Lock-Free Linked Lists Using Compare-and-Swap" by John D. Valois
- "A Practical Nonblocking Queue Algorithm Using Compare-and-Swap" by Chien-Hua Shann, Ting-Lu Huang, Cheng Chen
- "A Nonblocking Algorithm for Shared Queues Using Compare-and-Swap" by S. Prakash, Yann Hang Lee, T. Johnson
- Discussion "Lock-Free using cmpxchg8b..."
- Description of the CAS2 assembler instruction
- Java method
AtomicReferenceFieldUpdater.compareAndSet(T, V, V)
