Information Technology Reference
In-Depth Information
Since testing may not uncover deadlock problems, it is important to con-
struct systems that are deadlock-free by design.
6.2.1
Necessary conditions for deadlock
There are four necessary conditions for deadlock to occur. Knowing these con-
ditions is useful for designing solutions to deadlock: if you can prevent any one
of these conditions, then you can eliminate the possibility of deadlock.
1. Bounded resources. There are a finite number of threads that can
simultaneously use a resource.
2. No preemption. Once a thread acquires a resource, the ownership of
the resource cannot be revoked until the thread acts to release it.
3. Wait while holding. A thread holds one resource while waiting for an-
other. This condition is sometimes called multiple independent requests
because it occurs when a thread first acquires one resource and then at-
tempts to acquire another resource.
4. Circular waiting. There is a set of waiting threads such that each thread
is waiting for a resource held by another.
Example: Dining Philosophers.
To illustrate the circular waiting condition,
Figure 6.6 maps the state of a deadlocked Dining Philosophers implemen-
tation to an abstract graph that shows which resources are owned by which
threads and which threads wait for which resources. In this type of graph, if
there is one instance of each type of resource (e.g., a particular chopstick),
then a cycle implies deadlock (assuming the system does not allow preemp-
tion.)
These four conditions are necessary but not sucient for deadlock. If there
are multiple instances of a type of resource, then there can by a cycle of waiting
without deadlock because a thread not in the cycle may return resources to the
pool.
Example: Dining Philosophers.
Suppose we have a set of 5 philosophers
at a table with 5 chopsticks but that the chopsticks are placed in a tray at
the center of the table when they are not in use. We could be in the state
illustrated in Figure 6.7 where philosopher 1 has two chopsticks, philosophers
2, 3, and 4 each have one chopstick and is waiting for another chopstick, and
philosopher 5 has no chopsticks. In this state we have bounded resources
(5 chopsticks), no preemption (we cannot forcibly remove a chopstick from a
hungry philosopher's hand), wait while holding (philosophers 2, 3 and 4 are
holding a chopstick while waiting for another), and circular waiting (each of
philosophers 2, 3, and 4 are waiting for a resource held by another of them.)
However, we do not have deadlock; eventually thread 1 will release its two
