The workhorse primitive
Compare and swap, often written CAS, takes a memory location, an expected value, and a new value. Atomically it checks whether the location still holds the expected value, and only if so writes the new value. It reports whether the swap happened.
Why expected matters
CAS lets a thread say update this only if nobody changed it since I last looked. The expected value is the snapshot the thread read earlier. If another thread slipped in and modified the location, the expected value no longer matches, the CAS fails, and the thread knows it must retry.
The retry loop
The standard pattern reads the current value, computes a new value, then CAS. On failure it loops: re read, recompute, retry. Under low contention almost every CAS succeeds first try. Under high contention many threads retry, but the system as a whole always makes progress because some CAS always succeeds.
What it enables
- Lock free stacks, queues, and counters
- Optimistic updates with no mutex at all
- The building block beneath atomic add and reference counting
Key idea
Compare and swap writes only when the location still matches an expected snapshot, enabling optimistic retry loops without locks.