The Gateway to Computer Science Excellence
+51 votes

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


If $s < 0$ then wait;


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:


$\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$
in Operating System by
edited by | 9.1k views
Notice -> In entire above code operation that require synchronization is increment and decrement only.

means code could be optimized as follow -->

$P(s):  P_b(x_b);  s=s−1; V_b(x_b); $

              $if (s<0)  P_b(y_b); $

$V(s): P_b(x_b); s=s+1; V_b(x_b);  $

             $if (s<=0)V_b(y_b); $

Please correct me if i am wrong.
I have a doubt here.Even in option c) when there is busy waiting the lock on xb will be held up.Isn't deadlock a possibility here?even if some wants to release the lock it can't isn't it?

@chhotu I think u are incorrect. For eg take s = 2. And assume that three processes arrive in order P0, p1, p2. And each process executes upto 3rd line of your P(s) code (i.e. Vb(xb)) and prempt. Till now s value will be -1. Now, let's say control again returns to P0 and it executes the 4th statement of P(s) i.e. if statement. So now the value of s that will be read is -1, so it will wait ; and assume all other process also resume so they will also wait. Hence no process will go in Critical section. Which should not have happned; because s = 2 initially so 2 processes should have gone in thier CS.


@Chhotu @Vishal Rana @Akash Kanase @kenzou @Arjun @srestha @Bikram @Ayush Upadhyaya @Arvnd

Can someone comment on the order of these instructions -

  1. if (s<0)
    } //Why can't I execute $P_{b}(Y_{b})$; before $V_{b}(X_{b})$; in P(S).
  2. if (s≤0)$V_{b}(Y_{b})$;
    $V_{b}(X_{b})$; //Why can't I execute $V_{b}(X_{b})$; before $V_{b}(Y_{b})$; in V(S).



If you write Pb(Yb) before Vb(Xb) that means you are calling Down on Yb which may cause this process to go to sleep before releasing the lock on Xb and in case, it happens then no other process will be able to enter P(s) or V(s). That's why we first release the lock on Xb and then call Pb so that other processes do not face any problem while accessing the P(s) or V(s) even if this process goes to sleep.


for this case, let's take an example:

if the value of S was -1 that means there is one process in the blocked queue and now when we execute S=S+1; its value will become 0 and we need to wake some sleeping process up so that it can go in the ready queue. But now, if we release the lock on Xb before calling wakeUp(executing Vb(Yb)) then In case if this process preempts right here and some other process access the P(s) then that process will make S value -1 by executing S=S-1; and it will also get blocked by IF statement in P(s), and now there are two processes in blocked queue but S=-1 says that there is only one process in blocked queue which should not happen.

6 Answers

+113 votes
Best answer

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).


edited by
@akash  @priti sharma what is change here  value of Xb or s ?
Hi Akash. What about the value of Xb when P1 enters the critical section .? and Similarly value of Xb when process P2 is about to enter the CS and when P2 has entered the CS?


Xb and Yb are binary semaphore, so value of Xb and Yb either 0 or 1 for sure. and it will not change during execution of program. Means before entering the CS, the value of Xb and Yb  will be same as when Xb and Yb leaving CS

We know
$P(s)$ :$s=s-1;$
             If $s < 0$ then wait;

to implement wait operation in code
Vb(Xb) is not take care of it.
because V is a UP operation and allow any value inside it.
This thing will take care by Pb(Yb). Where as Yb value is 0, will cause to wait for other operation
I have a doubt here.Even in option c) when there is busy waiting the lock on xb will be held up.Isn't deadlock a possibility here?even if some wants to release the lock it can't isn't it?
nice explanation @ Akash
you can hardly find such nice and simple explanation anywhere other than GO


I just want to understand what happens when P4 enters critical section?

As when P3 entered critical section value of s was -1 and P3 was blocked by binary semaphore Yb which is the expected behavior. But when P4 enters the critical section value of s becomes -2 and now even P4 is blocked by the same semaphore Yb

So when V(s) is called expected behavior is either of P3 or P4 gets unblocked but not both. But as V(s) will make Yb to 1. Both P3 and P4 gets unblocked which should not be the case.

I am able to understand until P3 enters critical section but according to me this solution fails when P4 enters. Please correct me if there is some gap in my understanding of the question.

You are contradicting your own point first you have taken s=3 then you are performing operations for s=2, may be your answer is correct but that isn't correct logic.
+6 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
"Yb must be 0. otherwise two processes can be in critical section at the same time"

How is this possible?
Consider the case when S=1 and Yb=1,

First process will arrive and successfully execute P(S) and it will enter into critical section.

Second process will arrive, Since Yb = 1 it will also execute P(S) successfully and enter into critical section.

But if we take Yb=0 then first process will enter into CS but second process will be blocked ( when it will execute Pb(Yb) ) .

So at a time only one process will be into CS.
But we don't know the order in which the processes call P(s) and V(s). Also, we are not told to solve critical section problem here. Answer is C only, but the reason should be with respect to the given definition of counting semaphore- how the binary semaphore can implement them.
Sir, the purpose of semaphore is to ensure mutual exclusion only, no? It should be implemented in such way that it ensures mutual exclusion.

So what could be the reason according to the definition of counting semaphore ?
sir Yn ensure that at any point of time when s<0 DOWN operation (P(s)) shouldn't be successful and UP operation  (V(s)) always successful irrespective of s value.
@Arjun sir , i have a doubt

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. Suppose P0,P1,P3 want to enter in critical section in order then they will call wait(); one after one and wait();is being called 3 times and S value will be 0 at this time all  3 will be there in critical section Now, if two more process P4,P5 will come and call the wait(); one afer one  then s value will be -2 and they will be block and added to list of waiting process now, suppose if P0 comes out of critical section then it will call signal(); So S will be increment to -1 and it will see that S<=0 and it will call wakeup so, the process will be unblocked in same order(P3,thenP4)

MYDOUBT>now, if P3 wants to enter in critical section then it will call wait(); and S value will be -2 but S-value<0 then how will P3 will enter in critical section it will be again added to list of processs ,and if again P4comes out of critical section then again such thing will happen,

please tell me where i am making  mistake ?
Sir, I think in this case more than one process can be inside critical section because here we are implementing Counting Semaphore.
Which portion of program is considered critical section here
+3 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)


mostly correct, but binary semaphore value going negative? S < 0, then processes must wait as per question. Now, for waiting yb must be 0.
Oh yes . binary value can take a value betwee 0 and 1 only . i got it . thanks :)
+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
Which part is considered critical section here?
0 votes
Since atleast one process should enter in the critical section the initial value should of xb should be 1 where as the initial value of yb should be zero because in v(s) there is a if condition <= 0 and in p(s) there is a point p(yb) so if the initial value of yb is 1 then in v(s) it will be 0 then it'll satisfy condition and second process will enter into c.s so yb should be 0 so that it is value should be - so that second process cantc get enter in c.s

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
52,345 questions
60,468 answers
95,271 users