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|lll|}\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

---

Use Banker Algorithms 

Total available resources = (5,5,5)

Total allocated resources = (5 ,4 , 3) // for calculating this add all the the value of "Alloc" table correspondingly x,y,z .

:- Current Available resources = (Total available resources) - (Total current allocated resources)  after that apply banker algorithms

 

---

The question is NOT based on Banker's Algorithm, because then we would have given Max and Need Matrices as apriori information. 

This is Deadlock Detection with "Several Instances of a Resource Type". Here only Request Matrix is required.

Ref: http://www.cs.uic.edu/~jbell/CourseNotes/OperatingSystems/7_Deadlocks.html

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

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.

---

Here important point to note is,

Request = Need     .....through considering this we are getting our answer :)

Answer 2

Given:

🔹 Total Resources = [X Y Z] = [5 5 5]

🔹 Total Allocation = [X Y Z] = [5 4 3]

🔹 Available Resources = Total - Allocated

          = [5 5 5] - [5 4 3]

          = [0 1 2]

✅ Safe Sequence Check (Banker's Algorithm):

🔹 Step 1:

P1's request ≤ Available → [0 1 2] ≤ [0 1 2] → ✅

P1 executes → releases [2 0 1]

🔸 New Available = [0 1 2] + [2 0 1] = [2 1 3]

🔹 Step 2:

P0's request ≤ Available → [1 0 3] ≤ [2 1 3] → ✅

P0 executes → releases [1 2 1]

🔸 New Available = [2 1 3] + [1 2 1] = [3 3 4]

🔹 Step 3:

P2's request ≤ Available → [1 2 0] ≤ [3 3 4] → ✅

P2 executes → releases [2 2 1]

🔸 Final Available = [3 3 4] + [2 2 1] = [5 5 5]

✅ Conclusion:

🔸 Safe Sequence: P1 → P0 → P2

🔸 All processes can complete.

🔸 System is in a Safe State.

🔸 P2 executes last.

Answer 3

Here is the answer.

 

Comments

nice explanation bro

Answer 4

Here there are two safe sequence possible

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

Comments

P1 -> P2 -> P0 is not possible because after P1 finishes we will have following resources available
X = 2, Y=1, Z=3

For P2 to execute we need 2 instances of Y but only 1 instance of Y is availble hence only P0 can execute.

Therefore only correct sequence is P1 -> P0 -> P2