In counting semaphore, Mutual exclusion was not provided because we has the set of processes which required to execute in the critical section simultaneously.
However, Binary Semaphore strictly provides mutual exclusion. Here, instead of having more than 1 slots available in the critical section, we can only have at most 1 process in the critical section. The semaphore can have only two values, 0 or 1.
Let's see the programming implementation of Binary Semaphore.
StructBsemaphore
{
enum Value(0,1); //value is enumerated data type which can only have two values 0 or 1.
Queue type L;
}
/* L contains all PCBs corresponding to process
Blocked while processing down operation unsuccessfully.
*/
Down (Bsemaphore S)
{
if (s.value == 1) // if a slot is available in the
//critical section then let the process enter in the queue.
{
S.value = 0; // initialize the value to 0 so that no other process can read it as 1.
}
else
{
put the process (PCB) in S.L; //if no slot is available
//then let the process wait in the blocked queue.
sleep();
}
}
Up (Bsemaphore S)
{
if (S.L is empty) //an empty blocked processes list implies that no process
//has ever tried to get enter in the critical section.
{
S.Value =1;
}
else
{
Select a process from S.L;
Wakeup(); // if it is not empty then wake the first process of the blocked queue.
}
}
Every process needs some resources to complete its execution. However, the resource is granted in a sequential order.
The process requests for some resource.
OS grant the resource if it is available otherwise let the process waits.
The process uses it and release on the completion.
A Deadlock is a situation where each of the computer process waits for a resource which is being assigned to some another process. In this situation, none of the process gets executed since the resource it needs, is held by some other process which is also waiting for some other resource to be released.
Let us assume that there are three processes P1, P2 and P3. There are three different resources R1, R2 and R3. R1 is assigned to P1, R2 is assigned to P2 and R3 is assigned to P3.
After some time, P1 demands for R1 which is being used by P2. P1 halts its execution since it can't complete without R2. P2 also demands for R3 which is being used by P3. P2 also stops its execution because it can't continue without R3. P3 also demands for R1 which is being used by P1 therefore P3 also stops its execution.
In this scenario, a cycle is being formed among the three processes. None of the process is progressing and they are all waiting. The computer becomes unresponsive since all the processes got blocked.
Sr. | Deadlock | Starvation |
1 | Deadlock is a situation where no process got blocked and no process proceeds | Starvation is a situation where the low priority process got blocked and the high priority processes proceed. |
2 | Deadlock is an infinite waiting. | Starvation is a long waiting but not infinite. |
3 | Every Deadlock is always a starvation. | Every starvation need not be deadlock. |
4 | The requested resource is blocked by the other process. | The requested resource is continuously be used by the higher priority processes. |
5 | Deadlock happens when Mutual exclusion, hold and wait, No preemption and circular wait occurs simultaneously. | It occurs due to the uncontrolled priority and resource management. |
A resource can only be shared in mutually exclusive manner. It implies, if two process cannot use the same resource at the same time.
A process waits for some resources while holding another resource at the same time.
The process which once scheduled will be executed till the completion. No other process can be scheduled by the scheduler meanwhile.
All the processes must be waiting for the resources in a cyclic manner so that the last process is waiting for the resource which is being held by the first process.