Register

GATE CSE 2006 | Question: 66

• edited by
28,776 views
95 95 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$

6 Answers

Best answer
115 115 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
16 16 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

4 4 votes
Think logically about the situation and read my answer carefully step by step . I recommend to trace it down on paper for better understanding

At the present moment we have only two processes p and q who have been allocated xp and xq instances of resource R.Now note that these two processes are not going to need any extra resources as yp=yq=0.

Now after some time lets say a process k who have been allocated xk instances of resource R initially demands yk extra instances and at same time another process j who have been allocated xj instances of resource R demands extra yj instances.

Now as per question if p and q don't demand extra instances that means they can complete their execution. After completing their execution they will release their allocated resources.

Hence after releasing allocated resources the total available resources becomes atleast xp+xq

Now the deadlock will occur if any of the extra demand of process k and process j will not be satisfied with the current available instances xp+xq ie

If (xp+xq)< min(yk,yj)

Why did we took min condition??

This is because even if the min extra requirement of the process k or process j will not be satisfied neither of the process will release it's allocated instances so that other process can use it

So if deadlock is to be avoided then we must have enough instances such that we can ATLEAST satisfy the min extra requirement of the available process k or process j.

Hence condition for no deadlock become

(xp+xq)>= Min(yk) where k!=p and k!=q

 
1 1 vote

1. As far as neccessary is concerned, say there is a condition C and Event E:
If C is violated, then ~E
If C is satisfied, E may or may not hold

Here E is system is not approaching a deadlock
So, if a condition is violated, system is definitely approaching a deadlock. (~E)
If condition is satisfied, System might still approach a deadlock

2. At this pt of time, Pp and Pq will be releasing their respective resources as they haven’t placed any further requests. 

3. That’s why the total resources available = xp + xq

4. For Option A), violate the condition. min of resources held by Pp and Pq > max of resources requested by other process. So, if the least no. of resources amongst Pp and Pq itself is able to satisfy the max request, then deadlock will obviously not take place. This is against the criteria of necessary condition. So, Option A is wrong.

5. For Option B), the condition is the sum of no. of resources held by p and q should atleast satisfy the min request. If it is not able to satisfy the min request(if the condition is violated), then obviously xp + xq won’t be enough to satisfy other requests as well. So, deadlock takes place.

Now, if the condition is satisfied, then the min request process will be executed and the no. of resources available = xp + xq + xi . But, what if other processes need more resources than this. That is, what if other processes are interested in the resources held by other process.

So, even if the condition is met, deadlock is occurring. Hence, Option B is correct. 

6. In Option C), let’s violate the condition say max of the resources held by Pp and Pq is equal to 1. Both Pp and Pq are holding a single resource each. So, the total resources available for other processes are 2. Lets say every other process need 1 resource each to satisfy its request. So, deadlock is not taking place. Therefore, Option C is wrong.

7. In Option D), again by violating the condition say min of the resources held by Pp and Pq is 1, so the total resources available are 2. And again, other processes need only one resource to satisfy the request. So, again no deadlock in spite of the violation of condition. So, this option is also Wrong.

• edited by
0 0 votes
(xp+xq>=min(k!=p,q yk). To understand this easily, imagine a toy library where all toys are currently handed out, leaving zero toys on the shelves.

Since the two special processes p and q need zero extra toys to finish (yp = yq = 0), they can complete their tasks immediately without waiting and will return all of their held tokens back to the table, making a total of xp + xq resources newly available.

To keep the system moving and prevent a total deadlock, these resources left on the table must be enough to satisfy at least the next easiest process in line.

The easiest process to save is the one that requests the absolute minimum (min) number of extra resources among all the remaining processes (k!= p, q).

Therefore, the tokens left behind by p and q (xp + xq) must be greater than or equal to (>=) this smallest remaining request (min yk); if it is not, then not a single remaining process can proceed, and the entire system will freeze in a permanent deadlock immediately after p and q leave.

 

 
Voting & Accepting an answer helps improve the community
Answer:
← Previous · GATE CSE 2006 | Ques...Next → · GATE CSE 2006 | Ques...
← Previous in category · GATE CSE 2006 | Ques...Next in category → · GATE CSE 2006 | Ques...
Position:
Show:

Related questions

55 55 votes
7 answers 7 answers
14.6k
14.6k views
go_editor asked Apr 24, 2016
14,623 views
GATE CSE 2006 | Question: 79
Barrier is a synchronization construct where a set of processes synchronizes globally i.e., each process in the set arrives at the barrier and waits for all others to arr...
104 104 votes
6 answers 6 answers
28.1k
28.1k views
Rucha Shelke asked Sep 26, 2014
28,089 views
GATE CSE 2006 | Question: 78
Barrier is a synchronization construct where a set of processes synchronizes globally i.e., each process in the set arrives at the barrier and waits for all others to arr...
91 91 votes
11 answers 11 answers
53.5k
53.5k views
Rucha Shelke asked Sep 26, 2014
53,468 views
GATE CSE 2006 | Question: 65
Consider three processes, all arriving at time zero, with total execution time of $10$, $20$ and $30$ units, respectively. Each process spends the first $20\%$ of executi...
73 73 votes
9 answers 9 answers
40.8k
40.8k views
Rucha Shelke asked Sep 26, 2014
40,779 views
GATE CSE 2006 | Question: 64
Consider three processes (process id $0$, $1$, $2$ respectively) with compute time bursts $2$, $4$ and $8$ time units. All processes arrive at time zero. Consider the lon...