GATE2004-48

Question

Consider two processes $P_1$ and $P_2$ accessing the shared variables $X$ and $Y$ protected by two binary semaphores $S_X$ and $S_Y$ respectively, both initialized to 1. $P$ and $V$ denote the usual semaphore operators, where $P$ decrements the semaphore value, and $V$ increments the semaphore value. The pseudo-code of $P_1$ and $P_2$ is as follows:

$P_1$:	$P_2$:
While true do { $L_1$:…….. $L_2$:…….. X = X + 1; Y = Y -1; $V(S_X);$ $V(S_Y);$       }	While true do { $L_3$:…….. $L_4$:…….. Y = Y + 1; X = Y -1; $V(S_Y);$ $V(S_X);$

In order to avoid deadlock, the correct operators at $L_1$, $L_2$, $L_3$ and $L_4$ are respectively.

• A. $P(S_Y), P(S_X); P(S_X), P(S_Y)$

• B. $P(S_X), P(S_Y); P(S_Y), P(S_X)$

• C. $P(S_X), P(S_X); P(S_Y), P(S_Y)$

• D. $P(S_X), P(S_Y); P(S_X), P(S_Y)$

Answer 1

• A. deadlock $p1$ : line$1$|$p2$:line$3$| $p1$: line$2$(block) |$p2$ :line$4$(block)
  So, here $p1$ want $s(x)$ which is held by $p2$ and $p2$ want $s(y$) which is held by $p1$.
  So, its circular wait (hold and wait condition). So. there is deadlock.
   
• B. deadlock $p1$ : line $1$| $p2$ line $3$|$p1$: line $2$(block) |$p2$ : line $4$(block)
  Som here $p1$ wants sy which is held by $p2$ and $p2$ wants $sx$ which is held by $p1$. So its circular wait (hold and wait ) so, deadlock.
   
• C. $p1$ :line $1$|$p2$ : line $3| p2$ line $4$ (block) $|p1$ line $2$ (block) here, $p1$ wants $sx$ and $p2$ wants $sy$, but both will not be release by its process $p1$ and $p2$ because there is no way to release them. So, stuck in deadlock.
   
• D. $p1$ :line $1$ $|p2$ : line $3$ (block because need sx ) $|p1$ line $2 |p2$ : still block $|p1$: execute cs then up the value of sx |p2 :line 3 line $4$(block need $sy$)$| p1$ up the$ sy$ $|p2$ :lin$4$ $4$ and easily get $cs$.
  We can start from $p2$ also, as I answered according only $p1$, but we get same answer.
  So, option (D) is correct 

Comments

@sonam how option is C is getting blocked.

this is my try:

P1:P(X) | P2:P(x) (blocked) | P1:P(Y) | P2:P(Y)(blocked) so here p1 gets executed successfully.

or

P1:P(X) | P1:P(X) | P2: P(Y) | P2:P(Y) in both cases P1 and P2 is getting access. how there is deadlock in option C pls explain?

---

hey in option c) l1 p(sx) l2 p(sx) (in p1) and l3 p(sy) ,l4 p(sy) (in process p2) rt 

so how P1:P(X) | P2:P(x) (blocked) | P1:P(Y) | P2:P(Y)(blocked) this will be done ??

you did for option d)

---

@all

what here we found . a condition where there is no possibilty of deadlock ...or where there is some possiblity of deadlock.

in option d if we  run p1 ( p(sx)) and then wait for p2(p(sx)) then it will lead to deadlock ?

comment on thiz approach....

Answer 2

Option (A):

$\Rightarrow$ Deadlock possible

---

Option (B) . Same as Option (A). Deadlock possible.

---

Option (C):

No need to think of another process to get a deadlock situation:

$\Rightarrow$ Both processes will be blocked once they start.

---

Option (D) is ok ! as far as deadlock is concerned.

---

Comments

@debashish

in option A there may b not deadlock

P1(L1)  -> P1(L2)->P1(L3)->P1(L4) AND

DO IT FOR P2 REPLACE P1 WITH P2 IN ABOVE . AND SEQUENCLY DO IT FOR P1 AND P2 ,  WILL NEVER DEADLOCK

---

Ok.

Is there any possibility of deadlock ? In A ?

---

??,....

---

Yes, deadlock possible.

---

@ mcjoshi ..yes...I think the same ...but I asked @wanted...to his comment

---

@debashidh

in option A there may b not deadlock .

---

QS asks to avoid options having non zero probability of deadlock. Qs does not ask which option may have deadlock.

Answer 3

let execute P1 till L1 and then execute P2 till L3..
now check options.
Option A,B,C results deadlock.
even Option C always deadlocked..

Option D works fine ..