Compare-and-swap
Encyclopedia : C : CO : COM : Compare-and-swap
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.
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.
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. 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
- [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
From Wikipedia, the Free Encyclopedia. Original article here. Support Wikipedia by contributing or donating.
All text is available under the terms of the GNU Free Documentation License See Wikipedia Copyrights for details.