GATE CSE 1992 | Question: 02-xi

Question

A computer system has $6$ tape devices, with n processes competing for them. Each process may need $3$ tape drives. The maximum value of n for which the system is guaranteed to be deadlock-free is:

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

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

---

🫡

---

👍

---

"deadlock-free does NOT mean deadlock never appears temporarily, It means that the system can always make progress and reach a state where at least one process completes."

Suppose, there are two process 

P1 Process holds: R1, R2 → waiting for R3
P2 Process holds: R3, R4 → waiting for R1

So:

Used drives = R1, R2, R3, R4 (4 drives)

Free drives = R5, R6 (2 drives)

   Here Mutual exclusion , Hold & wait  , No preemption and Circular wait satisfied But: Free resources still exist So Progress is possible

So: OS gives R5 to P1

Therefore: NOT a deadlock

P1 finishes, releases all

P2 finishes

 

 In this system, deadlock is impossible with two processes because even in the worst-case allocation, some resources remain free, allowing at least one process to complete and release its resources. However, with three or more processes, it is possible to construct a state where all resources are allocated and each process is waiting for an additional resource, resulting in deadlock.

Answer 1

Allocate max-$1$ resources to all processes and add one more resource to any process (Pigeon hole principle) so that this particular process can be completed (resources can be freed) and there is no deadlock.

Max resources required is $3$.

$\therefore (3-1)*n+1=6$

$n=\left \lfloor \frac{5}{2} \right \rfloor=2$

Correct Answer: $A$

Comments

Please explain me this-

if I take 4 processes as- P1, P2, P3, P4 and allocate resources as 1, 1, 1, 3 respectively, then P4 will complete its task and release the resources held by it and hence others can complete their task. And hence the system is deadlock free by taking 4 processes.

Please help where am I missing the concept.

---

@PriyankaS

P1	P2	P3	P4
1	1	1	1
1	1

The case which you have taken will not lead to deadlock but if I consider this case for your example then there will be a deadlock.

So we need such a number of process in which if we try for any possibility deadlock should  not occur!

---

@PriyankaS I might be late But here we talk of the worst case. In the worst case if we have more than 2 processes here then it will lead to a deadlock. 

 You can even understand it using PHP(pigeonhole principle) we have 6 Resources(as pigeons) we have to distribute into the max processes(as holes) such that at least one of them will have 3 resources.

 then ceil(6/P) = 3 now if p =2 then only it will be 3 cause we need max process.

Answer 2

Answer: (A).

For $n=3$, $2-2-2$ combination of resources leads to deadlock.

For $n=2$, $3 - 3$ is the maximum need and that can always be satisfied.

Comments

@GaneshA We can come up with many such allocation which will not cause deadlock. Question is asking "guaranteed to be deadlock free". Even if there is is a single case causing deadlock, it will not be considered.

Worst case allocation is all process gets one less than their maximum demand and all are blocked as after such assignment no one goes to completion.

---

Please explain, I am not able to understand.

If I take 4 processes as- P1, P2, P3, P4 and allocate resources as 1, 1, 1, 3 respectively, then P4 will complete its task and release the resources held by it and hence others can complete their task. And hence the system is deadlock free by taking 4 processes.

How come using 4 processes deadlock free is not guaranteed?

Please help where am I missing the concept.

---

the main thing is we have to choose worst case. so in your case , we can't contrint the things,

there may be multiple arrangment possible thatdoes not lead to dead lock. but how can you restrict some process to use only one and later 2 or 3?

if os then let there be 5 process. and let allocate first process to 3 resource. and another process to 3 resource. then all will be dead lock free. even N process, one can finish execution, if 2 process use half of 6, simultanously.

but here, and in reality, we should use worst case.

Answer 3

Don’t use formulas until and unless it’s necessary!

This can easily be solved with the help of intuition. Ultimately, we want that at least one process should get executed completely, so 1st process consumes 3 resources. We are left with 3 more, now if we take 2 more processes then what might happen is each of 3 processes consume 2-2 resources each because of which deadlock occurs. So, at max only 1 more process we can select and it will be consuming the remaining 3 resources. So, total of 2 processes which give n =2, option A. I hope it helped. :)

Answer 4

We need to only that option in which system will always be deadlock free..

Case 1 if we have 4 processes.  indeed we do have possibility of deadlock with 4 processes.

p1	p2	p3	p4
1	1	1	1
1	1

Case 2 if we have 3 processes. Again with 3 processes we can have deadlock

p1	p2	p3
1	1	1
1	1	1

Case 3 if we have 2 processes. With 2 processes we can never have deadlock in any configuration..

p1	p2
1	1
1	1
1	1

We have to discard all the cases where we can have deadlock..2 is the only option in which system will be deadlock free.