The Producer–Consumer (Bounded Buffer) Problem

 

The Producer–Consumer (Bounded Buffer) Problem

The producer–consumer problem is a classic synchronization problem that captures many real-world concurrency issues.

The idea is simple:

  • Producers generate data items and place them into a shared buffer

  • Consumers remove data items from the buffer and use them

  • The buffer has a fixed size (bounded)

Key Constraints

  1. A producer must not insert into a full buffer

  2. A consumer must not remove from an empty buffer

  3. Producers and consumers must not corrupt shared data

  4. The solution must avoid race conditions and deadlock

First Attempt: Using empty and full Semaphores

In our first attempt to solve the producer–consumer (bounded buffer) problem, we introduce two counting semaphores:

  • empty – indicates how many buffer slots are empty

  • full – indicates how many buffer slots are full

These semaphores allow producers and consumers to coordinate access to the shared buffer.

Shared Buffer and Helper Routines

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;
}

  • put() inserts an item into the buffer

  • get() removes an item from the buffer

  • The buffer is treated as a circular array

Semaphore-Based Solution 

Semaphore Initialization

sem_init(&empty, 0, MAX);  // all slots initially empty
sem_init(&full, 0, 0);    // no slots initially full

  • empty = MAX → all buffer slots are free

  • full = 0 → no items available to consume

Producer Code ( Major )

sem_wait(&empty);   // Line P1: wait for empty slot
put(i);             // Line P2: insert item
sem_post(&full);    // Line P3: signal item available

Consumer Code ( Major) 

sem_wait(&full);    // Line C1: wait for full slot
tmp = get();        // Line C2: remove item
sem_post(&empty);   // Line C3: signal empty slot



Execution Scenario: MAX = 1 (Single Buffer Slot)

Assume:

  • One producer

  • One consumer

  • Single CPU

Step 1: Consumer Runs First

  • Consumer calls sem_wait(&full) (Line C1)

  • Since full = 0, it is decremented to –1

  • Consumer blocks and waits for data

✔ Correct behavior: consumer waits because buffer is empty

Step 2: Producer Runs

  • Producer calls sem_wait(&empty) (Line P1)

  • Since empty = 1, it decrements to 0 and proceeds

  • Producer inserts data using put()

  • Producer calls sem_post(&full) (Line P3)

    • full becomes 0

    • Consumer is woken up

Step 3: What Happens Next?

Two possible outcomes:

  1. Producer continues running

    • Tries sem_wait(&empty) again

    • Blocks because empty = 0

  2. Consumer runs

    • Returns from sem_wait(&full)

    • Consumes the item

    • Signals empty

✔ In both cases, behavior is correct

Why This Works (So Far)

  • Producer waits if buffer is full

  • Consumer waits if buffer is empty

  • Semaphores correctly coordinate access

  • Works for:

    • One producer, one consumer

    • Multiple producers and consumers

    • MAX = 1

Important Note

⚠️ This solution does not yet provide mutual exclusion

  • put() and get() access shared variables (fill, use)

  • With MAX > 1 and multiple producers or consumers, race conditions can occur

  • This limitation is addressed in the next step by adding a mutex semaphore

Key Takeaway

This first attempt correctly handles buffer availability, but not mutual exclusion.

It is a necessary but incomplete solution, laying the foundation for the fully correct producer–consumer implementation.


Why the First Attempt Fails When MAX > 1

So far, our solution using the empty and full semaphores works correctly only when there is a single producer and a single consumer, or when MAX = 1.

Now let’s consider a more realistic case:

  • MAX = 10 (buffer has multiple slots)

  • Multiple producers

  • Multiple consumers

At this point, a race condition occurs.

Where Is the Problem?

The problem is not with the semaphores empty and full.

The problem lies in the put() and get() functions, specifically in the shared variables:

int fill = 0;
int use = 0;

These variables are accessed and modified by multiple threads without protection.

Understanding the Race Condition (Two Producers Case)

Let’s walk through a concrete example.

Initial State

  • fill = 0

  • Buffer is empty

  • Two producer threads: Pa and Pb

Step-by-Step Execution

Step 1: Producer Pa Runs

  • Pa enters put()

  • Executes:

    buffer[fill] = value;   // fill = 0

  • Pa writes data into buffer[0]

  • Before Pa can execute fill = fill + 1, it gets interrupted

