Deadlock: Conditions, Detection, and Prevention

Two request threads each need two account locks. One thread locks Account A and waits for Account B. At the same time, the other locks Account B and waits for Account A.

Neither thread can continue:

Neither thread is broken on its own. The problem exists only in the loop between them, which is why deadlocks are invisible when you read either thread's code in isolation.

This is a deadlock: a set of execution contexts cannot make progress because each is waiting for an event that only another member of the same waiting set can cause.

More CPU time does not help. Neither thread is slow, and the required event is not arriving from an external device. Progress requires changing the resource-allocation state, terminating or rolling back work, or preventing the cycle from being created.

This chapter develops the four necessary conditions for deadlock, models waiting with resource and wait-for graphs, and examines avoidance, prevention, detection, diagnosis, and recovery techniques.