Monitors

01 Introduction

Lessons 6.3 and 6.4 presented two synchronization primitives — the lock and the semaphore — that are provided by the operating system or its libraries. Both are powerful and both are error-prone. A lock must be acquired before every access to the shared state and released after every access, with no path through the code that forgets either. A semaphore must be signalled exactly as many times as it is waited on, in the right order, with no path that forgets or over-signals. In both cases, the correctness of the program depends on the programmer's discipline in following a protocol that the compiler cannot check.

The monitor is a different approach. It is a synchronization abstraction provided by the programming language rather than the operating system. A monitor is a module — like a class in an object-oriented language — that contains a shared data structure, the procedures that operate on it, and the synchronization that protects it. The compiler enforces the mutual exclusion: a monitor procedure is executed by at most one thread at a time, and the programmer never writes an acquire or a release at all.

The monitor was introduced by Per Brinch Hansen in 1973 and developed by Tony Hoare in 1974. It was the first widely adopted high-level synchronization abstraction, and it influenced the design of Java's synchronized methods, C#'s lock statement, and the synchronized blocks of many other languages. It is the primitive that most modern programmers actually use, even if they do not call it by that name.

This lesson presents the monitor abstraction. It defines the structure of a monitor, explains how mutual exclusion is enforced, and introduces the condition variable — the mechanism a monitor uses to wait for a condition to become true. It presents the producer–consumer problem solved with a monitor, compares the two semantics that a monitor's signal operation can have (Hoare and Mesa), and explains why C and POSIX do not provide monitors directly. The condition variable itself is the subject of Lesson 6.6, which follows this one; here we introduce it enough to write correct monitor code.

02 Learning objectives

This lesson contributes to U6.3, U6.4, and U6.5, and to course learning outcomes CLO2, CLO3, and CLO8.

03 Required reading

• Operating System Concepts — Chapter 6, Section 6.7, Monitors. The standard treatment, including the producer–consumer solution with condition variables and the discussion of Hoare versus Mesa semantics.
• Tanenbaum & Bos — Modern Operating Systems, Chapter 2, Section 2.3.7, Monitors. A complementary treatment that places the monitor in the historical context of the 1970s and includes the dining philosophers solution.
• OSTEP — Chapter 30, Condition Variables. OSTEP treats the condition variable as the primitive and builds the monitor-style solutions around it. Read this as a preview of Lesson 6.6 and for the producer–consumer solutions using condition variables.
• Hoare, C. A. R. — Monitors: An Operating System Structuring Concept. Communications of the ACM, 1974. The original paper on monitors and condition variables. Read the first three sections; the rest is more technical.
• Brinch Hansen, P. — Operating System Principles, Chapter 3. The original presentation of the monitor concept from a design perspective.
• Java Language Specification — Section 17.1, Synchronization, and Section 8.4.3, synchronized Methods. The Java implementation of monitor semantics.

04 Core content

4.1 The monitor abstraction

A monitor is a programming-language construct that packages three things into a single unit:

• Shared data. The state that the monitor protects — a buffer, a counter, a queue, any data structure that requires synchronization.
• Procedures. The operations that read and modify the shared data. These are the only operations that external code can invoke.
• Initialization. Code that initializes the shared data when the monitor is created.

The essential property of a monitor is that at most one thread can be executing a monitor procedure at a time. The compiler or the runtime enforces this; the programmer does not write any code to make it happen. When a thread calls a monitor procedure, the runtime automatically acquires a lock on the monitor before the procedure body runs, and releases it when the procedure returns. If another thread is already inside a monitor procedure, the calling thread blocks until the monitor is free.

4.2 The difference from locks and semaphores

The essential difference between a monitor and the lower-level primitives is where the synchronization is enforced. With a lock or a semaphore, the synchronization is the programmer's responsibility: the programmer writes the acquire and release, or the wait and signal, and is responsible for every path through the code.

With a monitor, the synchronization is part of the abstraction. The compiler or runtime inserts the acquire and release around every monitor procedure, automatically and correctly. The programmer writes only the shared data and the operations on it.

The monitor's structural guarantee is a significant advantage: a whole class of errors — forgetting to release a lock, acquiring a lock twice, acquiring the wrong lock — becomes impossible by construction. This is why languages that provide monitors are widely regarded as easier to use for concurrent programming than C and C++.

4.3 Condition variables

