Log In
28 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)$

in Operating System
edited by

Pigeonhole Principle :)

how pigeonhole principal ??
I see "Pigeonhole Principle" with a smiley in a lot of questions. There are a lot of questions and there will be someone with just a comment "Pigeonhole Principle :)".

I want to ask those people, what is with this comment, okay it's related with pigeonhole principle but why just tell us the name. why don't explain the complete relation with pigeonhole principle. that would be really nice.

4 Answers

89 votes
Best answer
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
is the answer is a?
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
Can someone tell me when to take <= and >? I'm confused as to which variable needs to be taken as constant.
Didn't get your question?

Is it safe to say that option A is a NECESSARY condition but not a SUFFICIENT condition to avoid deadlock? @Arjun sir @Bikram sir @Digvijay Pandey sir



Dining Philosopher's problem -> m = 5 forks, n = 5 philosophers, s$_{i}$ = 2 forks


@Pascua option A can still have deadlock consider a case n=4, m=5 





So, ∀i,si,<m holds and now if every process holds 1 less than its max need, we get m resources split among n processes fully and all of them requiring 1 more instance of resource for completion but here, no extra resource is available so deadlock.

10 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.

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 ?
Thqq could u please tell me good resource for file systems concept that i can answer any question from gate
5 votes
If we allocate one resources less to each process

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

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

edited by
Why we should allocate on resource less than the required resources?
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 


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 


Related questions

28 votes
3 answers
Two shared resources $R_1$ and $R_2$ are used by processes $P_1$ and $P_2$. Each process has a certain priority for accessing each resource. Let $T_{ij}$ denote the priority of $P_i$ for accessing $R_j$. A process $P_i$ can snatch a resource $R_k$ from process $P_j$ ... conditions ensures that $P_1$ and $P_2$ can never deadlock? (I) and (IV) (II) and (III) (I) and (II) None of the above
asked Nov 4, 2014 in Operating System Ishrat Jahan 3.1k views
23 votes
2 answers
Normally user programs are prevented from handling I/O directly by I/O instructions in them. For CPUs having explicit I/O instructions, such I/O protection is ensured by having the I/O instruction privileged. In a CPU with memory mapped I/O, there is no explicit ... (s) I/O protection is ensured by a hardware trap I/O protection is ensured during system configuration I/O protection is not possible
asked Sep 22, 2014 in Operating System Kathleen 5.2k views
32 votes
6 answers
Which one of the following is true for a CPU having a single interrupt request line and a single interrupt grant line? Neither vectored interrupt nor multiple interrupting devices are possible Vectored interrupts are not possible but multiple ... interrupts and multiple interrupting devices are both possible Vectored interrupts are possible but multiple interrupting devices are not possible
asked Sep 22, 2014 in Operating System Kathleen 7.1k views
78 votes
7 answers
Consider the following code fragment: if (fork() == 0) { a = a + 5; printf("%d, %p n", a, &a); } else { a = a - 5; printf ("%d, %p n", a,& a); } Let $u,v$ be the values printed by the parent process and $x,y$ ... $u = x + 10 \text{ and } v != y$ $u + 10 = x \text{ and } v = y$ $u + 10 = x \text{ and } v != y$
asked Sep 15, 2014 in Operating System Nishant T-rex 12.3k views