recategorized by
2,970 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.

recategorized by

4 Answers

Best answer
5 votes
5 votes

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
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

Related questions

7 votes
7 votes
4 answers
1
go_editor asked Dec 18, 2016
2,784 views
State any undesirable characteristic of the following criteria for measuring performance of an operating system:Waiting time
9 votes
9 votes
5 answers
2
go_editor asked Dec 18, 2016
4,270 views
State any undesirable characteristic of the following criteria for measuring performance of an operating system:Turn around time
14 votes
14 votes
3 answers
3
go_editor asked Dec 19, 2016
4,026 views
Given below is solution for the critical section problem of two processes $P_0$ and $P_1$ sharing the following variables:var flag :array [0..1] of boolean; (initially fa...
2 votes
2 votes
0 answers
4
go_editor asked Dec 18, 2016
662 views
A modern day machine typically has an atomic TEST AND SET instruction. Why?