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

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.