Skip to content

Producer-Consumer (LLD)#

Problem statement (interviewer prompt)

Design a thread-safe bounded buffer with N producer threads writing and M consumer threads reading. Producers block when the buffer is full; consumers block when it's empty. Implement with mutex + condition variables and discuss the lock-free / channel alternatives.

classDiagram
  class BoundedBuffer~T~ {
    -capacity : int
    -queue : Deque~T~
    -lock : Mutex
    -notFull : Condition
    -notEmpty : Condition
    +put(item) void
    +take() T
  }
  class Producer {
    -buffer : BoundedBuffer
    +run()
  }
  class Consumer {
    -buffer : BoundedBuffer
    +run()
  }
  Producer --> BoundedBuffer
  Consumer --> BoundedBuffer

Producers wait on notFull (signal notEmpty after put); consumers wait on notEmpty (signal notFull after take).

classDef client fill:#dbeafe,stroke:#1e40af,stroke-width:1px,color:#0f172a;
classDef edge fill:#cffafe,stroke:#0e7490,stroke-width:1px,color:#0f172a;
classDef service fill:#fef3c7,stroke:#92400e,stroke-width:1px,color:#0f172a;
classDef datastore fill:#fee2e2,stroke:#991b1b,stroke-width:1px,color:#0f172a;
classDef cache fill:#fed7aa,stroke:#9a3412,stroke-width:1px,color:#0f172a;
classDef queue fill:#ede9fe,stroke:#5b21b6,stroke-width:1px,color:#0f172a;
classDef compute fill:#d1fae5,stroke:#065f46,stroke-width:1px,color:#0f172a;
classDef storage fill:#e5e7eb,stroke:#374151,stroke-width:1px,color:#0f172a;
classDef external fill:#fce7f3,stroke:#9d174d,stroke-width:1px,color:#0f172a;
classDef obs fill:#f3e8ff,stroke:#6b21a8,stroke-width:1px,color:#0f172a;

The bounded buffer is the canonical concurrency primitive. Get it right and you understand 80% of multi-threaded coordination.

Class diagram#

classDiagram
  class BoundedBuffer~T~ {
    -capacity : int
    -queue : ArrayDeque~T~
    -lock : ReentrantLock
    -notFull : Condition
    -notEmpty : Condition
    -closed : boolean
    +put(item) void
    +take() T
    +close()
  }
  class Producer {
    -buffer : BoundedBuffer
    -source : Iterator
    +run()
  }
  class Consumer {
    -buffer : BoundedBuffer
    -handler : Function
    +run()
  }
  Producer --> BoundedBuffer
  Consumer --> BoundedBuffer

The canonical implementation#

class BoundedBuffer<T> {
  private final int capacity;
  private final Deque<T> q = new ArrayDeque<>();
  private final ReentrantLock lock = new ReentrantLock();
  private final Condition notFull  = lock.newCondition();
  private final Condition notEmpty = lock.newCondition();

  public void put(T item) throws InterruptedException {
    lock.lock();
    try {
      while (q.size() == capacity) notFull.await();   // while, not if!
      q.addLast(item);
      notEmpty.signal();
    } finally { lock.unlock(); }
  }

  public T take() throws InterruptedException {
    lock.lock();
    try {
      while (q.isEmpty()) notEmpty.await();
      T item = q.removeFirst();
      notFull.signal();
      return item;
    } finally { lock.unlock(); }
  }
}

Three subtle bugs to avoid#

Bug Symptom Fix
if instead of while around await Spurious wakeups consume an empty/full buffer Always re-check the predicate in a loop
Signal under no lock Lost wakeup Hold the lock when calling signal()
Signal one when many waiting on different conditions One side starves Use separate notFull / notEmpty conditions, not one shared

Shutdown protocol#

public void close() {
  lock.lock();
  try {
    closed = true;
    notEmpty.signalAll();  // wake all consumers so they can exit
    notFull.signalAll();
  } finally { lock.unlock(); }
}

Consumers check closed && q.isEmpty() to exit. Producers throw if put after close.

Alternatives#

Library primitives#

Lang Built-in
Java ArrayBlockingQueue, LinkedBlockingQueue
Python queue.Queue
Go chan T (the language is this pattern)
Rust crossbeam::channel, tokio::sync::mpsc
C++ folly MPMCQueue, boost lockfree

Roll your own only as an exercise; production code uses these.

Lock-free MPMC ring (LMAX Disruptor)#