Mutual exclusion alone is not enough to solve the problems of the previous two lessons. The producer–consumer problem requires a producer to wait until a slot is free, and a consumer to wait until an item is available. Both waits are for a condition that another thread will make true — not merely for the monitor to be free.

A monitor provides condition variables for this purpose. A condition variable c is an object with three operations:

c.wait()

Release the monitor, suspend the calling thread, and add it to the wait queue for c. When the thread is woken (by a signal or broadcast), it re-acquires the monitor and returns from wait. The release-and-reacquire is automatic; the programmer writes only c.wait().

c.signal()

Wake one thread waiting on c, if any. If no thread is waiting, the signal has no effect — it is lost, unlike a semaphore's post, which would increment the value.

c.broadcast() (also c.notify_all())

Wake all threads waiting on c. Used when the condition that has become true may allow more than one waiter to proceed.

The central difference between a condition variable and a semaphore is that a condition variable has no memory. A signal that arrives when no thread is waiting has no effect. This is because the condition variable is always used inside a monitor, where the condition is a property of the shared data: if the condition is true, a thread that later enters the monitor will see it directly, without needing a remembered signal. The signal is only a wakeup, not a value.

A monitor may have any number of condition variables, each associated with a different condition on the shared data. In the producer–consumer solution, for example, we use one condition variable for "buffer is not full" and another for "buffer is not empty".

4.4 Producer–consumer with a monitor

The bounded-buffer producer–consumer problem, solved with a monitor, is the classic example. The monitor holds the buffer and its indices, and provides two procedures, insert and remove:

monitor BoundedBuffer {
    /* shared data */
    int  buffer[N];
    int  in = 0, out = 0, count = 0;

    /* condition variables */
    condition not_full;
    condition not_empty;

    procedure insert(int item) {
        while (count == N)
            not_full.wait();
        buffer[in] = item;
        in = (in + 1) % N;
        count++;
        not_empty.signal();
    }

    procedure remove() {
        while (count == 0)
            not_empty.wait();
        int item = buffer[out];
        out = (out + 1) % N;
        count--;
        not_full.signal();
        return item;
    }
}

A producer calls insert(item) and a consumer calls remove(). Neither calls any synchronization operation directly: the runtime acquires the monitor's lock on entry to the procedure and releases it on exit. The wait calls handle the cases where the buffer is full or empty; the signal calls notify a waiting thread that the condition has changed.

Compare this to the semaphore solution from Lesson 6.4. The monitor version is shorter, clearer, and has no explicit locking. The synchronization is expressed entirely in terms of the conditions the procedures must satisfy — count < N to insert, count > 0 to remove — and the wait-loop for each condition is local to the procedure that checks it. The semaphore version required the programmer to reason about three separate semaphore values and the order of the waits.

4.5 Hoare versus Mesa semantics

When a thread calls c.signal(), one of the waiters on c is woken. But there are two possible semantics for what happens next, and the choice between them has substantial consequences for how monitor code must be written.

Hoare semantics (signal-and-wait)

The signalling thread immediately gives up the monitor to the woken thread, which runs as soon as the signaller suspends. The signaller is placed in a special queue and resumes when the woken thread leaves the monitor or waits again. The woken thread can be sure that the condition it was waiting for is still true when it wakes, because no other thread has had a chance to change it.

Mesa semantics (signal-and-continue)

The signalling thread continues executing, and the woken thread is moved to the monitor entry queue, where it must compete with new arrivals for the monitor. By the time the woken thread actually runs, other threads may have entered the monitor and changed the shared data. The condition it was waiting for may no longer hold.

Hoare semantics is simpler to reason about: a thread that wakes from wait knows that the condition it was waiting for is true, so an if would suffice. But Hoare semantics is harder to implement — the signaller must be suspended and resumed with the correct priority — and it leads to more context switches, because every signal that wakes a thread causes the signaller to be suspended. For these reasons, virtually every real implementation of monitors uses Mesa semantics.

The consequence is that every wait must be inside a while loop. Under Mesa semantics, the woken thread must re-check the condition after it re-acquires the monitor, because another thread may have consumed the item or filled the slot in the meantime. This is why the producer–consumer code above uses while (count == N) rather than if (count == N). The while loop is correct under both semantics; the if is correct only under Hoare.

4.6 signal versus broadcast

A condition variable has two wakeup operations. The choice between them depends on how many waiters can proceed when the condition becomes true.

signal

