GATE CSE 2008 | Question: 63

Question

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

• A. $0$ and $0$
• B. $0$ and $1$
• C. $1$ and $0$
• D. $1$ and $1$

Comments

I have a doubt here :-

=============================

Lets 4 process are there P0 to P3 and S=2.

P0 and P1 successfully call P(S) and S become 0.

---------

P2, P3 call P(S), S becomes -2.  Because of s<0 goes into if condition calls Vb(Xb) and got preempted.

----------

Now P0 after executing CS, calls V(S). S becomes  S = -2+1=-1. Vb(Yb) gets called. Binary semaphore queue is empty so none to wake up. Yb value becomes Yb= 0+1=1.

Next P1 after executing CS calls V(S). S becomes S= -1+1=0. Vb(Yb) gets called. Yb value still remains 1. Because binary semaphore.

---------

Now P0 again starts exeution from where it got preempted. And calls Pb(Yb). Yb values becomes Yb= 1-1=0. P0 goes to execute CS.

Same way P1 starts executing from where it got preempted and call Pb(Yb). Now Yb is 0 so it waits in binary semaphore queue until P0 completes executing CS and makes Yb 1 again.

But according to our counting semaphore 2 processes can be there in the CS. But in this last scenario it is allowing only 1.

==================

Is there any wrong concept in this doubt?

Can anyone please help out?

---

We are using binary semphores not counting semaphores.

---

Purpose of $y_b$

$y_b$ is used as a blocking synchronization mechanism (a sleep queue). It is responsible for making a process "wait" (or sleep) when the counting semaphore $s$ has no available permits, and it acts as the "signal" to wake that process up when a permit finally becomes available.

Answer 1

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);$

Comments

Got so much clarity on counting semaphore. Thanks for the wonderful answer akash sir.

---

@srestha Mam,I understood the concept but in this question from where did the critical section code started?

---

I have a doubt take for instance s=-2 and i wish to perform wait operation hence i will go to P(s) now it will execute first instruction i.e. Xb=0 for that reason Xb should be initially 1 thats fine.

But when it will do s-- the value of s will be -3 and since it is less than 0 it will enter the  if clause now here the first instruction is signal() of Xb,Now Xb=1 and next instruction is:wait on Yb if Yb is initially 0 then how will it perfrom wait on Yb?

it will get blocked right?

Answer 2

Answer is (C).

So, there has been a question in the comment section, where is the Critical Section here.
Critical Section always be in the middle of P(s) and V(s).
So, basically the code block should look like below – 

P(s):

Pb(xb); s=s−1; if (s<0) {     Vb(xb);     Pb(yb); } else  Vb(xb);

========================
Critical Section 
========================
 

V(s):

Pb(xb); s=s+1; if (s≤0)     Vb(yb);     Vb(xb);

Now, to solve the question, we can assume whatever the value we want for ‘s’
Let’s say, I’m assuming the value of s = 3 which means maximum 3 processed can be inside the Critical Section at any point of time.

Now, Process P1 comes and it executes in the below manner – 

Step 1: P1 executes the Pb(Xb) and makes the value of Xb = 0 (Binary Semaphore, Xb value must have to be 1 initially, else no process can get into the code block)
Step 2: s = s – 1;   –  So, I assumed initially ‘s’ value as 3 and now, ‘s’ value would 2
Step 3: if(s < 0)      –  This block doesn’t execute since value ‘s’ is not less than 0
Step 4: else Vb(Xb);  – Yes, this block is executed and again Xb becomes available for a next process with it’s value as 1
Step 5: P1 gets into the Critical Section happily :) 

 

Now, Process P2 comes and it executes in the below manner – 

Step 1: P2 executes the Pb(Xb) and makes the value of Xb = 0 
Step 2: s = s – 1;   –  So, new ‘s’ value would be 1 from 2
Step 3: if(s < 0)      –  This block doesn’t execute since value ‘s’ is not less than 0
Step 4: else Vb(Xb);  – Yes, this block is executed and again Xb becomes available for a next process with it’s value as 1
Step 5: P2 also gets into the Critical Section happily and with a big smile :) 

 

