Semaphore | Semaphore in OS | Binary Semaphore

Semaphores in OS-

 

Before you go through this article, make sure that you have gone through the previous article on Semaphores in OS.

 

We have discussed-

• A semaphore is a simple integer variable used to provide synchronization among the processes.
• There are mainly two types of semaphores-

 

 

In this article, we will discuss about Binary Semaphores.

 

Binary Semaphores-

 

A binary semaphore is implemented as-

 

struct semaphore
{
   enum value (0,1);
   Queue type L;
}

Wait (semaphore s)
{
   if (s.value == 1)
   {
      s.value=0;
   }
   else
   {
      put process (PCB) in s.L;
      sleep();
   }
}

Signal (semaphore s)
{
   if (s.L is empty)
   {
      s.value=1;
   }
   else
   {
       select a process (PCB) from s.L;
       wake up();
   }
}

 

Explanation-

 

The above implementation of binary semaphore has been explained in the following points-

 

Point-01:

 

A binary semaphore has two components-

• An integer value which can be either 0 or 1
• An associated waiting list (usually a queue)

 

Point-02:

 

• The waiting list of binary semaphore contains the processes that got blocked when trying to enter the critical section.
• In waiting list, the blocked processes are put to sleep.
• The waiting list is usually implemented using a queue data structure.
• Using a queue as waiting list ensures bounded waiting.
• This is because the process which arrives first in the waiting queue gets the chance to enter the critical section first.

 

Point-03:

 

• The wait operation is executed when a process tries to enter the critical section.
• Then, there are two cases possible-

 

Case-01: Binary Semaphore Value = 1

 

If the value of binary semaphore is 1,

• The value of binary semaphore is set to 0.
• The process is allowed to enter the critical section.

 

Case-02: Binary Semaphore Value = 0

 

If the value of binary semaphore is 0,

• The process is blocked and not allowed to enter the critical section.
• The process is put to sleep in the waiting list.

 

Point-04:

 

• The signal operation is executed when a process takes exit from the critical section.
• Then, there are two cases possible-

 

Case-01: Waiting List is Empty-

 

• If the waiting list is empty, the value of binary semaphore is set to 1.

 

Case-02: Waiting List is Not Empty-

 

• If the waiting list is not empty, a process is chosen from the waiting list and wake up to execute.

 

Point-05:

 

Binary semaphores are mainly used for two purposes-

• To ensure mutual exclusion.
• To implement the order in which the processes must execute.

 

Example-

 

Wait (S1) Process P1 Signal (S2)

Process P2 Signal (S1)

Wait (S2) Process P3

 

In this example-

• Two binary semaphores S1 and S2 both initialized with 0 are used.
• The execution order of the processes is P2 → P1 → P3.

 

To gain better understanding about Binary Semaphores,

Watch this Video Lecture

 

Next Article- Practice Problems On Binary Semaphores

 

Get more notes and other study material of Operating System.

Watch video lectures by visiting our YouTube channel LearnVidFun.