Skip to content
Tutorials Center
My learning

Topics

Lesson 26 of 66 ยท Synchronization

The Producer-Consumer (Bounded Buffer) Problem

Solve the bounded-buffer problem with three semaphores, see why the order of wait calls matters, and watch a deadlock appear in a runnable Python simulation.

A producer creates items and a consumer uses them. A web server's network thread produces requests that worker threads consume. A shell pipeline ls | sort has a producer (ls) and a consumer (sort) connected by a pipe. They are decoupled by a bounded buffer: a queue of fixed size N in shared memory.

The rules are simple and the difficulty is in meeting all of them at once:

  • The producer must wait when the buffer is full (nowhere to put the item).
  • The consumer must wait when the buffer is empty (nothing to take).
  • Only one thread may change the buffer's internal state at a time (otherwise two producers could write the same slot).
flowchart LR
    P["Producer"] -- "put item" --> B["Buffer (N slots)"]
    B -- "take item" --> C["Consumer"]
    E["empty = N"] -. "free slots" .-> P
    F["full = 0"] -. "filled slots" .-> C

Two counting semaphores track free and filled slots; a third, mutex, protects the buffer itself.

The three-semaphore solution

Semaphore Initial value Meaning
empty N How many slots are free
full 0 How many slots hold an item
mutex 1 Exclusive access to the buffer indexes
TEXT
producer:                       consumer:
    produce item                    wait(full)       # wait for an item
    wait(empty)   # wait for room   wait(mutex)
    wait(mutex)                     remove item from buffer
    insert item into buffer         signal(mutex)
    signal(mutex)                   signal(empty)    # one more free slot
    signal(full)  # one more item   consume item

Each side waits on the semaphore that counts what it needs (empty for the producer, full for the consumer) and signals the semaphore the other side needs.

Running it

We reuse the mini kernel from the semaphores lesson: threads yield ("P", sem) or ("V", sem); the scheduler blocks and wakes them. Items are numbered so we can verify that everything produced is consumed, once and in order.

Python Bounded buffer with empty, full and mutex

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

All twelve items arrive in order, the buffer never holds more than 3, and nobody is stuck. Try more producers and consumers: change the call to run({"P1": producer(6), "P2": producer(6), "C1": consumer(6), "C2": consumer(6)}) and the items still all arrive (their order will now interleave, because two producers write them).

Swap two lines and everything deadlocks

The order of the two wait calls matters. Suppose the producer takes the mutex first and only then checks for free space:

TEXT
producer:   wait(mutex)       # WRONG ORDER
            wait(empty)       # blocks while holding the mutex!

If the buffer is full, the producer sleeps on empty while holding mutex. The consumer needs mutex to remove an item and make room, but the producer holds it. Neither can move. This is a deadlock, the topic of the next chapter.

Python The wrong order deadlocks

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The correct order never deadlocks. With the mutex taken first, the very first consumer (or a full buffer) can freeze the system, and many schedules do. Note the consumer in the buggy version has the same flaw: it holds the mutex while waiting on full.

What if there is no buffer limit?

With an unbounded buffer the producer never waits, so empty is unnecessary; only full and mutex remain. With a single slot the buffer is the same as a handoff between two threads. Real systems pick N to smooth out bursts: a larger buffer absorbs speed differences at the cost of memory and latency.

Where you meet this pattern

  • Pipes and sockets: the kernel keeps a bounded buffer; writes block when it is full, reads block when it is empty.
  • Thread pools and job queues: producers enqueue tasks, workers dequeue them.
  • Logging and I/O buffering: your program produces log lines, a background thread writes them out.
  • Stream processing: each pipeline stage is a consumer of the previous one and a producer for the next.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What are the initial values of empty, full and mutex for a buffer with N slots?

    All N slots start free (empty = N), none are filled (full = 0), and the mutex starts unlocked (1).
  2. 2. Why is mutex needed in addition to empty and full?

    empty and full only count; they do not stop two producers from writing the same slot at once. The mutex protects the buffer itself.
  3. 3. The producer calls wait(mutex) and then wait(empty). What can go wrong?

    Waiting for a condition while holding a lock the other side needs is a classic deadlock.
  4. 4. A pipe between two shell commands is an example of which pattern?

    The kernel's pipe buffer is bounded; the writer blocks when it is full and the reader blocks when it is empty.

Summary

  • The bounded buffer needs three semaphores: empty (N), full (0) and mutex (1).
  • Producers wait on empty and signal full; consumers do the reverse.
  • Always wait for the counting semaphore before taking the mutex; the reverse order can deadlock.
  • The same pattern appears in pipes, thread pools, logging and streaming.

Next: The Readers-Writers Problem