Monitors — condition variables, wait, signal, broadcast

WHAT is a Monitor?

WHY invent monitors? With raw semaphores, the lock acquire/release is scattered across your code by hand — forget one signal() and you deadlock forever. A monitor makes mutual exclusion structural: the compiler/runtime puts the lock around every procedure, so you can't forget it. You only reason about the conditions, not the locking.

WHAT is a Condition Variable?

The golden rule: WHY wait must be inside a while

Let's derive why while (not if) is mandatory. Suppose a consumer waits for count > 0:

1. Consumer sleeps in wait because count == 0. It is off the CPU and outside the lock.
2. Producer enters, sets count = 1, calls signal. Consumer is moved to "ready."
3. But "ready" ≠ "running." Between the signal and the consumer actually re-acquiring the lock, a third thread can sneak in and consume that item, setting count = 0 again.
4. The consumer finally runs — if it used if, it would proceed as if count > 0, but it's now $0$! Bug.

With while, on wake-up the consumer re-tests the predicate, sees it false, and loops back to wait. Safe. This is also the only correct way to survive spurious wake-ups (some OSes wake threads for no reason) and broadcast (many wake, only one wins).

HOW wait achieves atomicity (the crux)

Mesa vs. Hoare semantics — WHO holds the lock after signal?

Almost all real systems (Java, pthreads, Python threading.Condition, Go) use Mesa. So in practice: always while.

WORKED EXAMPLE 1 — Bounded Buffer (Producer/Consumer)

monitor BoundedBuffer:
    buf[N], count = 0
    condition notFull, notEmpty
 
    procedure produce(item):
        while (count == N)        # Why? buffer full → can't add. while, not if (Mesa).
            wait(notFull)         # Why? drop lock + sleep until space appears.
        buf.add(item); count++    # Why? safe: we hold the lock, count < N proven.
        signal(notEmpty)          # Why? a consumer may be sleeping on empty buffer.
 
    procedure consume():
        while (count == 0)        # Why? nothing to take → wait.
            wait(notEmpty)
        item = buf.remove(); count--
        signal(notFull)           # Why? we just freed a slot; a producer may wait.

Why two CVs? notFull and notEmpty represent different conditions. If you used one CV and signal, you might wake a producer when only a consumer can proceed → it re-sleeps, wasting a wakeup, possibly deadlocking. Separate CVs = wake exactly the right group.

WORKED EXAMPLE 2 — When you MUST use broadcast

Suppose a single CV ready guards a resource pool, and waiting threads need different amounts of memory. A thread frees 10 MB.

• signal(ready) wakes one thread. What if it needs 100 MB and can't proceed, but another waiter needs only 5 MB and could? The 5 MB thread stays asleep → wasted wakeup / starvation.
• broadcast(ready) wakes all; each re-tests its own predicate in its while; the one(s) that can proceed do, the rest go back to sleep. Correct.

WORKED EXAMPLE 3 — The lost-signal bug (and fix)

# BROKEN consumer
if (count == 0)        # ← if, not while
    wait(notEmpty);
take();

Why it breaks: Under Mesa, a third thread can empty the buffer between signal and re-acquire (the derivation above). Then take() runs on empty buffer → crash. Fix: change if → while. One character. Re-tests after wake.

Active Recall

Connections

• Semaphores — lower-level primitive; monitors are often built on top of them.
• Mutual Exclusion — the automatic guarantee a monitor provides.
• Producer-Consumer Problem — canonical monitor use case.
• Deadlock — wrong CV choice / missed signal can cause it.
• Race Conditions — lost-wakeup is the race wait atomicity prevents.
• Spurious Wakeups — second reason while is mandatory.

Concept Map

Hinglish (regional understanding)