#testseries

Question

Consider a system having ‘N ’ resources of the same type. ‘N’ resources are shared between 3 processes P₁ , P₂ and P₃ which have individual peak demand of 4, 6 and 8. The minimum value of ‘N’ to ensure that deadlock will never occur, if it is given the maximum requirement for combination of P₁ and P₃ is 9 are__________.

Comments

is it 14?

---

Given answer is 13.

---

video sol ans is 14 .. if you checked video

---

Which is the correct ans 13 or 14?

Answer 1

P1	P2	P3
4	6	8

Asked :
The minimum value of ‘N’ to ensure that deadlock will never occur.

Important Fact:

maximum requirement for combination of P₁ and P₃ is 9

Solution:
Ilustration about important fact is at any point of time both process does not require more than 9 resources
Analogy : For example you have two application(web) which are running simulatenously but ensuring that the bandwidth required by both of them will not exceed by some Value.

 Possible combination :
$P1:P3= $ $(4,5) (3,6) (2,7) (1,8)$

Thus to satisfy combination We need atmost 7 and one system backup resource.
Total Resource need =7+5+1(this one to ensure retrival once process completes execution)

Total=13

Comments

saxena0612 i am not getting this statement pls explain further

Thus to satisfy combination We need atmost 7 and one system backup resource.

---

From possible combination new requirement can be represented as :
P1:P2:P3=(4,6,5) (3,6,6) (2,6,7) (1,6,8). Now use Pigenhole Principle. 

---

php? @ saxena0612

---

P1:P3=(0,9) Combination is not included !

P1:P2:P3=(0,6,9) ,(4,6,5) (3,6,6) (2,6,7) (1,6,8)

Min resources=5+8+1 =14

if it is given the maximum requirement for combination of P₁ and P₃ is 9

  It is nowhere written in question that each process has to be allocated atleast one resource as you are assuming.

---

Problem statement : ‘N’ resources are shared between 3 processes P₁ , P₂ and P₃ which have individual peak demand of 4, 6 and 8.  You are assigning Resources to P3 more than what its peak demand.

---

I think you are right then !

 Possible combination :
P1:P3=(4,5) (3,6) (2,7) (1,8)

This will  then differ from problem to problem right ?

Depending upon what are the peak demands of processes !

---

Yes!

---

Peak demand of P1: $4$

Peak demand of P2: $6$

Peak demand of P3: $8$

P2 needs $6$ give it $5$ units

Let P1 needs $x$ units and P3 needs $y$ units, we have given $x+y<=9$

Using Pigeonhole principle, min resources so that deadlock never occurs

$5+(x-1)+(y-1)+1$

$4+x+y$

$4+9=13$

Hence 13 is correct answer

---

@saxena0612 are you talking about combination (1,8) and according to this 7 is the maximum requirement and allocating 7 to P1 and P3 and allocating 5 resources to P2 and at last +1.

So in total we have 7 + 5 + 1  = 13.

Is it what you want to say?

---

Accroding to this line

maximum requirement for combination of P₁ and P₃ is 9 :

it can be one of the instance.

---

But how deadlock is prevented by doing this.

Suppose u gave :  P1: 3  (waiting for 1 more resource )

                              P2: 4  (waiting for 2 more resource )

                              P3: 6 (waiting for 2 more resource)

This can cause a circular wait. All 13 resources have been allocated , how deadlock is prevented????

saxena0612  Ashwani Kumar 2 Rohit Gupta 8 

---

@ atul_21 Given that $P_1$ and $P_3$ max requirement at any point of time is no more than $9$

$\ \therefore$ allocating them $9$ would ensure that $OS$ can allocate remaining resources to $P_2$

---

I allocated P1 and P3, not more than 9 but still deadlock is possible .  

Clearly circular waiting is there, we will surely need 1 more resource .

Answer would be 14 definitely. Please check it once more

---

There is a difference b/w individual demand of resources and combined resource demand once you are combining $P_1$ and $P_3$ and evaluating according to their combined demand there is no need to take care of their individual demand of resource .
Now the example you gave ,$\{3,6,6\}$ i have already mentioned that case in answer and in this case once you are assigning the max combined resources there is no need to allocate more resources and therefore both processes would complete their execution and then $P_2$ will start as soon as resources are de allocated by them.

---

U must give then 9 resources to P1 and P2 combined. .  And to P2 : maximum demand -1  i.e. 5

Total 14 resources are required

---

"Minimum " is asked. allocating $9$ to both of them includes them one extra resource for preventing deadlock now consider this scenario.

1) $P_1$ and $P_3$ requested $9$ resources and OS allocated $9$ out of $13$ to both of them.Now this would suffice their computation and thus require no more resources.
2) If its the case $P_2$ requested for other resource more than $4$ then $OS$ will block it and resume its computation only after other two complete their execution because of short in resources.

Now $P_2$ can also request resource first in that case other one's will get block and resumed only after execution of $P_2$.

Note : Combined resource requirement is different from individual requirement because it hides the usage of resources by combined processes .

---

Can u show me how deadlock is not occuring when there are 13 resources only.

I have given u one possibility of deadlock, it means 13 is not possible. please check again.

---

@atul_21

@saxena0612

What I conclude from the above discussion is that: The line 

maximum requirement for combination of P₁ and P₃ is 9 

From this, we can allocate resources either P1 or P3 (but not both) less than or equal to 9. So, it is given that P1 and P3 peak demand is 4 and 8 respectively. So, at any point in time, any one of them gets exclusive control over the resources. Here exclusive means if one process gets x resources then another process gets 0 resources and vice versa, where x <= 9. So among P1 and P3, P3 have the peak demand of 8 which is greater than that of peak demand of P1 which is 4. So if we allocate exclusively 8 resources to P3 and 6 resources to P2, then Deadlock will not occur. Now they are asking for the minimum so allocate 7 resources to P3 and 5 resources to P1, and 1 resource to either P3 or P2, which is total is $7 + 5 + 1 = 13$. But note that during this allocation P1 gets none resources and P1 can execute after P3 release all resources.

And with those same 13 resources if processor chooses to execute P1 rather than P3, then it is still deadlock free because total we have 13 and collective requirement of P1 and P2 is 10, so clearly 10 <= 13 deadlock will never occur. 

So, the minimum system should have 13 resources to avoid any possibility of deadlock.

@saxena0612 , I think this is what you want to say. right?

---

@saxena what a nice explanation u provide and thanks rohit for asking this problem

---

Very good exp..

---

@Dheeraj Pant 13 or 14?

Answer 2

Let's focus this statement:- 

if it is given the maximum requirement for combination of P₁ and P₃ is 9

it means that at any time sum of maximum resources taken by P1& P3 is 9

now lets see all possiblties:-

P1:P3 :P2 =  (4,5)(3,6)(2,7)(1,8)

now for following cases consider the condition for no deadlock:- "allocate n-1 resource to evry process after then allocating one more resource guarantee of no_deadlock."

(4,5,6) =(4-1,5-1,6-1)+1=13

(3,6,6)=(2,5,5)+1=13

(2,7,6)=(1,6,5)+1=13

(1,8,6)=(0,7,5)+1=13

Answer 3

14

P1+P3=9 + (P2max-1)