flowchart LR
  P[Producer cursor] -->|claim next seq| Ring[(Ring buffer<br/>power-of-2 size)]
  Ring --> C[Consumer cursor]
  Ring -. seq barriers prevent overlap .-> C

    classDef client fill:#dbeafe,stroke:#1e40af,stroke-width:1px,color:#0f172a;
    classDef edge fill:#cffafe,stroke:#0e7490,stroke-width:1px,color:#0f172a;
    classDef service fill:#fef3c7,stroke:#92400e,stroke-width:1px,color:#0f172a;
    classDef datastore fill:#fee2e2,stroke:#991b1b,stroke-width:1px,color:#0f172a;
    classDef cache fill:#fed7aa,stroke:#9a3412,stroke-width:1px,color:#0f172a;
    classDef queue fill:#ede9fe,stroke:#5b21b6,stroke-width:1px,color:#0f172a;
    classDef compute fill:#d1fae5,stroke:#065f46,stroke-width:1px,color:#0f172a;
    classDef storage fill:#e5e7eb,stroke:#374151,stroke-width:1px,color:#0f172a;
    classDef external fill:#fce7f3,stroke:#9d174d,stroke-width:1px,color:#0f172a;
    classDef obs fill:#f3e8ff,stroke:#6b21a8,stroke-width:1px,color:#0f172a;
    class P,C service;
    class Ring queue;

CAS-based; eliminates the lock; cache-friendly. Used in low-latency trading.

Backpressure shape#

  • Blocking put (default): bounded buffer is the back-pressure.
  • offer with timeout: try, give up after T ms.
  • offer non-blocking: drop newest if full (telemetry pattern).
  • drainTo(coll): batch consume.

Where producer-consumer fits#

flowchart TB
  PC((Producer-<br/>consumer))
  CP[Concurrency primitives<br/>mutex + condvar parent]
  AS[Async models<br/>channels in Go / Rust]
  BP[Backpressure<br/>bounded buffer is one form]
  PS[Pub/Sub LLD<br/>multi-subscriber variant]
  CP --> PC
  AS -. channels alt .- PC
  PC --> BP
  PC -. extends to .-> PS

    classDef client fill:#dbeafe,stroke:#1e40af,stroke-width:1px,color:#0f172a;
    classDef edge fill:#cffafe,stroke:#0e7490,stroke-width:1px,color:#0f172a;
    classDef service fill:#fef3c7,stroke:#92400e,stroke-width:1px,color:#0f172a;
    classDef datastore fill:#fee2e2,stroke:#991b1b,stroke-width:1px,color:#0f172a;
    classDef cache fill:#fed7aa,stroke:#9a3412,stroke-width:1px,color:#0f172a;
    classDef queue fill:#ede9fe,stroke:#5b21b6,stroke-width:1px,color:#0f172a;
    classDef compute fill:#d1fae5,stroke:#065f46,stroke-width:1px,color:#0f172a;
    classDef storage fill:#e5e7eb,stroke:#374151,stroke-width:1px,color:#0f172a;
    classDef external fill:#fce7f3,stroke:#9d174d,stroke-width:1px,color:#0f172a;
    classDef obs fill:#f3e8ff,stroke:#6b21a8,stroke-width:1px,color:#0f172a;
    class PC service;
    class CP,AS,BP,PS datastore;

Glossary & fundamentals#

Tag Concept What it is Page
LLD Concurrency primitives mutex, condition variable concurrency-primitives
LLD Threading and deadlocks sibling failure modes threading-and-deadlocks
LLD Async models channels are async producer-consumer async-models
HLD Backpressure broader flow-control framing backpressure

Quick reference#

Recipe#

  • Mutex + two condition vars: notFull, notEmpty
  • put: while (full) notFull.await(); add; notEmpty.signal();
  • take: while (empty) notEmpty.await(); remove; notFull.signal();

Subtleties#

  • Use while, not if (spurious wakeups)
  • Signal while holding the lock
  • Separate conditions, not one shared
  • signalAll on shutdown to wake everyone

Shutdown#

  • Mark closed = true
  • signalAll() both conditions
  • Consumers exit when closed && empty

Alternatives#

  • Java: ArrayBlockingQueue, LinkedBlockingQueue
  • Python: queue.Queue
  • Go: chan T (language-native)
  • Rust: crossbeam, tokio mpsc
  • C++: folly MPMCQueue

Lock-free#

LMAX Disruptor ring buffer; CAS-based; cache-friendly; for ultra-low latency.

Backpressure modes#

  • Blocking put (default)
  • offer with timeout
  • offer drop-newest
  • drainTo for batches

Refs#

  • Herlihy & Shavit - Multiprocessor Programming
  • Java ArrayBlockingQueue docs
  • LMAX Disruptor

FAQ#

How do you implement a bounded buffer?#

A queue guarded by one mutex with two condition variables: notFull for producers waiting on space, notEmpty for consumers waiting on items. Signals wake exactly one peer.

Why use two condition variables instead of one?#

Splitting notFull and notEmpty avoids spurious wakeups across producer and consumer roles; signalling the right CV wakes only the side that can make progress.

What happens when notify wakes a thread but the predicate is still false?#

The thread must re-check the condition in a while loop because of spurious wakeups and because another thread may have raced ahead and consumed the slot first.

When is a lock-free queue better than mutex plus condition?#

When the producer-consumer rate is extremely high (millions per second) and any contention dominates. LMAX Disruptor and CAS-based ring buffers win at that scale.

How does this differ from Go channels?#

Channels are higher-level: select, close semantics, and built-in cancellation. Underneath, a buffered channel is still a bounded buffer with mutex and waker queues.

Further reading#

Video walkthrough

Producer Consumer Problem in Java: Blocking Queue + Threads : via Java Concurrency