Algorithm for Producer–Consumer Problem

The Producer–Consumer Problem is one of the most popular examples of process synchronization in operating systems. It describes a scenario where two types of processes Producers and Consumers share a common, fixed-size buffer.

• The Producer generates data and puts it into the buffer.
• The Consumer takes data from the buffer and processes it.

The challenge is to ensure that:

1. No two processes access the buffer at the same time (Mutual Exclusion).
2. The Producer waits if the buffer is full (No Overflow).
3. The Consumer waits if the buffer is empty (No Underflow).

This problem is also called the Bounded Buffer Problem because the shared memory space (buffer) has a fixed size.

The Problem in Simple Words

Imagine you have:

• One storage box (shared buffer)
• One person making items (Producer)
• One person taking items (Consumer)

Rules:

1. The box can hold only a limited number of items (buffer size).
2. The Producer should not put an item if the box is full.
3. The Consumer should not take an item if the box is empty.
4. Only one person can open the box at a time (mutual exclusion).

This exact problem happens in computer systems when two processes (or threads) share memory.

Why We Need Semaphores

We use three semaphores:

1. mutex – A binary semaphore (0 or 1)
   • Controls mutual exclusion so that only one process can access the buffer at a time.
   • Initial value: 1 (buffer is free).
2. empty – A counting semaphore
   • Tracks how many empty slots are left in the buffer.
   • Initial value: n (buffer size).
3. full – A counting semaphore
   • Tracks how many filled slots are in the buffer.
   • Initial value: 0 (buffer starts empty).

Algorithm for Producer–Consumer Problem

Producer Process

do {
    item = produce_item();   // Step 0: Create the item
    
    wait(empty);              // Step 1: Wait if buffer is full
    wait(mutex);              // Step 2: Lock the buffer
    
    insert_item(item);        // Step 3: Add item to buffer
    
    signal(mutex);            // Step 4: Unlock the buffer
    signal(full);              // Step 5: Increase filled slot count
} while (true);

What’s Happening Here

• produce_item() – The producer creates the data before even checking the buffer. This means production is independent from storage availability.
• wait(empty) – Checks if there’s at least one empty slot. If empty = 0 → buffer full → producer stops until consumer removes something.
• wait(mutex) – Prevents race conditions by ensuring that only one process at a time can change the buffer.
• insert_item(item) – Adds the new data to the buffer.
• signal(mutex) – Releases the lock so others can use the buffer.
• signal(full) – Increases filled slot count so that consumers know there’s something to take.

Consumer Process

do {
    wait(full);               // Step 1: Wait if buffer is empty
    wait(mutex);              // Step 2: Lock the buffer
    
    item = remove_item();     // Step 3: Remove item from buffer
    
    signal(mutex);            // Step 4: Unlock the buffer
    signal(empty);             // Step 5: Increase empty slot count
    
    consume_item(item);       // Step 6: Use the item
} while (true);

What’s Happening Here

• wait(full) – Checks if there’s at least one filled slot. If full = 0 → buffer empty → consumer waits until producer adds something.
• wait(mutex) – Ensures only one process modifies the buffer at a time.
• remove_item() – Takes an item from the buffer.
• signal(mutex) – Unlocks the buffer for the other process.
• signal(empty) – Increases the empty slot count so producers can produce again.
• consume_item(item) – Uses the data (e.g., prints it, processes it, etc.).

How This Algorithm Prevents Problems

1. Mutual Exclusion

Without mutex, both producer and consumer could change the buffer at the same time, causing corrupted data.

2. No Overflow

empty ensures the producer waits when the buffer is full.

3. No Underflow

full ensures the consumer waits when the buffer is empty.

4. Fairness

Semaphores follow a queue-like system so processes get served in order.

Example with Buffer Size = 3

Initial state:
mutex = 1, empty = 3, full = 0

Producer produces first item:

• wait(empty) → empty = 2
• wait(mutex) → mutex = 0 (locked)
• insert_item → buffer = [item1]
• signal(mutex) → mutex = 1
• signal(full) → full = 1

Consumer consumes item:

• signal(empty) → empty = 3
• wait(full) → full = 0
• wait(mutex) → mutex = 0 (locked)
• remove_item → buffer = []
• signal(mutex) → mutex = 1

Conclusion

The Producer–Consumer Problem is a fundamental example of how processes can coordinate with each other to share a common resource without conflicts.