603 views

A number of processes could be in a deadlock state if none of them can execute due to non-availability of sufficient resources. Let $P_i, 0 \leq i \leq 4$ represent five processes and let there be four resources types $r_j, 0 \leq j \leq 3$. Suppose the following data structures have been used.

Available: A vector of length $4$ such that if Available $[i]=k$, there are k instances of resource type $r_j$ available in the system.

Allocation. A $5 \times 4$ matrix defining the number of each type currently allocated to each process. If Allocation $[i,j]=k$ then process $p_i$ is currently allocated $k$ instances of resource type $r_j$.

Max. A $5 \times 4$ matrix indicating the maximum resource need of each process. If $Max[i,j]=k$ then process $p_i$, may need a maximum of $k$ instances of resource type $r_j$ in order to complete the task.

Assume that system allocated resources only when it does not lead into an unsafe state such that resource requirements in future never cause a deadlock state. Now consider the following snapshot of the system.$$\overset{\Large{\text{Allocation}}}{\begin{array}{llll} & r_{0} & r_{1} & r_{2} & r_{3} \\ p_{0} & 0 & 0 & 1 & 2 \\ p_{1} & 1 & 0 & 0 & 0 \\ p_{2} & 1 & 3 & 5 & 4 \\ p_{3} & 0 & 6 & 3 & 2 \\ p_{4} & 0 & 0 & 1 & 4 \\ \end{array}}\quad \qquad \overset{\Large{\text{Max}}}{\begin{array}{llll} r_{0} & r_{1} & r_{2} & r_{3} \\ 0 & 0 & 1 & 2 \\ 1 & 7 & 5 & 0 \\ 2 & 3 & 5 & 6 \\ 0 & 6 & 5 & 2 \\ 0 & 6 & 5 & 6 \\ \end{array}} \qquad \quad \overset{\Large{\text{Available}}}{\begin{array}{llll} r_{0} & r_{1} & r_{2} & r_{3} \\ 1 & 5 & 2 & 0 \\ \end{array}}$$Is the system currently in a safe state? If yes, explain why.

edited | 603 views
0 Let me know if i m wrong...

Here, we are asked to "Avoid Deadlock" and Bankers Algorithm is the algorithm for this.

The crux of the algorithm is to allocate resources to a process only if there exist a safe sequence after the allocation. i.e., after allocating the requested resources there exist a sequence of execution of the processes such that deadlock would not happen. There can be multiple safe sequences but we need to get any one of them to say that a state is safe.

Now coming to the given question, first lets make the $\text{NEED}$ matrix which shows the future need of all the processes and can be obtained by $\text{Max} - \text{Allocation}.$$\overset{\Large{\text{Max}}}{\begin{array}{llll} &r_{0} & r_{1} & r_{2} & r_{3} \\ p_0& 0 & 0 & 1 & 2 \\ p_1& 1 & 7 & 5 & 0 \\ p_2&2 & 3 & 5 & 6 \\ p_3& 0 & 6 & 5 & 2 \\ p_4& 0 & 6 & 5 & 6 \\ \end{array}} - \overset{\Large{\text{Allocation}}}{\begin{array}{llll} & r_{0} & r_{1} & r_{2} & r_{3} \\ p_{0} & 0 & 0 & 1 & 2 \\ p_{1} & 1 & 0 & 0 & 0 \\ p_{2} & 1 & 3 & 5 & 4 \\ p_{3} & 0 & 6 & 3 & 2 \\ p_{4} & 0 & 0 & 1 & 4 \\ \end{array}} = \overset{\Large{\text{Need}}}{\begin{array}{llll} &r_{0} & r_{1} & r_{2} & r_{3} \\ p_0& 0 & 0 & 0 & 0 \\ p_1& 0 & 7 & 5 & 0 \\ p_2&1 & 0 & 0 & 2 \\ p_3& 0 & 0 & 2 & 0 \\ p_4& 0 & 6 & 4 & 2 \\ \end{array}}.$$ Since$P_0$does not require any more resource we can finish this first releasing$1$instance of$r_2$and$2$instances of$r_3.$Thus our$\text{Available}$vector becomes $$\begin{bmatrix}1&5&2&0\end{bmatrix}+\begin{bmatrix}0&0&1&2\end{bmatrix} =\begin{bmatrix}1&5&3&2\end{bmatrix}.$$ Now, either$p_2$or$p_3$can finish as both their requirements are not greater than the$\text{Available}$vector. Say,$p_2$finishes. It releases$\begin{bmatrix}2&3&5&6\end{bmatrix}$and our$\text{Available}$becomes $$\begin{bmatrix}1&5&3&2\end{bmatrix}+\begin{bmatrix}2&3&5&6\end{bmatrix} =\begin{bmatrix}3&8&8&8\end{bmatrix}.$$ Now, any of$p_1,p_3,p_4\$ can finish and so we do not need to proceed further to determine that the state is safe. One of the possible safe sequence is $$p_0-p_2-p_1-p_3-p_4.$$

by Veteran (425k points)
0
@arjun when P2 finishes it releases [1,3,5,4] and available becomes [2,8,8,6] . you have done mistake, instead of adding allocated resources you added max allocated resources. check it or tell me if i am wrong.
Yes System is in Safe state .

Safe sequence is P0,P2,P1,P3,P4
by (303 points)
Need Matrix:-

0   0   0   0

0   7   5   0

1   0   0   2

0   0   2   0

0   6   4   2

P0---->available 1   5   3   2

P2---->available 2   8   8   6

P1---->P3---->P4
by (141 points)
yes it is safe state and safe sequence is P0->P2->P1->P3->P4->
by (433 points)