in Operating System recategorized by
2,943 views
7 votes
7 votes

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.

in Operating System recategorized by
2.9k views

3 Comments

Let me know if i m wrong...

1
1

@akash.dinkar12 Just a small mistake: Last row of allocated resources should be 3 14 12 12. Doesn't change the answer though. 

1
1
I think the best answer selected is wrong!
0
0

4 Answers

5 votes
5 votes
Best answer

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}1&3&5&4\end{bmatrix} =\begin{bmatrix}2&8&8&6\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.$$

edited by
by

3 Comments

@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.
3
3

Yes, you are right. By mistake sir has added Max row instead of Allocation row for $P_{2}$

3
3
Fixed now..
0
0
0 votes
0 votes
Yes System is in Safe state .

 

Safe sequence is P0,P2,P1,P3,P4
0 votes
0 votes
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
0 votes
0 votes
yes it is safe state and safe sequence is P0->P2->P1->P3->P4->

Related questions