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.

The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+25 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 <=0$ 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):$ | $P_b(x_b); \\ \text{ } s = s-1; \\ \text{ if } (s<0) \:\{ \\ \text{ } V_b(x_b); \\\text{ } P_b(y_b); \\ \} \\ \text{ else } V_b(x_b); $ |

$ V(s):$ | $P_b(x_b); \\\text{ } s= s+1; \\ \text{ if } (s<=0) V_b(y_b) ; \\\text{ } V_b(x_b);$ |

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

- 0 and 0
- 0 and 1
- 1 and 0
- 1 and 1

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

Pb(yb);

0

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?

+1

@Ayush

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

+5 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.

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.

+2

"Yb must be 0. otherwise two processes can be in critical section at the same time"

How is this possible?

How is this possible?

+2

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.

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.

+2

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.

+2 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)

+2 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**

- All categories
- General Aptitude 1.2k
- Engineering Mathematics 4.9k
- Digital Logic 2k
- Programming & DS 3.6k
- Algorithms 3k
- Theory of Computation 3.9k
- Compiler Design 1.5k
- Databases 2.9k
- CO & Architecture 2.5k
- Computer Networks 2.9k
- Non GATE 949
- Others 1.3k
- Admissions 408
- Exam Queries 419
- Tier 1 Placement Questions 17
- Job Queries 55
- Projects 9

34,780 questions

41,758 answers

118,934 comments

41,400 users