Process Deadlock: The Deadly Embrace
July 2001 WORK IN PROGRESS!
all seen deadlock occurring in real-life, special with automobiles. Figure 1 illustrates
a typical case of deadlock. In this case two cars are blocking the junction (at
A and D), and do not allow any of the other cars behind them to move. Unfortunately
both automobiles cannot move as there are automobiles blocking their entry into
the junction. The only way to clear the deadlock, apart from
the two cars who are turning into the junctions to give up and go straight ahead,
is for one of the automobiles which is blocking one of the junctions to reverse.
Unfortunately, in this case, they cannot, as there are automobiles behind them.
This is a deadly embrace. In resource terms, both of the car lanes of the main
road has one of the junctions, and requires the other, but none of the car lanes
can give their lane up.
Figure 1 Deadlock on a road junction (© billatnapier)
In process terms,
resource deadlock occurs when Process 1 holds Resource A, and Process 2 holds
Resource B, but Process 1 wants to gain access to Resource B, and vice-versa.
Each process then waits for the other to yield their exclusive access to their
resource. This is a deadly embrace. A typical problem can occur when data buffers
can become full. For example a print spooler can be setup so that it must receive
the full contents of a print file, before it will actually send it to the printer.
If print buffer is receiving print data from several sources, it can fill up the
buffer before any of the print jobs have completed. The only way round this problem
would be to increase the data buffer size, which can be difficult.
conditions that must occur for deadlock to occur are:
Mutual exclusion condition. This is where processes get exclusive control
of required resources, and will not yield the resource to any other process.
Wait for condition. This is where processes keep exclusive control of
acquired re-sources while waiting for additional resources.
No pre-emption condition. This is where resources cannot be removed
from the proc-esses which have gained them, until they have completed their access
Circular wait condition. This is a circular chain of processes on which
each process holds one or more resources that are requested by the next process
in the chain.
our example of deadlock in Figure 1 we can see that this passes all of these conditions.
A car blocking the junction defines mutual exclusion, and since the cars cannot
move away from the junction (in the deadlock case) there will be a condition for
wait and pre-emption. As both automobile lanes are waiting for each other, we
have a circular wait. Note that deadlock may occur very infrequently, but when
it does occur it normally requires some form of user input, to try and recover
the situation. In the case of the automobile deadlock, we would need someone to
make directions as to the best plan to overcome the deadlock (possibly, a traffic
If possible processes should run
without the problem of deadlock, as systems normally require a reboot to clear
the problem. One of the best-known avoidance algorithms is the Banker Algorithm,
which tries to avoid deadlock by estimating the amount of a given resource that
processes are likely to require, in order to run completion. It is typically applied
to define the amount of resources of the same type, but can be extended to resource
pools with differing resource types. In our automobile deadlock, we could have
applied the same principal, in that an automobile is not allow to turn to go into
the junction, unless both junctions can be cleared. Thus if one automobile could
not get into the junction, then the other automobile who wants to turn into the
other junction would not be allow to enter the junction, and would have to proceed
without turning into the junction. For example let's say that A is allowed to
wait at the junction, while there is an automobile waiting at junction F. It will
be allowed to do this, as deadlock will be avoided if there is no automobile turning
at D. If this continues, but an automobile now request to turn into C, and its
path is block, then it will not be allowed to do this as it can cause deadlock.
Mastering Computing, W.Buchanan, Palgrave.
Comments on this
If you've got any comments on this essay (no matter if you agree
or disagree with it), please send them to me using the form below.
Note your comments may be published
to a comments pages, but none of your details will be added to the comment, just
the date that it was sent. Thank you.