Chapter 20 of 38

Monitors

Think of a single-room doctor's clinic with a receptionist at the door. Patients do not decide for themselves when to walk in; the receptionist lets in one patient at a time. If the doctor needs a lab report before continuing, the patient is sent to sit in a waiting area outside ("wait for the report") so the next patient can come in. When the report arrives, the patient is called back.

That clinic is a monitor. The room is the shared data, the receptionist enforces mutual exclusion automatically, and the waiting areas are condition variables.

In Mutex Locks & Semaphores we saw how easy it is to misuse semaphores: swap a wait and a signal, forget one, or put them in the wrong order, and the program races or deadlocks. In Classical Synchronization Problems we saw that a single swapped line in the bounded buffer causes deadlock. Monitors were invented in the early 1970s (by Per Brinch Hansen and C. A. R. Hoare) to make such mistakes much harder by moving the locking into the language itself. Today the same idea lives on in Java's synchronized, C#'s lock, Python's threading.Condition and the pthreads mutex + condition variable pair.


What Is a Monitor?

A monitor is a high-level synchronization construct: an abstract data type that bundles shared variables, the procedures that operate on them, and initialization code, with the guarantee that only one process can be active inside the monitor at a time.

Its general shape, in the pseudocode used by most textbooks:

monitor MonitorName {
    /* shared variable declarations */

    procedure P1 (...) { ... }
    procedure P2 (...) { ... }
    ...
    initialization_code (...) { ... }
}

Three properties make this useful:

  1. Encapsulation. The shared variables can be accessed only through the monitor's procedures. Outside code cannot touch them directly, so it cannot forget to lock.

  2. Automatic mutual exclusion. The compiler (or runtime) inserts the lock and unlock around every procedure. The programmer writes no wait(mutex) or signal(mutex) at all.

  3. Condition variables for waiting inside the monitor until some condition becomes true (explained below).

A picture of the structure:

              entry queue (processes waiting to enter)
                P5 → P6 → P7
                      │
                      ▼
      ┌─────────────────────────────────────┐
      │  shared data: buf[], count, ...     │
      │                                     │   condition queues
      │  procedures: put(), get()           │    not_full : P2
      │                                     │    not_empty: P3 → P4
      │  initialization code                │
      │                                     │
      │  ACTIVE: P1   (at most one!)        │
      └─────────────────────────────────────┘

A process that calls a monitor procedure while another process is active inside simply waits in the entry queue. That is all the mutual exclusion the programmer ever sees.


Why Mutual Exclusion Alone Is Not Enough

Suppose we write a bounded buffer as a monitor with just shared data and procedures. What should get() do if the buffer is empty?

  • It cannot return garbage.

  • It cannot busy-wait inside the monitor: it would hold the monitor forever, so no producer could ever enter to add an item.

  • It cannot leave and re-enter in a loop either: that is just busy waiting with extra steps.

What we need is a way to say: "I give up the monitor for now, put me to sleep, and wake me when the buffer is no longer empty." That is exactly what a condition variable does.


Condition Variables

A condition variable x is a queue of processes waiting inside a monitor for some condition. It supports two operations: x.wait(), which suspends the calling process and releases the monitor, and x.signal(), which resumes exactly one suspended process (if any).

condition x, y;

x.wait();     /* release the monitor, sleep in x's queue                 */
x.signal();   /* wake one process sleeping in x's queue; if none, no effect */

Two details are the source of many exam questions:

  • x.wait() always blocks. Unlike a semaphore's wait, it does not check a counter first; it is up to the programmer to call it only when the condition is false.

  • x.signal() on an empty queue does nothing and is forgotten. Unlike a semaphore's signal, which increments a value that a later wait will use, a condition variable has no memory.

Semaphore S

Condition variable x

Has a value?

Yes, an integer

No, only a queue of waiters

wait

Blocks only if the value is 0

Always blocks (and releases the monitor lock)

signal with no waiter

