Semaphore | Semaphore in OS | Counting Semaphore

Process Synchronization-

 

Before you go through this article, make sure that you have gone through the previous article on Process Synchronization.

 

We have discussed-

• Process Synchronization provides a synchronization among the processes.
• Synchronization mechanisms allow the processes to access critical section in a synchronized manner.
• This avoids the inconsistent results.

 

Semaphores in OS-

 

• A semaphore is a simple integer variable.
• It is used to provide synchronization among multiple processes running concurrently.

 

Types of Semaphores-

 

There are mainly two types of semaphores-

 

 

1. Counting Semaphores
2. Binary Semaphores or Mutexes

 

In this article, we will discuss about Counting Semaphores.

Learn about Binary Semaphores.

 

Counting Semaphores-

 

A counting semaphore is implemented as-

 

struct semaphore
{
   int value;
   Queue type L;
}

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

Signal (semaphore s)
{
   s.value = s.value + 1;
   if (s.value <=0 )
   {
       select a process (PCB) from L;
       wake up();
   }
}

 

Explanation-

 

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

 

Point-01:

 

A counting semaphore has two components-

• An integer value
• An associated waiting list (usually a queue)

 

Point-02:

 

The value of counting semaphore may be positive or negative.

• Positive value indicates the number of processes that can be present in the critical section at the same time.
• Negative value indicates the number of processes that are blocked in the waiting list.

 

Point-03:

 

• The waiting list of counting 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-04:

 

• The wait operation is executed when a process tries to enter the critical section.
• Wait operation decrements the value of counting semaphore by 1.

 

Then, following two cases are possible-

 

Case-01: Counting Semaphore Value >= 0

 

• If the resulting value of counting semaphore is greater than or equal to 0, process is allowed to enter the critical section.

 

Case-02: Counting Semaphore Value < 0

 

• If the resulting value of counting semaphore is less than 0, process is not allowed to enter the critical section.
• In this case, process is put to sleep in the waiting list.

 

Point-05:

 

• The signal operation is executed when a process takes exit from the critical section.
• Signal operation increments the value of counting semaphore by 1.

 

Then, following two cases are possible-

 

Case-01: Counting Semaphore <= 0

 

• If the resulting value of counting semaphore is less than or equal to 0, a process is chosen from the waiting list and wake up to execute.

 

Case-02: Counting Semaphore > 0

 

• If the resulting value of counting semaphore is greater than 0, no action is taken.

 

Point-06:

 

• By adjusting the value of counting semaphore, the number of processes that can enter the critical section can be adjusted.
• If the value of counting semaphore is initialized with N, then maximum N processes can be present in the critical section at any given time.

 

Point-07:

 

• To implement mutual exclusion, the value of counting semaphore is initialized with 1.
• It ensures that only one process can be present in the critical section at any given time.

 

Point-08:

 

In a system,

• Consider n units of a particular non-shareable resource are available.
• Then, n processes can use these n units at the same time.
• So, the access to these units is kept in the critical section.
• The value of counting semaphore is initialized with ‘n’.
• When a process enters the critical section, the value of counting semaphore decrements by 1.
• When a process exits the critical section, the value of counting semaphore increments by 1.

 

In such scenarios, value of counting semaphore is initialized with value greater than 1.

 

Point-09:

 

• Other names by which wait operation may be referred : Down operation, P operation.
• Other names by which signal operation may be referred : Up operation, V operation, Release operation.

 

To gain better understanding about Counting Semaphores,

Watch this Video Lecture

 

Next Article- Practice Problems On Counting Semaphores

 

Get more notes and other study material of Operating System.

Watch video lectures by visiting our YouTube channel LearnVidFun.