Atomic add with a receipt
Fetch and add atomically adds a value to a memory word and returns the word old value. Unlike a plain increment it is uninterruptible, so concurrent adds never lose updates, and it hands back a unique number to each caller.
A correct shared counter
A counter incremented by many threads is the textbook race. Fetch and add fixes it directly: each thread does fetch and add of one, and because the operation is atomic, every increment counts and no value is dropped. There is no loop and no CAS retry needed.
The ticket lock
Fetch and add shines in the ticket lock, which restores the fairness that test and set lacks. The lock holds two counters, next and serving.
- To acquire, a thread does fetch and add on next to grab a unique ticket number
- It then spins until serving equals its ticket
- To release, the holder increments serving
Because tickets are handed out in order and served in order, threads enter strictly first come first served. That gives bounded waiting for free.
Key idea
Fetch and add returns a unique old value, giving lossless counters and fair ticket locks ordered first come first served.