Value is incremented; remembered for later

No effect; lost

Used where?

Anywhere

Only inside a monitor (while holding its lock)

The "condition" itself

Encoded in the value

Kept in ordinary shared variables (e.g. count == 0) that the program checks

That last row is the key mental model: the condition variable is not the condition. The real condition is a test on the monitor's data, such as count == 0. The condition variable is just a place to sleep until that test might have changed.


Bounded Buffer as a Monitor

monitor BoundedBuffer {
    item buf[N];
    int in = 0, out = 0, count = 0;
    condition not_full, not_empty;

    procedure put(item x) {
        while (count == N)
            not_full.wait();
        buf[in] = x;  in = (in + 1) % N;  count++;
        not_empty.signal();
    }

    procedure get() returns item {
        while (count == 0)
            not_empty.wait();
        x = buf[out];  out = (out + 1) % N;  count--;
        not_full.signal();
        return x;
    }
}

Compare this with the semaphore version in Classical Synchronization Problems. There is no mutex to remember, and no way to get "lock before wait" in the wrong order, because the wait on a condition variable releases the monitor automatically. The deadlock we found there simply cannot be written here.

In C: pthread mutex + condition variables

C has no monitor keyword, but the pthreads library gives us the two ingredients. We build the monitor by hand:

  • one pthread_mutex_t = the monitor's lock; every "monitor procedure" locks it on entry and unlocks it on exit;

  • one pthread_cond_t per condition; pthread_cond_wait(&cv, &m) atomically releases m and sleeps, and re-acquires m before returning; pthread_cond_signal(&cv) wakes at least one waiter; pthread_cond_broadcast(&cv) wakes them all.

Here is a bounded buffer of 3 slots with one producer and two consumers sharing 1000 items:

#include <stdio.h>
#include <pthread.h>

/* ---------- the "monitor": data + lock + condition variables ---------- */
#define SIZE 3
static int buf[SIZE], in = 0, out = 0, count = 0;
static pthread_mutex_t m = PTHREAD_MUTEX_INITIALIZER;     /* monitor lock  */
static pthread_cond_t not_full  = PTHREAD_COND_INITIALIZER;
static pthread_cond_t not_empty = PTHREAD_COND_INITIALIZER;

void put(int item)
{
    pthread_mutex_lock(&m);                 /* enter monitor            */
    while (count == SIZE)                   /* WHILE, not if            */
        pthread_cond_wait(&not_full, &m);   /* release m + sleep        */
    buf[in] = item;
    in = (in + 1) % SIZE;
    count++;
    pthread_cond_signal(&not_empty);        /* wake one consumer        */
    pthread_mutex_unlock(&m);               /* leave monitor            */
}

int get(void)
{
    pthread_mutex_lock(&m);
    while (count == 0)
        pthread_cond_wait(&not_empty, &m);
    int item = buf[out];
    out = (out + 1) % SIZE;
    count--;
    pthread_cond_signal(&not_full);         /* wake one producer        */
    pthread_mutex_unlock(&m);
    return item;
}
/* ---------------------------------------------------------------------- */

#define ITEMS 1000

void *producer(void *arg)
{
    (void)arg;
    for (int i = 1; i <= ITEMS; i++)
        put(i);
    return NULL;
}

void *consumer(void *arg)
{
    long *sum = arg;
    for (int i = 0; i < ITEMS / 2; i++)     /* two consumers share the work */
        *sum += get();
    return NULL;
}

int main(void)
{
    pthread_t p, c1, c2;
    long s1 = 0, s2 = 0;
    pthread_create(&p, NULL, producer, NULL);
    pthread_create(&c1, NULL, consumer, &s1);
    pthread_create(&c2, NULL, consumer, &s2);
    pthread_join(p, NULL);
    pthread_join(c1, NULL);
    pthread_join(c2, NULL);
    printf("Consumer 1 sum = %ld, Consumer 2 sum = %ld\n", s1, s2);
    printf("Total = %ld (expected %d)\n", s1 + s2, ITEMS * (ITEMS + 1) / 2);
    return 0;
}

