Atomic Operations and CAS
An atomic operation completes as a single indivisible step. No other thread can observe it half done. Hardware provides atomic instructions so we can update shared state without a full lock.
The cornerstone is compare and swap, often written CAS. It takes three values: a memory location, an expected old value, and a new value. The processor atomically checks whether the location still holds the expected value, and if so writes the new value, reporting success.
A typical lock free counter loops:
- Read the current value.
- Compute the new value.
- Attempt a CAS from old to new.
- If another thread changed the value, CAS fails, so retry.
This is the basis of lock free and wait free data structures. It avoids blocking, but a subtle hazard is the ABA problem, where a value changes from A to B and back to A, fooling CAS into thinking nothing happened. Version tags or hazard pointers solve it.
Key idea
Compare and swap atomically updates a value only if it is unchanged, enabling lock free algorithms that retry on contention.