Deadlocks

Let us assume that there are two folk who wish to do some ironing. The ironing board is in the hall cupboard, and the iron is under the sink in the kitchen. One algorithm is to wait for the ironing board to become available, obtain it, then wait for the iron to become available, and obtain that. Let's say that I follow this algorithm, but that my flatmate, takes the other approach, of waiting for the iron, then waiting for the ironing board.

The situation is possible that while I am putting up the ironing board, she has taken the iron. Both of us then wait for the other resource---I for the iron, she for the ironing board---and end up waiting forever. This situation is known as a deadlock. (It is the reason my clothes are never ironed.)

Another example might be if two car drivers meet in a narrow country road and each refuses to reverse. This could result in death by starvation, or in a short comedy involving Tony Hancock.

In cases with human beings, typically deadlock occurs only when people are being very stuborn. As you know though, computers and their software can be increadibly stuborn and so in computer systems, deadlock becomes a very real problem. In fact, any situation in which a process is allowed to wait for exclusive access to a resource (like an ironing board, or a narrow stretch of road, or a printer, or a tape drive, or a database record, or a file), there exists the potential for deadlock.

Resources can be physical things like peripherals, software resources like records, and files; a lock on a semaphore may also be regarded as a resource---deadlock is certainly possible with semaphores.

There are four conditions which are necessary for deadlock to occur:

  1. Mutual exclusion: only one process may use a resource at a time.
  2. 'Hold and wait condition': processes may wait for access to resources while holding on to other resources.
  3. No preemption: a resource may not be taken away from a process until it relinquishes it.
  4. Circular wait: there must be a cycle of processes, each of which is waiting on a resource held by another process in the cycle.
If one of these requirements is absent, deadlock may not occur.

In general, there are also four ways of dealing with the deadlock problem:

  1. Dynamic avoidance
  2. Detection and recovery
  3. Prevention
  4. Ignorance
last updated 23 April 1998