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

At $t = 3$, the process $P1$ has to wait because available $R1=1$, but $P1$ needs $2 \ R1$. so $P1$ is blocked.

Similarly, at various times what is happening can be analyzed by the table below.$$\small \begin{array}{l|l|l|l|l|l} \text{}  &  \text{} & \text{R1(3)} & \text{R2(2)} & \text{R3(3)} & \text{R4(2)} \\\hline  \text{} & \text{t=0} & \text{3} & \text{0} & \text{1} & \text{1}\\ 
\text{} & \text{t=1} & \text{3} & \text{0} & \text{0} & \text{1} \\  
\text{} & \text{t=2} & \text{1} & \text{0} & \text{0} & \text{0}\\ \ 
\text{Block P1} & \text{t=3} & \text{1} & \text{0} & \text{0} & \text{0}\\
\text{} & \text{t=4} & \text{0} & \text{0} & \text{0} & \text{0}\\ 
\text{Unblock P1} & \text{t=5} & \text{1} & \text{1} & \text{0} & \text{0} \\
\text{} & \text{t=6} & \text{1} & \text{1} & \text{1} & \text{0}\\ 
\text{} & \text{t=7} & \text{1} & \text{0} & \text{2} & \text{0}\\ 
\text{Block P1} & \text{t=8} & \text{2} & \text{0} & \text{2} & \text{1}\\ 
\text{Unblock P1} & \text{t=9} & \text{2} & \text{1} & \text{3} & \text{0}\\ 
\text{} & \text{t=10} & \text{} & \text{} & \text{} & \text{} \\\hline \end{array}$$There are no processes in deadlock, hence (A) is right choice 🙂

Comments

In the question it is given "A non-preemptive resource allocation policy is used". So shouldn't process 1 complete before process 2 starts?

Thanks!

---

help after t=7 plsss

---

At t=7

R1=1, R2=0, R3=2, R4=0

Now at the time t=8 P2 finishes.

Means all the resouses that P2 holds are releases and get ready for allow other requests.

So, which process P2 going to release?

those which it is holding

i.e. 2 units of R3 , 1 unit of R4 and 1 unit of R1.

---

ohh.. I missed that concept .. thnq so mch

---

At T=5,  P1 has released 1 instance of R1 and 1 instance of R2 as shown in your table.

In ques also P1 does the same at T=5 but only when it has requested 2 instances of R1 at T=3. It means it releases the resources after 2 time units of making the request. But in your solution it is getting the resources and releasing them at the same time. Is this possible?

---

help for t8 & t9

---

@sandeep

In the year 2009 there is NO Official Answer key released , so what you say official that may be provided by some books or come coaching centres !

---

At t=5, how is it possible for P1 to capture the resources.At t=5 the resources are released by the P3,and then P1 may capture during same time slot or may be in next time slot.As nothing is mentioned so we are free to choose.But then P1 holds the resources for 2 time slots and then release them after 2 time slots.In the given answer P1 is doing the work of 2 time slots in one time slots.How is it possible to capture resources at t=5 and then realse also in same slot whihc in fact should happen at t=7.

@Bikram sir,Arjun sir.Please help here

---

@ rahul sharma 5   and @ Rajendra Dangwal

As nothing is mentioned so we are free to choose 

Yes, we assume that resource release and capture done at same time slot .

And here in this qstn , No Hold and Wait condition .. so P1 hold some resorce and wait for some is not possible so no deadlock.

---

Bikram Sir, I couldn't understand how are we ensuring that there is no hold and wait condition possible?

It is given that "At any given instance, a request is not entertained if it cannot be completely satisfied" ... doesn't it mean that , that particular request is denied? It is not said that the process is getting blocked. How can we assume that?

---

yes (A) is correct answer! if deadlock was there, then system can't progress using any possibility!

---

@Bikram Sir, P1 uses R1 for two seconds and then release at t5. But, at t3, it is getting blocked. And it gets the required resources at t5...so shouldn't the entire execution of P1 be moved ahead by 2 seconds? That is, instead of releasing the resources at t5, shouldn't it release at t7?

