Producer-Consumer Problem

The Producer-Consumer Problem (also called the Bounded Buffer Problem) is one of the most fundamental synchronization problems in operating systems.

1. The Problem

Two types of processes share a fixed-size buffer:

• Producer: Generates data items and places them into the buffer.
• Consumer: Removes data items from the buffer and processes them.

Constraints:

1. The Producer must wait if the buffer is full (cannot produce into a full buffer).
2. The Consumer must wait if the buffer is empty (cannot consume from an empty buffer).
3. Access to the buffer must be mutually exclusive (only one process can modify the buffer at a time to prevent data corruption).

2. Solution using Semaphores

Three semaphores are needed:

• mutex (Binary Semaphore, init = 1): Ensures mutual exclusion when accessing the buffer.
• empty (Counting Semaphore, init = N): Tracks the number of empty slots in the buffer. Producer waits if this is 0.
• full (Counting Semaphore, init = 0): Tracks the number of filled slots. Consumer waits if this is 0.

Producer:

while (true) {
    item = produce();
    wait(empty);    // Decrement empty count; block if buffer full
    wait(mutex);    // Enter critical section
    buffer[in] = item;
    in = (in + 1) % N;
    signal(mutex);  // Exit critical section
    signal(full);   // Increment full count; wake consumer
}

Consumer:

while (true) {
    wait(full);     // Decrement full count; block if buffer empty
    wait(mutex);    // Enter critical section
    item = buffer[out];
    out = (out + 1) % N;
    signal(mutex);  // Exit critical section
    signal(empty);  // Increment empty count; wake producer
    consume(item);
}

3. Common Mistake: Deadlock

If the order of wait(empty) and wait(mutex) is swapped in the Producer, a deadlock can occur. The Producer acquires the mutex, then finds the buffer full and blocks on wait(empty). But the Consumer can never acquire the mutex to consume an item and signal empty, because the Producer holds it. Both processes are permanently stuck.

4. Real-World Applications

• Print Spooler: Applications (producers) add print jobs to a queue. The printer driver (consumer) processes them one at a time.
• Web Servers: Incoming HTTP requests are placed into a request queue by listener threads (producers). Worker threads (consumers) pick up and process requests.
• Video Streaming: The network thread (producer) fills a buffer with video frames. The display thread (consumer) reads and renders them.