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

Phalkey, that is why TUHIN used < and not <=

---

To make it simple if we have R resources and N processes each demand K resources to avoid deadlock give N-1 processes K-1 resources and give K resources to 1 process.

(N-1)(K-1) + 1*K = R

So we have 3 processes give K-1 to 2 processes and K to 1 process

2(k-1)+1*k = 4

2k-2+k=4

3k=6

k=2

---

it is already simple. you are making is complicated.

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!

Answer 3

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 4

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

I did not intend to provide incorrect information.

The formula that was given in the previous answer is: "The largest value of K that will always avoid deadlock in a system with N processes and M instances of the same resource type is M/N". This formula states that if each process can request up to M/N 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. This ensures that the system will never reach a deadlock state, where all processes are waiting for a resource that is held by another process.

I did not intend to provide a "wrong" formula or to contradict the previous answer. My previous response was intended to provide additional information and clarification about the formula that was given in the previous answer. I apologize if this was not clear to you.

---

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