vault

Producer-Consumer

21 min read

Producer-Consumer

The Producer-Consumer Problem (also called the bounded-buffer problem) is the canonical synchronization problem: one or more producer threads generate items and put them into a shared bounded buffer; one or more consumer threads remove and process them. Because the buffer has finite capacity, producers must block when it is full; because items are not always available, consumers must block when it is empty. The buffer decouples producers from consumers — they can run at different rates, smoothing bursts and isolating failure. Three textbook solutions exist: (1) two semaphores plus a mutex (Dijkstra 1965), (2) a single mutex with two condition variables, (3) lock-free queues using atomics. The problem appears every time you have a thread pool, a message queue, an HTTP server’s request pipeline, an OS scheduler’s run queue, or a streaming-data pipeline. In Python, queue.Queue is the thread-safe canonical implementation; in Java, the BlockingQueue interface and its implementations.

1. Intuition — The Factory Assembly Line

Picture a factory: a worker on the left side produces widgets and places them on a conveyor belt; a worker on the right side consumes them off the belt to package them. The belt holds at most 10 widgets at a time — it has bounded capacity. The producer’s hands are faster than the consumer’s, but only sometimes; sometimes it’s the other way around. Without coordination:

  • If the producer never stops, the belt overflows and widgets crash to the floor.
  • If the consumer doesn’t pause when the belt is empty, she grabs at empty air.
  • If both grab the same physical spot at the same moment, they fight over the widget.

The Producer-Consumer protocol is the rules they agree on: (a) the producer waits when the belt is full, (b) the consumer waits when the belt is empty, (c) they take turns reaching for the same physical spot so they never collide. Implemented in software, the belt is a bounded buffer — typically a fixed-capacity queue (Queue of size N, often a circular buffer); the rules are enforced by primitives (Mutex vs Semaphore vs Condition Variable).

A second analogy: a coffee shop. The barista (producer) makes drinks and places them on the pickup counter (buffer); customers (consumers) take drinks off the counter. The counter has only so much room — when full, the barista pauses; when empty, customers wait. Critically, the counter decouples the rate of espresso-making from the rate of customer arrival. Bursts in arrivals (a tour bus showing up) are absorbed by the counter without making the barista panic; lulls in arrivals just mean drinks sit on the counter longer. This decoupling is the reason producer-consumer is the universal pattern in distributed systems: it converts back-pressure (slow consumer) into a single observable signal (full buffer) that the producer can react to coherently.

2. Tiny Worked Example — Two Producers, One Consumer

Buffer capacity = 3. Producers P1, P2 each enqueue 4 items (so 8 total); Consumer C dequeues 8.

A possible interleaving:

StepActionBuffer stateNotes
1P1 puts 1[1]OK; size 1
2P2 puts 2[1, 2]OK; size 2
3P1 puts 3[1, 2, 3]OK; size 3 (full)
4P1 attempts 4[1, 2, 3]BLOCKS — buffer full
5C takes[2, 3]reads 1; size 2
6P1 wakes, puts 4[2, 3, 4]size 3
7P2 attempts 5[2, 3, 4]BLOCKS
8C takes[3, 4]reads 2
9P2 wakes, puts 5[3, 4, 5]size 3
…………

Consumer reads in FIFO order: 1, 2, 3, 4, 5, 6, 7, 8 (modulo whatever P1/P2 interleaving did to the order of 1, 2, 3, 4 vs 5, 6, 7, 8). The crucial properties: the buffer’s size is always in [0, 3] (safety) and producers eventually unblock when the consumer drains the buffer (liveness). If liveness fails — say the consumer crashes — both producers wedge forever; this is deadlock-by-stalled-consumer, mitigated in production by timeouts or shutdown signals.

3. Pseudocode — Three Classical Solutions

3.1 Solution 1 — Two Semaphores plus Mutex (Dijkstra 1965)

