The Producer Consumer Problem

The producer-consumer problem illustrates the need for synchronization in systems where many processes share a resource. In the problem, two processes share a fixed-size buffer. One process produces information and puts it in the buffer, while the other process consumes information from the buffer. These processes do not take turns accessing the buffer, they both work concurrently. Herein lies the problem. What happens if the producer tries to put an item into a full buffer? What happens if the consumer tries to take an item from an empty buffer?

In order to synchronize these processes, we will block the producer when the buffer is full, and we will block the consumer when the buffer is empty. So the two processes, Producer and Consumer, should work as follows:

(1) The producer must first create a new widget. (2) Then, it checks to see if the buffer is full. If it is, the producer will put itself to sleep until the consumer wakes it up. A "wakeup" will come if the consumer finds the buffer empty.(3) Next, the producer puts the new widget in the buffer. If the producer goes to sleep in step (2), it will not wake up until the buffer is empty, so the buffer will never overflow. (4) Then, the producer checks to see if the buffer is empty. If it is, the producer assumes that the consumer is sleeping, an so it will wake the consumer. Keep in mind that between any of these steps, an interrupt might occur, allowing the consumer to run.

(1) The consumer checks to see if the buffer is empty. If so, the consumer will put itself to sleep until the producer wakes it up. A "wakeup" will occur if the producer finds the buffer empty after it puts an item into the buffer. (2) Then, the consumer will remove a widget from the buffer. The consumer will never try to remove a widget from an empty buffer because it will not wake up until the buffer is full.(3) If the buffer was full before it removed the widget, the consumer will wake the producer. (4) Finally, the consumer will consume the widget. As was the case with the producer, an interrupt could occur between any of these steps, allowing the producer to run.

The code might look like this:

  BufferSize = 3;
  count = 0;

  Producer()
  {
    int widget;
    WHILE (true) {                   // loop forever
      make_new(widget);              // create a new widget to put in the buffer
      IF(count==BufferSize)
           Sleep();                  // if the buffer is full, sleep
      put_item(widget);              // put the item in the buffer
      count = count + 1;             // increment count of items
      IF (count==1)
         Wakeup(Consumer);           // if the buffer was previously empty, wake
   }                                 //  the consumer
  }

  Consumer()
  {
    int widget;
    WHILE(true) {                    // loop forever
      IF(count==0)
           Sleep();                  // if the buffer is empty, sleep
      remove_item(widget);           // take an item from the buffer
      count = count + 1;             // decrement count of items
      IF(count==N-1)
            Wakeup(Producer);        // if buffer was previously full, wake
                                     //  the producer
      Consume_item(widget);          // consume the item
     }
   }

In the next three sections, the Purple Line, we will discuss solutions to this problem using each of the three methods introduced in the Solution Types section:

Semaphores

Monitors

Message Passing

             
IPC Home    Subway    Problems    Readers/
  Page       Map                  Writers