HOME

TheInfoList



OR:

In
concurrent programming Concurrent means happening at the same time. Concurrency, concurrent, or concurrence may refer to: Law * Concurrence, in jurisprudence, the need to prove both ''actus reus'' and ''mens rea'' * Concurring opinion (also called a "concurrence"), ...
, a monitor is a synchronization construct that allows threads to have both
mutual exclusion In computer science, mutual exclusion is a property of concurrency control, which is instituted for the purpose of preventing race conditions. It is the requirement that one thread of execution never enters a critical section while a concurren ...
and the ability to wait (block) for a certain condition to become false. Monitors also have a mechanism for signaling other threads that their condition has been met. A monitor consists of a mutex (lock) object and condition variables. A condition variable essentially is a container of threads that are waiting for a certain condition. Monitors 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. Another definition of monitor is a thread-safe
class Class or The Class may refer to: Common uses not otherwise categorized * Class (biology), a taxonomic rank * Class (knowledge representation), a collection of individuals or objects * Class (philosophy), an analytical concept used differently ...
,
object Object may refer to: General meanings * Object (philosophy), a thing, being, or concept ** Object (abstract), an object which does not exist at any particular time or place ** Physical object, an identifiable collection of matter * Goal, an ...
, or
module Module, modular and modularity may refer to the concept of modularity. They may also refer to: Computing and engineering * Modular design, the engineering discipline of designing complex devices using separately designed sub-components * Modul ...
that wraps around a mutex in order to safely allow access to a method or variable by more than one thread. The defining characteristic of a monitor is that its methods are executed with
mutual exclusion In computer science, mutual exclusion is a property of concurrency control, which is instituted for the purpose of preventing race conditions. It is the requirement that one thread of execution never enters a critical section while a concurren ...
: At each point in time, at most one thread may be executing any of its
methods Method ( grc, μέθοδος, methodos) literally means a pursuit of knowledge, investigation, mode of prosecuting such inquiry, or system. In recent centuries it more often means a prescribed process for completing a task. It may refer to: *Scien ...
. By using one or more condition variables it can also provide the ability for threads to wait on a certain condition (thus using the above 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 Sir Charles Antony Richard Hoare (Tony Hoare or C. A. R. Hoare) (born 11 January 1934) is a British computer scientist who has made foundational contributions to programming languages, algorithms, operating systems, formal verification, and c ...
, and were first implemented in Brinch Hansen's
Concurrent Pascal Concurrent Pascal is a programming language designed by Per Brinch Hansen for writing concurrent computing programs such as operating systems and real-time computing monitoring systems on shared memory computers. A separate language, ''Seque ...
language.


Mutual exclusion

As a simple example, consider a thread-safe object for performing transactions on a bank account: monitor class ''Account'' 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 each 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, in the present example, two threads could cause money to be lost or gained for no reason. 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. The
syntactic sugar In computer science, syntactic sugar is syntax within a programming language that is designed to make things easier to read or to express. It makes the language "sweeter" for human use: things can be expressed more clearly, more concisely, or in an ...
"monitor class" in the above example is implementing the following basic representation of the code, by wrapping each function's execution in mutexes: class ''Account''


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 In computer science and software engineering, busy-waiting, busy-looping or spinning is a technique in which a process repeatedly checks to see if a condition is true, such as whether keyboard input or a lock is available. Spinning can also be use ...
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 condition A race condition or race hazard is the condition of an electronics, software, or other system where the system's substantive behavior is Sequential logic, dependent on the sequence or timing of other uncontrollable events. It becomes a software ...
s.


Incorrect without synchronization

A naïve 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() // Method representing each consumer thread's behavior: public method consumer() 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() // Method representing each consumer thread's behavior: public method consumer() 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 The program counter (PC), commonly called the instruction pointer (IP) in Intel x86 and Itanium microprocessors, and sometimes called the instruction address register (IAR), the instruction counter, or just part of the instruction sequencer, i ...
to be executed is at step 2, in the middle of the "wait" function/
subroutine In computer programming, a function or subroutine is a sequence of program instructions that performs a specific task, packaged as a unit. This unit can then be used in programs wherever that particular task should be performed. Functions may ...
. 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. * signal c, also known as notify c, is called by a thread to indicate that the assertion is true. Depending on the type and implementation of the monitor, this moves one or more threads from c's sleep-queue to the "ready queue", or another queue for it to be executed. It is usually considered a best practice to perform the "signal" operation before releasing mutex ''m'' that is associated with ''c'', but as long as the code is properly designed for concurrency and depending on the threading implementation, it is often also acceptable to release the lock before signalling. Depending on the threading implementation, the ordering of this can have scheduling-priority ramifications. (Some authors instead advocate a preference for releasing the lock before signalling.) A threading implementation should document any special constraints on this ordering. * broadcast c, also known as notifyAll c, is a similar operation that wakes up all threads in c's wait-queue. This empties the wait-queue. Generally, when more than one predicate condition is associated with the same condition variable, the application will require broadcast instead of signal because a thread waiting for the wrong condition might be woken up and then immediately go back to sleep without waking up a thread waiting for the correct condition that just became true. Otherwise, if the predicate condition is one-to-one with the condition variable associated with it, then signal may be more efficient than broadcast. As a design rule, multiple condition variables can be associated with the same mutex, but not vice versa. (This is a one-to-many correspondence.) This is because the predicate is the same for all threads using the monitor and must be protected with mutual exclusion from all other threads that might cause the condition to be changed or that might read it while the thread in question causes it to be changed, but there may be different threads that want to wait for a different condition on the same variable requiring the same mutex to be used. In the producer-consumer example described above, the queue must be protected by a unique mutex object, ''m''. The "producer" threads will want to wait on a monitor using lock ''m'' and a condition variable c_ which blocks until the queue is non-full. The "consumer" threads will want to wait on a different monitor using the same mutex ''m'' but a different condition variable c_ which blocks until the queue is non-empty. It would (usually) never make sense to have different mutexes for the same condition variable, but this classic example shows why it often certainly makes sense to have multiple condition variables using the same mutex. A mutex used by one or more condition variables (one or more monitors) may also be shared with code that does ''not'' use condition variables (and which simply acquires/releases it without any wait/signal operations), if those critical sections do not happen to require waiting for a certain condition on the concurrent data.


Monitor usage

The proper basic usage of a monitor is: acquire(m); // Acquire this monitor's lock. while (!p) // ... Critical section of code goes here ... signal(cv2); // Or: broadcast(cv2); // cv2 might be the same as cv or different. release(m); // Release this monitor's lock. To be more precise, this is the same pseudocode but with more verbose comments to better explain what is going on: // ... (previous code) // About to enter the monitor. // Acquire the advisory mutex (lock) associated with the concurrent // data that is shared between threads, // to ensure that no two threads can be preemptively interleaved or // run simultaneously on different cores while executing in critical // sections that read or write this same concurrent data. If another // thread is holding this mutex, then this thread will be put to sleep // (blocked) and placed on m's sleep queue. (Mutex "m" shall not be // a spin-lock.) acquire(m); // Now, we are holding the lock and can check the condition for the // first time. // The first time we execute the while loop condition after the above // "acquire", we are asking, "Does the condition/predicate/assertion // we are waiting for happen to already be true?" while (!p()) // "p" is any expression (e.g. variable or // function-call) that checks the condition and // evaluates to boolean. This itself is a critical // section, so you *MUST* be holding the lock when // executing this "while" loop condition! // If this is not the first time the "while" condition is being checked, // then we are asking the question, "Now that another thread using this // monitor has notified me and woken me up and I have been context-switched // back to, did the condition/predicate/assertion we are waiting on stay // true between the time that I was woken up and the time that I re-acquired // the lock inside the "wait" call in the last iteration of this loop, or // did some other thread cause the condition to become false again in the // meantime thus making this a spurious wakeup? // The condition we are waiting for is true! // We are still holding the lock, either from before entering the monitor or from // the last execution of "wait". // Critical section of code goes here, which has a precondition that our predicate // must be true. // This code might make cv's condition false, and/or make other condition variables' // predicates true. // Call signal or broadcast, depending on which condition variables' // predicates (who share mutex m) have been made true or may have been made true, // and the monitor semantic type being used. for (cv_x in cvs_to_signal) // One or more threads have been woken up but will block as soon as they try // to acquire m. // Release the mutex so that notified thread(s) and others can enter their critical // sections. release(m);


Solving the bounded producer/consumer problem

Having introduced the usage of condition variables, let us use it to revisit and solve the classic bounded producer/consumer problem. The classic solution is to use two monitors, comprising two condition variables sharing one lock on the queue: global volatile RingBuffer queue; // A thread-unsafe ring-buffer of tasks. global Lock queueLock; // A mutex for the ring-buffer of tasks. (Not a spin-lock.) global CV queueEmptyCV; // A condition variable for consumer threads waiting for the queue to // become non-empty. Its associated lock is "queueLock". global CV queueFullCV; // A condition variable for producer threads waiting for the queue to // become non-full. Its associated lock is also "queueLock". // Method representing each producer thread's behavior: public method producer() // Method representing each consumer thread's behavior: public method consumer() This ensures concurrency between the producer and consumer threads sharing the task queue, and blocks the threads that have nothing to do rather than busy-waiting as shown in the aforementioned approach using spin-locks. A variant of this solution could use a single condition variable for both producers and consumers, perhaps named "queueFullOrEmptyCV" or "queueSizeChangedCV". In this case, more than one condition is associated with the condition variable, such that the condition variable represents a weaker condition than the conditions being checked by individual threads. The condition variable represents threads that are waiting for the queue to be non-full ''and'' ones waiting for it to be non-empty. However, doing this would require using ''broadcast'' in all the threads using the condition variable and cannot use a regular ''signal''. This is because the regular ''signal'' might wake up a thread of the wrong type whose condition has not yet been met, and that thread would go back to sleep without a thread of the correct type getting signaled. For example, a producer might make the queue full and wake up another producer instead of a consumer, and the woken producer would go back to sleep. In the complementary case, a consumer might make the queue empty and wake up another consumer instead of a producer, and the consumer would go back to sleep. Using ''broadcast'' ensures that some thread of the right type will proceed as expected by the problem statement. Here is the variant using only one condition variable and broadcast: global volatile RingBuffer queue; // A thread-unsafe ring-buffer of tasks. global Lock queueLock; // A mutex for the ring-buffer of tasks. (Not a spin-lock.) global CV queueFullOrEmptyCV; // A single condition variable for when the queue is not ready for any thread // i.e. for producer threads waiting for the queue to become non-full // and consumer threads waiting for the queue to become non-empty. // Its associated lock is "queueLock". // Not safe to use regular "signal" because it is associated with // multiple predicate conditions (assertions). // Method representing each producer thread's behavior: public method producer() // Method representing each consumer thread's behavior: public method consumer()


Synchronization primitives

Implementing mutexes and condition variables requires some kind of synchronization primitive provided by hardware support that provides atomicity. Locks and condition variables are higher-level abstractions over these synchronization primitives. On a uniprocessor, disabling and enabling interrupts is a way to implement monitors by preventing context switches during the critical sections of the locks and condition variables, but this is not enough on a multiprocessor. On a multiprocessor, usually special atomic read-modify-write instructions on the memory such as test-and-set,
compare-and-swap In computer science, compare-and-swap (CAS) is an atomic instruction used in multithreading to achieve synchronization. It compares the contents of a memory location with a given value and, only if they are the same, modifies the contents of tha ...
, etc. are used, depending on what the
instruction set architecture In computer science, an instruction set architecture (ISA), also called computer architecture, is an abstract model of a computer. A device that executes instructions described by that ISA, such as a central processing unit (CPU), is called an ...
provides. These usually require deferring to spin-locking for the internal lock state itself, but this locking is very brief. Depending on the implementation, the atomic read-modify-write instructions may lock the bus from other cores' accesses and/or prevent re-ordering of instructions in the CPU. Here is an example pseudocode implementation of parts of a threading system and mutexes and Mesa-style condition variables, using test-and-set and a first-come, first-served policy. This glosses over most of how a threading system works, but shows the parts relevant to mutexes and condition variables:


Sample Mesa-monitor implementation with Test-and-Set

// Basic parts of threading system: // Assume "ThreadQueue" supports random access. public volatile ThreadQueue readyQueue; // Thread-unsafe queue of ready threads. Elements are (Thread*). public volatile global Thread* currentThread; // Assume this variable is per-core. (Others are shared.) // Implements a spin-lock on just the synchronized state of the threading system itself. // This is used with test-and-set as the synchronization primitive. public volatile global bool threadingSystemBusy = false; // Context-switch interrupt service routine (ISR): // On the current CPU core, preemptively switch to another thread. public method contextSwitchISR() // Thread sleep method: // On current CPU core, a synchronous context switch to another thread without putting // the current thread on the ready queue. // Must be holding "threadingSystemBusy" and disabled interrupts so that this method // doesn't get interrupted by the thread-switching timer which would call contextSwitchISR(). // After returning from this method, must clear "threadingSystemBusy". public method threadSleep() public method wait(Mutex m, ConditionVariable c) public method signal(ConditionVariable c) public method broadcast(ConditionVariable c) class Mutex struct ConditionVariable


Semaphore

As an example, consider a thread-safe class that implements a
semaphore Semaphore (; ) is the use of an apparatus to create a visual signal transmitted over distance. A semaphore can be performed with devices including: fire, lights, flags, sunlight, and moving arms. Semaphores can be used for telegraphy when arr ...
. There are methods to increment (V) and to decrement (P) a private integer s. However, the integer must never be decremented below 0; thus a thread that tries to decrement must wait until the integer is positive. We use a condition variable sIsPositive with an associated assertion of P_\mathtt = (s > 0). monitor class ''Semaphore'' Implemented showing all synchronization (removing the assumption of a thread-safe class and showing the mutex): class ''Semaphore''


Monitor implemented using semaphores

Conversely, locks and condition variables can also be derived from semaphores, thus making monitors and semaphores reducible to one another: The implementation given here is incorrect. If a thread calls wait() after broadcast() has been called, an originally thread may be stuck indefinitely, since broadcast() increments the semaphore only enough times for threads already waiting. public method wait(Mutex m, ConditionVariable c) public method signal(ConditionVariable c) public method broadcast(ConditionVariable c) class Mutex class ConditionVariable When a signal happens on a condition variable that at least one other thread is waiting on, there are at least two threads that could then occupy the monitor: the thread that signals and any one of the threads that is waiting. In order that at most one thread occupies the monitor at each time, a choice must be made. Two schools of thought exist on how best to resolve this choice. This leads to two kinds of condition variables which will be examined next: * ''Blocking condition variables'' give priority to a signaled thread. * ''Nonblocking condition variables'' give priority to the signaling thread.


Blocking condition variables

The original proposals by
C. A. R. Hoare Sir Charles Antony Richard Hoare (Tony Hoare or C. A. R. Hoare) (born 11 January 1934) is a British computer scientist who has made foundational contributions to programming languages, algorithms, operating systems, formal verification, and c ...
and Per Brinch Hansen were for ''blocking condition variables''. With a blocking condition variable, the signaling thread must wait outside the monitor (at least) until the signaled thread relinquishes occupancy of the monitor by either returning or by again waiting on a condition variable. Monitors using blocking condition variables are often called ''Hoare-style'' monitors or ''signal-and-urgent-wait'' monitors. We assume there are two queues of threads associated with each monitor object * e is the entrance queue * s is a queue of threads that have signaled. In addition we assume that for each condition variable , there is a queue * .q, which is a queue for threads waiting on condition variable All queues are typically guaranteed to be
fair A fair (archaic: faire or fayre) is a gathering of people for a variety of entertainment or commercial activities. Fairs are typically temporary with scheduled times lasting from an afternoon to several weeks. Types Variations of fairs incl ...
and, in some implementations, may be guaranteed to be first in first out. The implementation of each operation is as follows. (We assume that each operation runs in mutual exclusion to the others; thus restarted threads do not begin executing until the operation is complete.) enter the monitor: enter the method if the monitor is locked add this thread to e block this thread else lock the monitor leave the monitor: schedule return from the method wait : add this thread to .q schedule block this thread signal : if there is a thread waiting on .q select and remove one such thread t from .q (t is called "the signaled thread") add this thread to s restart t (so t will occupy the monitor next) block this thread schedule: if there is a thread on s select and remove one thread from s and restart it (this thread will occupy the monitor next) else if there is a thread on e select and remove one thread from e and restart it (this thread will occupy the monitor next) else unlock the monitor (the monitor will become unoccupied) The schedule routine selects the next thread to occupy the monitor or, in the absence of any candidate threads, unlocks the monitor. The resulting signaling discipline is known as ''"signal and urgent wait,"'' as the signaler must wait, but is given priority over threads on the entrance queue. An alternative is ''"signal and wait,"'' in which there is no s queue and signaler waits on the e queue instead. Some implementations provide a signal and return operation that combines signaling with returning from a procedure. signal and return: if there is a thread waiting on .q select and remove one such thread t from .q (t is called "the signaled thread") restart t (so t will occupy the monitor next) else schedule return from the method In either case ("signal and urgent wait" or "signal and wait"), when a condition variable is signaled and there is at least one thread waiting on the condition variable, the signaling thread hands occupancy over to the signaled thread seamlessly, so that no other thread can gain occupancy in between. If is true at the start of each signal operation, it will be true at the end of each wait operation. This is summarized by the following
contracts A contract is a legally enforceable agreement between two or more parties that creates, defines, and governs mutual rights and obligations between them. A contract typically involves the transfer of goods, services, money, or a promise to tr ...
. In these contracts, is the monitor's invariant. enter the monitor: postcondition leave the monitor: precondition wait : precondition modifies the state of the monitor postcondition and signal : precondition and modifies the state of the monitor postcondition signal and return: precondition and In these contracts, it is assumed that and do not depend on the contents or lengths of any queues. (When the condition variable can be queried as to the number of threads waiting on its queue, more sophisticated contracts can be given. For example, a useful pair of contracts, allowing occupancy to be passed without establishing the invariant, is: wait : precondition modifies the state of the monitor postcondition signal precondition (not empty() and ) or (empty() and ) modifies the state of the monitor postcondition (See Howard and Buhr ''et al.'' for more.) It is important to note here that the assertion is entirely up to the programmer; he or she simply needs to be consistent about what it is. We conclude this section with an example of a thread-safe class using a blocking monitor that implements a bounded,
thread-safe Thread safety is a computer programming concept applicable to multi-threaded code. Thread-safe code only manipulates shared data structures in a manner that ensures that all threads behave properly and fulfill their design specifications without un ...
stack Stack may refer to: Places * Stack Island, an island game reserve in Bass Strait, south-eastern Australia, in Tasmania’s Hunter Island Group * Blue Stack Mountains, in Co. Donegal, Ireland People * Stack (surname) (including a list of people ...
. monitor class ''SharedStack'' Note that, in this example, the thread-safe stack is internally providing a mutex, which, as in the earlier producer/consumer example, is shared by both condition variables, which are checking different conditions on the same concurrent data. The only difference is that the producer/consumer example assumed a regular non-thread-safe queue and was using a standalone mutex and condition variables, without these details of the monitor abstracted away as is the case here. In this example, when the "wait" operation is called, it must somehow be supplied with the thread-safe stack's mutex, such as if the "wait" operation is an integrated part of the "monitor class". Aside from this kind of abstracted functionality, when a "raw" monitor is used, it will ''always'' have to include a mutex and a condition variable, with a unique mutex for each condition variable.


Nonblocking condition variables

With ''nonblocking condition variables'' (also called ''"Mesa style"'' condition variables or ''"signal and continue"'' condition variables), signaling does not cause the signaling thread to lose occupancy of the monitor. Instead the signaled threads are moved to the e queue. There is no need for the s queue. With nonblocking condition variables, the signal operation is often called notify — a terminology we will follow here. It is also common to provide a notify all operation that moves all threads waiting on a condition variable to the e queue. The meaning of various operations are given here. (We assume that each operation runs in mutual exclusion to the others; thus restarted threads do not begin executing until the operation is complete.) enter the monitor: enter the method if the monitor is locked add this thread to e block this thread else lock the monitor leave the monitor: schedule return from the method wait : add this thread to .q schedule block this thread notify : if there is a thread waiting on .q select and remove one thread t from .q (t is called "the notified thread") move t to e notify all : move all threads waiting on .q to e schedule : if there is a thread on e select and remove one thread from e and restart it else unlock the monitor As a variation on this scheme, the notified thread may be moved to a queue called w, which has priority over e. See Howard and Buhr ''et al.'' for further discussion. It is possible to associate an assertion with each condition variable such that is sure to be true upon return from wait . However, one must ensure that is preserved from the time the notifying thread gives up occupancy until the notified thread is selected to re-enter the monitor. Between these times there could be activity by other occupants. Thus it is common for to simply be ''true''. For this reason, it is usually necessary to enclose each wait operation in a loop like this while not ( ) do wait c where is some condition stronger than . The operations notify and notify all are treated as "hints" that may be true for some waiting thread. Every iteration of such a loop past the first represents a lost notification; thus with nonblocking monitors, one must be careful to ensure that too many notifications cannot be lost. As an example of "hinting," consider a bank account in which a withdrawing thread will wait until the account has sufficient funds before proceeding monitor class ''Account'' In this example, the condition being waited for is a function of the amount to be withdrawn, so it is impossible for a depositing thread to ''know'' that it made such a condition true. It makes sense in this case to allow each waiting thread into the monitor (one at a time) to check if its assertion is true.


Implicit condition variable monitors

In the
Java Java (; id, Jawa, ; jv, ꦗꦮ; su, ) is one of the Greater Sunda Islands in Indonesia. It is bordered by the Indian Ocean to the south and the Java Sea to the north. With a population of 151.6 million people, Java is the world's mo ...
language, each object may be used as a monitor. Methods requiring mutual exclusion must be explicitly marked with the synchronized keyword. Blocks of code may also be marked by synchronized. Rather than having explicit condition variables, each monitor (i.e., object) is equipped with a single wait queue in addition to its entrance queue. All waiting is done on this single wait queue and all notify and notifyAll operations apply to this queue. This approach has been adopted in other languages, for example C#.


Implicit signaling

Another approach to signaling is to omit the signal operation. Whenever a thread leaves the monitor (by returning or waiting), the assertions of all waiting threads are evaluated until one is found to be true. In such a system, condition variables are not needed, but the assertions must be explicitly coded. The contract for wait is wait : precondition modifies the state of the monitor postcondition and


History

Brinch Hansen and Hoare developed the monitor concept in the early 1970s, based on earlier ideas of their own and of
Edsger Dijkstra Edsger Wybe Dijkstra ( ; ; 11 May 1930 – 6 August 2002) was a Dutch computer scientist, programmer, software engineer, systems scientist, and science essayist. He received the 1972 Turing Award for fundamental contributions to developing progra ...
. Brinch Hansen published the first monitor notation, adopting the
class Class or The Class may refer to: Common uses not otherwise categorized * Class (biology), a taxonomic rank * Class (knowledge representation), a collection of individuals or objects * Class (philosophy), an analytical concept used differently ...
concept of
Simula 67 Simula is the name of two simulation programming languages, Simula I and Simula 67, developed in the 1960s at the Norwegian Computing Center in Oslo, by Ole-Johan Dahl and Kristen Nygaard. Syntactically, it is an approximate superset of ALG ...
, and invented a queueing mechanism. Hoare refined the rules of process resumption. Brinch Hansen created the first implementation of monitors, in
Concurrent Pascal Concurrent Pascal is a programming language designed by Per Brinch Hansen for writing concurrent computing programs such as operating systems and real-time computing monitoring systems on shared memory computers. A separate language, ''Seque ...
. Hoare demonstrated their equivalence to semaphores. Monitors (and Concurrent Pascal) were soon used to structure process synchronization in the
Solo operating system Solo or SOLO may refer to: Arts and entertainment Comics * ''Solo'' (DC Comics), a DC comics series * Solo, a 1996 mini-series from Dark Horse Comics Characters * Han Solo, a ''Star Wars'' character * Jacen Solo, a Jedi in the non-canonical ''S ...
. Programming languages that have supported monitors include: *
Ada Ada may refer to: Places Africa * Ada Foah, a town in Ghana * Ada (Ghana parliament constituency) * Ada, Osun, a town in Nigeria Asia * Ada, Urmia, a village in West Azerbaijan Province, Iran * Ada, Karaman, a village in Karaman Province, T ...
since Ada 95 (as protected objects) * C# (and other languages that use the
.NET Framework The .NET Framework (pronounced as "''dot net"'') is a proprietary software framework developed by Microsoft that runs primarily on Microsoft Windows. It was the predominant implementation of the Common Language Infrastructure (CLI) until bein ...
) * Concurrent Euclid *
Concurrent Pascal Concurrent Pascal is a programming language designed by Per Brinch Hansen for writing concurrent computing programs such as operating systems and real-time computing monitoring systems on shared memory computers. A separate language, ''Seque ...
* D *
Delphi Delphi (; ), in legend previously called Pytho (Πυθώ), in ancient times was a sacred precinct that served as the seat of Pythia, the major oracle who was consulted about important decisions throughout the ancient classical world. The orac ...
(Delphi 2009 and above, via TObject.Monitor) *
Java Java (; id, Jawa, ; jv, ꦗꦮ; su, ) is one of the Greater Sunda Islands in Indonesia. It is bordered by the Indian Ocean to the south and the Java Sea to the north. With a population of 151.6 million people, Java is the world's mo ...
(via the wait and notify methods) * Go *
Mesa A mesa is an isolated, flat-topped elevation, ridge or hill, which is bounded from all sides by steep escarpments and stands distinctly above a surrounding plain. Mesas characteristically consist of flat-lying soft sedimentary rocks capped by a ...
*
Modula-3 Modula-3 is a programming language conceived as a successor to an upgraded version of Modula-2 known as Modula-2+. While it has been influential in research circles (influencing the designs of languages such as Java, C#, and Python) it has not ...
* Python (vi
threading.Condition
object) *
Ruby A ruby is a pinkish red to blood-red colored gemstone, a variety of the mineral corundum ( aluminium oxide). Ruby is one of the most popular traditional jewelry gems and is very durable. Other varieties of gem-quality corundum are called ...
*
Squeak Squeak is an object-oriented, class-based, and reflective programming language. It was derived from Smalltalk-80 by a group that included some of Smalltalk-80's original developers, initially at Apple Computer, then at Walt Disney Imagineering, ...
Smalltalk *
Turing Alan Mathison Turing (; 23 June 1912 – 7 June 1954) was an English mathematician, computer scientist, logician, cryptanalyst, philosopher, and theoretical biologist. Turing was highly influential in the development of theoretical co ...
, Turing+, and Object-Oriented Turing * µC++ * Visual Prolog A number of libraries have been written that allow monitors to be constructed in languages that do not support them natively. When library calls are used, it is up to the programmer to explicitly mark the start and end of code executed with mutual exclusion.
Pthreads POSIX Threads, commonly known as pthreads, is an execution model that exists independently from a language, as well as a parallel execution model. It allows a program to control multiple different flows of work that overlap in time. Each flow o ...
is one such library.


See also

*
Mutual exclusion In computer science, mutual exclusion is a property of concurrency control, which is instituted for the purpose of preventing race conditions. It is the requirement that one thread of execution never enters a critical section while a concurren ...
*
Communicating sequential processes In computer science, communicating sequential processes (CSP) is a formal language for describing patterns of interaction in concurrent systems. It is a member of the family of mathematical theories of concurrency known as process algebras, or ...
- a later development of monitors by
C. A. R. Hoare Sir Charles Antony Richard Hoare (Tony Hoare or C. A. R. Hoare) (born 11 January 1934) is a British computer scientist who has made foundational contributions to programming languages, algorithms, operating systems, formal verification, and c ...
*
Semaphore (programming) In computer science, a semaphore is a variable or abstract data type used to control access to a common resource by multiple threads and avoid critical section problems in a concurrent system such as a multitasking operating system. Semaph ...


Notes


Further reading

* Monitors: an operating system structuring concept, C. A. R. Hoare –
Communications of the ACM ''Communications of the ACM'' is the monthly journal of the Association for Computing Machinery (ACM). It was established in 1958, with Saul Rosen as its first managing editor. It is sent to all ACM members. Articles are intended for readers wi ...
, v.17 n.10, p. 549–557, Oct. 197

* Monitor classification P.A. Buhr, M. Fortier, M.H. Coffin –
ACM Computing Surveys ''ACM Computing Surveys'' is a quarterly peer-reviewed scientific journal published by the Association for Computing Machinery. It publishes survey articles and tutorials related to computer science and computing. The journal was established in 1 ...
, 199


External links


Java Monitors (lucid explanation)
*
Monitors: An Operating System Structuring Concept
by
C. A. R. Hoare Sir Charles Antony Richard Hoare (Tony Hoare or C. A. R. Hoare) (born 11 January 1934) is a British computer scientist who has made foundational contributions to programming languages, algorithms, operating systems, formal verification, and c ...
*
Signalling in Monitors
by
John H. Howard (computer scientist) John is a common English name and surname: * John (given name) * John (surname) John may also refer to: New Testament Works * Gospel of John, a title often shortened to John * First Epistle of John, often shortened to 1 John * Seco ...
*
Proving Monitors
by
John H. Howard (computer scientist) John is a common English name and surname: * John (given name) * John (surname) John may also refer to: New Testament Works * Gospel of John, a title often shortened to John * First Epistle of John, often shortened to 1 John * Seco ...
*
Experience with Processes and Monitors in Mesa
by
Butler W. Lampson Butler W. Lampson, ForMemRS, (born December 23, 1943) is an American computer scientist best known for his contributions to the development and implementation of distributed personal computing. Education and early life After graduating from th ...
and
David D. Redell David (; , "beloved one") (traditional spelling), , ''Dāwūd''; grc-koi, Δαυΐδ, Dauíd; la, Davidus, David; gez , ዳዊት, ''Dawit''; xcl, Դաւիթ, ''Dawitʿ''; cu, Давíдъ, ''Davidŭ''; possibly meaning "beloved one". w ...

pthread_cond_wait
– description from the Open Group Base Specifications Issue 6, IEEE Std 1003.1 *

by
Dave Marshall (computer scientist) Dave Marshall or David Marshall may refer to: * David Marshall (Canadian politician) (1846–1920), member of the Canadian Parliament for Elgin East * David Marshall (Singaporean politician) (1908–1995), Chief Minister of Singapore * David Marsha ...
*
Strategies for Implementing POSIX Condition Variables on Win32
by Douglas C. Schmidt and Irfan Pyarali
Condition Variable Routines
from the Apache Portable Runtime Library
wxCondition description


* ttp://zthread.sourceforge.net/html/classZThread_1_1Condition.html ZThread Condition Class Reference
Wefts::Condition Class Reference










– Perl extension for sharing data structures between threads * http://msdn.microsoft.com/en-us/library/ms682052(VS.85).aspx
Monitors
in Visual Prolog. {{Design Patterns patterns Programming constructs Concurrency control Software design patterns