Two runs on Linux:

$ gcc -std=c17 -Wall -pthread monitor_buffer.c -o monitor_buffer
$ ./monitor_buffer
Consumer 1 sum = 286970, Consumer 2 sum = 213530
Total = 500500 (expected 500500)
$ ./monitor_buffer
Consumer 1 sum = 128365, Consumer 2 sum = 372135
Total = 500500 (expected 500500)

How the 1000 items are split between the two consumers is decided by the scheduler, so the individual sums are different every run. The total is always 500500 (1 + 2 + ... + 1000): no item was lost or consumed twice.


Signal Semantics: Hoare vs Mesa

There is a subtle problem with x.signal(). Suppose process P is inside the monitor and signals, waking Q. Now both P and Q are ready to run inside the monitor, but only one is allowed. Who goes first? There are three classic answers:

Semantics

What happens on signal

Consequence

Used by

Signal-and-wait (Hoare)

The signaller P is suspended; Q runs immediately. P resumes when Q leaves or waits.

Q is guaranteed the condition still holds, so if (...) x.wait(); is enough.

Hoare's original paper, most textbook proofs

Signal-and-continue (Mesa)

P keeps running; Q is just moved to the ready/entry queue and runs later.

By the time Q runs, someone else may have changed the state, so Q must re-check: while (...) x.wait();

Mesa language, Java, C#, pthreads, Python – almost every real system

Signal-and-exit (Brinch Hansen)

signal must be the last statement of the procedure; P leaves and Q enters.

No conflict, but less flexible.

Concurrent Pascal

Real systems use Mesa semantics because it is simpler and faster: the signaller does not need two extra context switches. Treat a wake-up as a hint ("the condition might be true now"), not a promise. POSIX even allows spurious wakeups: pthread_cond_wait may return although nobody signalled. Both facts lead to the most important rule of condition variables:

Always wait in a while loop that re-checks the condition, never in an if.

Seeing the if bug for real

Here is the buffer again, now with one producer, four consumers and a million items, but with if instead of while. The program counts how many times a consumer got past the wait and found the buffer still empty:

#include <stdio.h>
#include <pthread.h>

/* Same monitor as before, but the waits use IF instead of WHILE (a bug) */
#define SIZE 3
static int count = 0, bad_gets = 0;
static pthread_mutex_t m = PTHREAD_MUTEX_INITIALIZER;
static pthread_cond_t not_full  = PTHREAD_COND_INITIALIZER;
static pthread_cond_t not_empty = PTHREAD_COND_INITIALIZER;

void put(void)
{
    pthread_mutex_lock(&m);
    if (count == SIZE)                       /* BUG: should be while */
        pthread_cond_wait(&not_full, &m);
    count++;
    pthread_cond_signal(&not_empty);
    pthread_mutex_unlock(&m);
}

void get(void)
{
    pthread_mutex_lock(&m);
    if (count == 0)                          /* BUG: should be while */
        pthread_cond_wait(&not_empty, &m);
    if (count == 0)                          /* woke up, but nothing there! */
        bad_gets++;
    count--;
    pthread_cond_signal(&not_full);
    pthread_mutex_unlock(&m);
}

#define ITEMS 1000000
#define CONSUMERS 4

void *producer(void *arg) { (void)arg; for (int i = 0; i < ITEMS; i++) put(); return NULL; }
void *consumer(void *arg) { (void)arg; for (int i = 0; i < ITEMS / CONSUMERS; i++) get(); return NULL; }

