CMSC 412

NOTE 12

March 17, 1999

Bounded-buffer Producer-Consumer Problem

1. Problem statement

A buffer of size N is shared by several processes. We are given sequential code We want functions Append(item) and Remove(item) such that the following hold:
  1. Mutually exclusive access to buffer: At any time at most one process should be executing add_item or remove_item.
  2. No buffer overflow: A process executes add_item only when the buffer is not full (i.e., the process waits if the buffer is full).
  3. No buffer underflow: A process executes remove_item only when the buffer is not empty.
  4. No busy waiting.
  5. No producer starvation: A process does not wait forever at Append() provided the buffer repeatedly becomes non-full.
  6. No producer starvation: A process does not wait forever at Remove() provided the buffer repeatedly becomes non-empty.
Note that conditions 1, 2, 3, and 4 are safety requirements (what a process should not do) and conditions 5 and 6 are progress requirements (what a process should eventually do).
 

2. Solution using Semaphores

The natural approach to this problem is to introduce an integer variable that keeps track of the number of items in the buffer, and then make processes wait on a semaphore if the condition is not right. This approach leads to a cumbersome solution. A more elegant approach results if we really make use of the power of semaphores.
Semaphore nItem initially 0;  // number of items in the buffer
Semaphore nSpace initially 0;  // number of spaces in the buffer
Semaphore mutex initially 1;  // protects add_item and remove_item

Append( item ) {
  P( nSpace );
  P( mutex );
  add_item;
  V( mutex );
  V( nItem );
}

Remove( item ) {
  P( nItem );
  P( mutex );
  remove_item;
  V( mutex );
  V( nSpace );
}
NOTE: