The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+19 votes
2.5k 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.7k points)
retagged by | 2.5k views

4 Answers

+26 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.9k 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.6k 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.6k points)
edited by
0 votes
Deadlock is possible when there is no order defined how resources will be consumed by processes. Therefore graph based protocol is free from deadlock as every process try checking from root and if first resource is occupied then the process is blocked and the process which has locked it first completes its execution. After checking the option you can see both processes are consuming resources in an order in option d. Sx followed by Sy which prevents deadlock.
answered by Active (3k points)
Answer:

Related questions



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

44,197 questions
49,669 answers
163,545 comments
65,818 users