int main(void)
{
    pthread_t p, c[CONSUMERS];
    pthread_create(&p, NULL, producer, NULL);
    for (int i = 0; i < CONSUMERS; i++) pthread_create(&c[i], NULL, consumer, NULL);
    pthread_join(p, NULL);
    for (int i = 0; i < CONSUMERS; i++) pthread_join(c[i], NULL);
    printf("Consumers took an item from an EMPTY buffer %d times\n", bad_gets);
    return 0;
}
$ gcc -std=c17 -Wall -pthread monitor_if.c -o monitor_if
$ ./monitor_if
Consumers took an item from an EMPTY buffer 1 times
$ ./monitor_if
Consumers took an item from an EMPTY buffer 2 times
$ ./monitor_if
Consumers took an item from an EMPTY buffer 5 times

The numbers change from run to run (and on some runs could be 0), but the bug is real. Here is how it happens under Mesa semantics:

1. Consumer A: count == 0  → not_empty.wait()  (sleeps, releases lock)
2. Producer:   count = 1   → not_empty.signal() (A becomes runnable, but
                                                 must re-acquire the lock)
3. Consumer B: arrives, gets the lock first, count == 1 → takes the item,
               count = 0
4. Consumer A: finally re-acquires the lock and continues AFTER the if
               ... and takes an item from an EMPTY buffer (count = -1)

With while, in step 4 A would re-check count == 0, see it is true, and go back to sleep. That is why the earlier monitor_buffer.c was always correct.


Monitors in Java

Java builds a monitor into every object. A synchronized method locks the object's monitor; wait(), notify() and notifyAll() are its condition operations, with Mesa semantics. Each object has only one implicit condition queue, which producers and consumers share:

public class BoundedBuffer {
    private final int[] buf = new int[3];
    private int in = 0, out = 0, count = 0;

    public synchronized void put(int item) throws InterruptedException {
        while (count == buf.length)
            wait();                       // releases the object's lock and sleeps
        buf[in] = item;
        in = (in + 1) % buf.length;
        count++;
        notifyAll();                      // wake waiting threads; they re-check
    }

    public synchronized int get() throws InterruptedException {
        while (count == 0)
            wait();
        int item = buf[out];
        out = (out + 1) % buf.length;
        count--;
        notifyAll();
        return item;
    }

    public static void main(String[] args) throws InterruptedException {
        BoundedBuffer b = new BoundedBuffer();
        long[] sum = new long[1];
        Thread producer = new Thread(() -> {
            try { for (int i = 1; i <= 1000; i++) b.put(i); }
            catch (InterruptedException e) { }
        });
        Thread consumer = new Thread(() -> {
            try { for (int i = 0; i < 1000; i++) sum[0] += b.get(); }
            catch (InterruptedException e) { }
        });
        producer.start();
        consumer.start();
        producer.join();
        consumer.join();
        System.out.println("Sum = " + sum[0] + " (expected 500500)");
    }
}
$ javac BoundedBuffer.java
$ java BoundedBuffer
Sum = 500500 (expected 500500)

Why notifyAll() and not notify()? Because producers and consumers sleep in the same queue. With several producers and consumers, notify() might wake another producer when the buffer is full (it will just go back to sleep) while the consumer that could have made progress keeps sleeping. In the worst case everyone ends up asleep. notifyAll() wakes everybody, and the while loops sort out who can actually proceed. If you need separate queues, use java.util.concurrent.locks.ReentrantLock with two Condition objects (notFull and notEmpty), which is exactly the pthreads design above.

Language / library

Monitor lock

Condition operations

C (pthreads)

pthread_mutex_lock/unlock

pthread_cond_wait / signal / broadcast

C++

std::mutex + std::unique_lock

std::condition_variable::wait / notify_one / notify_all

Java

synchronized

wait() / notify() / notifyAll()

C#

lock (obj) { ... }

Monitor.Wait / Pulse / PulseAll

Python

with cond: (a threading.Condition)

cond.wait() / notify() / notify_all(), or cond.wait_for(predicate)

Go

sync.Mutex

sync.Cond: Wait / Signal / Broadcast

