Semaphores in OS

In Operating Systems (OS), process synchronization plays a vital role in ensuring that multiple processes or threads can access shared resources without conflicts. One of the most powerful tools used for synchronization is the Semaphore 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. 

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

Process Synchronization ensures that multiple processes access shared resources in a controlled and conflict-free manner. Synchronization can be achieved through hardware and software solutions.

• Hardware-based solutions include:

  • Test-and-Set instruction

  • Swap instruction

  • Interrupt disabling

• Software-based solutions include:

  • Peterson’s Algorithm

  • Bakery Algorithm

  • Turn variable method

These traditional methods have limitations such as complexity, limited scalability, and busy waiting. To overcome these issues, the Semaphore was introduced as a kernel-level synchronization mechanism.

Basic Components of Semaphores

A semaphore manages access to shared resources through three main components: the Entry Section (Wait Operation), the Critical Section, and the Exit Section (Signal Operation). These components work together to ensure the safe and synchronized execution of processes.

1. Entry Section (Wait Operation)

When a process wants to enter the critical section, it must first execute the entry section code.
This code ensures that only permitted processes can access the shared resource at a time.

• The entry operation is commonly known as wait(), P(), or down(), depending on notation or system convention.

• The main purpose of this operation is to decrease the semaphore value by 1.

• If the semaphore value becomes less than zero, it indicates that no resource is available, and the process must wait (block) until another process releases the resource.

The exact form of the entry code can vary based on the type of semaphore used:

• Binary Semaphore / Mutex: Allows only one process in the critical section.

• Counting Semaphore: Allows multiple processes based on available resource count.

2. Critical section

The critical section is the part of a program where a process accesses shared resources, such as variables, files, or devices.
All cooperating processes contain a common segment of code that requires exclusive access to prevent data inconsistency.

• Before entering the critical section, a process must successfully execute the entry section (to obtain permission).

• After completing its operations inside, it must execute the exit section (to release the resource).

• This ensures that only one process (or a limited number, in case of counting semaphores) can execute the critical section at any given time.

3. Exit Section (Signal Operation)

When a process leaves the critical section, it executes the exit section code. This section ensures that other waiting processes can enter the critical section safely and in order.The exit operation may be referred to by different names depending on the system or notation used, such as signal(), V(), up(), post(), or release().

• The main purpose of the exit code is to increment the semaphore value by 1, indicating that a resource or access slot has been released.

• This allows another waiting process (if any) to enter the critical section.

• The implementation of the exit operation can vary depending on the type of semaphore (counting, binary, or mutex).

Types of Semaphores 

Semaphores are divided into types based on how they control access to shared resources. The two main types are Binary Semaphores and Counting Semaphores, used for process synchronization and resource management.

1. Binary Semaphore(S)

A Binary Semaphore can take only two values: 0 and 1, representing locked and unlocked states, respectively.
It ensures that only one process can enter the critical section at a time, making it ideal for mutual exclusion.

Entrance (Wait) Operation

Signal(S)
{
     if (Suspended_List is empty) {
                  S.value = 1; // Unlock the semaphore
     }
    else {
                 WakeUp(); // Wake one process from the suspended list
          }
}

Explianation

• Initially, S = 1, meaning one process can enter the critical section.
• When a process enters, it sets S = 0, locking the semaphore.
• If another process tries to enter while S = 0, it is blocked and placed in the suspended (waiting) list.
• The value of S in a binary semaphore is never negative.

Exit (Signal) Operation

Signal(S) {
                       if (Suspended_List is empty) {
                                    S.value = 1; // Unlock the semaphore
                               }
                      else {
                                 WakeUp(); // Wake one process from the suspended list

                           }
              }

Explanation:

• If no process is waiting, S is set back to 1, making the resource available again. If there are blocked processes, one process (for example, P2) from the suspended list is woken up.

• The woken-up process directly enters the critical section.

Important Notes

• In a binary semaphore, S can only be 0 or 1 — it cannot go negative.
• The semaphore is initialized as S = 1 to allow the first process to enter.
• If S = 0, all incoming processes are blocked until it becomes 1 again.

2. Counting Semaphore

A Counting Semaphore can take integer values ranging from positive to negative infinity.
It is used when multiple instances of a shared resource are available. The semaphore value represents how many processes can access the resource at a given time.

Entrance Section in Counting Semaphore

The Entrance Section in a Counting Semaphore decreases the semaphore value by one each time a process requests access. If the value becomes negative, the process is blocked and placed in the waiting list until resources become available.

Code:

Wait(S) {
                S.value = S.value – 1;
               if (S.value < 0){
                                             Sleep(); // Block the process and place it in the suspended list
                                         }
              else  {
                         // Allow the process to enter the critical section
                  }
    }

Explaination:

• The wait() operation decrements the semaphore value by 1.
• If S.value ≥ 0, the process can enter the critical section.
• If S.value < 0, the process is blocked and moved to the suspended (waiting) list.
• The semaphore value S indicates the number of available instances of a resource.

Example:

• If S = 0, no more processes can enter the critical section.
• If S = 4, up to 4 processes can access the critical section simultaneously.
• If S = -2, it means 2 processes are waiting in the blocked list.

Thus, the value of S gives an idea of both available resources (positive values) and waiting processes (negative values).

Exit Section in Counting Semaphore

The Exit Section in a Counting Semaphore increases the semaphore value by one when a process leaves the critical section. If any processes are waiting, one of them is unblocked and moved to the ready queue to attempt entering the critical section.

Code:

• When a process leaves the critical section, the signal() operation increments the semaphore value by 1.

• If S.value ≤ 0, it means some processes are waiting, so one blocked process is woken up (typically using FIFO order).

• The woken-up process is placed in the ready queue and will reattempt to enter the critical section when scheduled again.

Key Points

• Counting semaphores manage multiple resources simultaneously.
• Positive S value: number of available resources.
• Negative S value: number of waiting (blocked) processes.
• Ensures efficient process synchronization and resource utilization without conflicts.

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

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

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.

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.

Comparison between Binary and Counting Semaphore