GATE CSE 2006 | Question: 66

Question

Consider the following snapshot of a system running $n$ processes. Process $i$ is  holding $x_i$ instances of a resource $R$, $ 1\leq i\leq n$ . Currently, all instances of $R$ are occupied. Further, for all $i$, process $i$ has placed a request for an additional $y_i$ instances while holding the $x_i$ instances it already has. There are exactly two processes $p$ and $q$ and such that $y_p=y_q=0$. Which one of the following can serve as  a necessary condition to guarantee that the system is not approaching a deadlock?

• A. $ \min(x_{p},x_{q})<\max_{k\neq p,q}y_{k}$
• B. $ x_{p}+x_{q}\geq \min_{k\neq p,q}y_{k}$
• C. $ \max(x_{p},x_{q})>1$
• D. $ \min(x_{p},x_{q})>1$

Comments

Necessary condition

1. If necessary condition is violated you can't do future task.
2. If necessary condition is satisfied then anything can happen to future task $\left(may\ be\ done/ may\ not\ be\ done\right)$

Sufficient condition

1. If sufficient condition is satisfied you can do future task.
2. If sufficient condition is violated then anything can happen to future task $\left(may\ be\ done/ may\ not\ be\ done\right)$

   ---

    

Now coming to this question where they have asked wrt necessary condition:

if this condition gets violated $x_{p}+x_{q}\geq \min_{k\neq p,q}y_{k}$ then system will approach for deadlock.

$\therefore x_{p}+x_{q}\geq \min_{k\neq p,q}y_{k}$ must be satisfied

---

@sushmita, Can u or some-one pls explain, how u got this as Sufficient Condition ?

---

Similar question was asked based on this question in GATE 2019:

https://gateoverflow.in/302809/gate2019-39

Answer 1

B.  $x_{p}+x_{q}\geq \min_{k\neq p,q}y_{k}$

The question asks for "necessary" condition to guarantee no deadlock. i.e., without satisfying this condition "deadlock" MUST be there.

Both the processes $p$ and $q$ have no additional requirements and can be finished releasing $x_p$ + $x_q$ resources. Using this we can finish one more process only if condition B is satisfied.

PS: Condition B just ensures that the system can proceed from the current state. It does not guarantee that there won't be a deadlock before all processes are finished.

Comments

B is the correct option. But why d is also not correct because it is not relevant to talk about a process whose resource need is 0.

Kindly anyone answer to my query.

---

The best explanation!!!

---

Implementation of Banker’s algorithm. :)

Answer 2

See, as P and Q processes do not require any additional resource

This means, they will end and free all the resources that they are holding

Now Currently available resources in the sysem = 0 (given )

Now, when P and Q will finish executing, they will rekease Xp and Xq resources

New Available = Xp + Xq

Now this new available must be enough for the minimum need of the Processes.

This means that we have to find such a process, whose minimum need is less or equal to available

Isnt this the condition for banker’s Algorithm

So it is simple

Xp+Xq >= min(Yk)

where k not equal to p,q

Comments

Thanks for the simple explaination :)

---

einstein once said, if you cant explain someone a concept in simple words, you yourself have not understood it that deep.

Just following his words

:)

Thanks