Now, Process P3 comes and it executes in the below manner – 

Step 1: P3 executes the Pb(Xb) and makes the value of Xb = 0 
Step 2: s = s – 1;   –  So, new ‘s’ value would be 0 from 1
Step 3: if(s < 0)      –  This block doesn’t execute since value ‘s’ is not less than 0
Step 4: else Vb(Xb);  – Yes, this block is executed and again Xb becomes available for a next process with it’s value as 1
Step 5: P3 also gets into the Critical Section

 

Now, Process P4 comes and it executes in the below manner – (From here the actual DRAMA begins)

Step 1: P3 executes the Pb(Xb) and makes the value of Xb = 0 
Step 2: s = s – 1;   –  So, new ‘s’ value would be -1 from 0
Step 3: if(s < 0)      –  Now, this block gets execute since value ‘s’ is less than 0
Step 4: Vb(xb);   –  So, new value of Xb would be 1 again and makes itself available for the next process
             Pb(Yb);  –  Now, if we keep the Value of Yb as 1, then it would be DANGEROUS. Because, then Yb value would be 0 from 1 due to the Pb wait operation and the total IF() block would be successfully executed.
And, Process P4 will also get into the Critical Section.
That means, even though we assumed the value of S=3 initially, still total 4 process have gone inside the Critical Section, which is against the definition/property of Counting Semaphore.

So, Yb has to be 0 and that way, P4 can’t execute the IF() block successfully and keeps executing that and stays in the Wait queue, till a process doesn’t come out of the Critical Section.

Conclusion:

No way value of Binary Semaphore (or, Mutex) Xb can be 0. Then no process would be able to get into the code block and this whole design in the question would be useless.

No way value of Mutex, Yb can be 1. Then, then it would be against the property of the Counting Semaphore.

N.B.: The main funda of this question is, preparing a Counting Sempahore using 2 Binary Semaphores. It is an exclusive example of this funda.

Comments

Thank you so much. Explained very clearly… Can be able to understand easily.. Thank u.

---

kitna acha se explain kiya h easy lang. me as compared to others thank u very much

 

---

maza aagya thank you so much

---

Clear Explaination !!

---

In "Drama" part, in step 1 there should be P4 instead of P3 right?

---

Thanks You very much 🙏🙏

---

best explanation

---

best answer , thnx buddy...

Answer 3

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.

Comments

@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

Answer 4

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)

 

Comments

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

---

:D

Answer 5

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

Comments

Which part is considered critical section here?

Answer 6

This question was asked in gate 2008 in a different way.Anyway it will clear ur doubt I hope otherwise I will try to explain further.It is actually the implementation of a counting semaphore by 2 binary semaphores:

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 wakeup a process waiting on s;  

Assume that Pb and Vb the wait and signal operations on binary semaphores are provided. Two binary semaphores Xb and Yb are used to implement the semaphore operations P(s) and V(s) as follows:

P(s) : Pb(Xb);    
s = s - 1;
if (s < 0) {
    Vb(Xb) ;
    Pb(Yb) ;
    }
else Vb(Xb);
V(s) : Pb(Xb) ;
s = s + 1;
if (s <= 0) Vb(Yb) ;
Vb(Xb) ;  

The initial values of Xb and Yb are respectively
(A) 0 and 0
(B) 0 and 1
(C) 1 and 0
(D) 1 and 1

Answer (C)
Both P(s) and V(s) operations are perform Pb(xb) as first step. If Xb is 0, then all processes executing these operations will be blocked. Therefore, Xb must be 1.
If Yb is 1, it may become possible that two processes can execute P(s) one after other (implying 2 processes in critical section). Consider the case when s = 1, y = 1. So Yb must be 0.