Semphores

Whenever consumer wants to sleep, it will check Semaphore value, if the value is > 0 means it should not sleep.
But there arises synchronization problem if there are >1 consumers as they will try to update Semaphore value simultaneously.
That’s the reason Semaphores are implemented at Kernel level. This avoids the RACE condition.
In Kernel mode read, modification of variables will happen atomically [all at once or nothing].


Types of Semaphores

There are two types of Semaphors:
  1. Counting Semaphore
  2. Binary Semaphore
1. Counting Semaphore This semaphore is used for >1 processes.
struct semaphore
{
    int  value ;    // This tells how many process can enter in the critical section
    Queue type L; //  This queue will have processes which got blocked while accessing semaphore.
}

Down(Semaphore S)
{
    S.value = S.value -1;
    if (S.value < 0)
    {
        put process (PCB) in L;
    }
    else
        return; 
}

UP(Semaphore S)
{
    S.value = S.value + 1;
    if (S.value ≤ 0)     
    {
        Select a process from L();
        And wake that process , wakeup();
    }
}
Explanation
Suppose there 4 processes and all of them want to access critical section but at a time only two resources are available.
First process will call the Down function and the function works as follows:
  1. First it will reduce value by 1 and then check whether value is < 0 if yes that means there are no free resources as of now and will go to block queue and will sleep.
  2. As this is the first process to come value is 2 and it will make it as 1 and will go into critical section.
  3. Suppose second process came and made value as 0 and checked value which is not < 0 and went into critical section.
  4. Now third process came and made value as -1 and checked value as < 0, which is true so will go into blocked state.
  5. Similarly fourth process will come and will make value as -2 and will go into blocked queue and will sleep.
  6. Now process 1 came from critical section and will call Up function.
  7. So value will be incremented by 1 and will also check whether value ≤ 0. If yes then that means some processes are waiting in queue. So it will wake up the sleeping process.

Notion for Down and UP function are as follows:
Down and Up
P and V
Wait and Signal






Quantitative Aptitude
Reasoning
Programming
Interview