Wake exactly one waiter. Appropriate when the condition that has become true allows exactly one waiter to make progress. In the producer–consumer solution, one inserted item allows one consumer to remove it, so a signal is correct and more efficient than a broadcast.

broadcast

Wake all waiters, each of which must re-check its condition. Appropriate when the condition that has become true may allow more than one waiter to proceed, or when the set of waiters is heterogeneous and the signaller does not know which one can proceed. The classic example is a change to a global state that different waiters are waiting on different parts of.

A broadcast is always correct — it wakes more threads than necessary, and each re-checks its condition and waits again if the condition is still false. But it has a cost: it wakes threads that will immediately go back to sleep, causing useless context switches and contention on the monitor. On a system with many waiters, the difference between signal and broadcast can be substantial.

The general guidance is to use signal when the condition is specific and only one waiter can proceed, and broadcast when the condition is general or the waiters are heterogeneous. The dining philosophers problem, for example, uses broadcast because a philosopher putting down a fork may allow either of two neighbours to pick up a fork — and the signaller does not know which of them will succeed.

4.7 Monitors in modern languages

The monitor concept as Hoare and Brinch Hansen described it — a language construct with a compiler that enforces mutual exclusion — is rare in its pure form. But the ideas appear in every modern language that supports concurrency.

• Java. Every Java object has a monitor associated with it. A method declared synchronized is executed as a monitor procedure: the JVM acquires the object's monitor on entry and releases it on exit. A synchronized block acquires the monitor for the duration of the block. Java provides wait(), notify(), and notifyAll() on every object, corresponding to wait, signal, and broadcast. Java uses Mesa semantics.
• C#. The lock statement acquires a monitor on a specified object for the duration of a block. The Monitor class provides Wait, Pulse, and PulseAll. C# uses Mesa semantics.
• Python. The threading module provides Lock, RLock, and Condition. A Condition is a condition variable, used together with a lock in the same pattern as a monitor. Python's GIL limits the concurrency of pure-Python code, but the abstractions are the same.
• Ruby. The Monitor class in the standard library provides a reentrant mutex and condition variables, used in the monitor pattern.

In each case, the language provides the monitor's key guarantees: structural mutual exclusion for the protected region, and condition variables for waiting on a condition. The programmer does not write acquire and release around every critical section; the language inserts them.

4.8 Monitors in C and POSIX

C and POSIX do not provide monitors. There is no language-level construct that automatically acquires a lock on entry to a function and releases it on exit. The closest thing is the combination of a mutex and one or more condition variables, used together by convention:

/* The "monitor" is a struct containing a mutex and a condvar. */
typedef struct {
    pthread_mutex_t mutex;
    pthread_cond_t  not_full;
    pthread_cond_t  not_empty;
    int buffer[N];
    int in, out, count;
} buffer_t;

/* Monitor procedure — the caller must lock the mutex first. */
void insert(buffer_t *b, int item) {
    pthread_mutex_lock(&b->mutex);
    while (b->count == N)
        pthread_cond_wait(&b->not_full, &b->mutex);
    b->buffer[b->in] = item;
    b->in = (b->in + 1) % N;
    b->count++;
    pthread_cond_signal(&b->not_empty);
    pthread_mutex_unlock(&b->mutex);
}

This is not a monitor in the language sense — the programmer still writes the lock and unlock, and the compiler does not check that every path does so correctly. But the discipline is the same: the mutex protects the shared data, and the condition variables handle waiting for conditions. The pthread_cond_wait function takes the mutex as an argument, because it must atomically release the mutex and begin waiting — if the release and the wait were not atomic, another thread could signal between them and the signal would be lost.

The lesson for C programmers is that the monitor pattern is available in C, but only as a convention the programmer must follow. Nothing prevents a programmer from accessing the shared data without holding the mutex, or from calling pthread_cond_wait without the mutex, or from forgetting to release the mutex on some path. The structural guarantee of a true monitor is absent, and the correctness of the program depends entirely on the programmer's discipline. This is why C is considered harder for concurrent programming than Java or C#, and why the same patterns appear in C code with more ceremony and more opportunities for error.

4.9 The dining philosophers with monitors

The dining philosophers problem is a second classic. Five philosophers sit at a round table, each alternating between thinking and eating. Between each pair of adjacent philosophers is a single fork, so there are five forks for five philosophers. To eat, a philosopher must pick up both forks adjacent to them.

The monitor solution uses a single monitor for the table, with a state variable for each philosopher and a condition variable per philosopher:

