Mutexes
foundational · asked in almost every interview
The lost-update program with a lock around it. Twenty interleavings become two, and the losing orderings stop existing rather than becoming unlikely.
Enumerating the interleavings…
What this shows
A 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.
Why it is asked
Everyone says "add a mutex". Being able to say what happens to the interleaving space, and where the section must start and end, is the difference.
In an interview
Everyone says "add a mutex". Being able to say what happens to the interleaving space, and where the section must start and end, is the difference.
- locks
- critical section
- mutual exclusion
Run these next
- The lost update`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.
- DeadlockA cycle in the wait-for graph is the deadlock. Lock ordering removes it by construction, and it is only a policy when it is a total order over every lock.