The textbook OS solution from EWD 123, “Cooperating Sequential Processes,” 1965. Three primitives:

  • mutex: protects the buffer’s data structure (binary semaphore or true mutex).
  • empty: counting semaphore; tracks number of empty slots, init to N (buffer capacity).
  • full: counting semaphore; tracks number of filled slots, init to 0.
producer():
    loop:
        item = produce()
        empty.acquire()           # wait for space; decrements empty count
        mutex.acquire()
        buffer.put(item)
        mutex.release()
        full.release()            # increment full count; wakes a consumer

consumer():
    loop:
        full.acquire()            # wait for an item; decrements full count
        mutex.acquire()
        item = buffer.get()
        mutex.release()
        empty.release()           # increment empty count; wakes a producer
        consume(item)

Why two semaphores? Each one models a different resource. empty is “permission to add” — N tokens initially, depleted as the buffer fills. full is “permission to remove” — 0 tokens initially, replenished as the buffer fills. Producers consume empty-tokens and create full-tokens; consumers consume full-tokens and create empty-tokens. The mutex is needed because the buffer’s internal state (head/tail pointers, count) is not itself thread-safe.

Why the order matters: acquire empty before mutex (and full before mutex). If you swap the order — mutex.acquire() then empty.acquire() — and the buffer is full, the producer holds the mutex while waiting on empty, blocking all consumers from removing items, deadlocking the system. Always acquire the counting semaphore outside the mutex.

3.2 Solution 2 — Mutex with Two Condition Variables

The condvar solution is more readable and arguably more flexible. One mutex protects the buffer; two condvars (not_full and not_empty) carry the “buffer state changed” signals.

producer():
    loop:
        item = produce()
        mutex.acquire()
        while buffer.size == N:           # while, not if (Mesa semantics)
            not_full.wait(mutex)
        buffer.put(item)
        not_empty.notify()
        mutex.release()

consumer():
    loop:
        mutex.acquire()
        while buffer.size == 0:
            not_empty.wait(mutex)
        item = buffer.get()
        not_full.notify()
        mutex.release()
        consume(item)

Why two condvars? A producer wakes up when the buffer becomes “not full”; a consumer wakes up when it becomes “not empty.” If you used a single condvar shared between producers and consumers, you would have to notify_all on every change so that the right kind of waiter wakes up — the thundering herd. Two condvars on the same mutex give you precise targeting.

Why while not if: Mesa-style condvars (the kind used by Python, Java, C++, POSIX) do not guarantee that a waiter, once notified, finds the predicate true. Other threads can sneak in between notify and the waiter re-acquiring the mutex, possibly invalidating the predicate. Spurious wakeups (OS-allowed wake-ups with no notify) are also possible. Always re-check the predicate. See Mutex vs Semaphore vs Condition Variable §7.3.

3.3 Solution 3 — Lock-Free Queue (Atomics)

For very high-throughput systems where mutex contention dominates runtime, a lock-free queue uses atomic compare-and-swap (CAS) instead of locks. The classic algorithm is Michael-Scott’s MPMC queue (Michael & Scott, “Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms,” PODC 1996), which underlies java.util.concurrent.ConcurrentLinkedQueue.

# Sketch only — production code is dramatically more involved
enqueue(item):
    new_node = Node(item)
    loop:
        tail = tail_atomic.load()
        next = tail.next.load()
        if tail == tail_atomic.load():           # consistency check
            if next == NULL:
                if tail.next.compare_and_swap(NULL, new_node):
                    tail_atomic.compare_and_swap(tail, new_node)
                    return
            else:
                # tail is lagging; help advance it
                tail_atomic.compare_and_swap(tail, next)

dequeue() -> item:
    loop:
        head = head_atomic.load()
        tail = tail_atomic.load()
        next = head.next.load()
        if head == head_atomic.load():
            if head == tail:
                if next == NULL: return EMPTY
                tail_atomic.compare_and_swap(tail, next)
            else:
                item = next.value
                if head_atomic.compare_and_swap(head, next):
                    return item

