One indivisible step
Compare and swap, often called CAS, is a hardware read modify write. It atomically reads a location, checks it against an expected value, and writes a new value only if they match. The whole sequence is indivisible, so no other core can interleave between the read and the write.
How it is used
Code reads the current value, computes a new one, then attempts a CAS. If the location still holds the expected value the swap succeeds. If another thread changed it the CAS fails and the code retries with the fresh value. This loop is the heart of lock free stacks queues and counters.
Strengths and pitfalls
- It needs no lock, so a stalled thread cannot block others from progressing.
- It can fail under contention and spin, wasting work when many threads compete.
- It is vulnerable to the ABA problem, where a value changes from A to B and back to A, fooling the comparison. Version tags or hazard pointers guard against this.
Key idea
Compare and swap atomically updates a location only if it still holds an expected value, giving a lock free retry loop that powers concurrent data structures but must guard against the ABA problem.