How do wait(), notify(), and notifyAll() work? Why must wait() be called in a loop?

wait(), notify(), and notifyAll() are the monitor's coordination primitives. A thread that owns an object's monitor calls wait() to atomically release the lock and park in that monitor's wait set; another thread calls notify()/notifyAll() to move waiters back to the entry set so they can re-acquire and continue.

The hard preconditions

All three are methods on Object and may only be called by a thread that currently holds that object's monitor. Calling them without the lock throws IllegalMonitorStateException. So they are always used inside a synchronized region on the same object.

• wait() — release the lock, suspend; re-acquire the lock before returning.
• notify() — wake one arbitrary waiter on this monitor.
• notifyAll() — wake all waiters; they then compete to re-acquire the lock.

The guarded-block pattern

This is the canonical bounded-buffer style usage:

class Buffer<T> {
    private final Queue<T> q = new ArrayDeque<>();
    private final int cap;
    Buffer(int cap) { this.cap = cap; }

    public synchronized void put(T item) throws InterruptedException {
        while (q.size() == cap) {     // MUST be a loop, not 'if'
            wait();                   // releases lock, waits for space
        }
        q.add(item);
        notifyAll();                  // a consumer may be waiting
    }

    public synchronized T take() throws InterruptedException {
        while (q.isEmpty()) {
            wait();
        }
        T item = q.remove();
        notifyAll();                  // a producer may be waiting
        return item;
    }
}

Why wait() must be in a while loop

Three independent reasons, any one of which is sufficient:

1. Spurious wakeups — the JVM/OS is permitted to return from wait() with no matching notify() at all.
2. Stolen condition — after a notify(), the woken thread must re-acquire the lock. Between waking and re-acquiring, a third thread can run and invalidate the condition (e.g. take the slot that was just freed).
3. notifyAll() wakes many waiters for possibly one available resource; all but one will find the condition false again.

So you must re-check the predicate after wait() returns. An if would proceed on a stale assumption; a while re-tests and waits again if needed.