Why this is hard: the CAS-based version is correct only if you also handle the ABA problem (a pointer value A is freed, reallocated, returned to A — naive CAS can’t tell the difference) and the right memory model (acquire-release fences on each atomic operation). Java’s GC sidesteps ABA. C/C++ implementations use hazard pointers or epochs. Lock-free wins on contention but loses dramatically in code complexity. Don’t write your own. Use ConcurrentLinkedQueue (Java), crossbeam::channel or tokio::sync::mpsc (Rust), std::concurrent_queue from Boost (C++). For Python, the GIL makes lock-free largely moot at the bytecode level, but the underlying C extensions (queue.Queue, multiprocessing.Queue) do use lock-free or hybrid designs internally.

4. Python Implementation

Python’s queue.Queue is the canonical thread-safe bounded buffer. Internally it uses a collections.deque (see Queue) wrapped in a mutex and two condvars — a faithful Solution 2.

4.1 Using queue.Queue Directly

import queue
import threading
import time
import random
 
buf = queue.Queue(maxsize=10)         # bounded buffer of capacity 10
SENTINEL = object()                   # poison-pill for shutdown
 
def producer(producer_id, n_items):
    for i in range(n_items):
        item = (producer_id, i)
        buf.put(item)                 # blocks if full
        print(f"P{producer_id} produced {item}")
        time.sleep(random.uniform(0.0, 0.05))
    buf.put(SENTINEL)                 # signal end-of-stream
 
def consumer(consumer_id):
    while True:
        item = buf.get()              # blocks if empty
        if item is SENTINEL:
            buf.put(SENTINEL)         # propagate sentinel for other consumers
            break
        print(f"C{consumer_id} consumed {item}")
        buf.task_done()
        time.sleep(random.uniform(0.0, 0.1))
 
producers = [threading.Thread(target=producer, args=(i, 20)) for i in range(2)]
consumers = [threading.Thread(target=consumer, args=(i,))    for i in range(3)]
 
for t in producers + consumers: t.start()
for t in producers: t.join()
for t in consumers: t.join()

Key points.

  • Queue(maxsize=10): bounded. put blocks when full; get blocks when empty. Queue() (default) is unbounded, removing the back-pressure mechanism — a common bug.
  • put(item, timeout=...) and get(timeout=...) allow timeout-based waits, raising queue.Full / queue.Empty on expiry.
  • The sentinel pattern (poison pill) is the standard way to shut down consumers: producers put a sentinel object after their last real item, and consumers exit on receipt. With multiple consumers, propagate the sentinel so they all see one.

4.2 Hand-Rolled with threading.Condition (Solution 2 from Scratch)

import threading
from collections import deque
 
class BoundedBuffer:
    def __init__(self, capacity):
        self._buf = deque()
        self._capacity = capacity
        self._lock = threading.Lock()
        self._not_full  = threading.Condition(self._lock)
        self._not_empty = threading.Condition(self._lock)
 
    def put(self, item):
        with self._not_full:                      # acquires self._lock
            while len(self._buf) == self._capacity:
                self._not_full.wait()             # releases lock, blocks; on wake re-acquires
            self._buf.append(item)
            self._not_empty.notify()              # wake one consumer
 
    def get(self):
        with self._not_empty:
            while not self._buf:
                self._not_empty.wait()
            item = self._buf.popleft()
            self._not_full.notify()               # wake one producer
            return item

Critical detail: both condvars share self._lock. This is essential — if they had separate locks, the predicate (len(self._buf) == self._capacity) could be checked under a different lock than the one a producer changing len holds, racing the predicate. Sharing the lock makes both predicates linearizable with respect to the buffer’s state.

4.3 With Two Semaphores (Solution 1 from Scratch)

import threading
from collections import deque
 
