Information Technology Reference
In-Depth Information
//
//Astateissafeiffthereexistsasafesequenceofgrants
//thatwouldallowallthreadstoeventuallyreceivetheir
//maximumresourceneeds
//
bool
ResourceMgr::isDeadlock()
{
//avail[]holdsfreeresourcecount;
//alloc[][]holdscurrentallocation
//request[][]holdscurrently-blockedrequests
intj;
inttoBeAvail[]=copyavail[];
boolfinish[]=[false,false,false,...];
//finish[j]istrueifthreadjisguaranteedtofinish
while(true){
j=anythreadIDs.t.((finish[j]==false)&&(foralli:request[i][j]<=toBeAvail[i]));
if(nosuchjexists){
if(forallj:finish[j]==true){
returnfalse;
}
else{
returntrue;
}
}
else{
//Threadj*may*eventuallyfinishandreturnitscurrent
//allocationtothepool
finish[j]=true;
foralli:toBeAvail[i]=toBeAvail[i]+alloc[i][j];
}
}
}
Figure6.13: Coman et al.'s algorithm test for deadlock. This algorithm is
similar to the
isSafe()
test of the banker's algorithm shown in Figure 6.11.
We omit a detailed description of Coman's high level design and state decla-
rations; these are straightforward variations of the corresponding pseudo-code
for the Banker's Algorithm; see Figure 6.10 and 6.9.
If there are multiple instances of some resources, then we represent a resource
with k interchangable instances (e.g., k equivalent printers) as a node with k
connection points (e.g., see Figure 6.12-b). Now, a cycle is a necessary but not
sucient condition for deadlock.
Another solution, described by Coffman, Elphick, and Shoshani in 1971 is a
variation of Dijkstra's Banker's Algorithm. Now, we assume we no longer know
max[][]
, so we cannot assess whether the current state is safe or whether some
future sequence of requests can force us to deadlock. However, we can look at
the current set of resources, granted requests, and pending requests and ask
whether it is possible for the current set of requests to eventually be satisfied
assuming no more requests come and all threads eventually complete. If so,
there is no deadlock (yet, though we may be in an unsafe state); otherwise,
there is a deadlock.
Figure 6.13 shows the pseudocode of the main
testIfDeadlocked()
method,