Strictly speaking, only languages like Concurrent Pascal and Mesa had true monitors, where the compiler forces all access to go through the monitor. Java comes close (but you can forget synchronized on a method). In C, C++ and Go the "monitor" is a discipline: you promise to touch the data only while holding the mutex.


Dining Philosophers Using a Monitor

In Classical Synchronization Problems we listed a third fix for the dining philosophers: pick up both chopsticks or none. With a monitor it is short and clean. Each philosopher is in one of three states, and a philosopher may move to EATING only if neither neighbour is eating:

monitor DiningPhilosophers {
    enum { THINKING, HUNGRY, EATING } state[5];
    condition self[5];                /* where philosopher i sleeps */

    void pickup(int i) {
        state[i] = HUNGRY;
        test(i);                      /* can I eat right now? */
        if (state[i] != EATING)
            self[i].wait();           /* no: wait for a neighbour to wake me */
    }

    void putdown(int i) {
        state[i] = THINKING;
        test((i + 4) % 5);            /* left neighbour may eat now  */
        test((i + 1) % 5);            /* right neighbour may eat now */
    }

    void test(int i) {
        if (state[(i + 4) % 5] != EATING &&
            state[i] == HUNGRY &&
            state[(i + 1) % 5] != EATING) {
            state[i] = EATING;
            self[i].signal();
        }
    }

    initialization_code() {
        for (int i = 0; i < 5; i++)
            state[i] = THINKING;
    }
}

/* Philosopher i */
DiningPhilosophers.pickup(i);
    /* eat */
DiningPhilosophers.putdown(i);

Why it works:

  • No two neighbours eat together: test sets state[i] = EATING only if both neighbours are not eating, and it runs inside the monitor, so nobody can change the states halfway.

  • No deadlock: a philosopher never holds one chopstick while waiting for the other. "Taking both" is a single atomic step (state[i] = EATING), so hold and wait is impossible.

  • Who wakes a waiting philosopher? A neighbour, in putdown, calls test on her and signals her if she can now eat. Note that it is the neighbour who changes her state to EATING on her behalf.

The textbook uses if before self[i].wait() here, and that is actually safe even under Mesa semantics: the waker has already set state[i] = EATING before signalling, and no one else can undo it. Still, in real code we write a while to be safe against spurious wakeups. Here is a pthreads version that also checks, 100,000 times in total, that no two neighbours are ever eating together:

#include <stdio.h>
#include <pthread.h>
#include <unistd.h>

#define N 5
enum { THINKING, HUNGRY, EATING };

/* ----------------------- DiningPhilosophers monitor ----------------------- */
static int state[N];                          /* all THINKING (0) at start  */
static pthread_mutex_t m = PTHREAD_MUTEX_INITIALIZER;
static pthread_cond_t self[N];                /* one condition per person   */

static int LEFT(int i)  { return (i + N - 1) % N; }
static int RIGHT(int i) { return (i + 1) % N; }

static void test(int i)                       /* can i start eating now?    */
{
    if (state[i] == HUNGRY &&
        state[LEFT(i)] != EATING && state[RIGHT(i)] != EATING) {
        state[i] = EATING;
        pthread_cond_signal(&self[i]);
    }
}

void pickup(int i)
{
    pthread_mutex_lock(&m);
    state[i] = HUNGRY;
    test(i);                                  /* try to grab both now       */
    while (state[i] != EATING)
        pthread_cond_wait(&self[i], &m);      /* a neighbour will wake me   */
    pthread_mutex_unlock(&m);
}

void putdown(int i)
{
    pthread_mutex_lock(&m);
    state[i] = THINKING;
    test(LEFT(i));                            /* maybe my neighbours can eat */
    test(RIGHT(i));
    pthread_mutex_unlock(&m);
}
/* -------------------------------------------------------------------------- */

static pthread_mutex_t check = PTHREAD_MUTEX_INITIALIZER;
static int eating_now[N], violations = 0;

