CAS Retry Loops

A CAS retry loop repeatedly computes a desired value and attempts a compare-and-set operation until it succeeds or a stopping condition is reached. It provides a lock-free way to update shared atomic state when concurrent modifications are possible.

Compare-and-set (CAS) atomically checks whether a variable still contains an expected value and, if so, replaces it with a new value. The operation fails when another thread has changed the variable since the expected value was observed.

A retry loop handles that failure by rereading the current value, recomputing the desired result, and attempting CAS again. The crucial point is that the computation must be based on the value most recently observed; reusing a stale desired value can produce incorrect updates.

In Java, classes such as `AtomicInteger` provide `compareAndSet`. A typical loop reads the current value, calculates `next`, and invokes `compareAndSet(current, next)`. If it returns `false`, another thread won the race, so the loop repeats with a fresh value.

CAS loops are useful for counters, state transitions, and other small atomic updates. They avoid blocking locks, but repeated contention can cause many failed attempts, so they are not automatically faster than locking in every workload.

A CAS loop should also consider termination and contention. If progress is not guaranteed, an implementation may need bounded retries, backoff, or another synchronization strategy depending on the workload.

Key points

• CAS succeeds only when the observed value still equals the expected value.
• A failed CAS means another thread changed the state first; reread before retrying.
• Recompute the desired value from the newly observed state on every retry.
• CAS loops can provide lock-free progress for suitable atomic operations.
• Heavy contention can cause repeated failures and wasted CPU.

Interview questions

What problems can heavy contention cause in a CAS retry loop?

Heavy contention can make many CAS attempts fail because multiple threads repeatedly compete for the same variable. Those failures consume CPU and can reduce throughput even though no thread is blocked on a traditional lock. Backoff, reducing contention, sharding state, or selecting another synchronization strategy can help. The appropriate choice depends on the workload and the required consistency and progress guarantees.

When would you prefer an atomic operation such as `getAndIncrement()` over writing a CAS loop?

I would use the higher-level atomic operation when it directly expresses the required state transition. It is simpler, easier to review, and less likely to contain retry-loop mistakes. A custom CAS loop is appropriate when the update requires application-specific logic that the atomic class does not expose directly. For example, conditional state transitions often require reading, calculating, and validating a custom next state.

What is a CAS retry loop, and why is the retry necessary?

A CAS retry loop reads an atomic value, calculates a new value, and tries to replace the old value with CAS. CAS succeeds only if the value is unchanged since the read. If another thread modified it first, CAS fails, so the thread reads the new value and recalculates its update. The retry is necessary because the original calculation may now be based on stale state.

Why must the desired value be recomputed after a CAS failure?

The desired value usually depends on the value that was read before the CAS attempt. If another thread changes that value, the old desired value may no longer represent the correct next state. Recomputing from the newly observed value preserves the intended state transition. This is what allows multiple successful updates to compose correctly under contention.

Is a CAS loop always lock-free?

A correctly designed CAS loop around an atomic variable can provide lock-free progress: a failed CAS implies that some competing operation changed the shared state, so system-wide progress is occurring. However, that does not mean every individual thread is guaranteed to complete promptly. Under contention, one thread can repeatedly lose the CAS race and consume CPU. The exact progress guarantee depends on the algorithm and the atomic primitive being used.