Compare-and-swap
|
|
In computer science, the compare-and-swap CPU instruction 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. It is used to implement semaphores in multiprocessor systems.
It is also used to implement lock-free (non-blocking) algorithms in multiprocessor systems, something that Maurice Herlihy proved cannot be done with only read, write, and test-and-set.
In uniprocessor systems, it is sufficient to disable interrupts before accessing a semaphore.
However, in multiprocessor systems, it is impossible and undesirable to disable interrupts on all processors at the same time; and 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.
See also
External links
- compare_and_swap Kernel Service (http://publib16.boulder.ibm.com/pseries/en_US/libs/ktechrf1/compare_and_swap.htm)
- "Lock-Free and Practical Deques using Single-Word Compare-And-Swap (http://citeseer.ist.psu.edu/694700.html)" by Håkan Sundell, Philippas Tsigas
- "Fast, Reactive and Lock-free: Multi-word Compare-and-swap Algorithms (http://citeseer.ist.psu.edu/705549.html)" by Phuong Ha-Hoai, Philippas Tsigas
- "A Practical Multi-Word Compare-And-Swap Operation (http://citeseer.ist.psu.edu/harris02practical.html)" by Timothy L. Harris, Keir Fraser, Ian A. Pratt
- "Lock-Free Linked Lists Using Compare-and-Swap (http://citeseer.ist.psu.edu/valois95lockfree.html)" by John D. Valois
- "A Practical Nonblocking Queue Algorithm Using Compare-and-Swap (http://csdl.computer.org/comp/proceedings/icpads/2000/0568/00/05680470abs.htm)" by Chien-Hua Shann, Ting-Lu Huang, Cheng Chen
- "A Nonblocking Algorithm for Shared Queues Using Compare-and-Swap (http://csdl.computer.org/comp/trans/tc/1994/05/t0548abs.htm)" by S. Prakash, Yann Hang Lee, T. Johnson
- Discussion "Lock-Free using cmpxchg8b... (http://softwareforums.intel.com/ids/board/message?board.id=42&message.id=67)"
- Description of the CAS2 assembler instruction (http://68k.hax.com/CAS2)
- Java method "compareAndSet(T obj, V expect, V update) (http://java.sun.com/j2se/1.5.0/docs/api/java/util/concurrent/atomic/AtomicReferenceFieldUpdater.html#compareAndSet(T,+V,+V))"