GATE CSE 2018 | Question: 24

Question

Consider a system with $3$ processes that share $4$ instances of the same resource type. Each process can request a maximum of $K$ instances. Resources can be requested and releases only one at a time. The largest value of $K$ that will always avoid deadlock is ___

Comments

bhai mein k ko kabse R padh rha hu

---

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

---

Analogy to understand: 

Answer 1

Number of processes $= 3$
Number of Resources $= 4$

Let's distribute each process one less than maximum demand $(K-1)$ resources. i.e. $3(K-1)$
Provide an additional resource to any of three processes for deadlock avoidance.

Total resources $= 3(K-1) + 1 = 3K - 2$

Now, this $3K-2$ should be less than or equal to the number of resources we have right now.
$3K-2 \leq4$
$\implies 3K \leq 6$
$\implies K \leq 2$
So, largest value of $K=2$

Comments

@flash12 

Deadlock free condition is:

R ≥ P(N−1) + 1

Where R is total number of resources,

P is the number of processes, and

N is the max need of each resource.

For (N-1) resources it is deadlocked, because max need is N resources. Now, as they share same resource type.

P(N−1) --> This means each process P share (N-1) resources which is a deadlock, so it needs at least 1 resource to be deadlock free.

Example: Three processes needs 3 resources each.

so we give only 2 resources each that's deadlock. right?

now give just +1 extra resource to first process only you ll see first process is deadlock free and releases its resources, which help 2nd process to get free similarly 3rd. 

Hope it helps.

---

This question can be answered intuitively as well.

First try to distribute $1$ to each, then distribute $2$ and then $3$.

In $3$ deadlock will happen. So, not valid.

---

Kuljeet Can you give me the reference for this formula?

Answer 2

For many people being confused by the answer being either 1 or 2, here's an explanation that might help.

4 instances of R given.

3 Processes given.

Let each process take 1 resource. 1 R left. Clearly, K can be 1 since deadlock wont happen.

Now lets take 2.

In the worst case, every process will take 1 resource each with one R left out.

Assume P1 takes the remaining 1 R again and P2 requests for R. P2 will wait till P1 finishes. Therefore no deadlock. K=2.

Now lets try 3

Worst case again, each process takes 1 resource with 1 R left out. Say P1 requests for 2 more - it will lead to a deadlock since only 1 is available and 1 more is needed. Deadlock means program is literally 'dead' and 'locked' with no progress at all.

 

Therefore, K=2

Comments

Thanks for the intuition!

---

Your approach looks like pigeon hole principle!!!

Answer 3

We can use Pigeon Hole principle in this problem.

Give P1 , P2 AMD P3  each an equal resources 1, 1, 1

as per PGP we know that there is atleast 2 pigeon in a same hole so here one resources i sleft add it to any process and the max value of K= 1+1 =2

Answer 4

Let demand of each process be d
Give number of process is 3 , give one less resource to all processes that is (d-1)
so maximum number of resources but still deadlock occurs is 3(d-1)
Given resources =4
4<=3(d-1)
or
4>3(d-1)
=> 4>3d-3
=>4+3>3d
=>7>3d
putting value of d as 2 we get
7>6 which is true therefore 2 is the answer

Answer 5

To avoid deadlock, it is necessary to ensure that the system will never reach a state where all processes are waiting for a resource that is held by another process. One way to avoid deadlock is to ensure that each process can always obtain the resources it needs without having to wait for another process to release them.

In a system with 3 processes and 4 instances of the same resource type, the largest value of K that will always avoid deadlock is 2. This is because if each process can request up to 2 instances of the resource at a time, then each process can always obtain the resources it needs without having to wait for another process to release them.

In general, the value of K (not necessarily the minimum) that will always avoid deadlock in a system with N processes and M instances of the same resource type is M/N. This is because each process can request up to M/N instances of the resource at a time, ensuring that each process can always obtain the resources it needs without having to wait for another process to release them. To get the minimum value of K we have to use the formula $N(K-1) + 1 \leq M$ as that’ll ensure that at least 1 process can complete without waiting for any other process which will then release the resources held by it – thus ensuring other processes too eventually finish (no deadlock).

Comments

Whether it is clear to me or not doesn’t matter and I did not say you intentionally did it. But you are actually providing a lot of wrong information in many answers. Smart GATE aspirants know to avoid such answers but there are many ignorant aspirants who’ll think they are correct like they do for many youtube explanations. Before answering anything if you just confirm the concept used with authentic information (from official keys or standard books or GO PDFs) then your answers will be useful to you and also to the community. I have edited your answer here.

---

Thanks @gatecse

---

Suppose there are 7 resource instances!
We have:
T=7= total no. of instances,
K= max. no. of resource instances needed or requested ,
P= total no. of processes = 3
To avoid deadlock,atleast 1 process should have K instances to execute properly which implies that the remaining resource instances(T-K) can be shared among P-1 processes.
We assume the worst case scenario, i.e, remaining(P-1) processes have just 1 instance less than the max. need=(K-1). So the formula comes out to be: (P-1) * (K-1) <= T-K
Substituting the values: 2*(K-1)<=7-K   ------>    3K <=9    ------> K<=3
3 is maximum value that can be requested by the processes avoiding deadlock!
 

Answer 6

Number of processes, N = 3

Number of resources available = 4

Minimum resources required to avoid deadlock with N processes when each process can request at most K instances=

N(K-1)+1

If the minimum number of resources required to avoid deadlock is more than number of resources available, we CANNOT fulfil any request.

So, 

N(K-1)+1 <= Available

3(K-1)+1 <= 4

3K-2 <= 4

3K <= 6

K <= 2

Maximum value of K to avoid deadlock = 2