CSE Roadmap

Core tier · about 4 hours · 7 parts

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.