Semaphore in OS

What is Semaphore in OS?

A semaphore in an operating system is an integer variable used to control access to a shared resource by multiple processes. Two atomic operations act on it: wait (P), which decrements it before a process enters its critical section, and signal (V), which increments it on exit. A binary semaphore holds 0 or 1; a counting semaphore counts N instances.

Dijkstra introduced semaphores as a synchronization mechanism, with P and V referring to the Dutch words proberen (try) and verhogen (increase).

Concurrent Processes are those processes that are executed simultaneously or parallel and might or might not be dependent on other processes. Process Synchronization can be defined as the coordination between two processes that has access to common materials such as a common section of code, resources or data, etc.

For example: There may be some resource that is shared by 3 different processes, and none of the processes at a certain time can change the resource, since that might ruin the results of the other processes sharing the same resource. You'll understand it more clearly soon.

Now, this Process Synchronization is required for concurrent processes. For any number of processes that are executing simultaneously, let's say all of them need to access a section of the code. This section is called the Critical Section.

Now that you are familiar with these terms, we can move on to understanding the need for Semaphores with an example.

We have 2 processes, that are concurrent and since we are talking about Process Synchronization, let's say they share a variable "shared" which has a value of 5. What is our goal here? We want to achieve mutual exclusion, meaning that we want to prevent simultaneous access to a shared resource. The resource here is the variable "shared" with the value 5.

Process 1

Process 2

We start with the execution of process 1, in which we declare a variable x which has initially the value of the shared variable which is 5. The value of x is then incremented, and it becomes 6, and post that the process goes into a sleep state. Since the current processing is concurrent, the CPU does not wait and starts the processing of process 2. The integer y has the value of the shared variable initially which is unchanged, and is 5.

Then we decrement the value of y and process 2 goes into a sleep state. We move back to process 1 and the value of the shared variable becomes 6. Once that process is complete, in process 2 the value of the shared variable is changed to 4.

One would think that if we increment and decrement a number, its value should be unchanged and that is exactly what was happening in the two processes, however in this case the value of the "shared" variable is 4, and this is undesired.

For example: If we have 5 resources and one process uses it, decrementing its value by 1, just like in our example -- process X, had done. And if another process Y releases the same resource it had taken earlier, a similar situation might occur and the resultant would be 4, which instead should have been 5 itself.

This is called a race condition, and due to this condition, problems such as deadlock may occur. Hence we need proper synchronization between processes, and to prevent these, we use a signaling integer variable, called - Semaphore.

So to formally define Semaphore we can say that it is an integer variable that is used in a mutually exclusive manner by concurrent processes, to achieve synchronization.

Since Semaphores are integer variables, their value acts as a signal, which allows or does not allow a process to access the critical section of code or certain other resources**.

Types of Semaphore in OS

There are mainly two types of Semaphores, or two types of signaling integer variables:

1. Binary Semaphores
2. Counting Semaphores

Build an AI-First Career, Master the Complete Skillset

Choose from our industry-leading programs designed for career success

NSDC Certified

Modern Software and AI Engineering Program

Master full-stack development with AI integration

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

NSDC Certified

Modern Data Science and ML with specialisation in AI

Advanced data science techniques with AI specialization

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

NSDC Certified

Advanced AIML with Specialisation in Agentic AI

Deep dive into AIML with focus on Agentic systems

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

NSDC Certified

DevOps, Cloud & AI Platform Engineering

Build and manage AI-powered cloud infrastructure

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

NSDC Certified

AI Engineering Advanced Certification by IIT-Roorkee

Premier AI engineering certification from IIT-Roorkee

3 MonthsDuration

AI-LedCurriculum

Career SupportSupport

Go to Program

NSDC Certified

AI Forward Deployed Engineer Program

Full-stack engineering, production AI and client-facing consulting

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

Binary Semaphores

In these types of Semaphores the integer value of the semaphore can only be either 0 or 1. If the value of the Semaphore is 1, it means that the process can proceed to the critical section (the common section that the processes need to access). However, if the value of the binary semaphore is 0, then the process cannot continue to the critical section of the code.

When a process is using the critical section of the code, we change the Semaphore value to 0, and when a process is not using it, or we can allow a process to access the critical section, we change the value of semaphore to 1.

We'll discuss the working of the semaphores soon.

Counting Semaphores