class BoundedBufferSem:
    def __init__(self, capacity):
        self._buf = deque()
        self._mutex = threading.Lock()
        self._empty = threading.Semaphore(capacity)   # available empty slots
        self._full  = threading.Semaphore(0)          # available filled slots
 
    def put(self, item):
        self._empty.acquire()              # wait for space
        with self._mutex:
            self._buf.append(item)
        self._full.release()               # signal a filled slot
 
    def get(self):
        self._full.acquire()               # wait for an item
        with self._mutex:
            item = self._buf.popleft()
        self._empty.release()              # signal an empty slot
        return item

This is more compact than the condvar version because the semaphore subsumes both the predicate (“count > 0”) and the wait — no while loop, no condvar wait. The trade-off: harder to extend to predicates more complex than “buffer not full / not empty.” Condvars are more general; semaphores are more concise for this exact pattern.

4.4 multiprocessing.Queue for Cross-Process Producer-Consumer

from multiprocessing import Process, Queue
 
q = Queue(maxsize=10)                      # bounded; uses pipes + sem under the hood
 
def producer(q, n):
    for i in range(n):
        q.put(i)
 
def consumer(q, n):
    for _ in range(n):
        item = q.get()
        print(item)
 
p = Process(target=producer, args=(q, 20))
c = Process(target=consumer, args=(q, 20))
p.start(); c.start(); p.join(); c.join()

multiprocessing.Queue uses an OS pipe + serialization (pickling) + a feeder thread. It’s significantly slower per operation than queue.Queue (because of pickling overhead) but bypasses the GIL — useful when producers/consumers do CPU-bound Python work.

5. Java Implementation — BlockingQueue

Java’s java.util.concurrent.BlockingQueue is the de facto producer-consumer abstraction. Implementations:

  • ArrayBlockingQueue(capacity): bounded, array-backed (circular buffer); single internal lock.
  • LinkedBlockingQueue(capacity): bounded (or unbounded if no capacity given), linked-list-backed; two locks (head and tail) for higher throughput.
  • SynchronousQueue: capacity 0; producer hands directly to consumer (rendezvous).
  • PriorityBlockingQueue: priority order, unbounded, no head/tail blocking on capacity.
  • DelayQueue: items become available only after a per-item delay.
import java.util.concurrent.*;
 
BlockingQueue<Integer> q = new ArrayBlockingQueue<>(10);
 
// Producer
new Thread(() -> {
    try {
        for (int i = 0; i < 100; i++) {
            q.put(i);              // blocks if full
        }
    } catch (InterruptedException e) {
        Thread.currentThread().interrupt();
    }
}).start();
 
// Consumer
new Thread(() -> {
    try {
        while (true) {
            Integer x = q.take();   // blocks if empty
            process(x);
        }
    } catch (InterruptedException e) {
        Thread.currentThread().interrupt();
    }
}).start();

put/take block; offer/poll return immediately (with success/failure), and offer(elem, timeout, unit) / poll(timeout, unit) block with a deadline.

6. Correctness Analysis — Safety vs Liveness

6.1 Safety Properties

A correct producer-consumer protocol guarantees:

  1. Buffer-size invariant: 0 <= size <= N always. Established by initialization and preserved at every put/get.
  2. No lost items: every item put is eventually got (modulo shutdown). Equivalently, the multiset of put arguments equals the multiset of get return values.
  3. No duplicate consumption: each item is got exactly once.
  4. FIFO order (in standard implementations; not in priority queues): items are got in the order they were put.

Property 1 is preserved by the bounded-capacity check. Properties 2–4 are preserved by the buffer’s underlying queue (FIFO deque/ArrayBlockingQueue) and the mutual-exclusion of put/get.

6.2 Liveness Properties

  1. No deadlock: if there are items in the buffer, some consumer eventually gets one; if there is space in the buffer, some producer eventually puts one.
  2. No starvation: every individual producer/consumer eventually makes progress (assuming fair scheduling and counterparts exist).
  3. Bounded waiting (under fair queueing): a thread waits at most k operations before being served, where k is the number of contending threads.

