The idea: change it only if nobody else did
counter++ looks like one operation, but the CPU does three: load counter into a register, add 1, store the register back. If another thread stores to counter between the load and the store, that store is overwritten: a lost update.
Compare-and-swap (CAS) is a CPU instruction that makes the store conditional. CAS(&counter, old, new) stores new only if counter still equals old, the value you read, and tells you whether it did. Comparing and storing are one indivisible step. A failed CAS means "someone changed it since you looked": read again and retry.
bool CAS(int *p, int old, int new) { // done by the hardware, atomically
if (*p != old) return false;
*p = new;
return true;
}
do {
old = counter;
new = old + 1;
} while (!CAS(&counter, old, new));
How to use the animation
Every thread runs on its own CPU and executes the listing in a loop, adding 1 to counter each time round. A coloured marker shows the line each thread runs next, and each thread's registers old and new are shown under it. Every step runs one line, and between any two steps any thread may run. Choose a thread and press Step Thread, or let the round-robin or random scheduler choose. Loads and stores fly between the thread and memory; a CAS flies down as a request, the memory compares, and true or false flies back. Under the separator the page checks that no update was lost and names the threads whose old is already stale.
counter++ is three steps
Open the Bug: plain write tab and run Demo: lost update. T1 and T2 both read 0 and both compute 1. T2 stores 1, then T1 stores 1 over it. Two increments, counter = 1. Nothing went wrong in any single line: the bug is the gap between T1's read and its write, during which its value became stale.
The CAS retry loop
The CAS retry loop tab's Demo: same schedule runs the same order of threads. T2's CAS(0 → 1) succeeds. T1's CAS(0 → 1) finds 1 instead of 0, stores nothing and returns false. T1 goes back, reads 1, computes 2, and its CAS(1 → 2) succeeds. Both increments count, and no thread ever held a lock.
The pattern works for any update you can compute from the old value: a maximum, a bit set, a new head pointer for a stack. It is also exactly optimistic locking in a database: UPDATE … SET v = v + 1, version = 8 WHERE id = 1 AND version = 7 is a CAS on the version column (see Optimistic vs pessimistic locking).
Lock-free, not wait-free
With a lock, a thread that is preempted while holding it stops everybody else. With CAS no thread ever waits for another, and a CAS fails only because another thread's CAS succeeded, so in every round some thread makes progress. That property is called lock-free. It does not promise that every thread makes progress: Demo: three threads lets T3 lose twice in a row, and under heavy contention a thread can keep losing. A wait-free algorithm bounds every thread's steps; x86's LOCK XADD (fetch-and-add) is wait-free for a counter, which is why AtomicInteger.incrementAndGet uses it on x86 instead of a CAS loop.
Failed CASes are wasted work, and every CAS, failed or not, needs the cache line in exclusive state, so many threads hammering one word scale badly. Java's LongAdder spreads the counter over several cells for that reason.
The ABA problem
CAS compares values, not history. If a word goes from A to B and back to A between your read and your CAS, the CAS succeeds as if nothing happened. For a counter that is harmless, but not for pointers. In a lock-free stack, T1 reads top = A and A.next = B, then is preempted. T2 pops A, pops B (freeing it) and pushes A again. T1's CAS(&top, A, B) succeeds and makes the freed B the top of the stack. Fixes: pair the pointer with a version counter that changes on every update (a double-width CAS such as CMPXCHG16B, or Java's AtomicStampedReference), or make sure memory is not reused while a thread may still hold a pointer to it (garbage collection, hazard pointers, epoch-based reclamation).
CAS in hardware and languages
| Where | Compare-and-swap |
|---|---|
| x86 | LOCK CMPXCHG [mem], reg (expected value in EAX); CMPXCHG16B for two words |
| ARM | LDXR / STXR loop (load-linked / store-conditional), or CAS (ARMv8.1) |
| RISC-V, POWER, MIPS | LR/SC, lwarx/stwcx., LL/SC |
| C++ | std::atomic<T>::compare_exchange_strong / _weak |
| Java | AtomicInteger.compareAndSet, VarHandle.compareAndSet |
| Go | atomic.CompareAndSwapInt64 |
Load-linked / store-conditional is the RISC alternative: LL reads a word and starts watching it; SC stores only if nobody wrote the word since. It fails on any write, even one that put back the same value, so it does not have the ABA problem, but it may also fail for no visible reason (an interrupt, a cache eviction). That is why C++ has compare_exchange_weak, which may fail spuriously and belongs in a loop, and compare_exchange_strong, which does not.
Compare-and-swap is strictly stronger than test-and-set: a test-and-set lock is CAS(&lock, 0, 1), and Herlihy showed that CAS can build a wait-free version of any shared object for any number of threads, while test-and-set cannot for more than two. See Test-and-set for the spinlock built from the simpler instruction.
What the page leaves out
- Memory ordering. Real CAS calls take an ordering (
memory_order_acq_rel, …); the page treats memory as sequentially consistent. - Caches are drawn as one bus and one memory word.
- ABA is described above but not animated: the counter only grows, so it cannot happen here.
- Back-off: real loops often pause after a failed CAS to reduce contention.