Chapter 6: Deadlock

Overview

Deadlock occurs in a system when all its constituent processes are blocked. Another way of saying this is that the system is deadlocked because there are no eligible actions that it can perform. We have already seen an example of deadlock in the nested monitor example of the last chapter. There, neither producer nor consumer process could make further progress since the consumer was blocked waiting for characters from the producer and the producer was blocked waiting for the monitor lock held by the consumer. In other words, each process was blocked waiting for a resource held by the other, sometimes referred to as a “deadly embrace”. Coffman, Elphick and Shoshani (1971) identified four necessary and sufficient conditions for the occurrence of deadlock:

• Serially reusable resources: the processes involved share resources which they use under mutual exclusion.

  For example, monitors encapsulate resources which are accessed using mutual exclusion (i.e. synchronized methods).

• Incremental acquisition: processes hold on to resources already allocated to them while waiting to acquire additional resources.

  This is exactly the situation in the nested monitor deadlock where the consumer holds the monitor lock while waiting for the producer to put a character into the buffer.

• No preemption: once acquired by a process, resources cannot be preempted (forcibly withdrawn) but are only released voluntarily.

  Again, the relevance of this to the nested monitor deadlock can easily be seen since if the consumer thread could be forced to release the monitor lock then execution of the producer could proceed.

• Wait-for cycle: a circular chain (or cycle) of processes exists such that each process holds a resource which its successor in the cycle is waiting to acquire.

  The nested monitor deadlock is a specific example of this with a chain of length two. The consumer holds the monitor lock for which the producer is waiting and the producer has a character for which the consumer is waiting.

Strategies for dealing with deadlock involve ensuring that one of these four conditions does not hold. For example, consider a system which allows deadlocked cycles of processes to occur but then detects these cycles and aborts the deadlocked processes, perhaps by operator action. Such a system is denying the third condition (no preemption), since the aborted processes are forced to release the resources they hold. The system implements deadlock detection and recovery.

In this chapter, we are concerned with an alternative strategy. Our aim is to design programs such that deadlock cannot occur. We describe how to analyze models for deadlock and how to show that a model is free from deadlock. Finally, both the model and implementation of a classic concurrent programming problem, the Dining Philosophers, is presented.