Counting semaphores are signaling integers that can take on any integer value. Using these Semaphores we can coordinate access to resources and here the Semaphore count is the number of resources available. If the value of the Semaphore is anywhere above 0, processes can access the critical section or the shared resources. The number of processes that can access the resources/code is the value of the semaphore. However, if the value is 0, it means that there aren't any resources that are available or the critical section is already being accessed by a number of processes and cannot be accessed by more processes. Counting semaphores are generally used when the number of instances of a resource is more than 1, and multiple processes can access the resource.

Binary vs Counting Semaphores vs Mutex

Binary and counting semaphores both use semaphore values to control access to resources, but they differ in how many processes they can allow to proceed and how they are typically used. A mutex also supports mutual exclusion, but it has ownership.

You can see how a mutex lock differs from binary and counting semaphores more clearly in the comparison table below.

Now that we have compared these three concepts, let's look into how Semaphore works.

Example of Semaphore in OS

Now that we know what semaphores are and their types, we must understand their working. As we read above, our goal is to synchronize processes and provide mutual exclusion in the critical section of our code. So, we have to introduce a mechanism that wouldn't allow more than 1 process to access the critical section using the signaling integer - semaphore.

Here in this piece of pseudocode, we have declared a semaphore in line 1, which has the value of 1 initially. We then start the execution of a process i which has some code, and then as you can see, we call a function "P" which takes the value of mutex/semaphore as input and we then proceed to the critical section, followed by a function "V" which also takes the value of mutex/semaphore as input. Post that, we execute the remainder of the code, and the process ends.

Remember, we discussed that semaphore is a signaling variable, and whether or not the process can proceed to the critical section depends on its value. And in binary and counting semaphores we read that we change the value of the semaphore according to the resources available. With this thought, let's move further to read about these "P" and "V" functions in the above pseudocode.

Wait and Signal Operations in Semaphores

Wait and Signal operations in semaphores are nothing but those "P" and "V" functions that we read above.

Wait Operation

The wait operation, also called the "P" function, sleep, decrease, or down operation, is the semaphore operation that controls the entry of a process into a critical section. If the value of the mutex/semaphore is positive then we decrease the value of the semaphore and let the process enter the critical section.

Note that this function is only called before the process enters the critical section, and not after it.

In pseudocode:

Signal Operation

The function "V", or the wake-up, increase or up operation is the same as the signal function, and as we know, once a process has exited the critical section, we must update the value of the semaphore so that we can signal the new processes to be able to access the critical section.

For the updation of the value, once the process has exited the critical section, since we had decreased the value of the semaphore by 1 in the wait operation, here we simply increment it. Note that this function is added only after the process exits the critical section and cannot be added before the process enters the section.

In pseudocode:

If the value of the semaphore was initially 1, then on the entering of the process into the critical section, the wait function would have decremented the value to 0 meaning that no more processes can access the critical section (making sure of mutual exclusion -- only in binary semaphores). Once the process exits the critical section, the signal operation is executed and the value of the semaphore is incremented by 1, meaning that the critical section can now be accessed by another process.

Implementation of Binary and Counting Semaphore in OS

Let's take a look at the implementation of the semaphores with two processes P1 and P2. For simplicity of the example, we will take 2 processes, however, semaphores are used for a very large number of processes.

Binary Semaphores:

Initially, the value of the semaphore is 1. When the process P1 enters the critical section, the value of the semaphore becomes 0. If P2 would want to enter the critical section at this time, it wouldn't be able to, since the value of the semaphore is not greater than 0. It will have to wait till the semaphore value is greater than 0, and this will happen only once P1 leaves the critical section and executes the signal operation which increments the value of the semaphore.

This is how mutual exclusion is achieved using binary semaphore i.e. both processes cannot access the critical section at the same time.

Code:

In this code above we have implemented a binary semaphore that provides mutual exclusion.

Counting Semaphores:

In counting semaphores, the only difference is that we will have a number of resources, or in other words a set number of processes that can access the critical section at the same time.

Let's say we have a resource that has 4 instances, hence making the initial value of semaphore = 4. Whenever a process requires access to the critical section/resource we call the wait function and decrease the value of the semaphore by 1 only if the value of the semaphore is greater than 0. When 4 processes have accessed the critical section/resource and the 5th process requires it as well, we put it in the waiting queue and wake it up only when a process has executed the signal function, meaning that the value of the semaphore has gone up by 1.

Solving Producer-Consumer with Semaphores

Now that we have understood the working of semaphores, we can take a look at the real-life application of semaphores in classic synchronization problems.

The producer-consumer problem is one of the classic process synchronization problems.

