Progress without locks
A lock free retry loop updates shared state using an atomic compare and swap, or CAS, instead of a mutex. The pattern is: read the current value, compute a new value, and CAS it in only if the value is unchanged. If another thread won, the CAS fails and you loop again.
Why it is lock free
At least one thread always makes progress, because a failed CAS means someone else succeeded. There is no lock to hold, so a descheduled thread cannot block others, which avoids convoys and most deadlocks.
The hazards
- Contention livelock like waste — under heavy contention many threads spin and retry; throughput can degrade, so back off may be needed.
- The ABA problem — a value changes from A to B and back to A. A plain CAS sees A and succeeds, missing that the underlying state moved. Fix it with a version counter or tagged pointer so A with a new tag differs from the old A.
A safe shape
- Read value and any version.
- Compute the new value from that snapshot.
- CAS the value and version together; on failure, re read and retry.
Key idea
A lock free retry loop uses CAS with retry so some thread always progresses. Guard against the ABA problem with a version tag and add back off under heavy contention.