Semaphore World

Mutex, condition variables, monitors, barriers and semaphores are used to achieve mutual exclusion in concurrent programming.

Before going to the semaphore, we need to understand some of the fundamentals of concurrent programming.

• Race condition
• Critical section
• Critical section problem
• Mutual exclusion

Race condition

The situation where several processes try to access and manipulate shared data concurrently. As above we mentioned this Situation is called a race condition.

We need to synchronize the processes where this race condition occurs. This is the core objective of concurrent programming. To deal with this race condition, we have software level methods and hardware-level methods.

Critical Section Problem

Before going to address the problem, what is the critical section?
If we have n process and all competing to use some shared data. In here, Each process has a code segment called “Critical section” in which shared data is accessed.

“Actually, critical source depends on the problem not only the shared data”

This means when there is a situation like a race condition, the processes that make race condition have a code segment in which shared data is accessed. we called this code segmentation as a critical section.

The problem is we need to ensure that when one process in its critical section, no other process is allowed to execute in its critical section.

Mutual exclusion

Two processes will not collide, they will not run the critical section parallel.
The formal definition is “ If process Pi is executing in its critical section, then no other process can be executing in their critical sections”

What is semaphore?

Photo by Oussama Zaidi on Unsplash

we can simply say it is an unsigned integer with limited functionalities.

class Semaphore {
   unsigend int value;
   wait(); //Atomic function
   signal(); //Atomic function
}

It’s just an unsigned integer + 2 functionalities then how it can be used to achieve mutual exclusion? Let’s see ……….

Semaphore functionalities

We can’t directly manipulate the semaphore. If we need to do anything with semaphore, the only way is using semaphore’s functionality.

Semaphore has two functionalities one is, wait() and the other one is signal(). wait…….. what is wait()?

wait()

It is used to decrement the value up to 0 since semaphore unsigned value.

When the semaphore value is greater than 0 it decrements with success and, if the semaphore value is 0 then it waits or it is suspended.

Just look at the pseudo-code to understand this method

wait(){
 if semaphore.value > 0 {
   S= S-1
   return
 } 
 else{
   The process is appended on waiting set;
 }
}

Signal()

It will increment value if no one is in the waiting stage otherwise it wakes up one process from the set of waiting stage processes.

signal(){
 if some process in waiting set{
Wake up one process
 }
 else{
semaphore.value = semaphore.value+1
 }
}

The unsigned value is used to decide how many processes are allowed into the critical section.

wait() and the signal() functionalities are atomic functionalities

Anyone has wonder how this wait()/signal() is atomic?

One option is, using some mechanisms (flags, turns) to make them atomic.
another option is, using hardware instructions like compare and swap or test and set instruction which can be done in one single clock cycle.

With this definition of semaphore, the following can be proved

• S≥0 since semaphore is an unsigned value
• S = S0 + #Signal() + #Wait()

S0 → Initial value of the semaphore
#Signal → number of signal operations executed on S
#Wait → number of completed wait operations executed on S

Here, Wait() should be completed wait operation since if one process is called wait function then it should move to the critical section not suspended otherwise it is not completed.

Mutual exclusion using a Semaphore

            Semaphore S = new Semaphore(1);
process P1               process P2
while(True){             while(True){
 nonCriticalSection;      nonCriticalSection;
 wait(S);                 wait(S);
 criticalSection;         criticalSection;
 signal(S);               signal(S);
}                        }

Before entering the critical section the processes will call the wait() method of the semaphore. After executing their critical section, they will call the signal() method of the semaphore

Let’s assume if P1 and P2 are calling the wait() method at the same time. Since the wait() is an atomic operation, P1 or P2 will execute the wait() operation, not both. We assumed if P1 executed the wait() operation so when it executes it will decrement the semaphore value to 0 and it enters the critical section. After P1 executed the wait() function now P2 will execute the wait function but now the semaphore value is 0 so P2 will be suspended/ will wait in the set. After P1 executed the critical section, it will execute the signal() function in that time, it will wake up the P1 process. so P1 will enter the critical section. After it executed the critical section, it will execute the signal() operation. In that time, there is no process waiting set so it will increment semaphore to 1.

Do you need a mathematical way to prove mutual exclusion is achieved here? If you don’t need it, skip this section.

We already said above

• S≥0 since semaphore is an unsigned value
• S = S0 + #Signal() - #Wait()

With these two, we can prove it.

If we say the number of processes in the critical section(#CS) and semaphore value should be less than or equal to one. Since when the critical section is executed by a process then semaphore will be zero and if no process in the critical section then the semaphore value is 1

In symbols, we can describe as below

#CS + S = 1

If we proved the above equation then the mutual exclusion is achieved.

S0 = 1
#CS = #Wait - #Signal
S = S0 + #Signal - #Wait
S = S0 - #CS
S + #CS = S0
S + #CS =1

We proved…………..

We can also prove no deadlock, starvation and livelock.

Types of Semaphores

• Blocked-set semaphore → This is what, we describe above
  A signalling process(Signal function) awakens one (unspecified) of the suspended processes.
• Blocked-queue semaphore → Same as above but when we wake process it wakes up the process which suspended first.
  The suspended processes are kept in a FIFO queue and awakened in the same order they were suspended.
• Busy-wait semaphore → The value of the semaphore is tested in a busy-wait loop. The entire if-statement is executed as an atomic operation. but there may be interleaving between cycles of the loop.

Busy-wait semaphore
wait()
  loop
   if (semaphore.value> 0) then 
    semaphore.value = semaphore.value - 1;
    break;
  end loop
up()
  semaphore.value = semaphore.value + 1

If you think, you need to know more than this about semaphore. Let’s wait for semaphore world II