compare-and-swap

Test-and-set is powerful but blunt: it always overwrites. Compare-and-swap (CAS) is the more refined atomic instruction, and it is the workhorse behind most modern lock-free programming. The idea, done as one indivisible step, is: 'look at this memory location; only if it still holds the value I expected, replace it with this new value, and tell me whether you did.' It is like updating a shared whiteboard only if no one has changed it since you last looked — and finding out, atomically, whether your update stuck.

Concretely, CAS(address, expected, new) atomically does this: read the current value at address; if it equals expected, store new and report success; otherwise leave it unchanged and report failure (often by returning the value it actually found). The classic usage is a retry loop. To atomically increment a counter without a lock: read the current value into old; compute new = old + 1; then CAS(counter, old, new). If it succeeds, you are done. If it fails, some other thread changed the counter in the meantime, so you re-read and try again. The loop keeps spinning until one attempt lands on an unchanged value — and crucially, every failure means someone else made progress, so the system as a whole always advances.

CAS is more expressive than test-and-set because it can conditionally update based on the current value, which is what lets you build not just locks but lock-free stacks, queues, and counters that never block. Two honest caveats. First, CAS can fail spuriously under heavy contention and waste work retrying, so it is not automatically faster than a lock. Second, it has a famous trap: the ABA problem. CAS only checks that the value equals expected, not that it never changed in between; if it went from A to B and back to A, CAS happily succeeds even though the world shifted underneath it. Solving ABA needs extra machinery like version tags. Still, CAS is the single most important atomic primitive in concurrent programming.