Producer-Consumer Problem

system design

The producer-consumer problem is also known as the bounded-buffer problem. It’s about the synchronization between a producer and a consumer who share a bounded buffer. The producer generates and puts items into the buffer, one at a time, and pauses when the buffer is full. The consumer consumes and removes items from the buffer, one at a time, and pauses when the buffer is empty. We can generalize the producer-consumer problem to have multiple producers or consumers.

Semaphores

Recall that semaphores tell available resources. From a producer’s perspective, the resource is the available slots in the buffer. From a consumer’s perspective, the resource is the generated items in the buffer. We therefore need two separate semaphores for producers and consumers respectively. When there are only one producer and one consumer, these two semaphores are all what we need.

semaphore empty = n; // number of available slots in the buffer
semaphore full = 0; // number of generated items in the buffer

void Producer()
{
    Wait(empty);
    AddItemToBuffer(item);
    Post(full);
}

void Consumer()
{
    Wait(full);
    item = RemoveItemFromBuffer();
    Post(empty);
}

When there are multiple producers or consumers, two semaphores are still enough if the buffer can hold only one item. Both semaphores then become binary semaphores, where at a time only one producer is allowed to add an item, or only one consumer is allowed to consume an item. Once the buffer is holding more than one items, we need at least one additional mutual exclusion for buffer operations.

semaphore empty = n; // number of available slots in the buffer
semaphore full = 0; // number of generated items in the buffer
semaphore mutex = 1;

void Producer()
{
    Wait(empty);
    Wait(mutex);
    AddItemToBuffer(item);
    Post(mutex);
    Post(full);
}

void Consumer()
{
    Wait(full);
    Wait(mutex);
    item = RemoveItemFromBuffer();
    Post(mutex);
    Post(empty);
}

Monitors

Recall that a monitor consists of a mutex (lock) object and some condition variables. When the mutex is applied to the buffer, a synchronization bases on monitors is applicable for both single and multiple producer(s) and/or consumer(s). From a producer’s perspective, it’s waiting for the buffer to be not full. From a consumer’s perspective, it’s waiting for the buffer to be not empty. Similar to the semaphore solution, we allocate two separate condition variables for producers and consumers respectively.

Lock lock; // A mutex for the buffer.
ConditionVariable notEmpty; // Wait for the buffer to become non-empty.
ConditionVariable notFull; // Wait for the buffer to become non-full.

void Producer()
{
    lock.acquire();
    while (BufferIsFull())
    {
        Wait(lock, notFull);
    }
    AddItemToBuffer(item);
    Signal(notEmpty); // or NotifyAll(notEmpty);
    lock.release();
}

void Consumer()
{
    lock.acquire();
    while (BufferIsEmpty())
    {
        Wait(lock, notEmpty);
    }
    item = RemoveItemFromBuffer();
    Signal(notFull); // or NotifyAll(notFull);
    lock.release();
}

Compared to semaphores, condition variables allow broader conditions to be defined. Instead of using two condition variables, we can also rely on one single condition variable to cover the broader case when the buffer is neither full nor empty. Such case would allow either producers or consumers to access the buffer (under the mutex). On the other hand, with one single condition variable, a Signal operation won’t be able to distinguish between producers and consumers. Since producers and consumers have their own predicates, infinite blocking can happen when one producer wakes up another producer (instead of a consumer) while the buffer is full and all consumers are sleeping, or vice versa. To prevent such infinite blocking, we wake up everyone once the condition changes.

Lock lock; // A mutex for the buffer.
ConditionVariable notEmptyAndNotFull;

void Producer()
{
    lock.acquire();
    while (BufferIsFull())
    {
        Wait(lock, notEmptyAndNotFull);
    }
    AddItemToBuffer(item);
    NotifyAll(notEmptyAndNotFull);
    lock.release();
}

void Consumer()
{
    lock.acquire();
    while (BufferIsEmpty())
    {
        Wait(lock, notEmptyAndNotFull);
    }
    item = RemoveItemFromBuffer();
    NotifyAll(notEmptyAndNotFull);
    lock.release();
}

Lock free with single producer and consumer

When there are only one producer and one consumer, it is possible to have a lock-free solution with FIFO (first in, first out) buffers. The basic idea is to let the producer always add items to the end of the buffer, and let the consumer always remove items from the head of the buffer. As long as the buffer is neither full nor empty, there won’t be conflicts. Once the buffer becomes either full or empty, we pause the producer or consumer accordingly.

volatile unsigned int produceCount = 0;
volatile unsigned int consumeCount = 0;
ItemType buffer[BUFFER_SIZE];

void Producer()
{
    while (produceCount - consumeCount == BUFFER_SIZE);
    buffer[produceCount % BUFFER_SIZE] = item;
    ++produceCount;
}

void Consumer() {
    while (produceCount - consumeCount == 0);
    item = buffer[consumeCount % BUFFER_SIZE]);
    ++consumeCount;
}

Contents