Several Instances of a Resource Type

• The wait-for graph scheme is not applicable to a resource-allocation system with multiple instances of each resource type.
• We turn now to a deadlock-detection algorithm that is applicable to such a system. The algorithm employs several time-varying data structures:
  • Available. A vector of length $m$ indicates the number of available resources of each type.
  • Allocation. An $n \times m$ matrix defines the number of resources of each type currently allocated to each process.
  • Request. An $n \times m$ matrix indicates the current request of each process.
    • If $Request[i][j]$ equals $k$, then process $P_i$ is requesting $k$ more instances of resource type $R_j$ .
• The detection. algorithm described here simply investigates every possible allocation sequence for the processes that remain to be completed.
  1. Let $Work$ and $Finish$ be vectors of length $m$ and $n$, respectively. Initialize $Work=Available$. For $i=0,1,\ldots,n-1$, if $Allocation_i \neq 0$, then $Finish[i]=false$; otherwise, $Finish[i]=true$.
  2. Find an index $i$ such that both

     a.

     $Finish[i]==false$

     b.

     $Request_i \leq Work$

     If no such $i$ exists, go to step 4.
  3. $Work=Work + Allocation$
     $Finish[i]=true$
     Go to step 2.
  4. If $Finish[i]==false$, for some $i, 0 \leq i \leq n$, then the system is in a deadlocked state. Moreover, if $Finish[i]==false$, then process $P_i$ is deadlocked.
• Consider a system with five processes $P_0$ through $P_4$ and three resource types $A$, $B$, and $C$.
  • Resource type $A$ has seven instances,
  • Resource type $B$ has two instances,
  • Resource type $C$ has six instances.
• Suppose that, at time $T_0$, we have the following resource-allocation state:

  	Allocation	Request	Available
  $P_i$	$ABC$	$ABC$	$ABC$
  $P_0$	010	000	000
  $P_1$	200	202
  $P_2$	303	000
  $P_3$	211	100
  $P_4$	002	002

• If the algorithm is executed, it will be found that the sequence $< P_0, P_2, P_3, P_1, P_4 >$ results in $Finish[i] == true$ for all $i$.
• Suppose now that process $P_2$ makes one additional request for an instance of type $C$.
• Although we can reclaim the resources held by process $P_0$, the number of available resources is not sufficient to fulfill the requests of the other processes. Thus, a deadlock exists, consisting of processes $P_1, P_2, P_3$, and $P_4$.