GATE CSE 2007 | Question: 57

Question

A single processor system has three resource types $X, Y$ and $Z$, which are shared by three processes. There are $5$ units of each resource type. Consider the following scenario, where the column alloc denotes the number of units of each resource type allocated to each process, and the column request denotes the number of units of each resource type requested by a process in order to complete execution. Which of these processes will finish LAST?

$$\begin{array}{|l|lll|ll|}\hline &\text{}  \rlap{\textbf{alloc}}  &&&\rlap{  \textbf{request}}  \\\hline  &\text{X} & \text{Y} & \text{Z}  &\text{X} & \text{Y} & \text{Z}  \\\hline  \textbf{P0} & \text{1} & \text{2} & \text{1}& \text{1} & \text{0} & \text{3}  \\\hline  \textbf{P1} & \text{2} & \text{0} & \text{1} & \text{0} & \text{1} & \text{2} \\\hline \textbf{P2} & \text{2} & \text{2} & \text{1} & \text{1} & \text{2} & \text{0} \\\hline \end{array}$$

• A. $P0$
• B. $P1$
• C. $P2$
• D. None of the above, since the system is in a deadlock

Comments

Banker's Algorithm

Answer 1

The answer is (C).

$$\overset{\text{Available Resources}}{\begin{array}{|l|l|l||}\hline
\text{X} & \text{Y} & \text{Z} \\\hline  \text{0} & \text{1} & \text{2}
\\\hline\end{array}}$$ Now, $P1$ will execute first, As it meets the needs. After completion, The available resources are updated.

$$\qquad  \overset{\text{Updated Available Resources}}{\begin{array}{|l|l|l||}\hline
\text{X} & \text{Y} & \text{Z} \\\hline  \text{2} & \text{1} & \text{3}
\\\hline\end{array}}$$
Now $P0$ will complete the execution, as it meets the needs.

After completion of $P0$ the table is updated and then $P2$ completes the execution.

Thus $P2$ completes the execution in the last.

Comments

please explain me how you get "Available Resources" , even if it is not mention in the question  or may be i am not able to fetch that particular point so please help me ...@gate_keeda

---

Calculate the  total allocated resources.             5  instances of X are allocated                       4 of Y and 3  of Z.

So the available or left resources are      x=5-5=0 :::: y=5-4=1::::z=5-3=2.

Hope it helps.

---

got it thanks ...

---

Plzz explain how p1 will execute first.....as the need of p1 is 022????

---

safe sequence will not be uniqe then how can we conclude that p2 is at last.

---

@ Shubham Aggarwal for this particular question what is other sequence other than P1 -> P0 -> P2 ?

---

In this particular question, only one safe sequence is possible.

$P_{1}\rightarrow P_{0}\rightarrow P_{2}$

---

Why P0 not executed first like available resources is 0,1,2 and allocated to P0 is 1,2,1 . If we allocate 0,1,2 to P0 then it get 1,3,3 which satisfy the request made by P0 which is 1,0,3 .

---

Request is not maximum need, It's current need. If it would have been maximum need then Y alloc to P0 never had been 2.

Answer 2

Here there are two safe sequence possible

P1--> P0 -->P2 and P1-->P2-->P0 hence both option A and C are correct