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

• Fetch-and-add
• Load-Link/Store-Conditional

External links

• 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 "compareAndSet(T obj, V expect, V update)"