Let me know if i m wrong...

The Gateway to Computer Science Excellence

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

+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.$$

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.5k
- Others 1.5k
- Admissions 595
- Exam Queries 576
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 17

50,647 questions

56,497 answers

195,490 comments

100,815 users