---

For those who have doubt that how would $P_1$ get $2$ units of resource $R_4 \Rightarrow$

$\text{ At t=8 and t=9, P1 and P2 will be completed and hence will release R4 automatically}$

$\text{i.e 1 unit of R4 will be released from P2 and 1 unit from P2 and hence there is no deadlock }$

---

nice explanation @ sachin mittal sir

---

at t=2 p2 is requesting 1R4 that requirnment is not full fill till end so how p2 can finish its execution before fullfilling his requirnment

---

Sir can you please explain how can Process P1 release 1unit of R1 at t=5 if P1 has no instance of R1?

---

How can i  Show the Table Because some Entries Value I do not know How can i ? Explain Elaborted..

---

@ Bhagyashree Mukherje, because at t=5 p3 is also releasing 2 units of r1. by which p1 can up and release one unit of r1 after acquiring 2 unit.

 

@Vijay Dulam, at each time what is happening with resources we are just writing those in table and each time information is availabel in question.

---

Oh ok.thanku @shubhgupta

---

@Adwaith S

 "Non-preemptive resource allocation policy is used". It means processes can be preempted but resources cannot. And here resources are not being preempted at any instance of time.

---

And here in this qstn , No Hold and Wait condition .. so P1 hold some resorce and wait for some is not possible so no deadlock

how? why not hold and wait?

---

 @ sushmita ma'am 

 A non-preemptive resource allocation policy is used.

 i think this line make it not use hold and wait.

---

@Shubhgupta

"because at t=5, p3 is also releasing 2 units of R1. by which p1 can get up and release one unit of r1 after acquiring 2 unit."

So, $P1$ is just taking one instance of $R1$ by one hand and throwing immediately by other hand?? Without making any use of it? 

@Sachin Mittal 1, 

According to question(given in the question), the sequence of resource request/release which is given for $P1$ is the sequence $P1$ follows if it executes independently. 

So,  if only P1 was running in the system independently, then at $t=3,$ it would request for $R1$ and After making some use of it for 2 units of time, at $t=5$ it would release it. 

@Sachin Mittal 1 , @Arjun

Refer my answer here and let me know if I've mistaken somewhere : https://gateoverflow.in/1316/gate2009-30?show=327223#a327223

---

@srestha maa'm

... i read ur previous comment ....which is paste in below...

my doubt :   and the time t = 8  P2 finishes .... its right

 so we release all the resources that holds P2.....  i.e   1 unit of R4 , 1 unit of R1,   1 unit of R3  ( because 

at t = 6  :   1 unit of R3  is  released)   but u mention P2 release  : 2 unit of R3 .... plz explain

 

previous discussion (paste):

At t=7

R1=1, R2=0, R3=2, R4=0

Now at the time t=8 P2 finishes.

Means all the resouses that P2 holds are releases and get ready for allow other requests.

So, which process P2 going to release?

those which it is holding

i.e. 2 units of R3 , 1 unit of R4 and 1 unit of R1.

---

Please someone confirm-

Table (for remaining R1,R2,R3,R4) after t=3 will be like--

$t=4\;\rightarrow 0000$

$t=5\;\rightarrow 0000$

$t=6\;\rightarrow 0010$

$t=7\;\rightarrow 1010$

$t=8\;\rightarrow 2011$

$t=9\;\rightarrow 2132$

$t=10\rightarrow 2130$

$t=12\rightarrow 3232$

---

what is the significance of this line “A non-preemptive resource allocation policy is used”...

---

@Abhineet Singh it means that when you fall short of resources you cannot preeempt and process and allocate the required resources to the process that was falling short.

Answer 2

Answer A is correct but the method by which people (in other answers on this question) have gotten A is Not correct.

---

People are NOT even considering this statement in the question : "Three processes P1, P2, P3 request the resources as follows if executed independently."

In question it is given that If Each Process executed Independently (independent of other processes) then those processes will execute and request resources as given by the given sequence for each process.  

