the CAS retry loop
A single CAS is too small to do anything interesting on its own — it either installs your update or refuses it. The CAS retry loop is the standard pattern that turns that one-shot primitive into a complete atomic operation. It is the heartbeat of almost every lock-free algorithm, and once you recognise its shape you will see it everywhere.
The shape is always the same three steps, repeated until success. One: read a snapshot of the current shared value (call it old). Two: compute, in your own private registers, the new value you want based on old. Three: CAS the location from old to new. If the CAS succeeds, nothing changed underneath you while you were computing, so your update was valid and you are done. If it fails, some other thread changed the value in the meantime, so your snapshot is stale and your computed new value is built on a false premise — you simply re-read the fresh value and try the whole thing again. This is optimistic concurrency: you assume no conflict, do the work, and only pay a retry when an actual conflict occurred.
Two things to understand honestly. First, this loop is lock-free but not wait-free: a thread can lose the race over and over while others keep winning, so there is no bound on its retries — that is the line between the two progress classes. Second, step two must be a pure, side-effect-free computation, because it may run many times before one attempt sticks; you must not perform any visible action (printing, freeing memory, sending a message) inside the loop body, only inside the successful branch after the CAS wins.
/* Atomically apply f() to a shared value, lock-free. */ int old, neu; do { old = atomic_load(&shared); /* 1: snapshot */ neu = f(old); /* 2: pure compute, may run many times */ } while (!CAS(&shared, old, neu));/* 3: install only if unchanged, else retry */
Read, compute, CAS, retry-on-failure: the universal skeleton of an optimistic lock-free update.
The loop body must be pure and re-runnable, because it can execute many times before one CAS wins. Doing irreversible work (freeing, I/O) inside the loop instead of after the winning CAS is a classic bug.