Problem Detail:
A system has 6 identical resources and $N$ processes competing for them. Each process can request at most two requests. Which one of the following values of $N$ could lead to a deadlock?
- 1
- 2
- 3
- 4
My attempt: Deadlock free condition is: $R geq P(N-1)+1 ,$ Where R is total number of resources, P is the number of processes, and N is the max need of each resource. $6 geq P(2-1) + 1$ $6 geq P + 1$ $5 geq P$ So, the number of processes should be less than $5$ for the deadlock free condition. Hence, all options can not be deadlocked. In this exercise problem the answer given option (4).
Can you explain it in a formal way, please?
Asked By : Mithlesh Upadhyay
Answered By : David Richerby
I agree that no deadlock is possible here. If there are three or fewer processes, there clearly cannot be a deadlock because there are enough resources for every process to just hold two resources the whole time. So any deadlock must have at least four participating processes. To participate in a deadlock, a process must hold at least one resource. Further, a process cannot hold more than two resources so a process that currently has two resources can definitely run until it frees at least one of those resources. Therefore, if there is a deadlock, it must involve four processes, each holding exactly one resource. This means that there are two resources free so any process that requests a resource will be granted it and will then run until it releases one or both of the resources it holds. Out of our set of four supposedly deadlocked processes, at least one is always runnable, so there is no deadlock. (In fact, at least two are runnable at all times.) Perhaps the question-setter had the following situation in mind. Suppose processes 1 and 2 are using two resources each and processes 3 and 4 are using one resource each. Now, if 3 and 4 each request one more resource, they will block. But this is not deadlock because the situation can be resolved by either one of the two runnable processes (1 and 2) giving up one of their resources. Deadlock is the situation where every one of a set of processes is blocked and the only way to resolve the situation is for one of those blocked processes to give up resources, which it can’t do because it’s blocked.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/48660
