Bounded Buffer with Mutex and Condition Variables

1. The Anatomy of a Bounded Buffer in C

To implement our buffer, we need a struct to encapsulate all the necessary components. This includes not just the data buffer itself, but also all the state and synchronization primitives.

A simple array where we shift elements on removal is inefficient. A much better approach, common in systems programming, is a circular buffer (or ring buffer). This uses a fixed-size array and two indices: one for insertion (nextin or fill_ptr) and one for removal (nextout or use_ptr). These indices wrap around to the start of the array when they reach the end, which is efficiently handled using the modulo operator (%).

Our complete struct will contain:

1. The data array itself (buf).
2. The maximum capacity (BSIZE).
3. The current number of items (occupied or count).
4. Indices to manage the circular buffer (nextin, nextout).
5. A single mutex (pthread_mutex_t).
6. Two condition variables (pthread_cond_t): one for "buffer is not full" and one for "buffer is not empty".

2. Implementing the Producer and Consumer Functions

With the data structure defined, we can now implement the producer and consumer functions that operate on it. The logic will directly follow the design from our last lesson.

The Oracle POSIX threads documentation provides an excellent, complete C implementation of this pattern. It's a canonical example and serves as a perfect reference for our implementation.

3. Dissecting the Implementation

Let's break down the key pieces of the code you just studied.

The Producer (producer function)

void producer(buffer_t *b, char item) {
    // 1. Lock the mutex to gain exclusive access.
    pthread_mutex_lock(&b->mutex);

    // 2. Wait while the buffer is full.
    //    This uses the 'wait-in-a-loop' pattern.
    while (b->occupied >= BSIZE)
        pthread_cond_wait(&b->less, &b->mutex);

    // 3. Add the item to the circular buffer.
    b->buf[b->nextin++] = item;
    b->nextin %= BSIZE; // Wrap around if necessary.
    b->occupied++;

    // 4. Signal that the buffer is no longer empty.
    //    This wakes up a waiting consumer.
    pthread_cond_signal(&b->more);

    // 5. Unlock the mutex.
    pthread_mutex_unlock(&b->mutex);
}

This code precisely implements our design. The while loop is critical for handling spurious wakeups and ensuring the buffer actually has space before proceeding. The pthread_cond_wait function atomically unlocks the mutex before waiting and re-locks it before returning.

The resource also mentions invariants—logical statements about the state of the program. For a CS practitioner, thinking in terms of invariants is a powerful way to reason about correctness. For example, a key invariant is that 0 <= b->occupied <= BSIZE must always be true outside of the critical section.

The Consumer (consumer function)

The consumer logic is perfectly symmetric:

char consumer(buffer_t *b) {
    char item;
    // 1. Lock the mutex.
    pthread_mutex_lock(&b->mutex);

    // 2. Wait while the buffer is empty.
    while(b->occupied <= 0)
        pthread_cond_wait(&b->more, &b->mutex);

    // 3. Remove an item from the circular buffer.
    item = b->buf[b->nextout++];
    b->nextout %= BSIZE; // Wrap around.
    b->occupied--;

    // 4. Signal that the buffer is no longer full.
    //    This wakes up a waiting producer.
    pthread_cond_signal(&b->less);

    // 5. Unlock the mutex and return the item.
    pthread_mutex_unlock(&b->mutex);
    return(item);
}

Here, the consumer waits on the more condition and signals the less condition, ensuring producers and consumers wake each other up correctly.

4. A Second Canonical Implementation (OSTEP)

To reinforce that this is a standard, fundamental pattern, let's look at another canonical implementation from the Operating Systems: Three Easy Pieces textbook. It's conceptually identical but uses slightly different variable names (empty, fill). Seeing this reinforces the pattern itself, separate from any specific variable naming convention.

5. A Practical Build-Up: From Naive to Correct

The examples we've studied present the final, correct solution. However, it can be illuminating to see how one might arrive at this solution from a more naive starting point. The following video, while building a thread pool, effectively implements a bounded buffer (as a task queue) from scratch. It clearly demonstrates the progression of thought: first protecting the data with a mutex, realizing this leads to inefficient busy-waiting, and finally adding condition variables for an efficient solution.

Note that this video uses a simple array-shifting approach for its queue. This is less performant than the circular buffer we've implemented but serves well to illustrate the synchronization logic in isolation.

Conclusion

In this lesson, we have successfully translated the design of a bounded buffer into a complete, efficient, and robust C implementation. You now have the code for one of the most fundamental data structures in concurrent programming.

Key Takeaways:

• A bounded buffer is best implemented with a circular array to avoid inefficient data shifting. This is managed with two indices and the modulo operator.
• The entire state, including the buffer, indices, count, mutex, and two condition variables, should be encapsulated in a single struct.
• The producer function waits on a "not full" condition (less or empty) and signals a "not empty" condition (more or fill).
• The consumer function waits on the "not empty" condition and signals the "not full" condition.
• This two-condition-variable pattern is the standard, correct way to prevent deadlocks and ensure that producers wake consumers and vice-versa.

Preview of the Next Lesson:
You have now implemented the core data structure. In the next lesson, you will write a program with multiple producer and consumer threads interacting via the bounded buffer. We will create several producer and consumer threads and have them all operate on a single instance of your buffer_t, putting your implementation to the test in a true multi-threaded environment.