Implement a Thread-Safe Bounded Blocking Queue for Producers and Consumers

You are asked to implement a queue that producer threads and consumer threads share. Producers add items, consumers remove them in first-in, first-out order, and any number of producers and consumers may call the queue at the same time. A thread that cannot make progress must wait without burning CPU. The point of the exercise is the synchronization, so build the queue yourself from basic primitives. Whether the queue is bounded was not stated. Assume a fixed capacity given at construction unless the interviewer says otherwise, and this interface: ```text BlockingQueue(capacity) put(item) -> None # waits while the queue is full, then appends item at the tail take() -> item # waits while the queue is empty, then removes and returns the head ``` Use a mutex and condition variables, or your language's equivalent monitor primitives. Wrapping a ready-made concurrent or blocking queue from a library would skip the exercise. ```hint What each side waits for Producers and consumers wait for different events. Work out what each side is waiting for, and which operation should wake it. ``` ```hint Waking up is not a guarantee A thread that returns from a wait may find that the condition it waited for no longer holds. Decide what it must do before it touches the buffer. ``` ### Constraints and Clarifications - `capacity` is a positive integer fixed at construction. - Items leave in the order they arrived. - No busy-waiting: a blocked thread sleeps until it can make progress. - Apart from waiting, `put` and `take` should take constant time. ### Clarifying Questions - Is the queue bounded? If so, should `put` on a full queue block, fail immediately, or drop an item? - Do callers need timed variants, such as `offer(item, timeout)` and `poll(timeout)`? - Is there a shutdown path, so that consumers blocked on an empty queue can exit? - Which language and threading library should the implementation use? ### What a Strong Answer Covers - Every access to the buffer and its bookkeeping happens under one lock, with a clearly stated invariant - Separate wait conditions for "not full" and "not empty", and which operation signals each - Re-checking the wait condition after every wakeup, and why a single check is unsafe - Signal-one versus signal-all, and the lost-wakeup or deadlock risk of the wrong choice - Edge cases: capacity 1, many more producers than consumers, shutdown while threads are blocked - What the mutex and condition variable do underneath (atomic instructions, sleeping in the kernel), since the round also probed OS fundamentals ### Follow-up Questions - Add `offer(item, timeout)` and `poll(timeout)`. How do you keep the total wait bounded when a thread wakes up early? - Add `close()`: consumers should drain what remains and then stop, and producers should fail fast. What changes in the wait loops? - With a single condition variable shared by producers and consumers and a signal-one call, construct an interleaving in which every thread ends up asleep. - One well-known design uses a single lock for both ends of the queue; another uses separate locks for `put` and `take`. What does the two-lock design gain, and what keeps it correct?