Step 2: Producer Pb Runs

  • Pb also enters put()

  • fill is still 0

  • Pb executes:

    buffer[fill] = value;   // fill = 0

  • Pb overwrites buffer[0]

  • The data written by Pa is lost

What Went Wrong?

  • Both producers read the same value of fill

  • They both wrote to the same buffer slot

  • Updates to fill were not atomic

  • There was no mutual exclusion

Why Semaphores Alone Were Not Enough

The semaphores:

  • empty → ensure there is space in the buffer

  • full → ensure there is data to consume

✔ They control when producers and consumers run
❌ They do not protect how shared data is accessed

Root Cause of the Race Condition

The put() and get() functions form critical sections, but they are not protected by a lock.

Specifically:

  • buffer[]

  • fill

  • use

are shared variables accessed concurrently.

Key Insight for Students

Counting semaphores manage availability, not mutual exclusion.

To fix this problem, we must:

  • Introduce a mutex (binary semaphore)

  • Protect the put() and get() operations

  • Ensure only one producer or consumer manipulates buffer indices at a time

Summary

Aspect    Status
Race condition present    ❌ Yes
Data overwrite possible    ❌ Yes
Semaphores sufficient alone    ❌ No
Mutual exclusion needed    ✅ Yes

This realization leads directly to the next step:
👉 Adding a mutex semaphore to protect the critical section

Adding Mutual Exclusion: The Idea

We already identified the problem:

  • put() and get() access shared variables (buffer, fill, use)

  • These are critical sections

  • Therefore, we add a binary semaphore (mutex) to ensure mutual exclusion

So the intuition is correct:

“Only one thread at a time should execute put() or get().”

Figure 31.11 does exactly that by surrounding the code with a mutex.



Why This Still Doesn’t Work: Deadlock 

Even though mutual exclusion is added, the program can now deadlock.

Let’s see exactly how.

The Problematic Code Pattern (Figure 31.11)

Simplified view:

Consumer

sem_wait(&mutex);   // lock
sem_wait(&full);    // wait for data
get();
sem_post(&empty);
sem_post(&mutex);   // unlock

Producer

sem_wait(&mutex);   // lock
sem_wait(&empty);   // wait for space
put();
sem_post(&full);
sem_post(&mutex);   // unlock

Deadlock Scenario (Step-by-Step)

Assume:

  • Buffer is initially empty

  • One producer, one consumer

  • Single CPU

Step 1: Consumer Runs First

  1. Consumer calls:

    sem_wait(&mutex);

    → Acquires the mutex

  2. Consumer then calls:

    sem_wait(&full);

    → full == 0, so consumer blocks
    → Consumer is now sleeping
    → BUT it still holds the mutex

Step 2: Producer Runs

  1. Producer calls:

    sem_wait(&mutex);

    → Mutex is already held by the consumer
    → Producer blocks

And Now… Deadlock

At this point:

Thread        StateWaiting For
Consumer        Blocked    full to be signaled
Producer        Blocked    mutex to be released

Why this is fatal:

  • Consumer cannot release the mutex until full is posted

  • Producer cannot post full because it cannot acquire the mutex

  • No thread can make progress

👉 This is a circular wait — the defining condition of deadlock.

Why This Happens (Key Insight)

You must never sleep while holding a lock.

In this code:

  • sem_wait(&full) and sem_wait(&empty) can block

  • The mutex is acquired before those blocking calls

  • This violates a fundamental concurrency rule

Summary

What We Tried

  • Added a mutex to protect shared data

  • Correct idea ✅

What Went Wrong

  • Threads block while holding the mutex

  • Creates a circular wait

  • Results in deadlock ❌

Core Lesson 

Do not hold a mutex while performing a potentially blocking operation.

What Comes Next

The fix is simple but subtle:

  • Acquire empty / full first

  • Acquire the mutex only around the actual critical section

That leads to Figure 31.12, the correct and deadlock-free solution.



At Last, a Working Solution: Correct Producer–Consumer Design

The deadlock in the previous attempt occurred because threads were holding a mutex while performing blocking operations (sem_wait on full or empty). To fix this, we must reduce the scope of the lock.

Key Idea

  • The mutex should protect only the true critical section

  • Blocking operations (sem_wait, sem_post) should not be performed while holding the mutex