Liveness fails if the consumer dies — producers block forever on a full buffer. The standard production fix: timeouts on put (raise an alarm or drop the item), or a shutdown signal (sentinel) propagated through the system so threads exit cleanly.

6.3 Correctness Proof Sketch (Solution 1)

Invariant: empty.count + full.count + threads_in_critical_section <= N + 1. (+1 because at any moment one thread might hold the mutex and have decremented its semaphore but not yet entered the buffer.)

More usefully, define N_full = full.count and N_empty = empty.count. Invariant: N_full + N_empty = N (the total tokens are conserved across producer/consumer transfers). Each put: producer decrements empty, holds mutex briefly, increments full. Net: empty -= 1, full += 1. Each get: consumer decrements full, holds mutex briefly, increments empty. Net: full -= 1, empty += 1. Sum is preserved. Initially empty + full = N + 0 = N. So buffer occupancy = full always lies in [0, N]. Safety established.

Liveness: a producer blocks only when empty = 0, i.e., the buffer is full. Some consumer will eventually get, incrementing empty, releasing the producer. Symmetrically for consumers. No deadlock.

7. Variants and Sub-Patterns

7.1 Multiple Producers, Multiple Consumers (MPMC)

The setup we’ve described. The bounded buffer must serialize internally; both put and get are critical sections. With high contention and many threads, a single-mutex design becomes the bottleneck. LinkedBlockingQueue uses two locks (head and tail) to allow producers and consumers to operate concurrently.

7.2 Single Producer, Single Consumer (SPSC)

When only one producer and one consumer exist, you can implement a lock-free circular buffer using only atomic head and tail pointers, with no CAS needed (only loads + stores with appropriate memory fences). This is the fastest producer-consumer in existence — used in audio buffers, network device drivers, trading systems. Folly’s ProducerConsumerQueue and boost::lockfree::spsc_queue are reference implementations.

7.3 Single Producer, Multiple Consumers (SPMC) and MPSC

Distinct optimization opportunities. tokio::sync::mpsc (Rust) and crossbeam::channel are MPSC-optimized. Often the bottleneck is the multi-end (producer for MPSC, consumer for SPMC); the single-end can use lock-free reads.

7.4 Pipeline (Multiple Stages)

A chain of producer-consumer stages: stage 1 produces, stage 2 consumes-and-produces, stage 3 consumes-and-produces, … A general computation pipeline. Each pair of adjacent stages is a producer-consumer relationship with its own buffer. Used in: compiler stages, image-processing pipelines, machine-learning data preprocessing. Java Stream.parallel() and Apache Spark are pipeline executors.

7.5 Work-Stealing

Modern thread pools (Java ForkJoinPool, Go scheduler, Rust tokio work-stealing variant) generalize: each consumer (worker) has its own deque, and producers push to a worker’s deque; idle workers steal from other workers’ deques. The deque is double-ended (Deque); local consumption is from the bottom (LIFO, cache-friendly), stealing is from the top (FIFO). Reduces contention on a single shared queue.

7.6 Priority and Delay Variants

PriorityBlockingQueue: items are dequeued in priority order, not FIFO. Producers put (no blocking on full because typically unbounded); consumers take highest-priority item.

DelayQueue: each item has an “available at” timestamp; consumers can only take items whose time has come. Used for timeout queues, scheduled-task executors.

7.7 Bounded vs Unbounded — Backpressure

A bounded buffer enforces back-pressure: when the buffer fills, producers block, slowing them down until consumers catch up. An unbounded buffer has no back-pressure — producers always succeed, but the buffer grows without bound, eventually exhausting memory. Always use bounded queues in production, even if the bound is large. Reactive Streams / RxJava / Project Reactor make back-pressure a first-class concern.

7.8 Drop and Reject Strategies

