CSE Roadmap

Core tier · about 5 hours · 7 parts

Part 6 of 7 · 5 min read

Monitors

Monitors

Think of it this way. A bank teller's cage has one door, a counter, and a rule that only one customer is inside at a time. Customers who need something that is not there yet wait in a lobby and are called. The data and the rules for using them stay in one place. The analogy stops in one place: a real cage is built in stone, while a monitor in C is a convention that the programmer must follow.

In plain words: A monitor is a structure that bundles shared data with the operations that use it, a mutex that guards them, and condition variables for the waits. Every operation takes the mutex on entry and releases it on exit, so at most one thread runs inside the monitor at a time. Some languages build monitors in (the synchronized methods of Java, with wait and notify); in C, the programmer writes one by discipline.

A small monitor in C, a bank account in which withdraw waits for enough funds:

static struct { int balance; pthread_mutex_t mu; pthread_cond_t funds; } account =
    { 0, PTHREAD_MUTEX_INITIALIZER, PTHREAD_COND_INITIALIZER };

static void deposit(int n) {
    pthread_mutex_lock(&account.mu);
    account.balance += n;
    pthread_cond_broadcast(&account.funds);       /* the condition may now hold for someone */
    pthread_mutex_unlock(&account.mu);
}
static void withdraw(int n) {
    pthread_mutex_lock(&account.mu);
    while (account.balance < n)                   /* the real condition, in a loop */
        pthread_cond_wait(&account.funds, &account.mu);
    account.balance -= n;
    pthread_mutex_unlock(&account.mu);
}

A test starts three customers who each withdraw 50, and a depositor who deposits 20 ten times (200 in all, 20 ms apart). All three customers eventually got their 50, in whichever order they were served, and the final balance was 50 (200 − 150), as it should be. Broadcast is used because three threads wait for the same data with a threshold that they may meet at different times.

Two styles of monitors differ in what happens at a signal. In the Mesa style, used by POSIX threads, Java and most systems, the signaller keeps running and the woken thread only becomes ready, so the condition may be false when it runs: a loop is required. In the older Hoare style, the signaller hands the monitor straight to the woken thread, which can trust the condition without a loop. Hoare monitors are easier to reason about and harder to implement, and almost nobody uses them in practice. So the loop is never optional.

Monitor

A monitor is a synchronisation construct that groups shared data, the operations on it, a mutex that makes the operations mutually exclusive, and condition variables on which threads wait for states of the data.

Example: the account structure with deposit and withdraw, whose every operation locks the same mutex and which waits for funds on one condition variable.

Common mistake

Using if (!ready) pthread_cond_wait(...) instead of while. It works in simple tests, and fails when a second consumer takes the data between the wakeup and the lock, or on a spurious wakeup.

Interview angle

Answer in your head first, then open it.

Why does pthread_cond_wait take a mutex?

It releases it while the thread sleeps and relocks it on wakeup, atomically, to avoid a lost wakeup.

Why must the wait be in a while loop?

The condition may be false on wakeup, because of another thread's action or a spurious wakeup.

What is the difference between signal and broadcast?

Signal wakes one waiter and broadcast wakes all.

What is a monitor?

Data, a lock and condition variables packaged with the operations that use them.

What is a spurious wakeup?

A return from the wait with no signal, allowed by the standard.

Check yourself: 1. Why does withdraw use while and not if? 2. Which style of monitor do POSIX threads follow? 3. Why does deposit use broadcast?

Words you will meet

Word Meaning
Condition variable A queue of sleeping threads, used with a mutex
Wait Atomically release the mutex and sleep
Signal Wake at least one waiting thread
Broadcast Wake all waiting threads
Spurious wakeup A return from wait without any signal
Lost wakeup A signal that nobody receives
Predicate The condition that the waiting thread tests
Thundering herd Many threads wake and most sleep again
Monitor Data, a mutex and conditions packaged together
Mesa and Hoare Two styles, the signaller continues or hands over

Quick notes

  • A condition variable is a synchronisation object that is used with a mutex and that holds a queue of sleeping threads: a thread waits on it by atomically releasing the.
  • A spurious wakeup is the return of a thread from a condition-variable wait although no thread has signalled or broadcast, which the standard permits, and which is why a waiting thread must always retest its condition in a loop.
  • A lost wakeup is the failure in which a signal is sent before the target thread is waiting, or in the gap between its test and its sleep, so the thread never receives it and may wait for ever.
  • A broadcast on a condition variable wakes all threads waiting on it, each of which must retest its own condition, whereas a signal wakes at least one.
  • A monitor is a synchronisation construct that groups shared data, the operations on it, a mutex that makes the operations mutually exclusive, and condition variables on which threads wait for states of the data.