monitor Table {
    enum { THINKING, HUNGRY, EATING } state[5];
    condition self[5];

    procedure pickup(int i) {
        state[i] = HUNGRY;
        test(i);
        while (state[i] != EATING)
            self[i].wait();
    }

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

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

A philosopher calls pickup(i) before eating and putdown(i) after. The test procedure checks whether the philosopher can eat (both neighbours are not eating) and, if so, sets the state to EATING and signals the philosopher's condition variable. The pickup procedure sets the state to HUNGRY, runs the test, and waits if it cannot eat yet.

The solution avoids deadlock: the monitor serializes the state changes, and a philosopher is allowed to eat only when both neighbours are not eating. It also avoids starvation in a weak sense — a philosopher who is hungry and whose neighbours eventually put down their forks will be signalled by the test calls in the neighbours' putdown procedures. The problem is examined in more detail in Unit 7, where deadlock is the subject.

4.10 Common pitfalls

05 Worked example

The following example traces the monitor-based producer–consumer solution through a sequence of operations, and shows the difference between Hoare and Mesa semantics by tracing the same sequence under both.

06 Interactive activity

07 Knowledge check

08 Unit discussion

09 Practice exercise

10 Summary

• A monitor is a language-level construct that packages shared data, the procedures that operate on it, and the synchronization that protects it into a single unit. It was introduced by Brinch Hansen (1973) and Hoare (1974).
• The essential property of a monitor is that at most one thread is executing a monitor procedure at a time. The runtime enforces this automatically; the programmer writes no lock or unlock.
• This structural guarantee distinguishes the monitor from the lock and the semaphore, where the synchronization is the programmer's responsibility and the compiler cannot check it.
• A condition variable allows a thread to wait for a condition inside a monitor. Its operations are wait (release the monitor and suspend), signal (wake one waiter), and broadcast (wake all waiters).
• A condition variable has no memory: a signal that arrives when no thread is waiting has no effect. This is different from a semaphore, whose post increments a value that a later wait can find.
• Mesa semantics (signal-and-continue) is what nearly every real implementation provides. Under Mesa semantics, the signaller continues and the woken thread competes for the monitor, so the condition may no longer hold when the woken thread runs.
• Hoare semantics (signal-and-wait) is the semantics Hoare described in his original paper: the signaller immediately yields the monitor to the woken thread. It is simpler to reason about but harder to implement and causes more context switches.
• The consequence of Mesa semantics is that every wait must be inside a while loop that re-checks the condition. A wait inside an if is correct only under Hoare semantics and is a common bug.
• The monitor solution to the bounded-buffer producer–consumer problem uses one condition variable for "buffer not full" and one for "buffer not empty". It is shorter and clearer than the semaphore solution, and it cannot deadlock from a reversed acquisition order.
• Modern languages implement monitors in various forms: Java's synchronized methods and wait/notify, C#'s lock statement and Monitor class, and the condition variable libraries of Python and Ruby. C and POSIX do not provide monitors directly; the closest equivalent is the mutex-plus-condition-variable pattern, which requires the programmer to write the synchronization explicitly.

11 References

• Silberschatz, A., Galvin, P. B., & Gagne, G. Operating System Concepts, 10th ed., Chapter 6, Section 6.7.
• Tanenbaum, A. S., & Bos, H. Modern Operating Systems, 4th ed., Chapter 2, Section 2.3.7.
• Arpaci-Dusseau, R. H., & Arpaci-Dusseau, A. C. Operating Systems: Three Easy Pieces, Chapter 30. Available online at ostep.org.
• Hoare, C. A. R. Monitors: An Operating System Structuring Concept. Communications of the ACM, 1974. The original paper on monitors and condition variables.
• Brinch Hansen, P. Operating System Principles. Prentice-Hall, 1973. The original presentation of the monitor concept.
• Lampson, B. W., & Redell, D. D. Experience with Processes and Monitors in Mesa. Communications of the ACM, 1980. The paper that introduced signal-and-continue semantics.
• Lea, D. Concurrent Programming in Java: Design Principles and Patterns, 2nd ed. Addison-Wesley, 1999. The Java memory model and the implementation of monitors in the JVM.
• Linux man-pages: man 3 pthread_cond_init, man 3 pthread_cond_wait, man 3 pthread_cond_signal, man 3 pthread_cond_broadcast, man 3 pthread_cond_destroy.