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$ requests. Which one of the following values of $N$ could lead to a deadlock?

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

Comments

Did gate gave bonus marks for this question?

---

Important comments to understand this question 

https://gateoverflow.in/8114/gate-cse-2015-set-2-question-23?show=413769#a413769

---

They made wrong question. Even with 4 process it can never go in deadlock. All philosophy and whatnot but the question is wrong. Answer should be 6.

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.

---

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.

---

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

Answer 2

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

Comments

And GATE people also did the same :)

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

answer should be 6

Comments

not in option. so ans is 4.