When a bounded buffer is full and producers cannot block (because they need to keep up with an external source — e.g., network packets), three strategies exist:

  • Drop newest (the producer’s new item is rejected).
  • Drop oldest (an item already in the buffer is removed to make room).
  • Sample / coalesce (combine two items into one).

Java ThreadPoolExecutor exposes RejectedExecutionHandler (AbortPolicy, DiscardPolicy, DiscardOldestPolicy, CallerRunsPolicy) for exactly this choice.

8. Pitfalls

8.1 Forgetting to Handle Spurious Wakeups (Use while, Not if)

The most common condvar bug. Mesa-style condvars (every modern system) allow spurious wakeups and don’t guarantee predicate-truth on wake. Always:

while predicate_false:
    cv.wait()

never:

if predicate_false:    # WRONG
    cv.wait()

Repeated; cannot say it enough.

8.2 Acquiring the Semaphore After the Mutex (Solution 1)

# WRONG
mutex.acquire()
empty.acquire()        # if buffer is full, blocks while holding mutex → consumer can't get → DEADLOCK
buffer.put(item)
mutex.release()
full.release()

Always: empty.acquire() before mutex.acquire(). Same for the consumer with full.

8.3 Using notify() When You Should notify_all()

If multiple waiters might have different predicates served by the same condvar (Java’s intrinsic monitor case), notify() might wake the wrong one — it goes back to sleep, your predicate-true waiter never wakes, deadlock. With separate condvars per predicate (Python, Condition per predicate), notify() is correct and more efficient. With a shared condvar, notify_all() is needed for correctness.

8.4 Unbounded Queue → OOM

queue.Queue() without maxsize is unbounded. Slow consumer + fast producer = memory leak, eventually OOM. Always set maxsize for production code. The unbounded queue is appropriate only when input rate is provably bounded by an external mechanism.

8.5 Forgetting Shutdown — Threads Wedged on put/get

When the program is supposed to exit, blocking put and get calls keep threads alive forever. Two patterns:

  • Sentinel / Poison Pill: producer puts a special object that consumers recognize as “stop.” Each consumer must propagate the sentinel (re-put it) so other consumers also see it.
  • Interrupt-based: in Java, Thread.interrupt() causes blocking calls to throw InterruptedException. In Python, there’s no clean equivalent for queue.Queue.get(); use get(timeout=...) and check a shutdown flag in the loop.

8.6 Lost Items on Crash

If the consumer crashes mid-processing, the item it gets is lost. Production message-queue systems (RabbitMQ, Kafka, SQS) solve this with acknowledgments: the consumer must explicitly ack a message after successful processing; un-acked messages are redelivered after a timeout. The in-process BlockingQueue doesn’t provide this — it’s assumed the consumer is robust.

8.7 Iterating While Concurrent Modification

Iterating over a BlockingQueue (for item in q: in Python — actually queue.Queue is not iterable, but deque is) while another thread modifies it is undefined behavior in most implementations. To “drain”: loop on get until empty (with a non-blocking variant or timeout).

8.8 Single-Threaded Pretending To Be Multi-Threaded

A common interview anti-pattern: a candidate implements producer-consumer with a single thread that alternates between producing and consuming. This is not the problem — the bounded-buffer pattern’s value is in the concurrent execution. Make sure your interview answer actually has separate threads.

8.9 Two Mutexes for Two Predicates

Splitting the producer’s mutex from the consumer’s mutex (so producers and consumers never block each other on the lock) sounds good but breaks: each operation needs to read the buffer’s size, which is racing across the two locks. The buffer’s state is one state, protected by one lock. (LinkedBlockingQueue’s two-lock optimization is not this — it splits the queue into a head-end and tail-end, with each end having its own lock; the trick relies on the linked-list structure where the head and tail nodes are separate.)

8.10 Timing Issues With task_done() and join()

