Part 4 of 7 · 3 min read
Four conditions
In plain words: A deadlock does not need bad luck alone. It needs a particular shape of sharing. In 1971, Coffman, Elphick and Shoshani described four conditions that must all hold at the same moment for a deadlock to exist. All three of the main books repeat them. Think of a narrow bridge again to see each one.
| Condition | What it says | In the bridge story | In the lock demo |
|---|---|---|---|
| Mutual exclusion | A resource instance can be held by only one thread at a time | Only one car fits on the bridge | A mutex has one owner |
| Hold and wait | A thread holds one resource while waiting for another | A car sits on the bridge while waiting for the far end to clear | T1 holds A and waits for B |
| No preemption | A resource cannot be taken away from its holder; only the holder can release it | Nobody can lift a car off the bridge | The kernel does not take a lock from a thread |
| Circular wait | There is a cycle of threads, each waiting for a resource held by the next | Car 1 waits for car 2, and car 2 waits for car 1 | T1 waits for T2, and T2 waits for T1 |
Each condition by itself is common and harmless. Mutual exclusion is the reason locks exist at all. Hold and wait happens whenever code takes a second lock inside a critical section. Locks are not preempted because a lock that could be snatched away would not protect anything. Only the fourth, circular wait, is a real accident, and it depends on timing and on the order of acquisition.
The conditions are necessary: if even one is missing, no deadlock can occur. This is why prevention (page 3) works by removing one of the four. The conditions are not enough on their own for a general system (page 2 shows when a cycle is, and is not, a deadlock), but for resources with a single instance each, a cycle of waiting is exactly a deadlock.
Necessary conditions for deadlock
The necessary conditions for deadlock are four properties of a system. They are exclusive use of each resource (mutual exclusion), holding one resource while waiting for another (hold and wait), no forced removal of a resource (no preemption), and a cycle of waiting threads (circular wait). Only if all four hold at the same moment can a deadlock exist, so removing any one makes a deadlock impossible.
Example: if the program in section 1 took A and B in the same order in both threads, circular wait could never form, and the deadlock would be gone.
Common mistake
A deadlock does not need two threads or two locks. A single thread that locks a normal mutex twice in a row waits for itself. On this machine, a mutex of type PTHREAD_MUTEX_ERRORCHECK caught the second lock and returned error 35 (EDEADLK, "Resource deadlock avoided") instead of waiting. The default mutex type simply hangs.
Check yourself: 1. Which of the four conditions is the only one that depends on the order in which locks are taken? 2. Why can the kernel not simply take a lock away from a thread that has been holding it too long? 3. Name one condition that is missing when a thread locks a mutex, uses it and unlocks it before asking for anything else.