9.1k views

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$?

1. All processes will finish without any deadlock

2. Only $P1$ and $P2$ will be in deadlock

3. Only $P1$ and $P3$ will be in deadlock

4. All three processes will be in deadlock

edited | 9.1k views
0
Here process P1 will not get 2 units of R4 at the end of completion. which is the correct ans?
0
It means sir there are 2 type of resource allocation graph .1. preemptive resource alloction. 2 .Non preemptive resource allocation

I solved it like and got a wrong solution.

R1  R2  R3  R4(allocation)             R1  R2  R3   R4 (request)

P1  0      1    1      0                               3     2      1       2

P2  0      0     1    0                                1       0      2     1

P3  2     0     0     0                                 2      1       1    1

R1 ,R2,R3,R4 have  3,2,3,2 units of resources and 2,1,2,0 are allocated now available are 1,1,1,2 and with the help of 1,1,1,2 we can not fulfill requirment of any request.
0
Although P1 will get blocked at T3, got resource R1(2unit) at T5 and should release R1(1unit) at T7, but still, it does not lead to deadlock.
0
So A is right?
+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 🙂

by Boss (17.9k points)
edited
+4

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!

+2
help after t=7 plsss
+12
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.
+1
ohh.. I missed that concept .. thnq so mch
+7
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?
+1
help for t8 & t9
+2
@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 !
+3
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.

+1

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.

+2
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?
+1
yes (A) is correct answer! if deadlock was there, then system can't progress using any possibility!
+1
@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?
0

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 }$

+1
nice explanation @ sachin mittal sir
+1
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
+1
Sir can you please explain how can Process P1 release 1unit of R1 at t=5 if P1 has no instance of R1?
+1
How can i  Show the Table Because some Entries Value I do not know How can i ? Explain Elaborted..
+2

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.

+1
Oh ok.thanku @shubhgupta
0

"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.

0
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?
0

@  ma'am

A non-preemptive resource allocation policy is used.

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

+1

@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?

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.

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

0

@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.

0

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$

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

by Active (3.4k points)
0
I think you misunderstood, It is hold & wait.
–1

NO ,it violates hold and wait because it says request not entertained if it can't be completely satisfied meaning a process can't partially hold a resource and request for another one.

A process gets all all resources completely or none at all.hence it violates hold and wait  and hence no deadlock possible.

0
So A is right?
0

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

0
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

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

by Active (5.2k points)
edited by
+3
it took an eternity to reach the bottom 😊
0

lol @Arjun sir 😁

0

In the question it is given that--

At any given instance, a request is not entertained if it cannot be completely satisfied.

What does that mean? Is this means NO hold and wait..

0
One more question--

As per the given schedule P1 wants 2units of R1 at t=3 and releases 1 unit of R1 at t=5.

But P1 get blocked at t=3 and it will unblocked at t=5 and use the resource R1. At the same time (t=5) it have to release R1..how is it possible??

Edit:- events of p1 will be shifted accordingly.. due to delay in event of p1 at t=3, every next scheduled events will be delayed by 2 time units.
0

At any given instance, a request is not entertained if it cannot be completely satisfied.

At an instance if the number of instances requested by a process is not available then the process goes to blocked state
Eg-At t=T a process requests for N instances of some resource R but only N-1 instances of R are available, then the process will go to blocked state as the request for N instances isn't completely satisfied. The process will shift to ready state only when N number of instances of the resource are available

if the process has hold some resources previously and waiting for 1 instance of R to be free then it is hold and wait

0

As per the given schedule P1 wants 2units of R1 at t=3 and releases 1 unit of R1 at t=5.

But P1 get blocked at t=3 and it will unblocked at t=5 and use the resource R1. At the same time (t=5) it have to release R1..how is it possible??

At t=5 P3 has released 2 units of R1(which was the requirement of P1 at t=3). So when P3 releases two instances of R1, P1 will go to ready state on seeing R1=2.

I think your question is can a process release resource when it is in ready queue?

0

Ok..at t=5 P1 will go to ready state..

Then it will also have to release R1 at t=5..

But according to initial requirement P1 will have to take R1 in T3 then release R1 in T5..means it will take some time with R1(T3,T4).

How can it release R1 at T=5 when it get complete 2R1 in t=5 itself??

Is my doubt is clear? It is same as this  but i don't get satisfactory answer:/

0

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

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

Can be solved by making respective tables for each process at different time instances.
by Boss (19.9k points)
+1
how explain ??
Here hold and wait voilated so there will not be deadlock
by (457 points)

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$

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.

by Boss (27.4k points)
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.
by Active (4.7k points)
0
Someone please give the solution on paper