FOR FREE CONTENT

Binary Semaphore and NET-GATE question

Binary Semaphore

In binary semaphore, unlike counting semaphore only one process can allow at critical section.

In the case of counting semaphore, it counting that how many processes are in the critical section and how many processes are in the suspended list (blocked).

But in the case of binary semaphore, there is no counting mechanism; there are only two values 0 and 1. Because not more than one process is entered into the critical section at a time.

stractbinary_semaphore

{ enum value (0, 1) // contain only two value as binary.

queuetypequeuelist;

}

Note: Wait and Signal is the same as the Down and Up operation.

Some important point for Binary Semaphore operation: 

1. A binary semaphore may be initialized to 0 or 1.

2. B_Wait() function called when one process tries to enter into a critical section. The B_Wait operation checks the semaphore value. If the value is zero (critical section is not empty), then the process executing the B_Wait is blocked (Not allowed to enter into the critical section). If the value is one (critical section is free), then the value is changed to zero, enter into the critical section, and continues executing.

3. B_Signal() function called when one process leaves the critical section. When one process leaves the critical section, the B_Signal operation checks to see if any processes are blocked on this semaphore queuelist (semaphore value equals 0). If so, then select the process which is blocked by Wait operation from the semaphore queuelist and unblocked it. If no processes are blocked, then the value of the semaphore is set to one.

Q. UGC 2013 (July – PIII)

Suppose S and Q are two semaphores initialized to 1. P and Q are two processes that are sharing resources. 

P1                                             P2

Wait(S);                             Wait(Q);

Wait(Q);                               Wait(S);

CS1                                        CS2

Signal(S);                              Signal(Q);

Signal(Q);                             Signal(S);                             

This execution may lead to an undesirable situation called

(a) Starvation (b) Race Condition (c) Multi-threading (d) Deadlock

Answer: 

From the question, it is clear that the concept is a binary semaphore where only one process allows at the critical section.

We know Wait and Signal is the same as Down and UP or P and V. All are atomic instructions mean to check the instruction for critical section entry and decrease or set the value.

Here Wait operation check the semaphore value is 1 or not. If it is 1 then allow the process to go into a critical section and set the semaphore variable to 0. If it is not 1, then blocked the operation.

So, the wait operation cannot execute by two processes together for a semaphore variable. If one process already runs a Wait operation, then for the next process Wait operation will be blocked for the same semaphore variable.

Signal operation, simply open the critical section to set the semaphore variable to 1. It has no restriction that more than one process can run a Signal operation together for the same semaphore variable.

Let take an example to check which kind of undesirable situation will occur.

So, Two processes P1 and P2are blocked forever. It a deadlock.

Option D is correct.

Q. Gate 97

Each Process Pi, i = 1....9 is coded as follows

Mutex=1 (initially)

repeat

   P(mutex)

   {Critical section}

   V(mutex)

forever

The code for P10 is identical except it uses V(mutex) in place of P(mutex). The initial value of the binary semaphore is 1. What is the largest number of processes that can be inside the critical section at any moment?

A.2     

B. 9 

C.10   

D. None 

Answer:

As per the above given code:

P and V same as the Down and Up operation. 

Initially mutex = 1 (Binary variable).

Process P1 executes the P(mutex) operation and enters into the critical section. So, right now mutex = 0.

Now no other process can perform P operation i.e. P2 to P9 no processes can enter into the critical section until P1 is finished. 

Now code of P10 is interesting, at the beginning, it executes V(mutex) operation so, mutex = 1 (critical section is free), so immediately blocked process P2 enter into CS by using P(mutex).

Same way when P10 exits the critical section up(mutex) call again.

So, next block process P3 enter into a critical section and same way P10 enter Process is in while (1) so, it working continuously and all process P2 to P9 came into CS and last by P10.

So, due to a wrong code for P10, maximum all process P1 to P10 enter and inside the critical section at a time.

Option C correct.