The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+18 votes
2.3k views

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.

  1. $P(S_Y), P(S_X); P(S_X), P(S_Y)$

  2. $P(S_X), P(S_Y); P(S_Y), P(S_X)$

  3. $P(S_X), P(S_X); P(S_Y), P(S_Y)$

  4. $P(S_X), P(S_Y); P(S_X), P(S_Y)$

asked in Operating System by Veteran (59.6k points)
retagged by | 2.3k views

3 Answers

+25 votes
Best answer
  1. 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.
     
  2. 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.
     
  3. $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.
     
  4. $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 
answered by Boss (15.6k points)
edited by
0
@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?
+1

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)

0
@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....
+14 votes

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.


answered by Veteran (57.4k points)
0
@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
0
Ok.

Is there any possibility of deadlock ? In A ?
0
??,....
+2
Yes, deadlock possible.
+1

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

0

@debashidh

in option A there may b not deadlock .

0
QS asks to avoid options having non zero probability of deadlock. Qs does not ask which option may have deadlock.
+11 votes
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 ..
answered by Veteran (55.4k points)
edited by


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

40,874 questions
47,534 answers
146,072 comments
62,300 users