in Operating System edited
13,440 views
22 votes
22 votes
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 _________.
in Operating System edited
13.4k views

3 Comments

Pigeonhole Principle :)

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

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.

0
0

5 Answers

28 votes
28 votes
Best answer
Up to, $6$ resources, there can be a case that all process have $2$ each and dead lock can occur. With $7$ resources, at least one process's need is satisfied and hence it must go ahead and finish and release all $3$ resources it held. So, no dead lock is possible.
selected by
by

2 Comments

What if we think this manner, let the number of resources be 3 i.e. 3 tape units are given. These can be allocated to any one process, which after execution will free those 3 tape units. Now these 3 can be given to the other waiting process which will free it after sometime and lastly, give it to 3rd waiting process. The only disadvantage of this is the processes may suffer from starvation. But can't minimum number of resources be 3?
0
0
I think they asked for possibility of deadlock. When we have 3 resources and we follow your way then there is no deadlock but if we give 1 resource to each program then deadlock occurs. But if we have at least 7 resources then there is no possibility of deadlock in any way.
0
0
35 votes
35 votes
For these type of problems in which every process is making same number of requests, use the formula    

$$n.(m-1)+1\leq r$$
where,
$n= \text{ no. of processes}$
$m=\text{resource requests made by processes}$
$r=\text{no. of  resources}$

So, in above problem we get $3.(3-1)+1\leq r \implies   r \geq 7$

 Minimum number of resource required to avoid deadlock is $7.$
9 votes
9 votes

Max number of resourses by which deadlock happen

P1=2

P2=2

P3=2

So Max=6 deadlock will occur

therefore minimum number of resourses by which deadlock not happen=6+1>=7

2 votes
2 votes
If 6 resources are there then it may be possible that all three process have 2 resources and waiting for 1 more resource. Therefore, all of them will have to wait indefinitely. If 7 resources are there, then atleast one must have 3 resources so deadlock can never occur.
Answer:

Related questions