In concurrent programming, a monitor is a synchronization construct that prevents threads from concurrently accessing a shared object's state and allows them to wait for the state to change. They provide a mechanism for threads to temporarily give up exclusive access in order to wait for some condition to be met, before regaining exclusive access and resuming their task. A monitor consists of a mutex (lock) and at least one condition variable. A condition variable is explicitly 'signalled' when the object's state is modified, temporarily passing the mutex to another thread 'waiting' on the condition variable.
Another definition of monitor is a thread-safe object, class, or module that contains and uses a mutex to safely allow access to its methods or variables by more than one thread. The defining characteristic of a monitor is that its methods are executed with mutual exclusion: at each point in time, at most one thread may be executing any of the monitor's methods. By using one or more condition variables it can also provide the ability for threads to wait on a certain condition (thus using the first definition of a "monitor"). For the rest of this article, this sense of "monitor" will be referred to as a "thread-safe object/class/module."
Monitors were invented by Per Brinch Hansen and C. A. R. Hoare, and were first implemented in Brinch Hansen's Concurrent Pascal language.
Mutual exclusion
While a thread is executing a method of a thread-safe object, it is said to occupy the object, by holding its mutex (lock). Thread-safe objects are implemented to enforce that at any point in time, at most one thread may occupy the object. The lock, which is initially unlocked, is locked at the start of each public method, and is unlocked at each return from each public method.
Upon calling one of the methods, a thread must wait until no other thread is executing any of the thread-safe object's methods before starting execution of its method. Note that without this mutual exclusion, two threads could cause data races and logical errors. For example, two threads withdrawing 1000 from the account could both return true, while causing the balance to drop by only 1000, as follows: first, both threads fetch the current balance, find it greater than 1000, and subtract 1000 from it; then, both threads store the balance and return.
Condition variables
Problem statement For many applications, mutual exclusion is not enough. Threads attempting an operation may need to wait until some condition holds true. A busy waiting loop
while not ( ) do skip
will not work, as mutual exclusion will prevent any other thread from entering the monitor to make the condition true. Other "solutions" exist such as having a loop that unlocks the monitor, waits a certain amount of time, locks the monitor and checks for the condition . Theoretically, it works and will not deadlock, but issues arise. It is hard to decide an appropriate amount of waiting time: too small and the thread will hog the CPU, too big and it will be apparently unresponsive. What is needed is a way to signal the thread when the condition is true (or could be true).
Case study: classic bounded producer/consumer problem A classic concurrency problem is that of the bounded producer/consumer, in which there is a queue or ring buffer of tasks with a maximum size, with one or more threads being "producer" threads that add tasks to the queue, and one or more other threads being "consumer" threads that take tasks out of the queue. The queue is assumed to be non–thread-safe itself, and it can be empty, full, or between empty and full. Whenever the queue is full of tasks, then we need the producer threads to block until there is room from consumer threads dequeueing tasks. On the other hand, whenever the queue is empty, then we need the consumer threads to block until more tasks are available due to producer threads adding them.
As the queue is a concurrent object shared between threads, accesses to it must be made atomic, because the queue can be put into an inconsistent state during the course of the queue access that should never be exposed between threads. Thus, any code that accesses the queue constitutes a critical section that must be synchronized by mutual exclusion. If code and processor instructions in critical sections of code that access the queue could be interleaved by arbitrary context switches between threads on the same processor or by simultaneously-running threads on multiple processors, then there is a risk of exposing inconsistent state and causing race conditions.
Incorrect without synchronization A naive approach is to design the code with busy-waiting and no synchronization, making the code subject to race conditions:
global RingBuffer queue; // A thread-unsafe ring-buffer of tasks.
// Method representing each producer thread's behavior: public method producer() { while (true) { task myTask = ...; // Producer makes some new task to be added. while (queue.isFull()) {} // Busy-wait until the queue is non-full. queue.enqueue(myTask); // Add the task to the queue.
// Method representing each consumer thread's behavior: public method consumer() { while (true) { while (queue.isEmpty()) {} // Busy-wait until the queue is non-empty. myTask = queue.dequeue(); // Take a task off of the queue. doStuff(myTask); // Go off and do something with the task.
This code has a serious problem in that accesses to the queue can be interrupted and interleaved with other threads' accesses to the queue. The queue.enqueue and queue.dequeue methods likely have instructions to update the queue's member variables such as its size, beginning and ending positions, assignment and allocation of queue elements, etc. In addition, the queue.isEmpty() and queue.isFull() methods read this shared state as well. If producer/consumer threads are allowed to be interleaved during the calls to enqueue/dequeue, then inconsistent state of the queue can be exposed leading to race conditions. In addition, if one consumer makes the queue empty in-between another consumer's exiting the busy-wait and calling "dequeue", then the second consumer will attempt to dequeue from an empty queue leading to an error. Likewise, if a producer makes the queue full in-between another producer's exiting the busy-wait and calling "enqueue", then the second producer will attempt to add to a full queue leading to an error.
Spin-waiting One naive approach to achieve synchronization, as alluded to above, is to use "spin-waiting", in which a mutex is used to protect the critical sections of code and busy-waiting is still used, with the lock being acquired and released in between each busy-wait check.
global RingBuffer queue; // A thread-unsafe ring-buffer of tasks. global Lock queueLock; // A mutex for the ring-buffer of tasks.
// Method representing each producer thread's behavior: public method producer() { while (true) { task myTask = ...; // Producer makes some new task to be added.
queueLock.acquire(); // Acquire lock for initial busy-wait check. while (queue.isFull()) { // Busy-wait until the queue is non-full. queueLock.release(); // Drop the lock temporarily to allow a chance for other threads // needing queueLock to run so that a consumer might take a task. queueLock.acquire(); // Re-acquire the lock for the next call to "queue.isFull()".
queue.enqueue(myTask); // Add the task to the queue. queueLock.release(); // Drop the queue lock until we need it again to add the next task.
// Method representing each consumer thread's behavior: public method consumer() { while (true) { queueLock.acquire(); // Acquire lock for initial busy-wait check. while (queue.isEmpty()) { // Busy-wait until the queue is non-empty. queueLock.release(); // Drop the lock temporarily to allow a chance for other threads // needing queueLock to run so that a producer might add a task. queueLock.acquire(); // Re-acquire the lock for the next call to "queue.isEmpty()".
myTask = queue.dequeue(); // Take a task off of the queue. queueLock.release(); // Drop the queue lock until we need it again to take off the next task. doStuff(myTask); // Go off and do something with the task.
This method assures that an inconsistent state does not occur, but wastes CPU resources due to the unnecessary busy-waiting. Even if the queue is empty and producer threads have nothing to add for a long time, consumer threads are always busy-waiting unnecessarily. Likewise, even if consumers are blocked for a long time on processing their current tasks and the queue is full, producers are always busy-waiting. This is a wasteful mechanism. What is needed is a way to make producer threads block until the queue is non-full, and a way to make consumer threads block until the queue is non-empty.
(N.B.: Mutexes themselves can also be spin-locks which involve busy-waiting in order to get the lock, but in order to solve this problem of wasted CPU resources, we assume that queueLock is not a spin-lock and properly uses a blocking lock queue itself.)
Condition variables
The solution is to use condition variables. Conceptually, a condition variable is a queue of threads, associated with a mutex, on which a thread may wait for some condition to become true. Thus each condition variable is associated with an assertion . While a thread is waiting on a condition variable, that thread is not considered to occupy the monitor, and so other threads may enter the monitor to change the monitor's state. In most types of monitors, these other threads may signal the condition variable to indicate that assertion is true in the current state.
Thus there are three main operations on condition variables: wait c, m, where c is a condition variable and m is a mutex (lock) associated with the monitor. This operation is called by a thread that needs to wait until the assertion is true before proceeding. While the thread is waiting, it does not occupy the monitor. The function, and fundamental contract, of the "wait" operation, is to do the following steps: Atomically:
Once this thread is subsequently notified/signaled (see below) and resumed, then automatically re-acquire the mutex m. Steps 1a and 1b can occur in either order, with 1c usually occurring after them. While the thread is sleeping and in c's wait-queue, the next program counter to be executed is at step 2, in the middle of the "wait" function/subroutine. Thus, the thread sleeps and later wakes up in the middle of the "wait" operation. The atomicity of the operations within step 1 is important to avoid race conditions that would be caused by a preemptive thread switch in-between them. One failure mode that could occur if these were not atomic is a missed wakeup, in which the thread could be on c's sleep-queue and have released the mutex, but a preemptive thread switch occurred before the thread went to sleep, and another thread called a signal operation (see below) on c moving the first thread back out of c's queue. As soon as the first thread in question is switched back to, its program counter will be at step 1c, and it will sleep and be unable to be woken up again, violating the invariant that it should have been on c's sleep-queue when it slept. Other race conditions depend on the ordering of steps 1a and 1b, and depend on where a context switch occurs.