The Producer-Consumer Problem & POSIX Condition Variables

Topics

• The Producer-Consumer Problem
• Introduce condition variables and show how they can be used to solve the Producer-Consumer Problem

Producer-Consumer Problem

• One or more threads generate data and put it into a buffer
• One or more threads take data items from the buffer, one at time
• Only one producer or consumer may access the buffer at any one time
• Variants, of increasing difficulty:
  • Single producer & single consumer
  • Multiple producers & single consumer
  • Multiple producers & multipole consumers

Why are buffers called "buffers"? (How does a buffer relate to a pancake? How does a chemical buffer relate to a computer buffer?

What are examples of situations on an operating system that require buffers?

How are buffers in different layers of a system? Consider hardware device drivers, the file system, and user programs.

Significance of the Producer-Consumer Problem

• It occurs frequently in real applications
• It is often used to illustrate and compare different mutual exclusion and synchronization mechanisms
• When judging the quality of a solution, we may consider and compare:
  • correctness of mutual exclusion
  • generality (How many producers/consumers will it support?)
  • simplicity of expression
  • efficiency (execution time overhead)
  • fairness, if there are multiple consumers/producers

Your textbook shows a graduated series of solutions to this problem using various mechanisms, including semaphores. Here, we will use the POSIX thread synchronization mechanisms, instead.

Using an Infinite Buffer

Producer:

while (true) {
  /*produce item v */
  b [in] = v;
  in++;
}

Consumer:

while (true) {
  while (in <= out) /* do nothing */;
  w = b [out];
  out++;
  /*consume item w */
}

Infinite Buffer

Using a Circular Buffer

Producer:

while (true) {
  /*produce item v */
  while ((in + 1) % n == out) /* do nothing */;
  b [in] = v;
  in = (in + 1) % n;
}

Consumer:

while (true) {
  while (in == out) /* do nothing */;
  w = b [out];
  out = (out + 1) % n;
  /*consume item w */
}

Finite (Circular) Buffer

Complete Example Program using a Circular Buffer

See prodcons0.c for a complete program using a circular (ring) buffer and no other form of synchronization.

This solution works for a single producer and a single consumer, because the shared variables in and out have only a single reader and a single writer

It is a very important mechanism for those situations where it works, because:

• It is simple
• It requires no special mutual exclusion or synchronization mechanisms

It is especially useful for low-level device and systems programming, when the producer and consumer are executing on different physical processors.

A defect of this solution for other applications is that it wastes CPU time idling the processor.

Why is idling the processor a problem?

Why is it a special problem for library-level implementations of threads?

How to Avoid Unbounded Blocking with POSIX Threads

Producer:

while (true) {
  /* produce item v */
  while ((in + 1) % n == out) sched_yield();
  b [in] = v;
  in = (in + 1) % n;
}

Consumer:

while (true) {
  while (in == out) sched_yield();
  w = b [out];
  out = (out + 1) % n;
  /*consume item w */
}

This will not help if we are using strict priority scheduling and the threads have different prioritys. Why?

A complete program illustrating this solution is given in file prodcons1.c.

Using a Mutexes with a Circular Buffer (simplified view)

Producer:

while (true) {
  /*produce item v */
  pthread_mutex_lock (&M);
  while ((in + 1) % n == out) pthread_cond_wait(&Out_CV, &M);
  b [in] = v;
  in = (in + 1) % n;
  pthread_cond_signal (&In_CV);
  pthread_mutex_unlock (&M);
}

Consumer:

while (true) {
  pthread_mutex_lock (&M);
  while (in == out) pthread_cond_wait(&In_CV, &M);
  w = b [out];
  out = (out + 1) % n;
  pthread_mutex_unlock (&M);
  pthread_cond_signal (&Out_CV);
  /*consume item w */
}

We can use the producer-consumer example solution to explain the semantics of pthread_cond_wait() as well as to illustrate a style of designing with mutexes and CV's, which is derived from the "monitor" concept.

prodcons2.c Viewed as a Monitor: Mutex-Only View

When books explain monitors, they explain them as a programming language feature, because that is how the term was introduced. However, behind the monitor programming language concept there is an underlying design model that can be implemented without language. In particular, this design model is such a natural match with with mutexes and condition variables that one might say they were designed for one another.

A monitor starts with mutual exclusion, which can be implemented using a mutex. We can picture a collection of data objects that are protected by a mutex as a room with a door, with a guard posted at the door.

The mutex is the guard. It only allows one person (thread) into the room at a time. The pthread_mutex_lock(&M); call is used to go in, and the pthread_mutex_unlock(&M); call is used to exit.

prodcons2.c Viewed as a Monitor: Blocking

While one thread is in the room, the mutex prevents any other thread from entering. The figure shows what happens if a consumer thread tries to enter the room (by calling pthread_mutex_lock (&M);) while the producer thread is still in the room. The consumer blocks, in the call to pthread_mutex_lock.

prodcons2.c Viewed as a Monitor: Buffer Full Picture

Continuing with this analogy to a room with a guard, the function of a condition variable can be understood as a waiting room. In the figure, the producer goes into the room and finds that the buffer is still full. It cannot proceed, so it call pthread_cond_wait (&In_CV, &M);. The effect is as if the calling thread leaves the protected room and goes into a side room, then goes to sleep.

When the thread leaves the room, the guard (the mutex) notices and will now allow another thread into the room. For example, tn the figure the consumer that was blocked on a call to pthread_mutex_lock will be unblocked and allowed to enter the room.

The thread that is waiting in the side room will wait there until it wakes up, at which point it will try to get back into the protected room. To do so, it will need to relock the mutex. It does not need to call pthread_mutex_lock() to do this. The unlocking, sleeping, and then relocking are all part of the effect of the one call to pthread_cond_wait.

Semantics of pthread_cond_wait and pthread_cond_signal

1. unlock the mutex
2. sleep for a while (may wake up at any time)
3. relock the mutex

1. wake up at least one of the threads (if any) that is sleeping on the CV

The analogy to a person sleeping in a side room fits the pthread_cond_signal operation, too.

A thread that is waiting on a call to pthread_cond_wait may wake up at any time, just as a person who goes to bed may wake up before the alarm clock goes off.

When some other thread calls pthread_cond_signal for the given CV, the effect is similar to someone ringing a loud alarm bell in the side "room" that corresponds to the CV. If there is a thread waiting on a CV, it is guaranteed to wake up when that CV is signaled. If there are several threads waiting on the same CV, at least one is guaranteed to wake up. (Whether more than one wakes up depends on the implementation.) If there is no thread waiting on the CV, the pthread_cond_signal call has no effect.

prodcons2.c Viewed as a Monitor: Producer Early Wakeup

If the producer wakes up early, it will find there is still no space in the buffer, and it will go back to sleep again on In_CV.

prodcons2.c Viewed as a Monitor: Waking up the Producer

Eventually, the consumer, who was blocked trying to enter the room, will be allowed to enter and removes an item from the buffer. After the consumer has left the room, he calls pthread_cond_signal (&In_CV);. This will wake up the producer.

prodcons2.c Viewed as a Monitor: Producer After Wakeup

The producer inserts an item into the buffer, and then leaves the room by calling pthread_mutex_unlock. Before that, or immediately after, the producer needs to signal the condition variable on which the consumer(s) might be waiting.

prodcons2.c Viewed as a Monitor: Buffer Empty Picture

What have we gained by using pthread_cond_wait() instead of sched_yield()?

This solution now supports multiple readers and multiple writers. However, it does not guarantee fairness. Is that important here?

Full programs illustrating this solution are given in files prodcons2.c. and prodcons3.c.

The latter is done in an object-oriented style. The buffer datatype contains its own mutex and condition variables. What is the advantage of having these synchronization objects be per-buffer?

Note: The above examples, and others, are all in the directory examples/prodcons.

There are some very interesting animated examples of solutions to the producer-consumer and readers-writers problems on the web. For example, there is a list of animations for operating systems concepts, including the producer-consumer problem, at http://williamstallings.com/OS-Animation/Animations.html. You may like to try executing some of them to get a better picture of how monitors, semaphores, etc. work. (Beware: To run them you may need to install some Java class libraries, and Java is notorious for version dependences.)