CSE Roadmap

Core tier · about 6 hours · 7 parts

Part 2 of 7 · 2 min read

The problem

Think of it this way. A sushi chef places plates on a conveyor belt that has room for eight plates. Diners take plates off. If the belt is full, the chef must wait. If it is empty, the diners must wait. Chef and diners must not grab the same plate or put two plates in one place. The analogy stops in one place: a belt moves by itself, and the buffer in a program is only a block of memory that the threads must manage.

In plain words: The producer-consumer problem (also called the bounded-buffer problem) has these parts: producers create items and put them into a shared buffer of fixed size, and consumers remove items and use them. The requirements:

  1. Mutual exclusion on the buffer. Two threads must not change the buffer's indices at the same moment.
  2. No adding to a full buffer. A producer waits when there is no free slot.
  3. No removing from an empty buffer. A consumer waits when there is no item.

Also, no item may be lost or duplicated, and no thread may wait for ever when the work it needs is available.

Why a bounded buffer? An unbounded one would let fast producers fill all memory. A bound makes the system balance itself: a fast producer is slowed down by waiting for space, a limit that has the name backpressure (section 4). A buffer also smooths out bursts: while the producer is busy for a moment, the consumer can use the stored items.

Producer-consumer problem

The producer-consumer problem is the synchronisation problem of coordinating threads that put items into a shared fixed-size buffer and threads that take items out, so that the buffer is never overfilled or read when empty, its internal state is never corrupted, and no item is lost or duplicated.

Example: a thread that reads lines from a file produces them, a pool of workers consumes them, and the queue between them has room for 8 lines.

Check yourself: 1. What must a producer do when the buffer is full? 2. Name two reasons to bound the buffer. 3. Where have you already seen this pattern in this course?