Deadlock
intermediate · asked in almost every interview
Two threads, two locks, opposite acquisition order. Most interleavings finish fine — which is exactly why it ships — and the wait-for graph shows the cycle in the ones that do not.
Enumerating the interleavings…
What this shows
A 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.
Why it is asked
The four Coffman conditions are recall. Drawing the cycle, and knowing that a three-thread ring survives pairwise review, is not.
In an interview
The four Coffman conditions are recall. Drawing the cycle, and knowing that a three-thread ring survives pairwise review, is not.
- deadlock
- lock ordering
- wait-for graph
- Coffman