Design a Thread-Safe Producer-Consumer Queue

Problem Statement

Design and implement a thread-safe bounded queue that supports multiple producer and consumer threads concurrently.

Requirements:

• enqueue(item) — blocks if the queue is full
• dequeue() — blocks if the queue is empty
• Must handle multiple producers and multiple consumers safely
• No data races, no deadlocks

Constraints

• Queue has a fixed max capacity N
• Multiple threads call enqueue and dequeue simultaneously
• Must use mutexes and condition variables (no lock-free requirement)
• Language: C++ (but logic applies to any language)

Example

ThreadSafeQueue<int> q(5); // capacity 5

// Producer thread
q.enqueue(42);  // succeeds immediately if space available
q.enqueue(43);  // blocks if queue is full

// Consumer thread
int val = q.dequeue(); // blocks if queue is empty

What the Interviewer Expects

1. Mutex for mutual exclusion — protect shared state (the underlying container + size)
2. Two condition variables — one for "not full" (producers wait on), one for "not empty" (consumers wait on)
3. Proper wait predicate — always use while loop (not if) to handle spurious wakeups
4. Notify correctly — enqueue notifies "not empty", dequeue notifies "not full"
5. RAII locking — use unique_lock not raw lock/unlock

Follow-ups

1. What if no producer has started but all consumers are already waiting? How do you avoid permanent blocking?
2. What happens when the destructor is called while threads are blocked? How do you implement graceful shutdown?
3. How would you add a try_dequeue(timeout) that gives up after a deadline?
4. What's the difference between notify_one() and notify_all() here? When would you use each?
5. How would you make this lock-free using atomics? What are the trade-offs?