Semaphores in OS

A semaphores is an integer variable S which is use to solve critical section problems to achieve process synchronization in cooperative multi-processing environment. Semaphore exists at operating system (or kernel).

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

  1. Semaphore
  2. Mutex
  3. Peterson Solution

Hardware base solutions also available but they are difficult to implement. Lets explain semaphore 

Purpose of Semaphores

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

How Race Condition Is Eliminated

If co-operative processes P1 and P2 came at the same time then one of them will get the CPU at a time. And If P1 get access to CPU and start executing the critical section. If at the time of execution of critical section an interrupt is occur then CPU try to execute the other parallel process P2. When P2 tries to access critical access then it will be blocked because P1 is still in critical section and still not execute it’s exist code. In this way race condition is eliminated.

Basic components of Semaphores

1. Entrance code

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

  • DOWN
  • P()
  • Wait

Basic purpose of entry code is to decrement the Semaphore Value to 1.

2. Critical section

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

3. Exit code

When a process is came out from critical section then it executes the exit section code. Counting, binary, and Mutex Semaphore have their different code for exit to Critical Section. Anyone name for exist operation will be used

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

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

Note: take care if DOWN use in entry section then It’s correspond is UP in exit section, in the same way of if P () use in entry section then It’s correspond is V () in exit section. If WAIT is use in entry section then It’s correspond is signal/POST/Release in exit section.

Types of semaphores 

1. Binary Semaphore(S)

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

Binary semaphore

Entrance section of 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 critical section. But the value of S will not be negative.

If S value is given to Zero then it means block all the incoming process.

So Semaphore S is initialized with 1 in binary semaphore for first successful operation. When Process 1 came and check then condition is true  then 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() is directly enter into critical section without decrement the value of S. when wake Up process again leave the critical section then again check for suspended list if any suspend 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 question with binary semaphore which contains only two values 0 and 1

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

2. Counting Semaphore

Counting semaphore contains the value from +ve infinity to –ve infinity.

counting semaphore

Entrance section of 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 CODE Decrement the Semaphore (S) value. Intialy S=1 and when code executes then S value decrement to 0. As 0<0 condition false and process enter to critical section. If here the condition true as -1<0 condition true and process is block.

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

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

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

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

S value also tells us how many Instance of shared resource are available.

If S=4 then it means 4 threads can enter into 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 is exit the critical section then Semaphore value is incremented by 1. Now condition is checked if condition is true then One process is WakeUP (By FIFO sequence) from block list. It is not directly execute. If go for ready queue first and then try again for execution as it tries for first time.

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

Look at example

Room is the resource and 4 Rooms means there are 4 instance 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 have to wait for his turn. More explain in diagram given below

Solutions of Race Conditions

 Let’s explain, how two concurrent threads works 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 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 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 Remaining critical section and end Critical Section Running
0   Ready CALL V(S) Running
1   Ready Increment Semaphore Running
1   Ready Check Suspended List if any thread is available

 

Here no thread remaining

Thread 1 Terminated

Running
1   Ready Switch à any thread want to execute Critical section Ready

Questions

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

P operation is used in Entrance Section  which  increase the semaphore S value to 1 while  V operation is used in Exist Section which  decrease the Semaphore S to 1.

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

Note: If a process enter into critical section it’s called successful operation if it is blocked then it’s called unsuccessful operation.

 Advantages of Semaphores:

  • It allows more than one thread to access the critical section
  • Semaphores are machine-independent.
  • There is never the wastage 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 a complicated to implement for achieving mutual exclusion.
  • It may cause 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

 

Help Other’s By Sharing…

Contact Us

Burewala, Vehari, Punjab, Pakistan

cstaleem1@gmail.com

Website: CStaleem.com

Pin It on Pinterest