Python’s queue.Queue has a task_done() / join() mechanism: producers put items, consumers get items and call task_done() when finished, and the producer can join() to wait until all items are processed. Forgetting task_done() makes join() block forever. This is independent of the producer-consumer correctness above — it’s a separate feature for the “wait until queue is drained” pattern.

9. Diagram — The Bounded-Buffer Lifecycle

flowchart LR
    subgraph Producers
        P1[Producer 1]
        P2[Producer 2]
        P3[Producer 3]
    end

    subgraph Buffer["Bounded Buffer (capacity N=5)"]
        direction LR
        S1[slot 0]
        S2[slot 1]
        S3[slot 2]
        S4[slot 3]
        S5[slot 4]
    end

    subgraph Consumers
        C1[Consumer 1]
        C2[Consumer 2]
    end

    P1 -- put<br/>blocks if full --> Buffer
    P2 -- put --> Buffer
    P3 -- put --> Buffer
    Buffer -- get<br/>blocks if empty --> C1
    Buffer -- get --> C2

    Mutex[Mutex protects buffer state]
    NotFull[CV not_full: signals when slot freed]
    NotEmpty[CV not_empty: signals when item added]

    Buffer --- Mutex
    Mutex --- NotFull
    Mutex --- NotEmpty

What this diagram shows. Three producers on the left feed items into a bounded buffer of capacity 5 in the middle; two consumers on the right remove items. A producer’s put blocks when the buffer is full; a consumer’s get blocks when the buffer is empty. The right-hand annotations show the synchronization machinery: a single mutex serializes the buffer’s internal state changes (head/tail pointers, count); two condition variables — not_full and not_empty — carry the signals that producers and consumers respectively wait on. The visual takeaway: the buffer is the decoupling boundary between the variable-rate producer side and the variable-rate consumer side, smoothing rate mismatches (bursts on the left are absorbed; lulls on the right are tolerated). The protocol’s correctness depends entirely on the synchronization machinery on the right: without the mutex, the buffer’s pointers race; without the condvars (or equivalent semaphores), threads either busy-wait or miss wakeups.

10. Common Interview Problems

ProblemSourceProducer-Consumer Aspect
Implement bounded blocking queueLeetCode 1188 (Premium)Build the BoundedBuffer class from condvars
Print FooBar alternatelyLeetCode 1115Two-thread producer-consumer with size-1 buffer (rendezvous)
Print in orderLeetCode 1114Three-thread sequencing with two semaphores
Print Zero Even OddLeetCode 1116Three-thread coordination
Build H2OLeetCode 1117Counting semaphore + barrier (2 H + 1 O assemble)
Web crawler multithreadedLeetCode 1242Producer-consumer of URLs
Implement a thread-safe queue from scratchCommon system-design follow-upEither the condvar or two-semaphore solution
Design a thread poolSystem-design roundsWorker threads consume from a shared task queue
Design a logger / log bufferSystem-design roundsMany producers, one or few consumers, drop policy on overflow
Stream processing pipelineSystem-design roundsMulti-stage producer-consumer

11. Open Questions

  • When does batched producer-consumer (where producers submit batches of items and consumers process batches) outperform per-item? Empirically: when per-operation lock overhead dominates per-item work; the break-even depends on item size and lock cost.
  • How does adaptive batching — where batch size is dynamically chosen based on contention — perform compared to fixed batch sizes? Verify with benchmarks; this is an active area.
  • Are disruptor-style ring buffers (LMAX Disruptor, used in financial trading) genuinely better than LinkedBlockingQueue for high-throughput SPSC, or is the advantage mostly cache-line-aware false-sharing avoidance? See Martin Thompson’s LMAX papers for the empirical case.
  • How should producer-consumer with unreliable consumers (consumers may crash mid-processing) be designed? The general answer is acknowledgment-based protocols, but the interface design (visibility timeout, retry policy, dead-letter queue) varies widely; SQS, Kafka, RabbitMQ each pick different points.

12. See Also

Graph View

Backlinks