This leads to a correct and deadlock-free solution, shown in Figure 31.12.


Correct Producer Code

void *producer(void *arg) {
    int i;
    for (i = 0; i < loops; i++) {
        sem_wait(&empty);     // wait for empty slot
        sem_wait(&mutex);     // enter critical section

        put(i);               // critical section

        sem_post(&mutex);     // exit critical section
        sem_post(&full);      // signal item available
    }
}

Correct Consumer Code

void *consumer(void *arg) {
    int i;
    for (i = 0; i < loops; i++) {
        sem_wait(&full);      // wait for available item
        sem_wait(&mutex);     // enter critical section

        int tmp = get();      // critical section

        sem_post(&mutex);     // exit critical section
        sem_post(&empty);     // signal empty slot
        printf("%d\n", tmp);
    }
}

Why This Solution Works

1. No Deadlock

  • Threads never block while holding the mutex

  • sem_wait(&empty) and sem_wait(&full) occur before acquiring the mutex

2. Mutual Exclusion is Preserved

  • put() and get() are fully protected

  • Only one thread can modify buffer, fill, or use at a time

3. Correct Ordering

  • Producers wait for empty slots

  • Consumers wait for full slots

  • Semaphores correctly coordinate access

Design Pattern to Remember 

Use semaphores for resource counting (empty/full)
Use a mutex only for protecting shared data

Comments

Post a Comment

Popular posts from this blog

Operating Systems OS PCCST403 Semester 4 BTech KTU CS 2024 Scheme

 About Me Scheme and Syllabus Module-1 Introduction and CPU Scheduling Introduction to OS - 3 important pieces- virtualization, concurrency, persistence Operating System Services Operating System and Kernel Linux Versus Classic Unix Kernels Difference between Linux and Unix Kernels Process and Process Creation- overview Process States in Operating System Data Structures in Operating Systems Key Aspects of a Program and Process in an Operating System-Summary Sharing the Processor Among Processes System Boot Sequence Threads and Concurrency Case Study: Linux Kernel Process management Case Study: Linux Implementation of Threads CPU Scheduling Multi-level feedback Queue ( MLFQ) Scheduler How MLFQ Approximates Shortest Job First (SJF) I/O in MLFQ Problems With the Basic MLFQ Scheduler Solving the Issues with MLFQ Scheduler Case Study: Linux Completely Fair Scheduler (CFS) Module-2 Concurrency and Synchronization Tools Concurrency and Synchronization- Basic principles Critical secti...
Read more

Introduction to Operating System -Virtualization, Concurrency, and Persistence

  How Operating Systems Really Work: Virtualization, Concurrency, and Persistence Have you ever wondered how your laptop can play music, run a web browser, download files, and open a Word document—all at the same time—without melting down? It might look simple, but beneath the surface, your operating system (OS) is doing incredibly sophisticated work. In this , we’ll break down the three most important ideas that make modern operating systems possible: Virtualization Concurrency Persistence These concepts are the foundation of how computers manage programs(applications), memory, and data.  1. Virtualization: Making One Computer Look Like Many Virtualization is all about creating useful illusions . You might have Spotify playing, Instagram open, and a browser loading—all on one phone. It feels like all apps run simultaneously, but the phone is rapidly switching between them so smoothly you don’t notice. Virtualization = making one CPU appear like many. Ev...
Read more

Differences Between Linux and Classic UNIX Kernels

  Differences Between Linux and Classic UNIX Kernels Although Linux and classic UNIX kernels share a common heritage and a similar system-call interface, Linux introduces several important design improvements that distinguish it from traditional UNIX systems. 1. Dynamic Kernel Modules Linux supports dynamic loading and unloading of kernel modules at runtime. Even though Linux is a monolithic kernel , new functionality (such as device drivers) can be added without rebooting. Classic UNIX kernels are mostly static , requiring recompilation and reboot for changes. 2. Symmetric Multiprocessing (SMP) Support Linux has strong SMP support , allowing efficient use of multiple CPUs. Traditional UNIX implementations had limited or no SMP support. Many modern UNIX variants added SMP later, but Linux was designed with scalability in mind. 3. Kernel Preemption The Linux kernel is fully preemptive , meaning a running kernel task can be interrupted to improve r...
Read more