Hiring Partners:

GoogleAmazonMicrosoftFlipkartAdobe1200+ more

Problem Statement

The problem statement states that we have a buffer that is of fixed size, and the producer will produce items and place them in the buffer. The consumer can pick items from the buffer and consume them. Our task is to ensure that when the item is placed in the buffer by the producer, the consumer should not consume it at the same time the producer produces and places an item into the buffer. The critical section here is the buffer.

Solution

So to solve this problem, we will use 2 counting semaphores, namely "full" and "empty". The counting semaphore "full" will keep track of all the slots in the buffer that are used, i.e. track of all the items in the buffer. And of course, the "empty" semaphore will keep track of the slots in the buffer that are empty, and the value of mutex will be 1.

Initially, the value of the semaphore "full" will be 0 since all slots in the buffer are unoccupied and the value of the "empty" buffer will be 'n', where n is the size of the buffer since all slots are initially empty.

For example, if the size of the buffer is 5, then the semaphore full = 0, since all the slots in the buffer are unoccupied and empty = 5.

The deduced solution for the producer section of the problem is:

In the above code, we call the wait operations on the empty and mutex semaphores when the producer produces an item. Since an item is produced, it must be placed in the buffer reducing the number of empty slots by 1, hence we call the wait operation on the empty semaphore. We must also reduce the value of mutex so as to prevent the consumer from accessing the buffer.

Post this, the producer has placed the item into the buffer and hence we can increase the value of "full" semaphore by 1 and also increment the value of the mutex as the producer has completed it's task and the signal will now be able to access the buffer.

Solution to the consumer section of the problem:

The consumer needs to consume the items that are produced by the producer. So when the consumer is removing the item from the buffer to consume it we need to reduce the value of the "full" semaphore by 1 since one slot will be emptied, and we also need to decrement the value of mutex so that the producer does not access the buffer.

Now that the consumer has consumed the item, we can increment the value of the empty semaphore along with the mutex by 1.

Thus, we have solved the producer-consumer problem.

What Happens If You Get the Order Wrong

The order in which a process acquires semaphores matters. In the dining philosophers problem, resource acquisition order is also important. In the producer-consumer problem, the producer first calls wait(empty) and then wait(mutex). This allows it to wait for an empty slot without holding the mutex.

If the producer instead calls wait(mutex) first and then wait(empty), a deadlock can occur when the buffer is full. The producer acquires the mutex and then waits for an empty slot. Since the buffer is full, the producer remains blocked while still holding the mutex.

The consumer may have an item to remove, but it cannot acquire the mutex because the producer is holding it. The consumer therefore cannot remove an item and increase the number of empty slots. The producer continues waiting for an empty slot that the consumer cannot create.

This is why the ordering wait(empty) -> wait(mutex) for the producer and wait(full) -> wait(mutex) for the consumer must be preserved.

Busy Waiting vs Blocking Semaphores

A semaphore can be implemented in two ways when a process cannot enter the critical section immediately: busy waiting or blocking. The difference is what the process does while waiting for the semaphore to become available.

Busy-waiting form:

Blocking form:

In the blocking implementation, the process does not continuously check the semaphore. Instead, it waits in the semaphore's queue until another process performs signal() and the waiting process can be woken up. If you want to test a semaphore implementation in C, you can follow the steps for compiling and running a C program.

Therefore, semaphores do not inherently eliminate busy waiting. A semaphore implemented with a waiting queue avoids busy waiting, while a spinning implementation continues checking the semaphore until it becomes available.

Advantages of Semaphores

As we have read throughout the article, semaphores have proven to be extremely useful in process synchronization. Here are the advantages summarized:

• They allow processes into the critical section one by one and provide strict mutual exclusion (in the case of binary semaphores).
• No resources go to waste due to busy waiting as with the usage of semaphores as we do not waste processor time in checking the fulfillment of a condition to allow a process to access the critical section.
• The implementation/code of the semaphores is written in the machine-independent code section of the microkernel, and hence semaphores are machine independent.

Disadvantage of Semaphores

We have already discussed the advantages of semaphores, however, semaphores also have some disadvantages. They are:

• Semaphores are slightly complicated and the implementation of the wait and signal operations should be done in such a manner, that deadlocks are prevented.
• The usage of semaphores may cause priority inversion where the high-priority processes might get access to the critical section after the low-priority processes.

Take your first step towards becoming an operating system guru. Enroll in our free Operating System course with certification and get certified now!