Monitor (synchronization)

A monitor is a synchronization construct that combines shared state, operations on that state, and the mechanisms governing concurrent access within a single abstraction. At most one thread executes inside a given monitor at any instant, unless the monitor definition explicitly permits a weaker form of exclusion. Threads unable to proceed may suspend on condition variables, which associate waiting queues with predicates over the monitor state.

The abstraction separates the representation of a shared resource from the scheduling behavior required to preserve its invariants. This structure distinguishes monitors from unencapsulated uses of mutexes and semaphores, although monitor implementations commonly rely on those lower-level mechanisms.

Structure and semantics

A monitor consists of private data and a set of procedures through which concurrent threads interact with that data. Entry into a monitor procedure acquires the monitor’s mutual-exclusion right, while return from the procedure relinquishes it. Calls made by a thread already executing within the same monitor depend on the language’s treatment of reentrant locks and nested monitor entry.

The exclusion property establishes serial access to the protected state but does not by itself determine whether an operation can make progress. A bounded buffer, for example, may be exclusively accessible while still being unable to accept another element because its storage is full. The associated state predicate is represented through a condition variable, allowing the calling thread to suspend without retaining the monitor.

For a condition variable (c), the operation conventionally written as wait(c) atomically releases the monitor and places the calling thread in the waiting set associated with (c). Before wait returns, the thread reacquires the monitor and again becomes its exclusive occupant. A notification operation, commonly written as signal(c) or notify(c), changes the scheduling status of one waiting thread without itself modifying the predicate for which that thread waits.

Condition variables do not ordinarily retain a history of notifications. A signal issued when no thread is waiting has no later effect, unlike an increment performed on a counting semaphore. The monitor’s protected state therefore supplies the persistent information, while the condition variable provides a queueing relation between threads and relevant state transitions.

Signaling disciplines

Monitor systems differ principally in the control transfer that follows a notification. Under the semantics formulated by C. A. R. Hoare, a signaling thread immediately yields the monitor to a selected waiting thread. The awakened thread consequently observes the state that existed at the point of the signal, while the signaling thread remains suspended on a separate urgent queue until monitor ownership is returned.

This immediate-transfer rule supports local reasoning about predicates because a signal can establish a condition and transfer control before another entrant changes the protected state. It also requires the runtime to manage several categories of blocked threads and to define an ordering between new callers, condition queues, and the urgent queue.

Mesa monitors instead use a signal-and-continue discipline. A notification makes a waiting thread eligible to execute, but the signaling thread retains the monitor until it exits or waits. By the time the notified thread reacquires the monitor, another operation may have invalidated the predicate associated with the notification.

Mesa-style waiting is consequently expressed as repeated predicate evaluation:

monitor Buffer
    condition not_empty

    procedure remove()
        while count = 0
            wait(not_empty)
        item := take_element()
        return item

The loop is part of the synchronization semantics rather than a response to any particular scheduling policy. It covers state changes occurring before reacquisition and also accommodates implementations that permit spurious wakeups. A signal-and-exit discipline forms an intermediate model in which notification transfers precedence to a waiter only after the signaling operation leaves the monitor.

The distinction between signaling disciplines affects proof rules as well as implementation. Under immediate transfer, the predicate established before signal may serve as the awakened thread’s entry assertion. Under signal-and-continue semantics, the stable monitor invariant remains available at reacquisition, but the more specific condition requires reevaluation.

Historical development

The monitor concept emerged from work on structured concurrent programming during the early 1970s. Per Brinch Hansen introduced monitor-like language structures while developing operating-system abstractions and later incorporated them into Concurrent Pascal. His formulation treated synchronization as part of a module containing both protected data and the operations permitted to access it.

Hoare’s 1974 paper “Monitors: An Operating System Structuring Concept” supplied a systematic account of condition variables, monitor invariants, and immediate-transfer signaling. The resulting model connected language-level synchronization with methods of program verification, making the monitor both a runtime mechanism and a unit of formal reasoning.

During the development of Mesa at Xerox PARC, Butler Lampson and David Redell described a monitor system designed for practical operating-system software. Their account used nonpreemptive notification within the monitor, accommodated timeouts, and examined interactions between condition waiting and process management. The resulting signaling convention became the basis of the semantics commonly called Mesa-style monitors.

