GATE CSE 2015 | Set 2 | Question: 23

Question

A system has $6$ identical resources and $N$ processes competing for them. Each process can request at most $2$ resources. Which one of the following values of $N$ could lead to a deadlock?

• A. $1$
• B. $2$
• C. $3$
• D. $4$

Comments

Similar questions:

Operating System: GATE CSE 1992 | Question: 02-xi

Operating System: GATE CSE 1993 | Question: 7.9, UGCNET-Dec2012-III: 41

Operating System: GATE CSE 1997 | Question: 6.7

Operating System: GATE CSE 1998 | Question: 1.32

Operating System: GATE CSE 2005 | Question: 71

Operating System: GATE CSE 2014 Set 3 | Question: 31

Operating System: GATE CSE 2015 Set 2 | Question: 23

Operating System: GATE CSE 2018 | Question: 24

---

6 ?

---

<5

Answer 1

$3 \times 2 = 6$
$4 \times 2 = 8$

I guess a question can't get easier than this- (D) choice. (Also, we can simply take the greatest value among choice for this question)

[There are $6$ resources and all of them must be in use for deadlock. If the system has no other resource dependence, $N=4$ cannot lead to a deadlock. But if $N=4$, the system can be in deadlock in presence of other dependencies.

Why $N=3$ cannot cause deadlock? It can cause deadlock, only if the system is already in deadlock and so the deadlock is independent of the considered resource. Till $N=3,$ all requests for considered resource will always be satisfied and hence there won't be a waiting and hence no deadlock with respect to the considered resource. ]

Comments

minimum value of N for which deadlock may occur is 6.

---

not possible for 4?

---

suppose if there are 4 processes and each process request for 2 resources then we can allocate 6 resources to 3 processes and 4th one is waiting for others to finish and after they finished their work, they will release their resources and 4th one can finish too, where is the deadlock?

---

No deadlock if the processes have no other dependencies. Till N=3, the given resource can in no way be part of a deadlock. That is why 4 is the answer.

---

agreed :)

---

@Arjun Sir can you give me an example where N=4 can lead to a deadlock? as i see it for N=4 two possibilities are there

1->2 : 2->2 : 3->2 : 4->0  and  1->2 : 2->2 : 3->1 : 4->1

and in both cases circular wait condition is violated ... so no deadlock... please clarify.

---

1 -> 2 (waiting for res 2, assume 2 instances of res 1 in use by process 1)
2 -> 3 (waiting for res 1, assume 1 instance of res 1 in use by process 2)
3 -> 4 (waiting for res 1, assume 1 instance of res 1 in use by process 3)
4 -> 1 (waiting for res 2, assume 2 instances of res 1 in use by process 4)

Deadlock can occur like this as all 6 instances of res 1 are in use. The question is asking which value of N could lead to a deadlock. It is not saying that the system consists of only this resource.

---

I thinks the question was quite incomplete to answer..  What I mean to say that anybody can introduce their own policy to answer this question..

---

Arjun sir,

          then why not the answer 3 is right??

    1 -> 2 (waiting for res 1)
    2 -> 3 (waiting for res 1)
    3 -> 1 (waiting for res 1)

   here also deadlock occurred..

---

I have edited my comment to make it clear. There are 6 resources and all of them must be in use for deadlock. If the system has no other resource dependence, N=4 cannot lead to a deadlock. But if N=4, the system can be in deadlock in presence of other dependencies.

Why N=3 cannot cause deadlock? It can cause deadlock, only if the system is already in deadlock and so the deadlock is independent of the considered resource. Till N=3, all requests for considered resource will always be satisfied and hence there won't be a waiting and hence no deadlock with respect to the considered resource.

Will GATE give marks to all? Lets see on March 12, I suppose they might give.

---

And GATE people also did the same :)

---

sir, there will be no deadlock if No of process=4.

in worst case,

process:        p1    p2   p3    p4

Resources:    2       2     2     0

but still there is no deadlock because after some time one of the process will complete their execution & release their resources. So, p4 will get the resources after some time.

if the no of process =5, then still there will be no deadlock.

so question is absolutely wrong. 

---

@arjun sir not possible for 4 ?  

its possible 4*2=8 resouces required but we have only 6 reosurces .

and bdw what other people are calculating is by taking each process required exactly 2 resources . but the question says atmost ! so giv max and see now :)

---

No, If a process is having 2- it means it can complete execution. And this will release the 2 resources too.

---

I think it's too late to discuss on this but N=4 can lead to a deadlock if we consider the scenario below:

Consider there exists P1,P2,P3,P4 and R1,R2...,R6.

Now, consider that P1 and P2 completely consumes R1,R2,R3,R4 (since every process has two requests).

