Implement a bounded producer-consumer buffer using wait/notify. Why does wait() have to release the lock for this to work?

## The scenario *Producer-consumer* is the canonical concurrency exercise: one or more **producer** threads create items and put them into a shared **bounded buffer** (fixed capacity), and one or more **consumer** threads take items out. Two conditions must be respected: a producer must **block when the buffer is full**, and a consumer must **block when the buffer is empty**. wait/notify is the textbook way to express this. ## A correct implementation ```java class BoundedBuffer<T> { private final Queue<T> queue = new ArrayDeque<>(); private final int capacity; private final Object lock = new Object(); BoundedBuffer(int capacity) { this.capacity = capacity; } void put(T item) throws InterruptedException { synchronized (lock) { while (queue.size() == capacity) { // full → wait lock.wait(); } queue.add(item); lock.notifyAll(); // wake any waiting consumers } } T take() throws InterruptedException { synchronized (lock) { while (queue.isEmpty()) { // empty → wait lock.wait(); } T item = queue.remove(); lock.notifyAll(); // wake any waiting producers return item; } } } ``` ## Why wait() must release the lock Both `put` and `take` run inside `synchronized(lock)` — so only one thread is in the buffer's critical section at a time. Suppose the buffer is **full** and a producer calls `wait()`. If `wait()` simply *parked the thread while keeping the lock*, then: 1. The producer is asleep holding `lock`. 2. A consumer tries to enter `synchronized(lock)` in `take()` to remove an item — but the lock is held, so it blocks at the *entry*, never reaching `queue.remove()`. 3. No item is ever removed, so the buffer is never non-full, so the producer is never able to proceed. That is a **deadlock**. The whole mechanism only works because `wait()` **atomically releases the monitor** as it parks: the consumer can then enter `take()`, remove an item, and call `notifyAll()`, which wakes the producer; the producer re-acquires the lock inside `wait()` and re-checks its `while` condition. *Atomically* matters — the release and the park happen as one step so a `notify` cannot be lost in a gap between them. ## Why while, not if When a producer is woken, several things may be true: it may be a **spurious wakeup** (no real signal), or **another producer** woken by the same `notifyAll` may have already refilled the only freed slot. Re-checking `while (queue.size() == capacity)` ensures the thread only proceeds when the condition genuinely holds; an `if` would let it add to a full buffer. ## Why notifyAll, not notify Producers and consumers wait on the **same monitor** but for **different conditions** (full vs empty). `notify()` wakes one *arbitrary* waiter. After a `put`, you want to wake a **consumer**, but `notify()` might wake another **producer** — which re-checks 'full?', finds the buffer still has room maybe, or finds it full and goes back to sleep, leaving the consumer that should run still parked. With a single producer / single consumer you can sometimes use `notify()`, but `notifyAll()` is the safe, correct-by-default choice when waiters are not interchangeable. ## Production note In real code you would use `java.util.concurrent.ArrayBlockingQueue` / `LinkedBlockingQueue`, whose `put`/`take` already implement exactly this blocking behavior, or a `ReentrantLock` with two separate `Condition`s (`notFull`, `notEmpty`) so you can `signal` precisely the right waiter and avoid the thundering herd. Hand-rolled wait/notify is for understanding the primitive.