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

The answer is 6. which is not given in the options. if process=6 then it leads to deadlock. we dont have one more resource to avoide deadlock

p1	p2	p3	p4	p5	p6
1	1	1	1	1	1

---

None of these . 6 process will cause deadlock.
Good Read : https://gateoverflow.in/1669/gate1998_1-32

---

No. 6 processes MAY cause deadlock.

In the given question there is no none of these option. And in GATE key they gave mark only for 4- given the choices we have to select the most appropriate one among them- no point in arguing if we don't.

---

@arjun sir , I didn't get you . Question asked for what value of N deadlock is possible

• We have 6 Resources
• Allocate 1 resourse to each  
• 2 Resoueses will be available

	MAX	Allocated	Need
p1	2	1	1
p2	2	1	1
p3	2	1	1
p4	2	1	1

Available (2)

Using Bankers Algorithm , This Requests can be satisfied in any order . The lowest value of N for which the system will be in deadlock is 6 .

Then how can 4 process will lead to deadlock ?
Correct me if wrong .

---

I already explained in answer. Had this been a numerical question "6" would have been the answer.

---

yes @arjun sir . I have read them all. I feel like it is another policy of making D as  answer . But when I use  bankers algorithm im getting it is deadlock free :D .

I couldnt fully understand how 4 process will cause deadloack. What I understood from the entiire explanation is as follows :-

• Well, I have considered total of 6 resourses  ( bankers algorithm explanation is given above )
• and you have considered  2 instance of one type of resourse [ say  2 instance of R1 ,2 instance of R2,2 instance of R3 etc. ] ( i guess so )

	MAX	Allocated
p1	<2 0 0 0>	<2 0 0 0>
p2	<0 2 0 0>	<0 2 0 0>
p3	<0 0 2 0>	<0 0 2 0>
p4	<0 0 0 2>	<0 0 0 0>

Available <0 0 0 0> DEADLOCK

• "There are 6 resources and all of them must be in use for deadlock " :- You are Making a restriction.

Had there been no such a restriction then it would have been 6. In Question they didn't mention any such things . Moreover

Each process can request atmost 2 requests

A process can maximum put 2 requests . This implies that that the process need not hold all the resourses . This part actually made me to choose
None of these .

---

What is I do like this,

P1-2 resource given

P2-2 resource given

P3-2 resource given

Now, any process can make at most(maximum) 2 req for resource, we can take instance like this!

Now, all 6 resources are allocated, if P4 comes, does'nt it in a deadlock?

Let me know, where I am lacking!

---

If P4 comes it will not create deadlock, because after some time any one of process P1, P2 or p3 will release the resourse after completion and P4 will get chance to comlete their job

---

If "none of these" was an option, by our default analysis & assumptions we should pick it.
Here no other sentence is given against our default assumptions too.
But we can't leave a question too.  Since mark to all is not given in recent years.
So from the given options.... 4 is the most suitable option.... simply the more the number of processes more is the chance of deadlock but definitely some other conditions exist on this question which is not mentioned.

---

Related Q. -> https://gateoverflow.in/2065/gate2014-3-31

---

I think the answer should be 6.

---

answer will be $4$

---

How can deadlock possible with 4 processes ? If possible then it should also be possible with 2 process.

---

I think this question is correct because here it is mentioned in the question that there could be a deadlock not must be a deadlock.

---

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.