Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Process Synchronization
2.1.
Race Condition
2.2.
Critical Section
2.2.1.
The solution to a critical section problem
3.
Semaphores
3.1.
Counting Semaphore
3.2.
Binary Semaphore
4.
Advantages and Disadvantages of Semaphores
4.1.
Advantages of Semaphores
4.2.
Disadvantages of Semaphores
5.
Frequently Asked Questions
5.1.
What is a spinlock in an operating system?
5.2.
What are monitors in an operating system?
5.3.
Is there a solution to the spinlock problem in semaphore?
6.
Conclusion
Last Updated: Mar 27, 2024

Semaphores in OS

Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @
Operating Systems

Introduction

The term semaphore has constantly disrupted students. This is one of the most important concepts of an operating system and plays a vital role in achieving process synchronization in a multiprogramming environment.

This blog will help you in getting a better understanding of the topic. Before moving on, let’s first understand some other important concepts that might come in handy while understanding the semaphores better.

Also see: Multiprogramming vs Multitasking, Open Source Operating System

Process Synchronization

A process is defined as a program under execution.

The process is classified into two types based on the synchronization:

  1. Independent Process- Execution of one process does not depend on any other process.
  2. Cooperative Process- Execution of one process affects the other processes. In this case synchronization problem arises because resources are shared between processes.

In a multiprogramming environment, when multiple processes are present, all the processes need to be synchronized in an appropriate order to avoid deadlock or maintain the process's credibility so that incorrect output is not produced.

Race Condition

When two or more processes try to read, write over the same data or work on the same shared variable, there is a possibility that it may produce an incorrect output as it depends on the order in which access takes place.

Such a type of race condition can occur in the critical section. To avoid such a situation, we need to treat the critical section to use atomic instruction, which can be done using process synchronization and introducing locks or atomic variables.

Critical Section

It is a region in a program containing shared variables and can lead to race conditions. To avoid that, we must ensure that only one process is executed instantly by introducing a proper synchronized schedule and locks to maintain the consistency of the data.

Process Structure

 

The solution to a critical section problem

Any solution to a Critical Section problem must satisfy three conditions:

  1. Mutual Exclusion: If a process is already present in the critical section, another process cannot enter into the critical section.
  2. Progress: If no process is executing in CS, and other processes are present outside CS, then the processes not executing in their remainder section can participate in deciding which process will move to CS in such a way that it does not create a situation of indefinite postponement.
  3. Bounded waiting: Bound must exist on a given process that decides the number of times it can enter the critical section.

 

Semaphore is one of the solutions to the critical section problem.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Semaphores

A semaphore is an integer variable that works on a signaling mechanism and can be accessed only through two operations: wait()/Down()/p() and signal()/up()/v().

Wait()- Helps in controlling the entry of processes in CS. The operation decrements the value of its argument as soon as a process enters the critical section.

Signal()- Helps control the process's exit after execution from CS. Increment the value of its argument as soon as the execution is finished.

There are two types of semaphores:

  1. Counting Semaphore
  2. Binary Semaphore

Counting Semaphore

They can have any integer value, which is not restricted to a specific range.

This semaphore can be used when we need to have two or more processes in the critical section simultaneously. It depends on the count variable of the semaphore that helps the task be acquired or released numerous times.

Consider the below code:

int count=n;			// number of processes we want to occur simultaneously
Wait (Semaphore S)  
{  
    count = count - 1;	//count value will get decreased when a new process enter  
    if (count< 0)  
    {    
        Sleep();		//the process will get into the blocked state. 
    }  
    else  
        return;  
}  


Signal (Semaphore s)  
{  
    count=count+1;		//count value will get increased when process is executed  
    if(count<=0)  
    {   
        Wake();			//if count>=0, then wake one of the processes in the blocked queue.                      
    }   
}  

 

Illustration Image

 

Here, the count value indicates the maximum number of processes that can enter the critical section at a given instant. The processes present in the blocking queue wake in the same order as they are stored.

Binary Semaphore

In this semaphore type, only two values, i.e., 0 and 1, are possible either the process would enter the CS or not only these two possibilities are present.

Consider the following code:

Wait(semaphore S)   
{  
    if (value == 1) 	// if a slot is available in the CS process can enter   
    {  
        value = 0;  	// initialize the value to 0 so that no other process can enter for now.   
    }  
    else  
    {  
        Sleep ();   	//if the value is one, let the process wait in the blocked queue.   
    }  
}  
Signal(semaphore S)   
{  
    If (queue is empty) // no process is present.     
    {  
        value=1;   
    }  
    else  
    {   
        Wake(); 		// if not empty, then wake the first process of the blocked queue.   
    }   
}  

Advantages and Disadvantages of Semaphores

Advantages of Semaphores

  1. Semaphores strictly follow the mutual exclusion principle and only one process in the critical section. They are much more efficient than other techniques for process synchronization.
  2. They are machine-independent.
  3. Due to busy waiting in semaphore, there is no resource wastage.
  4. Allow flexible management of resources.

 

Disadvantages of Semaphores

  1. They allow only one process to enter the critical section. The other process is waiting for the critical section to get free checks on the semaphore value 's' to become zero again, continuously checking on it, wasting CPU cycles.
  2. The operating system has to keep track of all the wait and signal calls in the semaphore.
  3. They may lead to a priority inversion problem where the process with low priority enters the critical section first, then that of high priority.
  4. This is not a practical method for large-scale applications as their use leads to loss of modularity.
  5. Semaphores must be implemented in the correct order to avoid deadlock.

 

Must Read Evolution of Operating System

Must Read Process Management in OS

Frequently Asked Questions

What is a spinlock in an operating system?

It is a type of lock that causes a thread trying to acquire it to wait in a loop while repeatedly checking whether the lock is available or not.

What are monitors in an operating system?

Monitors are the constructs of a programming language that helps control shared data access. It is a module that encapsulates the shared data, and procedures inside it.

Is there a solution to the spinlock problem in semaphore?

We can add all those processes in a waiting queue waiting for the critical section to get free. This is done through a block() call, and whenever a process gets executed in CS, it sends a wake-up call() to the queue, and the one process is given the critical section.

Conclusion

This article discussed semaphores in the operating system, and all the information one needs to know about them.

Recommended Readings:


Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Previous article
Communication between Two Processes using Signals
Next article
Difference between Spinlock and Semaphore
Live masterclass