All the solutions we have seen till now were intended to provide mutual exclusion with busy waiting. However, busy waiting is not the optimal allocation of resources because it keeps CPU busy all the time in checking the while loops condition continuously although the process is waiting for the critical section to become available.
All the synchronization mechanism with busy waiting are also suffering from the priority inversion problem that is there is always a possibility of spin lock whenever there is a process with the higher priority has to wait outside the critical section since the mechanism intends to execute the lower priority process in the critical section.
However these problems need a proper solution without busy waiting and priority inversion.
Let's examine the basic model that is sleep and wake. Assume that we have two system calls as sleep and wake. The process which calls sleep will get blocked while the process which calls will get waked up.
There is a popular example called producer consumer problem which is the most popular problem simulating sleep and wake mechanism.
The concept of sleep and wake is very simple. If the critical section is not empty then the process will go and sleep. It will be waked up by the other process which is currently executing inside the critical section so that the process can get inside the critical section.
In producer consumer problem, let us say there are two processes, one process writes something while the other process reads that. The process which is writing something is called producer while the process which is reading is called consumer.
In order to read and write, both of them are using a buffer. The code that simulates the sleep and wake mechanism in terms of providing the solution to producer consumer problem is shown below.
#define N 100 //maximum slots in buffer
#define count=0 //items in the buffer
void producer (void)
{
int item;
while(True)
{
item = produce_item(); //producer produces an item
if(count == N) //if the buffer is full then the producer will sleep
Sleep();
insert_item (item); //the item is inserted into buffer
countcount=count+1;
if(count==1) //The producer will wake up the
//consumer if there is at least 1 item in the buffer
wake-up(consumer);
}
}
void consumer (void)
{
int item;
while(True)
{
{
if(count == 0) //The consumer will sleep if the buffer is empty.
sleep();
item = remove_item();
countcount = count - 1;
if(count == N-1) //if there is at least one slot available in the buffer
//then the consumer will wake up producer
wake-up(producer);
consume_item(item); //the item is read by consumer.
}
}
}
The producer produces the item and inserts it into the buffer. The value of the global variable count got increased at each insertion. If the buffer is filled completely and no slot is available then the producer will sleep, otherwise it keep inserting.
On the consumer's end, the value of count got decreased by 1 at each consumption. If the buffer is empty at any point of time then the consumer will sleep otherwise, it keeps consuming the items and decreasing the value of count by 1.
The consumer will be waked up by the producer if there is at least 1 item available in the buffer which is to be consumed. The producer will be waked up by the consumer if there is at least one slot available in the buffer so that the producer can write that.
Well, the problem arises in the case when the consumer got preempted just before it was about to sleep. Now the consumer is neither sleeping nor consuming. Since the producer is not aware of the fact that consumer is not actually sleeping therefore it keep waking the consumer while the consumer is not responding since it is not sleeping.
This leads to the wastage of system calls. When the consumer get scheduled again, it will sleep because it was about to sleep when it was preempted.
The producer keep writing in the buffer and it got filled after some time. The producer will also sleep at that time keeping in the mind that the consumer will wake him up when there is a slot available in the buffer.
The consumer is also sleeping and not aware with the fact that the producer will wake him up.
This is a kind of deadlock where neither producer nor consumer is active and waiting for each other to wake them up. This is a serious problem which needs to be addressed.
A flag bit can be used in order to get rid of this problem. The producer can set the bit when it calls wake-up on the first time. When the consumer got scheduled, it checks the bit.
The consumer will now get to know that the producer tried to wake him and therefore it will not sleep and get into the ready state to consume whatever produced by the producer.
This solution works for only one pair of producer and consumer, what if there are n producers and n consumers. In that case, there is a need to maintain an integer which can record how many wake-up calls have been made and how many consumers need not sleep. This integer variable is called semaphore. We will discuss more about semaphore later in detail.