Semaphore in the Operating System

Introduction

In this article, we will discuss semaphores in the operating system.

Semaphore was introduced in the year of 1965 by Dijkstra. It is the most convenient way to manage concurrent processes with the help of semaphores which is nothing but simple integer value. A semaphore represents nothing but an integer variable that is shared among threads. Using this variable we can conquer the critical section problem and make process synchronization in the multiprocessing environment.

Types

Semaphores are of two types:

Binary Semaphore

Binary semaphores are special types of semaphores. They are also known as mutex locks. They represent only logical values: 0 and 1. Using binary semaphores we can implement the solution of critical section problems with numerous processes.

Counting Semaphore

The domain of counting semaphores is an unrestricted domain. It is used to control access to a resource that has multiple instances.

Now we will see how semaphores do the operation:

P(semaphore mySemaphore)
{
while(mySemaphore == 0); // Wait till mySemaphore reaches to zero
mySemaphore = mySemaphore - 1; // Decrement by one
}

V(semaphore mySemaphore)
{
mySemaphore = mySemaphore + 1; // Increment the value by one
}

The P and V operations have been explained below:

1. The P operation is also known as wait, sleep or down operation.

2. The V operation is also known as the signal, wake-up, or up operation.

3. The P and V operations both are atomic in nature. The semaphore(s) is assigned as a value equal to one. Here, atomic implies that the variable on which read, modify and update operation occurs at the same time with no pre-emption.

4. The critical section is covered with both operations to implement process synchronization.

Code Implementation

We will now implement binary semaphores:

struct semaphore {
enum data(0, 1);

Queue<process> myQueue;

} P(semaphore mySemaphore)
{
if (mySemaphore.data == 1) {
mySemaphore.data = 0;
}
else {

// Append the process to the waiting queue
myQueue.push(P) sleep();
}
}
V(Semaphore mySemaphore)
{
if (mySemaphore.myQueue is empty) {
mySemaphore.data = 1;
}
else {

// Select a process from waiting queue
Process myProcess = myQueue.front();

// Withdraw the process from wating as it has been
// sent for CS
myQueue.pop();
wakeup(myProcess);
}
}

The description above is for a binary semaphore that can have only two values 0 and 1 and make sure mutual exclusion. The other type of semaphore also exists which is known as counting semaphore. A counting semaphore can take a value greater than one.

Its limitations are the following:

1. Priority inversion is one of the limitations of semaphore.

2. The operating system requires to keep the track of all the calls to wait and to signal the semaphore.

3. A process may try to wake up another process that is present in a non-sleep state. Therefore, deadlock might get collapsed indefinitely.

We will now see how we can implement counting semaphore:

struct Semaphore {

int value;

// myQueue contains all Process Control Blocks(PCBs)
Queue<process> myQueue;

} P(Semaphore mySemaphore)
{
mySemaphore.value = mySemaphore.value - 1;
if (mySemaphore.value < 0) {

// Add process to queue
// here myProcess is a process which is currently executing
myQueue.push(myProcess);
block();
}
else
return;
}

V(Semaphore mySemaphore)
{
mySemaphore.value = mySemaphore.value + 1;
if (mySemaphore.value <= 0) {

// Withdraw process myProcess from queue
Process myProcess = myQueue.pop();
wakeup(myProcess);
}
else
return;
}

Explanation

Whenever the process waits it is appended to the waiting queue of the process linked with the semaphore. This is achieved by calling the system call block() on the process.

Conclusion

In this article, we discussed semaphores in the operating system. We saw the working of binary as well as counting semaphores. We believe that this article has surely helped you to gain some knowledge.