Information Technology Reference
In-Depth Information
P0
owned by
waiting
for
waiting
for
CS
owned by
owned by
waiting
for
owned by
waiting
for
Figure6.7: Graph representation of the state of a Dining Philosophers system
that includes a cycle among waiting threads and resources but that is not
deadlocked. Circles represent threads, boxes represent resources, dots within a
box represent multiple instances of a resource, an arrow from a dot/resource
instance to a circle/thread represents anownedbyrelationship and an arrow
from a circle/thread to a box/resource represents awaitingforrelationship.
Thread 1
Thread 2
1
Acquire A
2
Acquire B
3
Acquire C
4
Wait for C
5
Wait for B
How could we avoid this deadlock? The deadlock's circular waiting occurs
when we reach step 5, but our fate was sealed much earlier. In particular, once
we complete step 2 and thread 2 acquires B, deadlock is inevitable. In this case
to prevent the deadlock we have to be smart enough to see the deadlock that
will occur at step 5 much earlier; once step 1 completes and thread 1 acquires
A, we cannot allow thread 2 to complete step 2 and acquire B or deadlock will
follow.
This example illustrates that given an arbitrary program, preventing dead-
lock can be challenging. Deadlock prevention solutions, therefore, often restrict
or take advantage of the structure of a program to avoid such complexity. As a
result, no single solution is best in all cases.
Section 6.2.1 listed four necessary conditions for deadlock. These conditions
are useful because they suggest approaches for preventing deadlock: if a system
