The Compare and Swap Loop
Compare and swap, or CAS, is an atomic instruction with three inputs: a memory location, an expected old value, and a new value. It atomically checks whether the location still holds the expected value and, if so, writes the new value. It reports whether it succeeded.
CAS by itself only does one attempt, so it is wrapped in a retry loop. The pattern is:
- Read the current value into a local copy.
- Compute the desired new value from that copy.
- CAS to swap the new value in, expecting the value you read.
- Retry the whole sequence if CAS fails because another thread changed the value first.
This loop turns any read modify write into an atomic operation without a lock. An atomic increment, for example, reads the counter, adds one, and CASes the result, looping until it wins.
The strengths are that there is no lock to deadlock on and a thread that is paused never blocks others. The weakness is contention. Under heavy write traffic many threads collide, fail their CAS, and burn cycles retrying, which can degrade to livelock.
CAS also underpins lock free structures and is the building block for atomic counters, flags, and pointers.
Key idea
A CAS loop reads a value, computes an update, and atomically swaps it in only if unchanged, retrying on conflict to update shared state without a lock.