The lost update
foundational · asked in almost every interview
Two threads, one shared counter, one `count++` each. Every interleaving of load, add and store, enumerated — and the eighteen of twenty that lose an update marked.
Enumerating the interleavings…
What this shows
`count++` is three operations, not one. Only two of its twenty interleavings produce 2; the failure is the common case, and an atomic increment removes the orderings rather than making them rarer.
Why it is asked
Being able to draw the interleaving rather than name it. "Race condition" is recall; showing which two orderings are safe is understanding.
In an interview
Being able to draw the interleaving rather than name it. "Race condition" is recall; showing which two orderings are safe is understanding.
- race condition
- read-modify-write
- atomicity
- interleaving
Run these next
- Atomic operationsAtomicity is not speed and not a lock. It is indivisibility: no interleaving can slot between the read and the write, so the orderings that lost updates cease to exist.
- MutexesA lock removes orderings from the space. The critical section must span the whole read-modify-write — guarding only the write leaves the window exactly where it was.
- Check-then-actThe window is between the check and the act. A lock that begins after the check protects nothing; the fix is to ask and act in one indivisible operation.