The Producer/Consumer (Bounded Buffer) Problem

Remember the producer/consumer problem from the previous chapter? Let's try to solve it with semaphores!

We'll cover the following

The next problem we will confront in this chapter is known as the producer/consumer problem, or sometimes as the bounded buffer problem“Information Streams Sharing a Finite Buffer” by E.W. Dijkstra. Information Processing Letters 1, 1972. http://www.cs.utexas.edu/users/EWD/ewd03xx/EWD329.PDF. Did Dijkstra invent everything? No, but maybe close. He certainly was the first to clearly write down what the problems were in concurrent code. However, practitioners in OS design knew of many of the problems described by Dijkstra, so perhaps giving him too much credit would be a misrepresentation.. This problem is described in detail in the previous chapter on condition variables; see here for details.

First attempt

Our first attempt at solving the problem introduces two semaphores, empty and full, which the threads will use to indicate when a buffer entry has been emptied or filled, respectively. The code for the put and get routines is given below:

Press + to interact
int buffer[MAX];
int fill = 0;
int use = 0;
void put(int value) {
  buffer[fill] = value; //Line F1
  fill = (fill + 1) % MAX; //Line F2
}
int get() {
  int tmp = buffer[use]; // Line G1 
  use = ( use + 1) % MAX; //Line G2 
  return tmp;
}

Our attempt at solving the producer and consumer problem is in the code snippet below.

Press + to interact
sem_t empty;
sem_t full;
void *producer(void *arg) {
    int i;
    for (i = 0; i < loops; i++) {
        sem_wait(&empty);  //Line P1
        put(i);            //Line P2
        sem_post(&full);   //Line P3
    }
}
void *consumer(void *arg) { 
    int i,tmp = 0;
    while (tmp != -1) {
        sem_wait(&full);      //Line C1
        tmp = get();          //Line C2
        sem_post(&empty);     //Line C3
        printf("%d\n", tmp);
    }
}
int main(int argc, char *argv[]) {
    // ...
    sem_init(&empty, 0, MAX); // MAX are empty
    sem_init(&full, 0, 0);    // 0 are full
    // ...
}

In this example, the producer first waits for a buffer to become empty in order to put data into it, and the consumer similarly waits for a buffer to become filled before using it. Let us first imagine that MAX=1 (there is only one buffer in the array), and see if this works.

Imagine again there are two threads, a producer and a consumer. Let us examine a specific scenario on a single CPU. Assume the consumer gets to run first. Thus, the consumer will hit Line C1, calling sem_wait(&full). Because full was initialized to the value 0, the call will decrement full (to -1), block the consumer, and wait for another thread to call sem_post() on full, as desired.

Assume the producer then runs. It will hit Line P1, thus calling the sem_wait(&empty) routine. Unlike the consumer, the producer will continue through this line, because empty was initialized to the value MAX (in this case, 1). Thus, empty will be decremented to 0 and the producer will put a data value into the first entry of buffer (Line P2). The producer will then continue on to P3 and call sem_post(&full), changing the value of the full semaphore from -1 to 0 and waking the consumer (e.g., move it from blocked to ready).

In this case, one of two things could happen. If the producer continues to run, it will loop around and hit Line P1 again. This time, however, it would block, as the empty semaphore’s value is 0. If the producer instead was interrupted and the consumer began to run, it would return from sem_wait(&full) (Line C1), find that the buffer was full, and consume it. In either case, we achieve the desired behavior.

You can try this same example with more threads (e.g., multiple producers, and multiple consumers). It should still work.

Get hands-on with 1400+ tech skills courses.