edited by
16,515 views
45 votes
45 votes

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. $\displaystyle{\sum_{i=1}^n} \: s_i  < (m+n)$

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

edited by

6 Answers

Best answer
124 votes
124 votes
To ensure deadlock never happens allocate resources to each process in following manner:
Worst Case Allocation (maximum resources in use without any completion) will be $(\text{max requirement} -1)$ allocations for each process. i.e., $s_i-1$ for each $i$
Now, if $\displaystyle{\sum_{i=1}^{n}{(s_i - 1)}} \leq m$ dead lock can occur if $m$ resources are split equally among the $n$ processes and all of them will be requiring one more resource instance for completion.

Now, if we add just one more resource, one of the process can complete, and that will release the resources and this will eventually result in the completion of all the processes and deadlock can be avoided. i.e., to avoid deadlock

$\displaystyle{\sum_{i=1}^{n}{(s_i - 1)}} + 1 \leq m$

$\implies \displaystyle{\sum_{i=1}^{n}{s_i }} - n + 1 \leq m$

$\implies \displaystyle{\sum_{i=1}^{n}{s_i }}  < (m + n).$

Correct Answer: $C$
edited by
11 votes
11 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.

9 votes
9 votes
If we allocate one resources less to each process

(s1-1) + (s2-1) + (s3-1) + .............. (sn-1)  <  m

s1 + s2 + s3 +......sn -n  <  m

s1+s2....sn < m+n
edited by
4 votes
4 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 

Answer:

Related questions