GATE CSE 2014 Set 3 | Question: 31

Question

A system contains three programs and each requires three tape units for its operation. The minimum number of tape units which the system must have such that deadlocks never arise is _________.

Comments

Pigeonhole Principle :)

---

In worst case, all 3 programs may be allocated two-two resources each. So, currently 6 resource are allocated and system still in deadlock, if we have one more resource i.e total 7 resources then one program among three programs can take this 7th resource and will finish its execution and release all three allocated resources. Now, these free resources can be used by other two programs. So, with minimum 7 resource we never have deadlock.

---

Extension of @Chhotu comment – we have to distribute n(resources) among m(process) then according to the pigeonhole principle there will be at least one process that will have at least 3 resources. 

So ceil(n/m) = 3 where m is given as 3 then n will be 7. and obviously it’s minimum. cause if we would have anything above 7 instance of the resources then there won’t be any deadlock.

But the only thing is here that we are implicitly mentioning that in each process we are distributing max resources such that it will be in a deadlock.

Answer 1

As we know from the resource-request algorithm, which is a variant of Banker's algorithm-

Demand < Number of processes + Number of resources

now, the demand is 3 tape drives for each of the three programs, therefore 9.

let the minimum number of tapedrives or resources be R.

So,

9 < 3 + R

$\therefore$ R > 6. So minimum number of tapedrives should be 7.

Comments

@Gupta731

WHAT WILL BE IN CASE OF WHEN THREE POCESS  P1, P2 , P3 REQUIRED 4 , 2 , 5 TAPEDRIVERS.

WHAT WILL BE THE MUNIMUM NUMBER OF TAPE DRIVERS,DEADLOCK NEVER ARISE ??? 

---

Your doubt will be cleared if you try the process I explained on this question.

https://gateoverflow.in/1800/gate2014-1-31

see how easily you can solve it. Just calculate the need and available for the three processes and apply the above concept.

---

@Gupta731

Please solve according to your above concept ???

---

In that question the NEED on calculating comes out to be (8,4,2), (3,0,0), (1,2,2) for processes P0,P1,P2 respectively.

And the available is given (3,2,2)

According to resouce request algorithm:

Request <= Need

Request < Available

which only request 2 satisfies.

---

@Gupta731

I'm asking the answer of this question??

WHAT WILL BE IN CASE OF WHEN THREE POCESS  P1, P2 , P3 REQUIRED 4 , 2 , 5 TAPEDRIVERS.

WHAT WILL BE THE MUNIMUM NUMBER OF TAPE DRIVERS,DEADLOCK NEVER ARISE ??? 

---

Oh, in that case demand will be 4+2+5 = 11.

Demand < no of processes + no of resources

11 < 3 + R

R > 8

so minimum number of resources or tapedrives in that case would be 9.

---

Thanks.