5.6k 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.

 Process P1: $t=0$: requests $2$ units of $R2$ $t=1$: requests $1$ unit of $R3$ $t=3$: requests $2$ units of $R1$ $t=5$: releases $1$ unit of $R2$ and $1$ unit of $R1$. $t=7$: releases $1$ unit of $R3$ $t=8$: requests $2$ units of $R4$ $t=10$: Finishes Process P2: $t=0$: requests $2$ units of $R3$ $t=2$: requests $1$ unit of $R4$ $t=4$: requests $1$ unit of $R1$ $t=6$: releases $1$ unit of $R3$ $t=8$: Finishes Process P3: $t=0$: requests $1$ unit of $R4$ $t=2$: requests $2$ units of $R1$ $t=5$: releases $2$ units of $R1$ $t=7$: requests $1$ unit of $R2$ $t=8$: requests $1$ unit of $R3$ $t=9$: Finishes

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 | 5.6k 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.

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 with table below.

 $R1(3)$ $R2(2)$ $R3(3)$ $R4(2)$ $t=0$ $3$ $0$ $1$ $1$ $t=1$ $3$ $0$ $0$ $1$ $t=2$ $1$ $0$ $0$ $0$ block $P1$ $t=3$ $1$ $0$ $0$ $0$ $t=4$ $0$ $0$ $0$ $0$ UB $P1$ $t=5$ $1$ $1$ $0$ $0$ $t=6$ $1$ $1$ $1$ $0$ $t=7$ $1$ $0$ $2$ $0$ B $P1$ $t=8$ $2$ $0$ $2$ $1$ UB $P1$ $t=9$ $2$ $1$ $3$ $0$ $t=10$

there are no process in deadlock, hence (A) is right choice :)

edited by
+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!

+1
help after t=7 plsss
+6
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
+4
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
+1
@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 !
+2
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!
0
@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

Can be solved by making respective tables for each process at different time instances.
0
how explain ??

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

Here hold and wait voilated so there will not be deadlock
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.
answered ago by Active (3k points)