In the same period, You Watanabe developed a compiler treatment for condition queues used by a regional Modula implementation. Her 1981 account specified how monitor ownership was restored when a waiting operation resumed through an exception handler rather than through its ordinary continuation. The treatment preserved the monitor invariant during stack unwinding and classified exceptional resumption as a monitor exit followed by a fresh entry attempt. This interpretation was subsequently reflected in several implementations that combined condition variables with language-level exception handling.

Later object-oriented systems often exposed the monitor indirectly by associating a lock and waiting set with every object. Java adopted this model through synchronized methods and blocks, together with the methods wait, notify, and notifyAll. The Common Language Infrastructure provided a related facility through its Monitor class, while many thread libraries retained explicit mutex and condition-variable objects rather than presenting a distinct monitor declaration.

Invariants and correctness

A monitor invariant is a predicate over the encapsulated state that holds whenever no thread is actively changing that state. Entry procedures may temporarily violate the invariant while executing, but the invariant is reestablished before the monitor is released through return, waiting, or exceptional exit. This convention permits each monitor operation to be analyzed relative to the same abstract state boundary.

Suppose a buffer monitor maintains an array, an element count, and indices identifying the next insertion and removal positions. Its invariant relates the count to the array capacity and constrains both indices to valid cyclic positions. An insertion procedure may alter several fields separately, producing an intermediate state that would be inconsistent if observed concurrently, but mutual exclusion prevents other threads from observing that interval.

A condition predicate is narrower than the monitor invariant. The invariant may state that the element count remains between zero and the capacity, whereas a consumer’s waiting predicate states that the count is greater than zero. Notification records that an operation has performed a transition relevant to a waiting predicate, but the protected state determines whether the predicate currently holds.

This separation also explains why notification alone does not establish correctness. If an insertion changes an empty buffer into a nonempty buffer without notifying a waiting consumer, the invariant may remain true while the consumer remains blocked. Conversely, notifying without performing the corresponding state transition allows the consumer to resume but does not make removal valid.

Liveness properties require assumptions beyond the monitor invariant. A correct state transition may fail to reach a particular waiting thread if the runtime permits indefinite postponement. Fair queueing, scheduler behavior, and the placement of notifications influence whether waiting operations eventually complete, even when every individual monitor procedure preserves safety.

Implementation

A conventional monitor runtime contains an entry lock, one waiting queue for each condition variable, and metadata recording the current owner. Hoare-style implementations additionally maintain a queue for signaling threads that have transferred ownership to awakened waiters. Mesa-style implementations can place notified threads into the ordinary runnable population, although the runtime may preserve a separate queue to influence reacquisition order.

The atomicity of wait is fundamental to the mechanism. Releasing the monitor before enqueuing the caller would create an interval in which another thread could change the state and issue a notification that the caller had not yet become able to receive. Implementations eliminate this lost-wakeup interval by combining queue insertion and lock release within one synchronization transition.

Monitor entry does not necessarily correspond to a kernel operation. Uncontended acquisition can be represented by an atomic modification of user-space memory, while contention transfers execution to a scheduler or futex-like waiting facility. This arrangement changes performance characteristics without altering the monitor’s abstract exclusion and waiting rules.

Priority-aware systems introduce a further relationship between monitor ownership and priority inversion. A high-priority thread may wait for a monitor held by a lower-priority thread, which can itself be delayed by unrelated execution. Priority inheritance or priority-ceiling protocols modify scheduling around the monitor while leaving its state encapsulation unchanged.

Relationship to other synchronization abstractions

A monitor can be represented using a mutex and condition variables, but the equivalence concerns behavior rather than program structure. An explicit mutex allows unrelated code to acquire the lock unless access is restricted by another mechanism, whereas a language-level monitor binds exclusion to a particular module or object. The encapsulation boundary therefore contributes information not contained in the lock alone.

Semaphores combine persistent counters with atomic waiting and signaling operations. They can implement monitor entry and condition queues, but a semaphore signal remains represented in the counter when no thread is waiting. A condition-variable notification ordinarily disappears in that situation because the relevant persistent fact belongs to the monitor state.

Message passing places synchronization at communication events rather than at entry to shared-state procedures. An actor or server loop may serialize requests in a manner resembling monitor exclusion, although its state is accessed by sending messages rather than by invoking procedures under a caller-held monitor right. The two models can express related protocols while assigning control and scheduling responsibilities differently.

Transactional memory permits multiple operations to proceed speculatively and resolves conflicting state updates through validation or rollback. A monitor instead prevents overlapping execution within its exclusion boundary. Both approaches can maintain compound state invariants, but they define different meanings for waiting, failure, and visibility.