What this means is that : Say In the system, Only P1 is executing, then P1 will do these things : At $t=0,$ it will request 2 instances of resource $R2$ ;  At $t=1,$ it will request 1 instances of resource $R3$ ; At $t=3,$ it will request 2 instances of resource $R1$ ; then After using $R1$ for $two$ time units and after using $R2$ for $five$ units of time, At $t=5,$ it will release 1 instance of resource $R1$ and 1 instance of resource $R2.$ And so on.... 

Hence, according to question, The Given sequence of resource request/release for a process is followed by that process $if \,\, it \,\, executed \,\, independently.$ 

So, If $P1$ acquires two instances of  resource $R1$ at time $t$ then It will release one instance of $R1$ at time $t+2 $ After using $R1$ for two time units.  

Now, we can proceed to solve the question :

---

Since at any instance of time, three processes are concurrently running, We can assume that there are three processors ($C1,C2,C3$) in the system and Process $Pi$ is executing on processor/core $Ci.$ (This assumption is only for making things easy to understand and It is without loss of generality so even if one doesn't want to assume it then also fine, answer and method won't change .)

---

In the beginning, $R1 = 3, R2 = 2, R3 = 3, R4 = 2$

Now, Processes are executing (their given sequence of resource/relases) concurrently.

At $t=0 :$ 

$P1,P2,P3$ will without any problem acquire what they requested, so after $t=0$, we have  $R1 = 3, R2 = 0, R3 = 1, R4 = 1$

At $t=1 :$  

$P1$ will acquire what it requested, so after $t=1$, we have  $R1 = 3, R2 = 0, R3 = 0, R4 = 1$

At $t=2 :$ 

$P2,P3$ will without any problem acquire what they requested, so after $t=2$, we have  $R1 = 1, R2 = 0, R3 = 0, R4 = 0$

At $t=3 :$ 

$P1$ requests two units of $R1$ But we only have one unit of $R1$ free in the system, so this request can't be satisfied completely, so $P1$ will have to wait and it will be blocked when two instances of $R1$ becomes available. 

It is worth noting that whenever $P1$ will acquires these two units of $R1$, It will use them for 2 units of time and then after that it will release one instance of $R1.$

So, After $t=3$, we have  $R1 = 1, R2 = 0, R3 = 0, R4 = 0$

At $t=4 :$ 

$P2$ will without any problem acquire what it requested, so after $t=4$, we have  $R1 = 0, R2 = 0, R3 = 0, R4 = 0$

At $t=5 :$ 

$P3$ will put an instruction to release two units of $R1$, at this moment, system will assign these two units of $R1$ to $P1$ and wake it up. So after $t=5$, we have  $R1 = 0, R2 = 0, R3 = 0, R4 = 0$

Now, Since $P1$ has gotten two units of $R1$ at time $t=5,$ It will execute its next instruction of resource request/release at time $t=7$ (after using $R1$ for two units of time as It would have done if it executed independently because that is how the program of the process has been written)   So, whole code/sequence of resource request/release of process $P1$ has shifted/delayed by 2 units of time. So, at this moment, we must consider that what it was doing at $t=5$ if it was executing independently, now it will do that at $t=7$ when executing concurrently. 

At $t=6 :$ 

$P2$ releases one unit of $R3$, so after $t=6$, we have  $R1 = 0, R2 = 0, R3 = 1, R4 = 0$

At $t=7 :$ 

$P1$ release one unit of $R1,R2$, And $P3$ requests one unit of $R2$ which it will be granted since $P1$ has released one unit of $R2$ (No matter P1 runs first(slightly..in nano-seconds maybe) or P3 runs first... P3 will get what it requested after t=7.  If P1 releases R2 slightly before P3 requests then P3 will get it.. But if P3 requests slightly before P1 releases then P3 will block for some fraction of time unit and then p1 will put an instruction to release R2 so system will assign it to blocked P3 and wake it up )

So after $t=7$, we have  $R1 = 1, R2 = 0, R3 = 1, R4 = 0$

