Concurrency: State Models and Java Programs

Chapter 6. Deadlock

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 ...