Design a Thread-Safe Bounded Blocking Queue
Design and implement a thread-safe Bounded Blocking Queue with put(element) and get() methods. When the queue is full, producer threads calling put() must block until space becomes available. When the queue is empty, consumer threads calling get() must block until an element is added.
Requirements
- ✓Bounded capacity specified at construction time.
- ✓put(element): inserts element, blocking if full until space is available.
- ✓get(): retrieves and removes head element, blocking if empty until element is available.
- ✓Thread safety: safe under concurrent access by multiple producer and consumer threads.
- ✓FIFO ordering: elements are retrieved in the order they were inserted.
Constraints & Scale
- —No busy-waiting / polling loops (while true sleep). Must use condition synchronization.
- —Guard against spurious wakeups.
- —Prevent deadlocks between producers and consumers.
What is the difference between a mutex lock and a condition variable? Why is a single mutex insufficient without condition variables?
A mutex provides mutual exclusion (only one thread enters critical section). Condition variables allow threads to release the mutex and sleep until signaled that state has changed. We need two conditions: notEmpty (consumers wait on) and notFull (producers wait on).
Trade-offs
- ⚖One lock + two condition variables: clean, thread-safe, prevents deadlocks.
- ⚖Two locks (head lock & tail lock like Java LinkedBlockingQueue): allows simultaneous enqueue and dequeue, boosting concurrency at cost of complex state tracking.
Concepts used in this stage