Now consider that only single requests each from P3 and P4 acquires R5 and R6.

Now single requests remain from both P3 and P4 (to R5 and R6). You see, now if a request from P4 tries to acquire resource of P3(R5) and similarly P3's request to P4's acquired resource (R6). This leads to a deadlock.

So this scenario COULD lead to a deadlock.

Let me know if my analysis is right.

---

P1 and P2 have two resources each. They need at most 2, they will use them and free the resources. These resources can now be used by P3 and P4.

Am I right?

---

I agree with you mohit199.

---

@arjun sir can u explain what do u mean by "if N=4, the system can be in deadlock in presence of other dependencies?"

---

@arjun sir, The answer to this question must be 6.
Even if we assign 5 resources to 5 different processes (ie; 1 resource for each process) then also the 1 resource left with us (6-5=1) will be able to satisfy atleast one process and hence all the processes will be satisfied and there will be no deadlock. Hence, atleast N=6 processes is the answer to the question.

---

how could be deadlock possible for 4 processes?

---

What if we allocate 6 resources for each process and since they can request for atmost 2 resource,if they need another resource,they will be waiting for the process to release the resource leading to deadlock

---

A deadlock can occur when the following four conditions are met:

1. Mutual exclusion: A resource is held by only one process at a time
2. Hold and wait: A process holds at least one resource while waiting for another
3. No preemption: A resource can only be released by the process that holds it
4. Circular wait: A process P1 is waiting for a resource held by process P2, P2 is waiting for a resource held by process P3, and so on, forming a circular chain of waiting processes.

In the case of 6 identical resources and N processes, each process can request at most 2 resources. For N processes to lead to a deadlock, we should have N2 > 6. Therefore, N=4 can lead to a deadlock as 42=8 > 6.

In this case, if all the four processes request 2 resources each, and all resources are assigned to different processes. It creates a circular wait as all processes are waiting for the resources held by other process, and hence a deadlock occurs.

---

What you wanna say? 1process can  request only 2 resources at a time after getting it will run and release after that

---

but we know that, if there are 4 process and max. demand for all is of 2 resources then with 5 resources we can guarantee there will never be a deadlock. so is this statement false? also gate itself asked many time questions with exactly same statement. i think ques is wrong or ambiguous.

Answer 2

answer should be 6

Comments

not in option. so ans is 4.

Answer 3

for this type of question always allocate (max_need-1)resource to each process and keep 1 extra resource , allocating that extra resource to any process , the process can execute and all its resources will be available. so in this particular Question max need is 2, allocate (2-1)=1 to each process and u need 1 extra resource, so actually u can support 5 process with 6 resource. as the highest number of process is 4 go for D.

actually min no. of resource required to guarantee deadlock free condition = (sum of all (max_need -1))+1

Comments

@Supromit : I have understood your point. But I am confused about when to use the following formula to keep system deadlock free.

Sum of all maximum need < (No of process + No of resource) . It is an exercise question of Galvin.

Please comment.

---

According to your point, we can support maximum 5 process with 6 resources and system will be deadlock free. But previous answer  says with 4 process, system will be in deadlock. How can you conclude to this answer?

---

thats too generic. i m in particular dealing with min no. of resources required.

check this link

https://gateoverflow.in/19379/what-logic-calculating-minimum-resources-remove-deadlock

---

you will find a no. of example of same type of question in others previous years of gate

Answer 4

Whenever this type of question came, related to resource and deadlock or process and deadlock the simple way to solve is

Allocate each process a resource equal to their maximum need - 1, This type of allocation gives you maximum no resources that lead to deadlock but if you just add 1 to this number you will get minimum no of resources causing no deadlock.

for example 

let us say the total no of resources is R and we have to N process and each can take almost M resource the what is the value of N? 

N * (M-1) + 1 <= R 

for this question, the maximum no of processes is 5 without deadlock, the minimum no of the process causing deadlock is 6 but it is not given in option so go with 4

Answer 5

supos there are n process p1,p2,p3....pn share m identical resource which can be release/allocate one at the time.

the max resource required for process pi is si, where si>0

the sufficient condition for ensuring that DL doesn't occure:  Σsi(for i=1 to n) < (m+n)

where m= number of resource

      n= number of process

      si= total req(request resource for ith process)

Comments

And what is answer coming ?

2N<N+6

N should be min 3 ti satisfy deadlock,rt?

---

@Hira Thakur and @srestha

 shouldn’t 3 i.e. option C satisfy the answer as we can make resource allocation graph for this    ?

Answer 6

Nos of Resources=R=6

nos of processes=N

Max demand=P=2

Now deadlock will not occur if R>=N*(P-1)+1 which gives N <=5, Now the max option given  4  which is taken as the solution.

Hence the option D is correct.