Semaphore in OS

What is Semaphore in OS?

If you have read about Process Synchronization, you are aware of the critical section problem that arises for concurrent processes.

If not, let's quickly get comfortable with these terms above.

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

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.

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.

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.

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!