G53OPS - Operating Systems

This course is run at the The University of Nottingham within the School of Computer Science & IT. The course is run by Graham Kendall (EMAIL : gxk@cs.nott.ac.uk)

The Producer-Consumer Problem

This problem is outlined in a later page. You should read this now.

To implement a solution to the problem using SLEEP/WAKEUP we need to maintain a variable, count, that keeps track of the number of items in the buffer

The producer will check count against n (maximum items in the buffer). If count = n then the producer sends itself the sleep. Otherwise it adds the item to the buffer and increments n.

Similarly, when the consumer retrieves an item from the buffer, it first checks if n is zero. If it is it sends itself to sleep. Otherwise it removes an item from the buffer and decrements count.

The calls to WAKEUP occur under the following conditions.

· Once the producer has added an item to the buffer, and incremented count, it checks to see if count = 1 (i.e. the buffer was empty before). If it is, it wakes up the consumer.
· Once the consumer has removed an item from the buffer, it decrements count. Now it checks count to see if it equals n-1 (i.e. the buffer was full). If it does it wakes up the producer.

Here is the producer and consumer code.

int BUFFER_SIZE = 100;
int count = 0;

void producer(void) {
int item;
while(TRUE) {
produce_item(&item); // generate next item
if(count == BUFFER_SIZE) sleep (); // if buffer full, go to sleep
enter_item(item); // put item in buffer
count++; // increment count
if(count == 1) wakeup(consumer); // was buffer empty?
}
}

void consumer(void) {
int item;
while(TRUE) {
if(count == 0) sleep (); // if buffer is empty, sleep
remove_item(&item); // remove item from buffer
count--; // decrement count
if(count == BUFFER_SIZE - 1) wakeup(producer); // was buffer full?
consume_item(&item); // print item
}
}

This seems logically correct but we have the problem of race conditions with count.

The following situation could arise.

· The buffer is empty and the consumer has just read count to see if it is equal to zero.
· The scheduler stops running the consumer and starts running the producer.
· The producer places an item in the buffer and increments count.
· The producer checks to see if count is equal to one. Finding that it is, it assumes that it was previously zero which implies that the consumer is sleeping - so it sends a wakeup.
· In fact, the consumer is not asleep so the call to wakeup is lost.
· The consumer now runs - continuing from where it left off - it checks the value of count. Finding that it is zero it goes to sleep. As the wakeup call has already been issued the consumer will sleep forever.
· Eventually the buffer will become full and the producer will send itself to sleep.
· Both producer and consumer will sleep forever.

One solution is to have a wakeup waiting bit that is turned on when a wakeup is sent to a process that is already awake. If a process goes to sleep, it first checks the wakeup bit. If set the bit will be turned off, but the process will not go to sleep.

Whilst seeming a workable solution it suffers from the drawback that you need an ever increasing number wakeup bits to cater for larger number of processes.

 Last Updated : 14/01/2002