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
- Semaphore
- Mutex
- 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.
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.
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
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 |