edited by
22,845 views
68 votes
68 votes

The $P$ and $V$ operations on counting semaphores, where s is a counting semaphore, are defined as follows:

$P(s):$

$s=s-1;$
If $s < 0$ then wait;

$V(s):$

$s=s+1;$
If $s \leq0$ then wake up process waiting on s;

Assume that $P_b$ and $V_b$ the wait and signal operations on binary semaphores are provided. Two binary semaphores $x_b$ and $y_b$ are used to implement the semaphore operations $P(s)$ and $V(s)$ as follows:

$P(s):$ 

$\quad P_b(x_b);$
$\quad s = s-1;$
$\quad \text{if } (s<0)$
$\quad \{$
$\qquad V_b(x_b);$
$\qquad  P_b(y_b); $
$\quad \}$
$\quad \text{ else } V_b(x_b); $

$ V(s):$ $\quad P_b(x_b);$
$\quad s= s+1;$
$\quad \text{if } (s\leq0) V_b(y_b) ;$
$\quad V_b(x_b);$

The initial values of $x_b$ and $y_b$ are respectively

  1. $0$ and $0$
  2. $0$ and $1$
  3. $1$ and $0$
  4. $1$ and $1$
edited by

8 Answers

Best answer
154 votes
154 votes

Answer is (C) .

Reasoning :-

First let me explain what is counting semaphore & How it works. Counting semaphore gives count, i.e. no of processes that can be in Critical section at same time. Here value of $S$ denotes that count. So suppose $S = 3$, we need to be able to have $3$ processes in Critical section at max. Also when counting semaphore $S$ has negative value we need to have Absolute value of $S$ as no of processes waiting for critical section.

(A) & (B) are out of option, because $Xb$ must be $1$, otherwise our counting semaphore will get blocked without doing anything. Now consider options (C) & (D).

Option (D) :-

$Yb = 1, Xb = 1$

Assume that initial value of $S = 2$. (At max $2$ processes must be in Critical Section.)

We have $4$ processes, $P1, P2, P3 \& P4.$

$P1$ enters critical section , It calls $P(s) , S = S - 1 = 1.$ As $S > 1$, we do not call $Pb(Yb)$.

$P2$ enters critical section , It calls $P(s) , S = S - 1 = 0.$ As $S >0$  we do not call $Pb(Yb).$

Now $P3$ comes, it should be blocked but when it calls $P(s) , S = S - 1 = 0-1 = -1$ As $S < 0$  ,Now we do call $Pb(Yb)$. Still $P3$ enters into critical section & We do not get blocked as $Yb$'s Initial value was $1$.

This violates property of counting semaphore. $S$ is now $-1$, & No process is waiting. Also we are allowing $1$ more process than what counting semaphore permits.

If $Yb$ would have been $0, P3$ would have been blocked here & So Answer is (C).

$Pb(yb);$

edited by
8 votes
8 votes
Answer is (c)

Xb must be 1 because both P(S) and V(S) operations perform Pb(Xb) first. So if Xb= 0 then all the processes performing these operations will be blocked.

Yb must be 0. otherwise two processes can be in critical section at the same time, when s=1 and Yb=1 . So Yb must not be 1.
edited by
5 votes
5 votes

In the given above question, we need to analyse that here counting semaphore is implemented with the help of binary semaphore.

Now let us compare both $P(s)$ code, if we see we can find that in second one they are using a binary semaphore for $s$ which implies that at a time only one process will access counting semaphore variable. 

So options a and b can be eliminated as if $x_b=0,$ then no process can access $s$.

so $x_b$ is 1 .

Now the answer can be either c or d. 

Now for $y_b$:

In the description of P(s), it is mentioned that if $s < 0,$ process must wait and so in our implementation $y_b$ must be 0 as then only $P_b(y_b)$ does wait (definition of P operation on binary semaphore). So, initial value of $y_b$ must be 0. 

So, option C.

Here $x_b$ is used to ensure that only one process access S at a time and $y_b$ ensures a wait operation if $s$ becomes negative. ($s$ being a counting semaphore it does allow multiple processes to access the critical section based on the initial value. If initial value of $s$ is 1, it becomes a binary semaphore)

 

3 votes
3 votes

option A & option B: fails coz if $x_b = 0$ initially then it's a state of deadlock, nothing happens.

option D:
question demans the functionality that if s<0 then Wait
So, if $y_b = 1$ initially then on execution of P(s) in case when $s=0$ initially; It will successfully first decrement $x_b$ then $s$ and then signal $x_b$ then decrement $y_b$ and exit. NO waiting by P(s) happened even though s<0. This failed to implement the functionality.

option C:
suggests that keep $y_b = 0$ initially; So, if P(s) is executed given that $s=0$ initially then it will be suspended on performing $P_b(y_b)$ operation, it will continue to wait until $s$ is incremented, increment of $s$ will still be possible and also functionality of resuming a sleeping process will happen. both Functionality implemented successfully here.

answer = option C

edited by
Answer:

Related questions

29 votes
29 votes
3 answers
2
Kathleen asked Sep 12, 2014
16,901 views
A process executes the following codefor(i=0; i<n; i++) fork();The total number of child processes created is$n$$2^n-1$$2^n$$2^{n+1} - 1$
23 votes
23 votes
4 answers
3
32 votes
32 votes
2 answers
4
Kathleen asked Sep 11, 2014
15,059 views
The data blocks of a very large file in the Unix file system are allocated usingcontinuous allocationlinked allocationindexed allocationan extension of indexed allocation...