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

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