void *philosopher(void *arg)
{
    int i = *(int *)arg;
    for (int meal = 0; meal < 20000; meal++) {
        pickup(i);
        pthread_mutex_lock(&check);           /* verify: neighbours not eating */
        if (eating_now[LEFT(i)] || eating_now[RIGHT(i)]) violations++;
        eating_now[i] = 1;
        pthread_mutex_unlock(&check);

        pthread_mutex_lock(&check);
        eating_now[i] = 0;
        pthread_mutex_unlock(&check);
        putdown(i);
    }
    return NULL;
}

int main(void)
{
    pthread_t t[N];
    int id[N];
    for (int i = 0; i < N; i++)
        pthread_cond_init(&self[i], NULL);
    for (int i = 0; i < N; i++) {
        id[i] = i;
        pthread_create(&t[i], NULL, philosopher, &id[i]);
    }
    for (int i = 0; i < N; i++)
        pthread_join(t[i], NULL);
    printf("Each philosopher ate 20000 times, neighbour violations = %d\n", violations);
    return 0;
}
$ gcc -std=c17 -Wall -pthread dining_monitor.c -o dining_monitor
$ ./dining_monitor
Each philosopher ate 20000 times, neighbour violations = 0

But it is not starvation-free. Philosopher 1 can stay hungry forever if philosophers 0 and 2 take turns eating so that at every moment at least one of them is eating. Fixing that needs extra rules, for example ageing (a hungry philosopher who has waited too long gets priority over her neighbours).


Implementing a Monitor Using Semaphores

