The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+16 votes
1.9k views

Suppose $n$ processes, $P_1, \dots P_n$ share $m$ identical resource units, which can be reserved and released one at a time. The maximum resource requirement of process $P_i$ is $s_i$, where $s_i > 0$. Which one of the following is a sufficient condition for ensuring that deadlock does not occur?

  1. $\forall i,\: s_i, < m$

  2. $\forall i, \:s_i <n$

  3. $\Sigma_{i=1}^n \: s_i  < (m+n)$

  4. $\Sigma_{i=1}^n \: s_i  < (m \times n)$

asked in Operating System by Veteran (69k points)
retagged by | 1.9k views

Pigeonhole Principle :)

how pigeonhole principal ??

3 Answers

+52 votes
Best answer

to ensure deadlock never happens allocate resource to each process in following manner..
allocation will be (max requirement -1) i.e. Si-1 for each i..
now (S- 1) + 1( to prevent deadlock) <= m( available resources)
∑ S- ∑1 + 1 <= m
Si - n + 1 <= m
Si + 1 <= m + n
Si < m + n

answered by Veteran (53.4k points)
edited by
is the answer is a?
nope
den?
Answer is option c
why (max requirement -1) ? please elaborate
because if every process holds one resource less than it really requires, and one extra resource is present, any of the process can take that resource, finish itself and release its resources which can further satisfy the need of other processes.
meaning of reserved and released one at a time
+5 votes

There are N processes and they share M resources.

Sum of the requirement of all processes will be " Sum of all Si" ie ∑i=1nSi∑i=1nSi . Now If you dont want the deadlock to occur,then you should share M resources such that each process will get 1 less than their maximum requirement and then add 1 resource to any one of the processes. This way you can avoid deadlock.

So the expression should be like this : ∑i=1nSi∑i=1nSi- N+ 1= M meaning we are summing all requirements, then subtracting N,that is 1 resource from each of the processes' requirement, so that all Processes will be waiting. then adding 1, that is allocating 1 resource to any 1 of the processes so that it can complete its execution and leave its resources so that other process can use. This should be equal to M.

Now if you move N to RHS then expression will be like ∑i=1nSi∑i=1nSi-1 = M+N.

If clearly, now if we ignore 1, then the expression wil be reduced to ∑i=1nSi∑i=1nSi < M+N. Right.

answered by Active (1.5k points)
Thanks for this nice explanation :)

And just to confirm, in this line

"So the expression should be like this : ∑i=1nSi∑i=1nSi- N+ 1= M" --> shouldn't LHS<=RHS instead of LHS=RHS ?
+3 votes

maximum number of resourses by which deadlock never happen in our system

m> ∑ Si -n   ;;;; where i>=1 and i<=n 

So minimum number of resourses by which we can conclude that deadlock never happen

m> ∑ Si -n +1  ;;;; where i>=1 and i<=n 

m+n >  ∑ Si +1  ;;;; where i>=1 and i<=n 

answered by Boss (8.4k points)

maximum number of resourses by which deadlock never happen in our system

m> ∑ Si -n   ;;;; where i>=1 and i<=n 

 

can you please explain the above line 

Answer:

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

33,593 questions
40,128 answers
114,021 comments
38,389 users