Why do real spin loops read the lock word before attempting an atomic write, and why do they add backoff and adaptive spin limits instead of retrying as fast as possible?

## Why the naïve loop is bad The textbook spinlock is: ``` while atomic_test_and_set(lock) == LOCKED: /* retry */ ``` Every iteration executes an atomic read-modify-write. Under a MESI-style coherence protocol, any write-class operation requires the cache line in the **exclusive/modified** state, which means sending an invalidate to every other core holding a copy and waiting for acknowledgement. So each spinner, on each iteration, rips the line away from every other core — including the core running the lock holder, whose release will need that same line. The consequences compound: - Coherence traffic grows with the number of spinners, saturating the interconnect and hurting unrelated work. - The holder is slowed by having its line stolen, so the hold time **H** grows — the very quantity the spin decision assumed was tiny. - Throughput can decrease as you add cores: the classic negative-scalability curve. ## Test-and-test-and-set The standard fix is to separate the cheap check from the expensive attempt: ``` loop: while load(lock) == LOCKED: # plain read: line stays SHARED cpu_pause_hint() if atomic_test_and_set(lock) == FREE: return # got it goto loop # lost the race, back to reading ``` Plain reads can be satisfied from a shared copy in the local cache with no bus traffic at all, so waiters spin in silence while the lock is held. Only when the holder writes FREE — invalidating the shared copies once — do the waiters observe the change and attempt the atomic. This converts continuous traffic into a single burst per release. The remaining burst is the *thundering herd*: k waiters all attempt at once, one wins, k−1 retry. ## Backoff To thin the herd, waiters wait a growing interval between attempts — exponential backoff, capped, with randomisation to break lockstep between waiters that started together. This is the same idea as network collision backoff and for the same reason: uncoordinated retriers converge into synchronised storms unless you inject randomness. Backoff trades latency for traffic. Too aggressive and a waiter is still sleeping when the lock becomes free, adding delay; too timid and the herd persists. It is a heuristic, which is part of why queue locks (below) are attractive: they remove the herd structurally instead of damping it. ## The pause / yield hint Processors expose a hint instruction intended for spin loops. It has two effects worth knowing: - It relieves the pipeline of a burst of speculative loads that will be squashed when the value finally changes, avoiding a memory-order violation penalty on exit from the loop. - On simultaneous-multithreading cores it de-prioritises the spinning thread so its sibling — which may be doing real work, or may even be the lock holder — gets the shared execution units. Without it, a busy spinner can roughly halve its sibling's throughput. It also lowers power draw, which matters for turbo headroom on dense machines. ## Adaptive spinning Adaptive spinning makes the spin budget a function of evidence rather than a constant: - **History-based.** Track how long this particular lock has been held recently; spin proportionally. A lock that has always been released in 80 ns earns a spin; one that historically holds for 20 µs does not. - **Owner-state-based.** If the runtime can see whether the lock's current owner is presently executing on a CPU, spin only while it is. If the owner is descheduled, spinning cannot possibly succeed soon, so park immediately. This is the single most valuable adaptive signal, because it directly tests the precondition that makes spinning sound. - **Success-feedback.** If recent spins on this lock mostly ended in a park, shrink the budget; if they mostly succeeded, grow it. The universal fallback is spin-then-park, which bounds the wasted CPU at roughly the cost of the park it was trying to avoid. ## Queue locks: fixing it structurally MCS and CLH locks eliminate both the ping-pong and the herd. Each waiter enqueues a node it owns and **spins on a flag inside its own node**, hence on its own cache line. The holder, on release, writes to the next waiter's node only. Properties: - One cache-line transfer per hand-off, independent of the number of waiters. - FIFO order, so no starvation and a bounded wait. - Cost: an extra node per waiter and a slightly more expensive uncontended path, plus more complex cancellation. This is why kernel and runtime lock implementations converge on queue-based designs for heavily contended locks while keeping a simple atomic fast path for the uncontended case. ## Putting it together A modern lock's contended path typically reads: try the atomic once; if it fails, test-and-test-and-set with a pause hint for a short adaptive budget informed by owner state; if that fails, enqueue and park. Each stage exists because a specific cost dominates in a specific regime, and being able to name which cost each stage attacks — coherence traffic, herd synchronisation, SMT starvation, wasted CPU on a descheduled owner — is what the question is really testing.