To get rid of the problem of wasting the wake-up signals, Dijkstra proposed an approach which involves storing all the wake-up calls. Dijkstra states that, instead of giving the wake-up calls directly to the consumer, producer can store the wake-up call in a variable. Any of the consumers can read it whenever it needs to do so.
Semaphore is the variables which storesthe entire wake up calls that are being transferred from producer to consumer. It is a variable on which read, modify and update happens automatically in kernel mode.
Semaphore cannot be implemented in the user mode because race condition may always arise when two or more processes try to access the variable simultaneously. It always needs support from the operating system to be implemented.
According to the demand of the situation, Semaphore can be divided into two categories.
Counting Semaphore
Binary Semaphore or Mutex
We will discuss each one in detail.
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();
}
}
}
In this mechanism, the entry and exit in the critical section are performed on the basis of the value of counting semaphore. The value of counting semaphore at any point of time indicates the maximum number of processes that can enter in the critical section at the same time.
A process which wants to enter in the critical section first decrease the semaphore value by 1 and then check whether it gets negative or not. If it gets negative then the process is pushed in the list of blocked processes (i.e. q) otherwise it gets enter in the critical section.
When a process exits from the critical section, it increases the counting semaphore by 1 and then checks whether it is negative or zero. If it is negative then that means that at least one process is waiting in the blocked state hence, to ensure bounded waiting, the first process among the list of blocked processes will wake up and gets enter in the critical section.
The processes in the blocked list will get waked in the order in which they slept. If the value of counting semaphore is negative then it states the number of processes in the blocked state while if it is positive then it states the number of slots available in the critical section.
The questions are being asked on counting semaphore in GATE. Generally the questions are very simple that contains only subtraction and addition.
Wait → Decre → Down → P
Signal → Inc → Up → V
The following type questions can be asked in GATE.
S = 12 (initial)
10 p (wait) :
SS = S -10 = 12 - 10 = 2
then 4 V :
SS = S + 4 =2 + 4 = 6
Hence, the final value of counting semaphore is 6.