⏪Previous Next⏩

For the solution to the critical section problem one synchronization tool is used which is known as semaphores. A semaphore ‘S’ is an integer variable which is accessed through two standard operations such as wait and signal. These operations were originally termed ‘P’ (for wait means to test) and ‘V’ (for single means to increment). The classical definition of wait is

Wait (S)

{

While (S <= 0)

{

Test;

}

S--;

}

the classical definition of the signal is

Signal (S)

{

S++;

}

In case of wait the test condition is executed with interruption and the decrement is executed without interruption.

Binary Semaphore:

A binary semaphore is a semaphore with an integer value which can range between 0 and 1. Let ‘S’ be a counting semaphore. To implement the binary semaphore we need following the structure of data.
Binary Semaphores S₁, S₂; int C;

Initially S₁ = 1, S2 = 0 and the value of C is set to the initial value of the counting semaphore ‘S’. Then the wait operation of the binary semaphore can be implemented as follows.

Wait (S₁)
C--;

if (C < 0)

{ Signal (S₁);

Wait (S₂);

}

The signal operation of the binary semaphore can be implemented as follows:

Wait (S₁);

C++;

if (C <=0)

Signal (S2);

Else

Signal (S1);

Counting Semaphore

There are the scenarios in which more than one processes need to execute in critical section simultaneously. However, counting semaphore can be used when we need to have more than one process in the critical section at the same time.

The programming code of semaphore implementation is shown below which includes the structure of semaphore and the logic using which the entry and the exit can be performed in the critical section.

struct Semaphore
{
int value; // processes that can enter in the critical section simultaneously.
queue type L; // L contains set of processes which get blocked
}
Down (Semaphore S)
{
  SS.value = S.value - 1; //semaphore's value will get decreased when a new
//process enter in the critical section
if (S.value< 0)
{
put_process(PCB) in L; //if the value is negative then
//the process will get into the blocked state.
Sleep();
}
else
return;
}
up (Semaphore s)
{
  SS.value = S.value+1; //semaphore value will get increased when
//it makes an exit from the critical section.
if(S.value<=0)
{
select a process from L; //if the value of semaphore is positive
//then wake one of the processes in the blocked queue.
wake-up();
}
}
}