A compiler that supports monitors must translate them into something lower level. The classic translation (with Hoare's signal-and-wait semantics) uses semaphores. This is a favourite question in university exams.

For the monitor as a whole:

semaphore mutex = 1;     /* the monitor lock                               */
semaphore next  = 0;     /* signallers suspend here (signal-and-wait)       */
int next_count  = 0;     /* how many processes are suspended on next        */

/* Each monitor procedure F is compiled as: */
wait(mutex);
    /* body of F */
if (next_count > 0)
    signal(next);        /* let a suspended signaller continue ...          */
else
    signal(mutex);       /* ... or else open the monitor to a new process   */

For each condition variable x:

semaphore x_sem = 0;
int x_count = 0;         /* how many processes are waiting on x             */

/* x.wait() */
x_count++;
if (next_count > 0)
    signal(next);        /* hand the monitor to a suspended signaller       */
else
    signal(mutex);       /* or release it                                   */
wait(x_sem);             /* sleep until signalled                           */
x_count--;

/* x.signal() */
if (x_count > 0) {       /* only if someone is waiting (else: no effect)    */
    next_count++;
    signal(x_sem);       /* wake one waiter ...                             */
    wait(next);          /* ... and suspend myself (signal-and-wait)        */
    next_count--;
}

Notice how this matches everything we said: x.signal() with x_count == 0 does nothing (no memory), the signaller suspends itself on next so the woken process runs immediately (Hoare), and when anyone leaves or waits, suspended signallers get priority over new arrivals waiting on mutex.

The reverse is also possible: a semaphore can be built from a monitor (an integer plus one condition variable). So the two tools are equally powerful; the difference is in how easy they are to use correctly.

monitor Semaphore {
    int value;
    condition positive;

    procedure P() {
        while (value == 0)
            positive.wait();
        value--;
    }
    procedure V() {
        value++;
        positive.signal();
    }
}

Semaphores vs Monitors

Semaphore

Monitor

Level

Low-level primitive (an integer + two operations)

High-level language construct (data + procedures + conditions)

Mutual exclusion

Programmer must place wait/signal correctly everywhere

Automatic for every monitor procedure

Waiting for a condition

Counting semaphores

Condition variables plus explicit checks on the data

Signal with nobody waiting

Remembered (value increments)

Lost

Shared data

Global; any code can touch it

Encapsulated; only monitor procedures can touch it

Typical errors

Swapped or missing wait/signal → races, deadlock

if instead of while; notify instead of notifyAll with a shared queue

Language support needed?

No (a library or system call is enough)

Yes for a true monitor; otherwise a mutex + condition variables discipline

Expressive power

Equal: a semaphore can implement a monitor

Equal: a monitor can implement a semaphore

Monitors do not solve everything. Calling one monitor from inside another (nested monitor calls) can deadlock, a process can still forget to call a monitor procedure at all, and a monitor serializes all its procedures, which can limit parallelism. Deadlock itself is the subject of the next chapter, Deadlocks.


Common Mistakes

  • Using if instead of while around a wait. Under Mesa semantics (Java, pthreads, Python, C#) this is a real bug, as our program showed.

  • Confusing the condition variable with the condition. not_empty is a waiting queue, not a boolean. The actual condition is count > 0.

  • Expecting a signal to be remembered. If you signal before anyone waits, the signal is lost. Always check the shared state before waiting.

  • Calling pthread_cond_wait or Java's wait() without holding the lock. In Java this throws IllegalMonitorStateException; with pthreads it is undefined behaviour.

  • Using notify() when different kinds of waiters share one queue. Use notifyAll() or separate conditions.

  • Doing slow work inside the monitor. Only one process can be inside; keep procedures short and do I/O outside.


Interview Questions

What is a monitor?

A high-level synchronization construct that encapsulates shared data with the procedures that operate on it, and guarantees that only one process is active inside at a time. Waiting for conditions is done with condition variables.

What is a condition variable? What do wait and signal do?

A queue of processes waiting inside a monitor. x.wait() releases the monitor and suspends the caller; x.signal() resumes one waiting process, or does nothing if none is waiting.

How is a condition variable different from a semaphore?

A semaphore has a value: its signal is remembered and its wait blocks only when the value is 0. A condition variable has no value: wait always blocks and a signal with no waiters is lost.

Hoare vs Mesa semantics?

Hoare (signal-and-wait): the signalled process runs immediately and the signaller waits, so the condition is guaranteed true. Mesa (signal-and-continue): the signaller keeps running and the woken process runs later, so it must re-check the condition in a while loop. Most real systems use Mesa.

Why must we use while and not if before pthread_cond_wait?

Because of Mesa semantics (another thread may change the state between the signal and the wake-up) and because POSIX allows spurious wakeups. The loop re-checks the condition after every wake-up.

What is a spurious wakeup?

A return from a condition wait even though no thread signalled. POSIX and Java permit it, so waits must always be in a loop.

How does Java support monitors?

Every object has an intrinsic lock and one wait set. synchronized methods/blocks lock it, and wait(), notify(), notifyAll() act as the condition operations. ReentrantLock with Condition objects gives multiple condition queues.

Is the monitor solution to dining philosophers deadlock-free? Starvation-free?

Deadlock-free, because a philosopher takes both chopsticks in one atomic step (no hold and wait). Not starvation-free: two neighbours can alternate eating forever.

Can monitors be implemented with semaphores?

Yes: a mutex semaphore for entry, a next semaphore and next_count for suspended signallers, and for each condition a semaphore x_sem with a counter x_count. Semaphores can also be implemented with monitors, so they are equally powerful.


Summary

  • A monitor packages shared data, the procedures that use it, and initialization, and lets only one process be active inside at a time. Mutual exclusion is automatic.

  • Condition variables let a process wait inside a monitor: wait always blocks and releases the monitor; signal wakes one waiter and is lost if nobody is waiting.

  • Hoare semantics run the woken process immediately; Mesa semantics (used by Java, pthreads, C#, Python) let the signaller continue, so waits must be in a while loop. We saw the if version take items from an empty buffer.

  • In C a monitor is a mutex plus condition variables; in Java it is synchronized with wait/notifyAll.

  • The monitor solution to dining philosophers picks up both chopsticks at once: deadlock-free, but not starvation-free.

  • Monitors can be built from semaphores and vice versa; monitors are not more powerful, just much harder to misuse.