GATE CSE 2009 | Question: 30

Question

Consider a system with $4$ types of resources $R1$ ($3$ units), $R2$ ($2$ units), $R3$ ($3$ units), $R4$ ($2$ units). A non-preemptive resource allocation policy is used. At any given instance, a request is not entertained if it cannot be completely satisfied. Three processes $P1$, $P2$, $P3$ request the resources as follows if executed independently.

$$\begin{array}{|l|l|l|}\hline \textbf{Process P1:}  &  \textbf{Process P2:} & \textbf{Process P3:}  \\ \hline \text{$t=0$: requests $2$ units of $R2$} & \text{$t=0$: requests $2$ units of $R3$} & \text{$t=0$: requests $1$ unit of $R4$} \\ \text{$t=1$: requests $1$ unit of $R3$} & \text{$t=2$: requests $1$ unit of $R4$} & \text{$t=2$: requests $2$ units of $R1$}\\\text{$t=3$: requests $2$ units of $R1$} & \text{$t=4$: requests $1$ unit of $R1$} & \text{$t=5$: releases $2$ units of $R1$} \\ \text{$t=5$: releases $1$ unit of $R2$} & \text{$t=6$: releases $1$ unit of $R3$} & \text{$t=7$: requests $1$ unit of $R2$} \\ \text{and $1$ unit of $R1$}& \text{$t=8$: Finishes} & \text{$t=8$: requests $1$ unit of $R3$}\\
\text{$t=7$: releases $1$ unit of $R3$} && \text{$t=9$: Finishes} \\ \text{$t=8$: requests $2$ units of $R4$} & \text{} \\ \text{$t=10$: Finishes} & \text{}  \\ \hline \end{array}$$
Which one of the following statements is TRUE if all three processes run concurrently starting at time $t = 0$?

• A. All processes will finish without any deadlock

• B. Only $P1$ and $P2$ will be in deadlock

• C. Only $P1$ and $P3$ will be in deadlock

• D. All three processes will be in deadlock

Comments

INITIAL VALUE R1=3 AT T=2 P3 REQUESTED FOR 2 UNITS OF R1 SO NOW  ONLY 1 REMAINING

 

MORE DETAILED POINT AT T=3 P1 REQUESTED FOR R1  THAT TOO FOR 2 UNITS BUT AT THAT INSTANCE

ONLY 1 INSTANCE OF R1 IS AVAILABLE  SO P1 IS NOT ALLOCATED R1 AND P1 IS BLOCKED   WITH LETS SAY VALUE  -2

R1 VALUE =1 AS IT IS NOT ALLOCATED BUT P1 HAS -2 AS IT HAS REQUEST

 

********* AT T=4

AT T=4 P2 REQUESTED FOR R1 THAT TOO FOR  1 UNIT IT CAN BE SATISFIED NOW R1 =0 NO RESOURCES AVAILABLE OF TYPE R1

***********

 

AT T=5

WHAT HAPPENS AT SINGLE POINT  TIME VALUE 5  P3 RELEASED 2 UNITS OF R1 SO NOW 0+2 =2 NOW  WE

WILL CHECK WHETHER WE CAN PROCESS P1 YES P1 NEEDS ONLY  2 SO NOW P1 IS UNBLOCKED AND

ALLOCATED AND AGAIN AT THE SAME TIME POINT T=5 P1 RELEASED 1 UNIT OF R1  SO FINAL VALUE  OF R1 WOULD BE 1 AT T=5

---

This was indeed a very time consuming question

---

A small doubt: These are execution logs of the 3 processes (as timestamps are given). That means, this has already happened and none of them got stuck in deadlock as all 3 do complete.

Unless the logs are wrong (which should have been made explicit in the question), why should one believe anything else other than all 3 completed (that is option A is by definition the only answer)

Please clear this for me..

Answer 1

The answer is A.

Can be solved by making respective tables for each process at different time instances.

Comments

how explain ??

Answer 2

for those who face difficulty in table [detailed and step by step]

Comments

excellent explaination !

Answer 3

Here hold and wait voilated so there will not be deadlock

Answer 4

At=3,available R1=1,but P1 needs 2 R1.

        so,P1 is blocked.

At t=5, 3R1 are released,but previously blocked P1 takes 2 R1

         to unblock it.so available R1=1.

At t=8, P2 finishes,so it will releases what it grabbed.

           From the process P2 column in question we can

          see it releases 1 R1,1R3 and 1R4,but at the same time P1 wants

          2 R4 but available is just 1.so P1 is blocked.P3 wants 1 R3 ,it can 

          be fulfilled.

At t=9,P3 finishes ,it releases 1 R2,1 R3,1 R4.So now previously blocked P1

         can be unblocked

At t=10,All finishes.

 

So at last none of the processes are blocked.

So,All processes will finish without deadlock. 

Comments

Someone please give the solution on paper

---

@Bharti goyal   on paper