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

@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)
   {
   $V_{b}(X_{b})$
   $P_{b}(Y_{b})$
   } //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).

---

@ayushsomani

1.

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.

2.

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.

---

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?

Answer 1

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.

Answer 2

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

Answer 3

https://www.youtube.com/watch?v=PtXEcqrp6Kw&list=PL4hV_Krcqz_KyOBQEm6825QQJ6m2c1JRY&index=54

Answer 4

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.