Semaphores in OS

A semaphore is an integer variable S, which is used to solve critical section problems to achieve process synchronization in a cooperative multi-processing environment. Semaphore exists in the operating system (or kernel).

Race conditions can be removed by achieving process synchronization through the following software-based solutions. like

  1. Semaphore
  2. Mutex
  3. Peterson Solution

Hardware-based solutions are also available, but they are difficult to implement. Let’s explain semaphore 

Purpose of Semaphores

To prevent or remove race conditions (two processes try to win for their codes), which causes a lot of problems. For problems like incorrect response, deadlock, and other problems, there are many methods available to resolve this issue, and one of them is semaphore.

How Race Condition Is Eliminated

If cooperative processes P1 and P2 come at the same time, then one of them will get the CPU at a time. If P1 gets access to the CPU and starts executing the critical section. If, at the time of execution of the critical section, an interrupt occurs, then the CPU tries to execute the other parallel process, P2. When P2 tries to access critical access, it will be blocked because P1 is still in the critical section and still not executing its existing code. In this way, the race condition is eliminated.

Basic Components of Semaphores

1. Entrance code

When a process comes in for a critical section, then it executes the entry section code. Counting, binary, and Mutex Semaphore have their different code for entry to the Critical section. Anyone’s name for entry operation will be used

  • DOWN
  • P()
  • Wait

The basic purpose of the entry code is to decrease the Semaphore Value to 1.

2. Critical section

A common piece of code of cooperative process will be in the critical section; to enter the Critical section, every process has to execute the entrance and exit code section first.

3. Exit code

When a process comes out from the critical section, it executes the exit section code. Counting, binary, and Mutex Semaphore have their different code for exit to the Critical Section. Anyone’s name for an existing operation will be used

  • UP
  • V ()
  • Signal/POST/Release

The basic purpose of the exit code is to increment the Semaphore Value to 1.

Note: take care if DOWN is used in the entry section, then Its corresponding is UP in the exit section; in the same way that, if P () is used in the entry section, then Its corresponding is V () in the exit section. If WAIT is used in the entry section, then Its corresponding signal/POST/Release is in the exit section.

Types of semaphores 

1. Binary Semaphore(S)

The binary semaphore contains the values 0 and 1. It means only one thread can enter into a critical section at a time.

Binary semaphore

The entrance section of the counting semaphore contains the following code  

Entrance Wait() CODE

Wait (S)
  {
 IF(S.Value ==1)
{ 
    S.value=0
                 }
 ELSE   {
Sleep()  // Block this process And place in Suspended List            
  }                                   
   }

Initially S=1. It means 1 process can enter into a critical section. But the value of S will not be negative.

If the S value is given to Zero, then it means blocking all the incoming processes.

So Semaphore S is initialized with 1 in binary semaphore for the first successful operation. When Process 1 came and checked the condition was true the value of S changed to 0

EXIT Signal() CODE

Signal (S)      
 { 
IF(Suspended List is empty)  { 
S.Value=1    
}
ELSE      
  {
     Wake Up()    // Select a process From Suspended List         
   } 
}

If condition is true then value of S is incremented to 1 otherwise one process from block list is wake up.

And wake Up() directly enters into the critical section without decreasing the value of S. When the wake-up process again leaves the critical section, then check for the suspended list again. If any suspended thread is there, then repeat the previous procedure. Otherwise, semaphore S is incremented to 1.

We cannot down the value from S=0 to S=-1 because here, we are solving the question with a binary semaphore, which contains only two values, 0 and 1.

Question: if p2, p3, and p4 are in the block list and p2 is wake up by exit code, then how the other processes are unblocked?

2. Counting Semaphore

The counting semaphore contains the value from +ve infinity to –ve infinity.

counting semaphore

The entrance section of the counting semaphore contains the following code:

Entrance Wait() CODE

Wait (S)
     {          
S.Value = S.Value-1
  IF(S.value <0)  {
      Sleep()  //Block Process And put in Suspended List        
        }        
  ELSE          
       {               
  // Do Work    Return             
   }
 } 

Wait for CODE Decrement the Semaphore (S) value. Initially, S=1, and when the code executes, the S value decreases to 0. As 0<0, the condition is false, and the process enters the critical section. If here the condition is true as -1<0 condition, and the process is blocked.

