GATE CSE 2013 | Question: 16

Question

Three concurrent processes $X$, $Y$, and $Z$ execute three different code segments that access and update certain shared variables. Process $X$ executes the $P$ operation (i.e., $wait$) on semaphores $a$, $b,$ and $c$; process $Y$ executes the $P$ operation on semaphores $b$, $c,$ and $d$; process $Z$ executes the $P$ operation on semaphores $c$, $d$, and $a$ before entering the respective code segments. After completing the execution of its code segment, each process invokes the $V$ operation (i.e., $signal$) on its three semaphores. All semaphores are binary semaphores initialized to one. Which one of the following represents a deadlock-free order of invoking the $P$ operations by the processes?

• A. $X:$ $P(a)P(b)P(c)$ $Y:$ $P(b)P(c)P(d)$ $Z:$ $P(c)P(d)P(a)$
• B. $X:$ $P(b)P(a)P(c)$ $Y:$ $P(b)P(c)P(d)$ $Z:$ $P(a)P(c)P(d)$
• C. $X:$ $P(b)P(a)P(c)$ $Y:$ $P(c)P(b)P(d)$ $Z:$ $P(a)P(c)P(d)$
• D. $X:$ $P(a)P(b)P(c)$ $Y:$ $P(c)P(b)P(d)$ $Z:$ $P(c)P(d)P(a)$

Comments

Here , the thing to keep in mind that we have to perform up operations only to the respective semaphores of the respective concurrent process .

Example : if we perform operations on process Y . Then we have to perform Up operation only on b,c,and d .

While keeping this in mind option (b) is correct .

Correct me if I'm wrong .

Answer 1

For deadlock-free invocation, $X, Y$ and $Z$ must access the semaphores in the same order so that there won't be a case where one process is waiting for a semaphore while holding some other semaphore. This is satisfied only by option B. 

In option A, $X$ can hold a and wait for $c$ while $Z$ can hold $c$ and wait for $a$
In option C, $X$ can hold $b$ and wait for $c,$ while $Y$ can hold $c$ and wait for $b$
In option D, $X$ can hold $a$ and wait for $c$ while $Z$ can hold $c$ and wait for $a$

So, a deadlock is possible for all choices except B. 

http://www.eee.metu.edu.tr/~halici/courses/442/Ch5%20Deadlocks.pdf

Comments

Yes theredeepakb, not only RBR, even ME, ACE and other institutes copy answers from here ;)

---

"For deadlock-free invocation, X,Y and Z  must access the semaphores in the same order so that there won't be a case where one process is waiting for a semaphore while holding some other semaphore. This is satisfied only by option B."

Can anyone help to understand this. I didn't get how the order is maintained in option B.

---

@pranab10

Note that all binary semaphores are initialized to 1 here

So, in option B, either $X$,$Y$(or) $Z$ can start first

Out of $X$ and $Y$, only one can use semaphore $b$. lets consider all possible options now

• $X$ takes semaphore $b$ – Now, Y cannot proceed anymore and it will wait for $b$. Next, either $X$ (or) $Z$ can take semaphore $a$. Again let consider two cases
  • $X$ takes $a$ - Then , $Z$ cant take $c$ as $Z$ has to wait for $a$. Now, $X$ can take $c$ and proceed. Once $X$ completes, $Z$ can proceed followed by $Y$
    
    Seq : $X$ -> $Z$ -> $Y$
     
  • $Z$ takes $a$ - Then , $X$ cant take $c$ as $X$ has to wait for $a$. Now, $Z$ can take $c$ and proceed. Once $Z$ completes, $X$ can proceed followed by $Y$
    
    Seq : $Z$ -> $X$ -> $Y$
     
• $Y$ takes semaphore $b$ – Now, $X$ cannot proceed anymore and it will wait for $b$. Next, either $Y$ (or) $Z$ can take semaphore $c$. Again let consider two cases
  • $Y$ takes $c$ - Then , $Z$ cant take $c$ as $Z$ has to wait for $c$. Now, $Y$ can take $d$ and proceed. Once $Y$ completes, $Z$ can proceed followed by $X$
    
    Seq : $Y$ -> $Z$ -> $X$
     
  • $Z$ takes $c$ - Then , $Y$ cant take $c$ as $Y$ has to waiting for $c$. Now, $Z$ can take $d$ and proceed. Once $Z$ completes, $Y$ can proceed followed by $X$
    
    Seq : $Z$ -> $Y$ -> $X$

In a similar manner, we can see that all 6 orders are possible. 

We are checking if 'Hold and wait' and 'Circular wait' conditions do not hold simultaneously which is possible only in option B

Hope this clarifies

Answer 2

Find crossings like above.

Comments

There is no logic . Even in B there may be crosses

---

Since ,all semaphores are binary.

And we have to check possiblity of deadlock.

Deadlock will occur when we have some resource and waiting for other resource held by other process and that too is waiting for our resource.

In above example,finding crossing means there is cycle and if there is cycle there will be deadlock because all resources have only one instance (here resource means binary semaphores).

In fig.for example in 1. option, a acquire lock X ,and c Acquire lock z,now c is waiting for x and a is waiting for z.

so ,there is deadlock.similarly in other examples except 2.

---

Please solve the below problem with the same logic

Two processes, A and B, each need three records, 1, 2. and 3, in a database. If A asks for them in the order 1, 2, 3, and B asks for them in the same order, deadlock is not possible. However, if B asks for them in the order 3, 2, 1, then deadlock is possible. With three resources, there are 3! or 6 possible combinations each process can request the resources. What fraction of all the combinations are guaranteed to be deadlock free?

Here we will get ans as only $\dfrac{1}{6}$ by this method but shouldn't the ans be $\dfrac{1}{3}$ according to this logic

 

---

@jatin saini bro is this the correct way to solve such questions??

---

In b the lines will be parallel, not a cross! check @sresta s comment in the above answer for some insights

Answer 3

Explanation: Option A can cause deadlock. Imagine a situation process X has acquired a, process Y has acquired b and process Z has acquired c and d. There is circular wait now.

Option C can also cause deadlock. Imagine a situation process X has acquired b, process Y has acquired c and process Z has acquired a. There is circular wait now.

Option D can also cause deadlock. Imagine a situation process X has acquired a and b, process Y has acquired c. X and Y circularly waiting for each other.

See http://www.eee.metu.edu.tr/~halici/courses/442/Ch5%20Deadlocks.pdf

Consider option A) for example here all 3 processes are concurrent so X will get semaphore a, Y will get b and Z will get c, now X is blocked for b, Y is blocked for c, Z gets d and blocked for a. Thus it will lead to deadlock.

Similarly one can figure out that for B) completion order is Z,X then Y.

Comments

Can you explain a bit more about how to get the execution sequence of option B.. Iam unable to get it..

---

But, if we consider this scenario for option (B)
Process X has acquired b and a, then Process Y and Z will not run as value of b and a both are 0 they will be waiting. The only possible way for Process X is to acquire c nothing else, by keeping value d = 1.Then how the answer is Option (B) ? @Paras Nath

Answer 4

A) 

cycle- 'a' is held by X. X requests for 'b' which is held by Y. Y requests for 'd' which is held by Z. Z requests for 'a' which is held by X

similarly option C, D will have cycle but not option B