Producer-Consumer Problem

operating-systems concurrency

Definition

Producer-Consumer Problem

The producer-consumer problem (or bounded-buffer problem) is a classic synchronisation problem where two types of processes—producers and consumers—share a common, fixed-size buffer.

• Producers generate data and place it into the buffer.
• Consumers retrieve data from the buffer and process it.

Synchronisation Requirements

To ensure the system operates correctly, two types of synchronisation must be enforced:

1. Mutual Exclusion: Only one process (either a producer or a consumer) may access the buffer at any given time to prevent data corruption.
2. **Condition Synchronisation_*:
   • A producer must wait if the buffer is full (in the bounded case).
   • A consumer must wait if the buffer is empty.

Visual Representation

Implementation with Semaphores

The following implementation uses three semaphores:

• S: A binary semaphore for mutual exclusion on the buffer.
• N: A counting semaphore representing the number of items currently in the buffer (initialised to 0).
• E: A counting semaphore representing the number of empty slots (initialised to the buffer size $K$).

Producer

loop
    produce(item);
    wait(E); // Wait for an empty slot
    wait(S); // Enter critical section
    append(item);
    signal(S); // Leave critical section
    signal(N); // Increment count of items
end loop;

Consumer

loop
    wait(N); // Wait for an item to be available
    wait(S); // Enter critical section
    item := take();
    signal(S); // Leave critical section
    signal(E); // Increment count of empty slots
    consume(item);
end loop;

Deadlock Risk

The order of wait operations is critical. If a process acquires the mutex S before checking the condition semaphore (N or E), a deadlock may occur if the buffer is empty/full, as the process will block while holding the lock.