The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+3 votes
564 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.

in Operating System by Veteran (100k points)
edited by | 564 views
0

Let me know if i m wrong...

4 Answers

+2 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}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 (418k points)
0 votes
Yes System is in Safe state .

 

Safe sequence is P0,P2,P1,P3,P4
by (303 points)
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
by (131 points)
0 votes
yes it is safe state and safe sequence is P0->P2->P1->P3->P4->
by (435 points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,092 questions
55,239 answers
190,755 comments
85,992 users