Ry
it signities that process P, has requested an instance of resource type Ry ancl
{is currently waiting for that resosice, A directed edge from resoutee type R
to process P, Js denoted by Rj — Pit signifies that an instance of resource
type &, has been allocated to process P,. A directed exige P, —> R, is called a
request edge; a directed elge Ry —> 7 i called an assignment edge.
Pictorially, we represent each process P, asa citcle and each resource type
R; asa rectangle. Since resource type R, may have more than one instance, we
represent each sich instance as a dot within the rectangle. Note that a request
edge points to only the rectangle Rj, whereas an assignment edge nnust also
designate one of the dots in the rectangle.
‘When process P; requests an instance of resource type R), a request edge
fs inserted in the resource-allocation graph. When this request can be Fuliled,
the request edge is instantaneously transformed to an assignment edge. When
the process no longer needs access to the resource, i releases the 1eSOUce; as a
result the assignment edge is deleted,
The resouree-allocation graph shown in Figure 7.2 depicts the following.
situation,
© The sets P, Rand E
Pi, Ps, Ps}
Ri, Ros Roe Ra)
E={P) > Ry Pe RR Py
© Resource instances
R= PR Pb
One instance of resource type Ry
Tivo instances of resource type Re
(One instance of resource type Rs
Tiare instances of resource type Ry 20
Chapter? Deadlocks
Figure 7.2. Resource-alocation graph.
# Process states:
© Process P; is holding an instance of resource type Re and is waiting for
an instance of resouree type &
Process P is holding an instance of Ry and an instance of Ry and is
‘waiting for an instance of Ry
2 Process Py is holding an instance of Ry
Given the definition of a resource-allocation graph, itean be shown that, if
the graph contains no cycles, then no process in the system is deadlocked. IE
the graph does contain a cycle, then a deadlock may exist
Teach resource type has exactly one instance, then a cycle implies that a
deadlock has occurred. If the cyele involves only a set of resource types, each
of which has only a single instance, then a deadlock has occurred. Each process
involved in the eyele is deadlocked. In this case, a cycle in the graph is both a
necessary and a sufficient condition for the existence of deadlock
Tfeach resource type has several instances, then a cycle does not necessarily
imply that a deadlock has occurred. In this case, a cycle in the graph is a
necessary but not a sufficient condition for the existence of deadlock.
To illustrate this concept, we return to the resource-allocation graph
depicted in Figure 7.2, Suppose that process Ps requests an instance of resource
type Rs. Since no resource instance is currently available, a request edge Py —
Reisadded to the graph (Figure 73), At this point, two minimal cycles exist in
the system:
Pm Ri Po Ro ho Bo
Ao Rh AS Ro Pe
Processes P}, Ps,anel Py are deadlocked, Process Ps is waiting forthe resource
Ry, which is held by process Py, Process Py is waiting for either pracess Por 7.2 Deadlock Characterization 251
Figure 73. Resource-aloation graph witha deadlock.
process P: to release resource Ry In addition, process P, is waiting for process
Ps to release resource Ri
Now consider the resource-allocation graph in Figure 7.4. In this example,
we also havea cycle
P+ RB BB
However, there isno deadlock. Observe that process P; may release ts instance
‘of resource type Ro, That resource can then beallocated to Ps, breaking the cycle
In summary, if resource-allocation graph does not have a cycle, then the
system is not in a deadlocked state. If there isa eyele, then the system may or
‘may not be in a deadlocked state, This observation is important swhen we eal
with the deadiock problem,
Figure 7.4 Resource-alocation graph wih a cycle but no deacock, 73
Chapter? Deadlocks
Methods for Handling Deadlocks
Generally speaking, we can deal with the deadlock problem in one of three
‘+ We can use a protocol to prevent or avoid deadlocks, ensuring that the
system will never enter a deadlock state.
‘= We can allow the system to enter a deadlock state, detect it, and recover
‘= We can ignore the problem altogether and pretend that deadlocks never
jccur in the system.
The third solution is the one used by most operating systems, including UNIX
and Windows: it is then up to the application developer to write programs that
handle deadlocks.
Next, we elaborate briefly on each of the three methods for handling
leadilocks. Then, in Sections 7-4 through 77, we present detailed algorithms,
However, before proceeding, we should mention that some researchers have
Argued that none of the basic approaches alone is appropriate for the entire
spectrum of resourceallocation problems in operating systems. The basic
approaches can be combined, however, allowing, us to select an optimal
approach for each class of resouices in a system.
Toensure that deadlocks never occut, the system can use either a deadlock:
prevention or a deadlock-avoidance scheme. Deadlock prevention provides
2 set of methods for ensuring that at least one of the necessary conditions
(ection 72.1} cannot hold. Thoso methods prevent deadlocks by consteaining
hhow requests for resources ean be made. We discuss these methods in Section,
74.
Deadlock avoidance requires that the operating system be given in
advance additional information concerning which resources a process will
request and use during its lifetime, With this additional knowledge, ican
decide for each request whether or not the process should wait. To decide
whether the current request can be satisfied or must be delayed, the system
‘must consider the resources currently available, the resources eurcently allo
‘ated to each process, and the future requests and releases of each process. We
discuss these schemes in Section 7.5,
Ifa system does not employ either a deadlockprevention or a deadlock
avoidance algorithm, then a deadlock situation may arise In this environmen
the system can provide an algorithm that examines the state of the system tc
determine whether a deadlock has occurred and an algorithm to recover from
the deadlock (if a deadlock has indeed occurred), We discuss these issues in
Section 7.6 and Section 77.
Ifa system neither ensures that a deadlock will never occur nor provides
1 mechanism for deadlock detection and recovery, then we may arrive al
a situation where the system is in a deadlocked state yet has no way of
recognizing what has happened. In this case, the undetected deadlock will
est in deterioration ofthe system's performance, because resources are being,
held by processes that cannot run and because more and more processes, a5
they make requests for resources, wll enter a deadlocked state, Eventually, the
system will top functioning and will need to be restarted manually 74
74 Deadlock Prevention 253,
Although this method may not seem to bea viable approach to thedeadilock
problem, it is nevertheless used in most operating systems, as mentioned
tarlier In many systems, deadlocks occur infrequently (say, once per Year)
thus, this method is cheaper than the prevention, avoidance, or detection and
recovery methods, which mustte used constantly. Also, insome circumstances,
a system is in a frozen state but not ina deadlocked state. We see this situation,
for example, with a real-time process runing at the highest priority (or any
process running on a nonpreemptive scheduler) andl never returning control
to the operating system. The system must have manual recovery methods for
such conditions anid may simply use those techniques for deadlock recovery.
Deadlock Prevention
As we noted in Section 721, fora deadlock t oceur, each ofthe four necessary
‘conditions must hold, By ensuring that atleast one ofthese conditions cannot
hold, we can prewnt the occurrence of a deadlock. We claborate on this
approach by examining each of the four necessary conditions separately
7.4.1 Mutual Exclusion
‘The mutual-exclusion condition must hold for nonsharable resources. For
example, a printer cannot be simuiltancously shared by several processes,
Sharable resources, in contrast, do not require mutually exclusive access and
thus cannot be involved in a deadlock. Read-only files are a good example of
a sharable resource. If several processes attempt to open a read-only file at the
Same time, they can be granted! simultancous acess fo the file. process never
reeds to wait for a sharable resource. In general, however, we cannot prevent
deadlocks by denying the mutual-exclusion condition, because some resources,
are intrinsically nonsharable
7.4.2 Hold and Walt
‘Toensure that the hold-and-wait condition never occurs in thesystem, we must,
guarantee that, whenever @ process requests a resouree, it does not hold any
ther resources, One protocol that can be used requires each process to request
land be allocated all is resources before it begins execution, We can implement
this provision by requiring that system calls requesting resources fora process
precede all other system calls.
"An alternative protocol allows a process to request resources only when it
has none, process may request some resources and use them. Before it can
request any additional resources, however, it must release all the esources that
itis currently allocated,
‘To illustrate the difference between these two protocols, we consider a
process that copies data from a DVD drive toa file on disk, sorts the file, and
then prints the results to a printer fall resources must be requested at the
beginning of the process, then the process must initially request the DVD dive,
disk file, and printer. Itwill hold the printer for its entire execution, even though
itmeeds the printer only at the en
“The second method allows the process to request initially only the DVD
rive and disk file. It copies from the DVD drive to the disk and then releases 258
Chapter Deadlocks
both the DVD drive and the disk file, The process must then again request the
disk file and the printer. After copying the disk file to the printer, releases
these two resources and terminates
Both these protocols have two main disadvantages First, resource utiliza
tion may be low, since resources may be allocated but unused for along period.
In the example given, for instance, we can release the DVD drive and disk file,
and then again request the disk file and printer, only if we can be sure that ou
tlata will remain on the disk file. If we cannot be assured that they wil, then.
ve must request all resources at the beginning for both protocols,
Second, starvation is possible. A process that needs several popular
resources may have to wait indefinitely, hocause at least one ofthe resources
that it needs is always allocated to some other process
7.4.3. No Preemption
‘The third necessary condition for deadlocks és that there be no preemption
Cf resources that have already been allocated. To ensure that this condition
does not hold, we can use the following protocol. Ifa process is holding some
resources and requests another resource that cannot be immediately allocated
to it (that is, the process must wait), then all resources eurzently being held
are preempted. In other words, these resources ate implicitly released. The
[preempted resources are added to the list of resources for which the process is
Waiting. The process will be restarted only when itcan regaia its old resources,
as wellas the new ones that it is requesting.
Alternatively, fa process requests some resources, we frst check whether
they are available. 1 they are, Wwe allocate them. It Hey are Mot, we check
‘whether they are allocated to some other process that is waiting for additional
:esourees.IFs0, we preempt the desired resources From the waiting process and
allocate them to the requesting process. Ifthe resources are neither available
nor held by a waiting process, the requesting, process must wait. While it
‘waiting, some ofits resources may be preempted, but only if another process
requests them. A process can be restarted only when iti allocated the new
resources it Is requesting and recovers any resources that wete preempted
While # was wating,
‘This protocol is often applied to resources whose state can be easily saved
and restored ater such as CPU registers and memory space, teannot generally
be applied to such resources as printers and tape drives,
7.4.4 Circular Wait
The fourth and final condition for deadlocks is the cireular-wait condition. One
ay to ensure that this condition never holds is to impose a total ordering of
all resource types and to require that each process requests resources in an
increasing order of enumeration.
To illustrate, we let R = {Ry, Rs, », Ru} be the set of resource types. We
assign to each resource type @ unique integer number, which allows us to
compare two resources and! to determine whether one precedes another in our
ordering, Formally, we define a one-to-one function FR N, where Nis the
set of natural numbers. For example, if the set of resource types R includes, 74. Deadlock Prevention 255
tape dives, disk drives, and printers, then the function F might be defined as
follows:
Ettape drive)
Fidisk drive)
Fiprinter) = 12
We can now consider the following protocol to prevent deadlocks: Each
process can request resources only in an increasing order of enumeration. That
Js, a process can intially request any number of instances of a resource type—
say, R. After that, the process can request instances of resource type Ry ifand
only if F(R;) > F(R) I several instances of the same resource type are needed,
single request forall of them must be issued. For example, using the function
slefined previously, a process that wants to use the tape drive and printer at
the same time must fist request the tape drive and then request the printer
Alternatively, we can require that, whenever a process requests an instance of
resource type Ri, it has released any resources R, such that F(R) = F(R))
IF these two protocols are used, then the circularswvait condition cannot
hold, We ean demonstrate this fact by asstiming that a circular wait exists
{proof by contradiction). Let the set of processes involved in the circular waite
[Pj Py, Pa}, where P, is waiting fora resource R,, which is held by process
ist. (Mlodulo arithmetic is used on the indexes, so that P, is waiting for
a resource Ry held by Pp.) Then, since process P+ is holding resource R,
While requesting resource Res), we must have F(R) < F(Rrs) forall i, But
this condition means that F(R) = F(Ri) = w= F(R) < F(R). By transitivity
P{Ry) © F(R), which is impossible Therafore, there cam be na ciealar wait
We can accomplish this scheme in an application program by developing.
an ordering among all synchronization objects inthe system. All requests for
synchnonization objects must be made in increasing order. For example, ifthe
lock ordering inthe Ptheead program shown in Figute 7.1 was.
F(eirat-mutex) =1
F(second mater)
5
then thresd.tvo could not request the locks out of onier,
Keep in mind that developing an ordering, or hierarchy in itself does not
prevent deadlock. Its up to-application developers to write programs that
follosr the ordering. Also note thatthe function F should be defined according.
tothe normal order of usage of the resources in a system. For example, because
the tape drive is usually needed before the printer, it would be reasonable t0
define Ftape drive) < Fiprinter)
‘Although ensuring that resources are acquired in the proper order is the
responsibility of application developers, certain software can be used to verify
that locks are acquired in the proper order and to give appropriate warnings
when locks are aequited out of orser and deadlock s possible, One lock-onder
verifies, which works on BSD versions of UNIX such as FreeBSD, is known as
witness, Witness uses mutual-exclision locks to protect ctitical sections, as
doseribod in Chapter 6; i¢ works by dynamically maintaining the relationship
of lock orders ina system. Lets use the program shown in Figure 7.L as an
fexample. Assume that thraad one isthe ist to acquire the locks andl does so in 26
78
Chapter? Deadlocks
the order (1) first mutex, 2) second zutex. Witness reconds the relationship
that first mutex must be acquired before eecond.2utex, If thread twa later
acquires the locks out of order, witness generates a warning message on the
system console.
Deadlock Avoidance
Deadlock prevention algorithms, as discussed in Section? 4, prevent deadlocks
by restraining how requests can be made. The restraints ensure that atleast
‘one of the necessary’ conditions for deadlock cannot occur and, hence, that
deadlocks cannot hold. Possible side effects of preventing deadiocks by this
method, horvever, are low levice utilization and reduced system throughput,
‘An alternative method for avoiding deadlocks is to require additional
information about how resources are to be requested. For example, ina system
‘with one tape drive and one printer, the system might need to know that
[process P will request first the tape drive and then the printer before releasing,
both resources, whereas process Q will request first the printer and then the
tape drive. With this knowledge of the complete sequence of requests and
releases for each process, the system can decide for each request whether or
rot the process should wait in arder to avoid a possible future deadlock, Each
request requires that in making this decision the system consider the resources
currently available, the resources currently allocated to each process, and the
Future requests and releases of each process
The variousalgorithms that use this approach differin theamountand type
ofinformation required. The simplest and most useful model requites thateach,
[process declare the mavinum nur of resources ofeach type that it may need.
Given this a priori information, itis possible to construct an algorithm that
ensures that the system will never entera deadlocked state, Such an algorithm,
defines the deadlock-avoidance approach. A deadlock-avoidance algorithm
dynamically examines the resouree-allocation state to enstice that a ercul
‘wait condition can never exist. The resourceallocation state is defined by the
‘number of available and allocated resources and the maximum demands of
the processes. In the following sections, we explore two deadlock-avoidance
algorithms.
7.5.1 Safe State
AA state is sa ifthe system can allocate resources to each process (up ta its
‘maximum) in some order and still avoid a deadlock. More formally, a system
is ina sale state only if there exists a safe sequence. A sequence of processes
18. safe sequence for the current allocation state if, for each
P,, the resource requests that P, can still make can be satisfied by the currently
available resources plus the resources held by all P,, with j= in this situation,
if the resources that P, needs are not immediately available, then P, can wait
tuntl all P, have finished. When they’ have finished, P, can obtain all ofits
needed resources, complete its designated task, return its allocated resources,
and terminate. When F, terminates, P=: can obtain its needed resources, and
soon, Ifno such sequence exists, then the system state is said to be safe 75 Deadlock Avoidance 257
—— = onsale
| seaoa. |
Figure 7.5. Sale, unsate, and deadlock state spaces,
A safe state is not a deadlocked state. Conversely, a deadlocked state is
an unsafe state, Not all unsafe states are deadlocks, however (Figure 75).
‘An unsafe state ny lead to a deadlock, As long as the state is safe, the
‘operating system can avoid unsafe (and deadlocked) states. In an unsafe state,
the operating system cannot prevent processes from requesting resources stich
that a deadlock occurs: The behavior ofthe processes controls unsafe states.
To illustrate, we consider a system with 12 magnetic tape drives and three
processes: My Ps, and Ps, Process Py requires 10 tape drives, process P, may
rnovd as many a6 4 tape drives, and process P» may need up to 9 tape drives,
Suppose that, at time fy, process Py is holding 5 tape drives, process Fis,
holding 2 tape drives, andl process P: is holding 2 tape delves (Thus, there age
Bree tape drives)
Maximum Needs Current Needs
% 10 5
» 4 2
P 9 2
Attime the system is in a safe state. The sequence satisfies
the safety condition. Process P} ean immediately be allocated alts tape drives
and then return them (the system will then have 5 available tape drives); then
process P can getall its tape drives and return them (the system will then have
10 available tape drives); and finally process P: can get al its tape drives and
seturn them (the system will then have all 12 tape drives available).
AA system can go from a safe slate loan unsafe state. Suppose that, at time
41, process P2 requests and is allocated one more tape drive, The system is m0
Jonger ina safe site, At this point, only process P; can be allocated all ts tape
dlrives, When it returns them, the system will have only 4available tape drives.
Since process Py is allocated 5 tape drives but has a maximum of 10, it ma
request 5 move tape drives. Since they’ are unavailable, process P rmust wat
Similarly, process Ps may request an additional 6 tape dives and have to wait,
resulting ina deadlock, Our mistake was in granting the request from process
P for one more tape drive. If we had mace P wait until either of the other 28
Chapter? Deadlocks
processes had finished and released is resources, then we could have avbided
the deadlock
Given the concept of a safe state, we can define avoidance algorithms that
censure that the system will never deadlock. Theicea is simply to ensure thatthe
system will alway’ remain in a safe state, Initially, the system is in a safe state
Whenever a process requests a resource that is currently available, the system
must decide whether the resource can be allocated immediately of whether
the process must wait, The request is granted only if the allocation leaves the
system ina safe state,
In this scheme, ifa process requests a resource that is currently available,
it may stil have to wait: Thus, resource utilization may be lower than it would
otherwise be,
7.8.2. Resource-Allocation-Graph Algorithm
Hwehavea resource-allocation system with only one instance of each resource
type, a variant of the resource-allocation graph defined in Section 7.2.2 ean be
used for deadlock avoidance. In addition to the request and assignment edges
already described, we introduce a new type of edge, called a claim edge.
A claim edge P, > R; indicates that process 7) may request resource Rat
Some time inthe future. This edge resembles a request edge in direction but is
represented in the graph by a dashed line, When process P, requests resource
R), the claim edge P, > R, is converted to a request edge. Similarly, when a
resource R; is released by P,, the assignment edge R) — P, is reconverted '0
a claim edge P) > R), Wenote that the rusourees muist be claimed a prior! in
the system. That is before process P, starts executing, all its claim edges must
already appear in the ssouee-allocation graph. We can relay this condition By
allowing a claim edge P, — R) to be acded to the graph only if all the edges
associated with process P; are claim edges.
Suppose that process P, requests resource Ry. The request can be granted
only if converting the request edge P, — R, to an assignment edge R) —» P,
doesnot resultin the formation of acyele in the resource-allocation graph. Note
that we check for safety by usinga eycle-detection algorithm. An algorithm for
detecting a cycle in this graph requires an order of operations, where iis
the number of processes in the system,
ino cycle exists, then the allocation of the resource will leave the system
ina safe state. Ifa cycle is found, then the allocation will put the system in
A
Sar
Figure 7.6. Resource-alocation graph for deadlock svoidanes, 7.5. Deadlock Avoidance 259
Figure 7.7. An unsate state ma resource-lleeationgragh
an unsafe state, Therefore, process P, will have to wait for its requests to be
satisfied,
‘To illustrate this algorithm, we consider the resource-allocation graph of
Figure 7.6. Suppose that Ps requests Rs. Although Ry is currently free, we
cannot allocate i to Ps, since this action will create a cycle in the graph (Figure
77), A cycle indicates that the system isin an unsafe state, IP; requests Ry,
and Ps requests Ri ther a deadlock will occut
7.5.3 Banker's Algorithm,
The resourceallocation-graph algorithm is not applicable to a resource
allocation system with multiple instances of each resource type. The deadlock-
Gvoidance algorithm thal we describe nent is spplicable to such a system but
is less efficient than the resource-allocation graph scheme, This algorithm is
commonly known as the haaker’salgorita The name was chosen because the
algorithm could be ased in a banking system to ensure that the bank never
allocated its available cash in such a way that it could no longer satisfy the
needs of al its customers.
‘When a new process enters the system, it must declare the maximum
numberof instances of each resource type that it may need. This number may
not exceed the total number of resources in the system. When a user requests
a set of resources, the system must determine whether the allocation of these
resources will leave the system in a safe state. I it will, the resources are
allocated otherwise, the process must wait until some other process releases
enough resources,
Several data structures must be maintained to implement the banker's
algorithm. These data structures encode the state of the resource-allocation,
System, Let i be the number of processes in the system and nr be the number
cof resource types. We need the following data structures
* Available. A vectorof length indicates the number of available resources
‘of each type. If Aauitblel/| equals &, there are k instances of resource type
R, available,
© Max. An ir nr matrix defines the maximum demand of each process
If Max(lf] equals &, then process P, may request at most k instances of
resource type R Chapter? Deadlocks
‘© Allocation, Anyi 1 matrix defines the numberof resources of eac type
‘currently allocated to each process If Allocation} equals then process
P, is currently allocated k instances of resouce type &,
+ Need. An 1 = m matsix indicates the remaining resource need of each
process. I Nofifflequals then process P, may need k more instances of
Fesource type R, to complete its task. Note that Neil] equals Mas]
‘Alloatont
“These data structures vary over time in both size and value.
‘To simplify the presentation of the banker's algorithm, we next establish
some notation, Let X and Y be vectors of length 1. We say that X = Y ifand
only if Xi] = YQ] forall i= 1, 2. 1 For example, if X= (1.73.2) and ¥ =
(032, then Y =X. Y= XY = Nand ¥# X.
‘We ean treat each row in the matrices Allocation and Neat as vectors
and refer to them as Allocation, and New. The vector Aileention, specifies
the resources curently allocated to process Py; the vector New; specifies the
‘additional resources that process P, may still quest to complete its task.
75341. Safety Algorithm
We can now present the algorithm for finding out whether or not a system is,
Ina safe state. This algorithm can be described as follows:
11. Let Work and Finish be vectors of length nt and 1, respectively. Initialize
‘Work = Available and Finish{] = flse fOr i= 0,1, ue t= 1
2. Find an i such that both
false
b. New = Work
a. Finish) ==,
If no such Fexists, goto step 4.
3. Work = Work + Allocation,
Finis] = tre
Goto step 2,
4. Te Finishi]
fre forall then the system is in a safe state
‘Thisalgorithm may requirean order ofm « 1»? operations todetermine whether
astateis safe
7532 Resource-Request Algorithm
We now describe the algorithm which determines if requests can be safely
granted.
‘Let Request be the request vector for process PIF Request; [J] == f, then.
[process P, avants f instances of resource type Ry. When a request for resources
is made by process P, the following actions are taken:
1. UF Reuest, < Nee, goto step 2. Otherwise, raise an error condition, since
the process has exceeded its maximum claim. 75 Deadlock Avoidance 261
IE Rojuest, < Available, go to step 3, Otherwise, P must wait, since the
resources are not available
3. Have the system pretend to have allocated the requested resources to
process P, by modifying the state as follows
Available = Available - Request
Allocation, = Allocation, + Reques
Non: = Neo, = Regu
If the resulting resource-allacation state is safe, the transaction is com-
pleted, and process P, is allocated its resources. However, ifthe new state
is unsafe, then P, must wait for Request, and the old resource-allocation
state is restored,
753.3 Am Illustrative Example
Finally to illustrate the use ofthe banker's algorithm, consider a system with
five processes Py through P, and three resource types 4, B, and C. Resoure
lype A has 10 instances, resource type B has 5 instances, and resource type C
thas 7 instances. Suppose that, at time Th, the following snapshot of the system
has been taken:
ation Max Available
ABC ABC ABC
m 010-753-332
P 200-322
P3902 902
A 211222
Pp 002433,
‘The content of the matrix Nea is defined to be May — Allecition and is as
follows:
Need
ABC
mh 743
m 122
600
Pond
P43
‘We claim that the system is currently in a safe state, Indeed, the sequence
Ry and Ry — P; for some resource 76 Deadlock Detection 263
B)
a
@
A a
@ ©
Figure 78 (| Resousce-llocaion rap.) Corresponding waiter graph,
A, For example, in Figure 78, we presenta resource-allocation graph and the
corresponding wait-for graph
‘Asbeforea deadlock exists in the system if and only if the waitfor graph
contains a cycle. To detect deadlocks the system needs to maint the waitor
teaph and poriadiclly fro on algorithm that oarches for s cyclen the graph
“Rn algorithm to detect a eyele ina graph requites an onder of? operations,
‘where is the numberof vertices in the graph
7.6.2 Several instances of a Resource Type
‘The wait-for graph scheme is not applicable to a resourceallocation system
with multiple instances of each resource type. We turn now to a deadlock:
sletection algorithm thats applicable to such a system. The algorithm employs
several time-varying data structures that are similar to those used in the
banker's algorithm (Section 7.5.3)
‘Available. A vector of length m indicates the numberof available resources
of each type.
> Allocation. An ir 1 matrix defines the numberof resources of each type
currently allocated to each process
‘© Request. An 2 m matrix indicates the current request of each process,
If Request lll equals k, then process P, is requesting k more instances of
resource type R
‘The =telation between twovectorsisdefined asin ection 7.53. Tosimplify
notation, we again treat the rows in the matrices Allocation and Royest as
vectors: ve refer to them as Allocation, and Request, The detection algorithm 261 Chapter? Deadlocks
leseribed here simply investigates every possible allocation sequence for the
processes that remain to be completed. Compare this algorithm with the
‘banker's algorithm of Section 7.3.3.
1. Let Work and Finish be vectors of length m and m, respectively. Initialize
Wark = Available. For i=0, 1, ..-n-1, if Allocation, #0, then Finis
otherwise, Finis] = true
2, Find an index i such that both
a, nisl] == fae
B. Rejuest; < Work
no such exists, goto step 4.
3. Work
Finish
Goto step 2
4. RFit
slate. Moreover if Finish]
Work + Allocation
= {<1 then the system isin a deadlocked
ise, then process P, is deadlocked.
‘This algorithm requires an order of mx 1 operations to detect whether the
system is in a deadlocked state.
You may wonder why we reclaim the resources of process P, (in step 3)
fas soon as we determine that Rejuest, = Work (in step 2b). We know that Pi
ss currently nor involved in a deadlock (since Reguest; = Work). Thus, we take
an optimistic attitude and assume that P, will require no more resources to
‘complete its task; it will thus soon return all currently allocated resources to
the system. If our assumption is incorrect, a deadlock may occur latet. That
deadlock will be detected the next time the deadlock-letuetion algorithm is,
invoked,
"To illustrate this algorithm, we consider a system with five processes Ry
through Ps and three resource types A.B, and C. Resource type A has seven
instances, resource type B has two instances, and resource type C has six
instances: Suppose that, at time Tp, we have the following resource-allocation
state
Allocation Request Available
ABC ABC ABC
Pm 010-0000
e200 | 203)
mR 303° 000
mm
Py 002 on
We claim that the system isnot ina deadlocked state. Indeed! if we execute
‘our algorithm, we will find that the sequence
