26,983 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

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

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 🙂

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

I was wondering about the situation where P1 gets blocked for the first time. It should release resources at t = 7 which it would otherwise have done at t = 5, like you said. I think this should be the selected answer.
finally!! thanks man
This seems like the proper approach. Thank You!
Thanks a lot sir, that t=3 and t=5 part was all where the concept was.

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

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

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

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

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