At $t=8 :$ 

$P3$ will without any problem acquire what it requested,  and $P2$ will finish so it will release all its acquired resources, So after $t=8$, we have  $R1 = 2, R2 = 0, R3 = 1, R4 = 1$

At $t=9 :$ 

$P3$ will finish and $P1$ will release 1 unit of $R3$, So after $t=9$, we have  $R1 = 2, R2 = 1, R3 = 3, R4 = 2$

At $t=10 :$ 

$P1$ will without any problem acquire what it requested, so after $t=10$, we have  $R1 = 2, R2 = 1, R3 = 3, R4 = 0$

At $t=11 :$ 

Something internal happening of P1.

At $t=12 :$ 

$P1$ will finish, so after $t=12$, we have  $R1 = 3, R2 = 2, R3 = 3, R4 = 2$

---

Hence, All Processes will execute/finish without any deadlock. Answer is A.

---

PS :

1. Many are giving argument that  "No hold and wait so there will not be deadlock" ..This is wrong. Nowhere in the question it is mentioned that Hold and wait isn't there. Some students are wrongly inferring that No Hold and wait from this line in the question "At any given instance, a request is not entertained if it cannot be completely satisfied." This statement only wants to say that If process $P1$ requested 2 instances of $R1$ at any point of time and say only one instance is available then the system won't assign one instance that is free to $P1$ because Unless the request is $completely$ satisfies, it won't be entertained. 

Hold and wait condition says "A process must be holding at least one resource and waiting to acquire additional resources that are currently being held by other processes." Clearly there is Hold and wait in this system because When $P1$ requested 2 units of $R1,$ one instance of $R1$ was being held by $P3$ so $P1$ was waited for $R1$ to become available. 

2. If you disagree with any part in this answer, let me know and we'll discuss that in comments.

Comments

Thanks a lot sir, that t=3 and t=5 part was all where the concept was.

---

Great Explanation

---

Small correction sir , when P1 requested 2 units of R1, one instance of R1 was being held by R3. Instead of 1 it must be 2 sir .

Answer 3

using resource allocation graph

P1's request isn't fulfilled. P1 goes to blocked state for R1=1. at this point P1 wont release any resources as well. P1 can continue only when 1 instance of R1 is available

P2's request isn't fulfilled so it can't proceed. P2 goes to blocked state. P2 waits for R1=1
at T=4, both P1 and P2 are in blocked/wait state

P3 releases 2 instances of R1. Both P1 ad P2 were waiting for R1=1 and R1=1. Now both the processes can be allocated resources. P1 and P2 both goes to ready state

When P1 goes to ready state, it'll simultaneously release one instance of R1 and 1 instance of R2

P2 finishes and releases its resources. P3's request is fulfilled. P1 goes to blocked/wait state for R4=1

P3 finishes and releases the resources it held. Now P1 will come out of blocked state(P1 was waiting for R4=1)

P1 continues execution

at T=10, P1 finishes execution and releases all the resources it held

R1=3, R2=2, R3=3, R4=2
the system is in safe state and there is no deadlock

sequence of execution of process is P2->P3->P1

Comments

so the question boils down to can allocation and release of resources happen in the same cycle

I can't answer this

@Arjun sir please help

---

Answer by Deepak poonia(Dee) sir clears that doubt..

---

@aditi19  Thankyou for this answer, this made many things clear 😊

Answer 4

"At any given instance, a request is not entertained if it cannot be completely satisfied", means no wait. so, deadlock isn't possible.

Comments

So A is right?

---

@Harshitkmr brother i am not understanding the solution mentioned above means 1st solution what is happening at t=5

---

p1 is blocked at t=3(coz it needs 2 units of R1)

at t=5  P3 releases 2 units of R1 and P1 releases 1 unit of R1 and 1 unit of R2.

so   it changes to                R1   R2   R3     R4

at t=5                                   3        1     0       0

so now P1 is unblocked  as it can get 2 unit of R1. and changes to   

                                      R1   R2   R3     R4

at t=5                               1      1     0       0