396 CHAPTER 6 Graph Theory
6.15.1 WAITFOR Graphs
To model the general situation of handling the request for and the allocation of resources
involving many users and many resources, we formally define a special type of directed
graph.Definition 1. A WAITFOR graph for the allocation status of a set of resources is a
directed bipartite graph D = (V, E) where V 1 and V 2 are a bipartition of V. The el-ements of V 1 = {P 1 , P 2.. P} I represent users of the resources, and the elements of
V 2 = {R 1 , R 2. , Rm} represent resources. For P E VI and R E V 2 , there is an edge(P, R) e E if user P requests resource R and has not been granted resource R and an
edge (R, P) E E if user P has been allocated the resource R where P E V 1 and R E V 2.
A WAITFOR graph can be thought of as taking a snapshot of the status of requests for
and allocations of resources at a fixed point in time. Different points in time may generate
different WAITFOR graphs for the same users and the same resources.
In the operation of a computer, it is important to know at each point in time if any of
the processes being executed by an operating system cannot progress toward completion.
Two or more processes waiting indefinitely for an event that can only be completed by one
of the waiting processes are said to be in a deadlock state, or deadlock. A deadlock state
will depend on the scheme that is used by the operating system to allocate resources such
as input or output devices or files. Regardless of the allocation scheme, an operating system
must deal with the problems of detecting a deadlock state and deciding what to do when
a deadlock state is detected. One allocation scheme for an operating system is to allocate
resources so that any resource is assigned completely to one process at a time but can be
reassigned when one process has completed its use. Typically, printers, tape drives, and
files are allocated in this way. Such an allocation scheme is called a single-unit resource
scheme.
Figure 6.57 shows a WAITFOR graph that represents a deadlock state for an operating
system using the single-unit resource allocation scheme. User 1 needs both a tape drive and
a printer to continue. The tape drive is allocated to User 1, but the printer is allocated to
User 3. At the same time, User 3 needs both a tape drive and a printer to continue. User 3
has been allocated the printer but must wait for the tape drive. The problem is that neither
User 1 nor User 3 can proceed until one of the devices allocated to the other is freed.
Since neither can proceed until all their requested resources are allocated, the processing
comes to a deadlock state. The operating system could break the deadlock by taking the
tape drive away from User 1 or by taking the printer away from User 3. The reader should
draw the WAITFOR graphs that result from these drastic actions to see whether they are
deadlock free. Figure 6.57 also shows a second problem that an operating system must
solve. In the case, if User 1 finishes with the tape drive or the operating system takes it
away from User 1, should User 2 and User 3 be given access to that resource next? The
WAITFOR graph gives no help with this question. A key property about WAITFOR graphs
is summarized in the next theorem.