compare-and-swap
/ C-A-S /
Suppose two people both want to claim the last seat at a table, and the rule is: only take it if it is still empty. The danger is that both check 'empty?', both see yes, and both sit — a collision. What you want is a single indivisible action: 'if this seat is still empty, sit; otherwise tell me it was taken.' No one can sneak in between the check and the sit. Compare-and-swap is exactly that indivisible action for a memory location: in one atomic step it checks whether a location still holds an expected value and, only if so, writes a new value.
Its signature reads CAS(address, expected, new). Atomically — with no other core able to interleave — it does: read the value at address; if it equals expected, store new there and report success; otherwise change nothing and report failure (usually returning the value it actually found). The hardware guarantees the whole read-compare-write happens as one uninterruptible unit. This is the workhorse atomic read-modify-write primitive, and it is how you safely update shared data without a lock: read the current value, compute the new one, then CAS it in — if CAS fails because another core changed the value first, loop and retry with the fresh value.
Compare-and-swap is the foundation of lock-free programming: counters, stacks, queues, and reference counters that many threads update concurrently are built on CAS retry loops. It is powerful but not a free lunch. Under heavy contention many threads keep failing and retrying, wasting work, and CAS is vulnerable to the subtle ABA problem — a value changes from A to B and back to A, so CAS sees the expected A and succeeds even though the world moved underneath it. The fix (version counters, or the load-linked/store-conditional alternative) is part of why lock-free code is famously hard to get right.
Lock-free increment of a shared counter: loop { old = counter; new = old + 1; } until CAS(&counter, old, new) succeeds. If another thread bumps the counter between the read and the CAS, the expected 'old' no longer matches, CAS fails, and we retry with the new current value — so the increment is never lost, with no lock.
CAS turns read-modify-write into one atomic step, so a failed swap simply retries — the core trick of lock-free counters and stacks.
CAS can silently succeed across an ABA change (value goes A to B back to A and looks unchanged). Lock-free code must guard against this, e.g. with version tags or load-linked/store-conditional, which detects any intervening write.