Sleep and Wakeup Problem

To avoid the CPU busy waiting and SPIN LOCK we follow the sleep and wake method.
We introduce the Producer and Consumer methodology. Producer makes the item and consumed by the consumer.
The pseudo code is follows,

    Producer:
1. #define N 100                   // number of slots in the buffer
2. #define count= 0              // items in the buffer
3. void producer  (void) 
4. {
5.  int item;
6.  while(TRUE)
7.  {
8.      item = produce_item();
9.      If (count == N) sleep();
10.         insert_item(item);
11.         count  = count + 1;
12.         if(count == 1 ) wake_up(consumer);
13.     }
14. }
Consumer:
1. void consumer(void)
2. {
3.  int item;
4.  while(TRUE)
5.  {
6.      If(count = 0) sleep();
7.      item = remove_item();
8.      count = count -1;
9.      if (count = N -1 ) wake_up(producer);
10.         Consume_item(item);
11.     }
12. }

When there is 1 item in the buffer producer will wake up the consumer because may be the consumer went to sleep as buffer was empty.
Similarly when there are N-1 items in the buffer consumer will wake up the producer as there might be the case that producer went to sleep as the count could have been N and consumer consumed one item and count became N-1 but producer will go to sleep if the count is N. been N and consumer consumed one item and count became N-1 but producer will go to sleep if the count is N.

Problem:

Consumer about to go to sleep but got preempted, buffer is >= 1 and producer will send the wake_up signal but the consumer is not sleeping yet and the signal will get wasted. And then consumer got scheduled and went to sleep. And the producer is thinking that consumer is not sleeping. When count is N then producer will go to sleep. Now if you see that both producer and consumer are sleeping. And that is a deadlock.

Solution:

Whenever someone is about to sleep then a bit is maintained to tell do not sleep. But when there are N producer and consumer then we have to record N wake up calls. So Dijkstra introduced something called as Semaphores which will tell how many wake up calls happened. However Semaphores need support from Operating System.
So in the next chapter we will discuss about SEMAPHORS.






Quantitative Aptitude
Reasoning
Programming
Interview