If S=0, then it means no more processes can enter the critical section.

If S=4, then it means the condition will be false four times, and 4 threads of a process or different processes can enter into critical sections.

Suppose at a point where S=-4, then it means 4 times conditions are false, and 4 processes are blocked.
If we start at S=3 and run until S =-2, then the result will be 3 processes in the Critical section, and 2 processes will be in the Block list.

We can say if p1, p2, and p3 are in the critical section and p4 and 5 are in block state, then S (semaphore S value will be -2).

S value also tells us how many Instances of shared resources are available.

If S=4, then it means 4 threads can enter into a critical section and can use 4 instances of resource at a time.

Purpose Of entrance Code: Decrement Semaphore S value to 1 and block the incoming process according to condition

EXIT Signal() CODE

Signal (S)
                   {
                   S.Value = S.Value+1
IF(S.value ≤0)
                        {
Select a process from
Suspended list
Wake Up()

         }                                  

}

When the entrance process exits the critical section, the Semaphore value is incremented by 1. Now, the condition is checked. If the condition is true, then One process is WakeUP (By FIFO sequence) from the block list. It is not directly executed. If go for the ready queue first and then try again for execution as it tries for the first time.

Purpose Of exit Code: Increments Semaphore S value to 1 and unblocks the process existing in the Block list according to condition.

Look at example

Room is the resource, and 4 Rooms means there are 4 instances of resource Room.

Keys =4 means S=4

5 users are 5 threads of a resource User. Or 5 different processes

4 users get 4 keys, but 5th has to wait for their turn. This is explained in the diagram given below

Solutions of Race Conditions

 Let’s explain how two concurrent threads work in process synchronization.

Semaphore Value Thread 0 State Thread 1 State
1 Initial Section Running   Ready
1 Call P(S) Running   Ready
0 P(S) Executed By Decrement Semaphore Running   Ready
0 Critical Section: Begin

 

If(S<0) à Sleep

Else Do work

(ELSE Executed because the condition is false)

Running   Ready
0 Thread Switch à T1 Ready Initial Section Running
0   Ready Call P(S) Running
-1   Ready P(S) Executed By Decrement Semaphore Running
-1   Ready Critical Section: Begin

 

If(S<0) à Sleep

Else Do work

(IF Executed because the condition is True)

Sleeping
-1   Running Thread Switch à T0 Sleeping
-1 Critical Section end Running   Sleeping
-1 CALL V(S) Running   Sleeping
0 Increment Semaphore Running   Sleeping
0 Check Suspended List Wake T1

 

Thread 0 terminated

Running   Ready
0 Switch àT1 Ready   Running
0   Ready P(S) Return Running
0   Ready Execute the Remaining critical section and end the Critical Section Running
0   Ready CALL V(S) Running
1   Ready Increment Semaphore Running
1   Ready Check the Suspended List if any thread is available

 

Here, no thread remaining

Thread 1 Terminated

Running
1   Ready Switch à any thread wants to execute the Critical section Ready

Questions

Question 1: If S=10 and perform 6 P operation and 4 V operation, then the value of Semaphore will be 8. As, (10-6+4=8)

P operation is used in the Entrance Section, which increases the semaphore S value to 1, while the V operation is used in the Exist Section, which decreases the Semaphore S to 1.

Question 2:  If S=17 and perform 6 P operation and 3 V operation, then the value of Semaphore will be 14. As, (17-6+3=14)

Note: If a process enters into a critical section, it’s called a successful operation. If it is blocked, then it’s called an unsuccessful operation.

 Advantages of Semaphores:

  • It allows more than one thread to access the critical section
  • Semaphores are machine-independent.
  • There is never a waste of process time and resources time because there is busy waiting in semaphore.

Disadvantage of semaphores

  • One of the biggest limitations of a semaphore is priority inversion.
  • The operating system has to keep track of all calls to wait and signal semaphore.
  • Semaphore programming is complicated to implement for achieving mutual exclusion.
  • It may cause a deadlock or violation of mutual exclusion due to programmer error.

Comparison between Binary and Counting Semaphore

Binary Semaphore Counting Semaphore
Mutual exclusion present No mutual exclusion
Value only 0 and 1 Any integer value
It has a mutual exclusion mechanism. Provide a set of Processes
Only one slot More than one slot