Describe how a compare-and-swap instruction works and how you build an arbitrary atomic update on top of it with a retry loop. Why can the loop iterate more than once, and what happens to a thread that keeps losing?

## The primitive Compare-and-swap is a single atomic instruction with the semantics: ``` CAS(location, expected, new) -> bool: atomically: if *location == expected: *location = new return true else: return false ``` Many interfaces return the value actually found instead of a boolean, which saves a re-read on failure. The key property is that the comparison and the conditional store are one indivisible step: nothing can slip between them. CAS is theoretically special — it is a *universal* primitive, meaning any concurrent object can in principle be implemented for any number of threads using it, which simple atomic reads and writes cannot achieve. Practically, it is the escape hatch for updates the hardware does not implement directly. Fetch-and-add covers addition; CAS covers everything else: maximum, saturating decrement, conditional state transitions, pushing onto a list, updating a packed struct. ## The retry loop The optimistic pattern is always the same three beats: **read, compute, install-or-retry**. ``` atomicUpdate(location, f): loop: old = location.load() new = f(old) if CAS(location, old, new): return old # else: someone else won; discard `new` and start over ``` The reason to loop rather than adjust is that `new` is only meaningful relative to `old`. If `old` is no longer current, `new` encodes a decision made about a world that no longer exists, and installing it would silently discard the other thread's update — the same lost update you were trying to prevent. This imposes discipline on `f`: - **It must be pure.** No I/O, no logging, no mutation of other shared state, no allocation you cannot afford repeatedly. Whatever it does happens once per attempt, and attempts are discarded. - **It must be cheap.** A long computation widens the window in which someone else can win, which raises the failure rate, which lengthens the loop — a self-reinforcing effect under contention. - **It must be idempotent in effect.** Only the final successful attempt counts; every earlier one must leave no trace. ## Why failures happen, and what they mean A CAS fails for exactly one reason in the abstract model: the value changed. (Some hardware, notably load-linked/store-conditional implementations, can also fail *spuriously* — the store-conditional aborts because the cache line was touched at all, including by an unrelated variable sharing the line, or because of a context switch. Code written as a retry loop absorbs this transparently, which is one reason the loop is the canonical shape rather than a single attempt.) Every real failure implies some other thread succeeded. That is the source of the progress guarantee for the structure as a whole: the system cannot deadlock on CAS, because nobody holds anything, and no thread's stall can block others — unlike a lock, where a thread preempted inside the critical section stops everyone. What is *not* guaranteed is per-thread progress: an unlucky thread can lose every race indefinitely and starve. That distinction — system-wide progress versus per-thread progress — is the point of the formal progress hierarchy. ## Cost and contention A CAS is not cheap. The executing core must take the cache line into an exclusive state, so every attempt — successful or not — pulls the line away from other cores. Under contention, N threads hammering one location produce a storm of cache-line transfers; failed attempts consume bandwidth while accomplishing nothing, and throughput can go *down* as you add cores. Mitigations: exponential backoff between retries, reading the value cheaply and skipping the CAS if the update would be a no-op, or restructuring so the hot location is not shared — per-thread or striped state combined only when read. ## Where the pattern silently breaks Two traps worth naming: **Multi-location invariants.** CAS is single-location. Keeping two variables consistent needs both packed into one atomic word, a lock, or a more elaborate protocol; two CASes in sequence give you an inconsistent window in between. **Value recurrence.** A successful CAS proves the value matches now, not that nothing happened. If the location can return to a previous value — recycled nodes, reused indices — a stale attempt can succeed on a world that has moved, which is the ABA problem and needs a version stamp or another mechanism.