What is the Producer-Consumer problem?

Background and introduction

The Producer-Consumer problem is a classic synchronization problem in operating systems.

The problem is defined as follows: there is a fixed-size buffer and a Producer process, and a Consumer process.

The Producer process creates an item and adds it to the shared buffer. The Consumer process takes items out of the shared buffer and “consumes” them.

The tricky part

Certain conditions must be met by the Producer and the Consumer processes to have consistent data synchronization:

1. The Producer process must not produce an item if the shared buffer is full.

2. The Consumer process must not consume an item if the shared buffer is empty.

3. Access to the shared buffer must be mutually exclusive; this means that at any given instance, only one process should be able to access the shared buffer and make changes to it.

Solution

The solution to the Producer-Consumer problem involves three semaphore variables.

• semaphore Full: Tracks the space filled by the Producer process. It is initialized with a value of $0$ as the buffer will have $0$ filled spaces at the beginning
• semaphore Empty: Tracks the empty space in the buffer. It is initially set to buffer_size as the whole buffer is empty at the beginning.
• semaphore mutex: Used for mutual exclusion so that only one process can access the shared buffer at a time.

Using the signal() and wait() operations on these semaphores, we can arrive at a solution.

Let’s look at the code for the Producer and Consumer processes.

void Producer(){
    while(true){
        // Produce an item
        wait(Empty);
        wait(mutex);
        add();
        signal(mutex);
        signal(Full);
    }
}

In the code above, the Producer process waits for the Empty semaphore. This means that the Producer process is kept in busy-waiting if the Empty semaphore value is $0$, indicating that there are $0$ empty spaces available. The Producer will have to wait for the Consumer to consume some items from the buffer and make some space available for itself.

The Producer then waits for the mutex semaphore, which merely ensures that once a thread has entered the critical section of the code, the rest of the threads cannot access it and cause race conditions.

The add() function appends the item to the shared buffer. Once a Producer process reaches this point in the code, it is guaranteed that no other process is accessing the shared buffer concurrently, preventing data inconsistency.

After the Producer process adds the item to the shared buffer, it uses the signal() operation to increase the value of the mutex semaphore by one, thereby allowing any other threads which were busy-waiting in the mutex semaphore to access the critical section.

Lastly, the Producer process uses the signal() operation on the Full semaphore, increasing its value by $1$, indicating that an item has been added to the shared buffer and the count for the filled spaces has increased by one.

The code for the Consumer process is as follows.

void Consumer(){
    while(true){
        wait(Full);
        wait(mutex);
        consume();
        signal(mutex);
        signal(Empty)
    }
}

The Consumer waits for the Full semaphore. If the Full semaphore value is 0, it indicates that there are no items to consume, and it must wait for the Producer process to produce an item and add it to the shared buffer for consumption.

As previously mentioned, the mutex semaphore ensures mutually exclusive access to the critical section of the code so that the shared buffer is only accessed by one thread at a time for data synchronization.

Once the Consumer process reaches the critical section of the code, i.e., the consume() function, it executes the function and takes one item from the shared buffer.

After taking an item from the buffer, the Consumer process first uses signal(mutex) to release the mutex semaphore, allowing other threads that may have been busy-waiting in the mutex to access the critical section.

Lastly, the Consumer uses signal(Empty) to increase the value of the Empty semaphore by one, indicating that a free slot has been made in the shared buffer. Any Producer processes that may have been waiting in the Empty semaphore are now allowed to add an item to the shared buffer.