edited by
16,286 views
58 votes
58 votes

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?

  1. $ \min(x_{p},x_{q})<\max_{k\neq p,q}y_{k}$
  2. $ x_{p}+x_{q}\geq \min_{k\neq p,q}y_{k}$
  3. $ \max(x_{p},x_{q})>1$
  4. $ \min(x_{p},x_{q})>1$
edited by

2 Answers

Best answer
83 votes
83 votes
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.
edited by
12 votes
12 votes

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

Answer:

Related questions