.gif)
Monitor (synchronization)
Encyclopedia
In concurrent programming
, a monitor is an object
or module intended to be used safely by more than one thread
. The defining characteristic of a monitor is that its methods are executed with mutual exclusion
. That is, at each point in time, at most one thread may be executing any of its methods
. This mutual exclusion greatly simplifies reasoning about the implementation of monitors compared to reasoning about parallel code that updates a data structure.
Monitors also 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. Monitors also have a mechanism for signaling other threads that such conditions have been met.
Monitors were invented by C. A. R. Hoare
and Per Brinch Hansen
,
and were first implemented in Brinch Hansen's
Concurrent Pascal
language.
monitor class Account {
private int balance := 0
invariant balance >= 0
public method boolean withdraw(int amount)
precondition amount >= 0
{
if balance < amount then return false
else { balance := balance - amount ; return true }
}
public method deposit(int amount)
precondition amount >= 0
{
balance := balance + amount
}
}
While a thread is executing a method of a monitor, it is said to occupy the monitor. Monitors
are implemented to enforce that at each point in time, at most one thread may occupy the monitor.
This is the monitor's mutual exclusion
property.
Upon calling one of the methods, a thread must wait until no other thread is executing any of the monitor'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.
In a simple implementation, mutual exclusion can be implemented by the compiler equipping each monitor object with a private lock, often in the form of a semaphore
. This lock, which is initially unlocked, is locked at the start of each public method, and is unlocked at each return from each public method.
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.
The solution is condition variables. Conceptually a condition variable is a queue of threads, associated with a monitor, 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 two main operations on condition variables:
As an example, consider a monitor that implements a semaphore
.
There are methods to increment (V) and to decrement (P) a private integer
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
.
monitor class Semaphore
{
private int s := 0
invariant s >= 0
private Condition sIsPositive /* associated with s > 0 */
public method P
{
if s = 0 then wait sIsPositive
assert s > 0
s := s - 1
}
public method V
{
s := s + 1
assert s > 0
signal sIsPositive
}
}
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:
and Per Brinch Hansen
were for blocking condition variables. Monitors using blocking condition variables are often called Hoare style monitors. 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.
-su.png)
We assume there are two queues of threads associated with each monitor object
In addition we assume that for each condition variable
, there is a queue
All queues are typically guaranteed to be fair (in all futures, each thread that enters the queue will be chosen infinitely often ) 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
or, in the absence of any candidate threads, unlocks the monitor.
The resulting signaling discipline is known a "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
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 on 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
. 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 blocking monitor that implements a bounded, thread safe stack
.
monitor class SharedStack {
private const capacity := 10
private int[capacity] A
private int size := 0
invariant 0 <= size and size <= capacity
private BlockingCondition theStackIsNotEmpty /* associated with 0 < size and size <= capacity */
private BlockingCondition theStackIsNotFull /* associated with 0 <= size and size < capacity */
public method push(int value)
{
if size = capacity then wait theStackIsNotFull
assert 0 <= size and size < capacity
A[size] := value ; size := size + 1
assert 0 < size and size <= capacity
signal theStackIsNotEmpty and return
}
public method int pop
{
if size = 0 then wait theStackIsNotEmpty
assert 0 < size and size <= capacity
size := size - 1 ;
assert 0 <= size and size < capacity
signal theStackIsNotFull and return A[size]
}
}
-mesa.png)
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
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
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
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 
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 can not 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 {
private int balance := 0
invariant balance >= 0
private NonblockingCondition balanceMayBeBigEnough
public method withdraw(int amount)
precondition amount >= 0
{
while balance < amount do wait balanceMayBeBigEnough
assert balance >= amount
balance := balance - amount
}
public method deposit(int amount)
precondition amount >= 0
{
balance := balance + amount
notify all balanceMayBeBigEnough
}
}
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.
-java.png)
In the Java
language, each object may be used as a monitor. (However, methods that require mutual exclusion must be explicitly marked as 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 notify all operations apply to this queue.
This approach has also been adopted in other languages such as C#.
wait
:
precondition
modifies the state of the monitor
postcondition
and 
and Per Brinch Hansen
developed the idea of monitors around 1972, based on earlier ideas of their own and of E. W. Dijkstra.
Brinch Hansen was the first to implement monitors. Hoare developed the theoretical framework and demonstrated their equivalence to semaphores
.
Monitors were soon used to structure inter-process communication
in the Solo operating system.
Programming languages that have supported monitors include
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
is one such library.
Concurrent computing
Concurrent computing is a form of computing in which programs are designed as collections of interacting computational processes that may be executed in parallel...
, a monitor is an object
Object (computer science)
In computer science, an object is any entity that can be manipulated by the commands of a programming language, such as a value, variable, function, or data structure...
or module intended to be used safely by more than one thread
Thread (computer science)
In computer science, a thread of execution is the smallest unit of processing that can be scheduled by an operating system. The implementation of threads and processes differs from one operating system to another, but in most cases, a thread is contained inside a process...
. The defining characteristic of a monitor is that its methods are executed with mutual exclusion
Mutual exclusion
Mutual exclusion algorithms are used in concurrent programming to avoid the simultaneous use of a common resource, such as a global variable, by pieces of computer code called critical sections. A critical section is a piece of code in which a process or thread accesses a common resource...
. That is, at each point in time, at most one thread may be executing any of its methods
Method (computer science)
In object-oriented programming, a method is a subroutine associated with a class. Methods define the behavior to be exhibited by instances of the associated class at program run time...
. This mutual exclusion greatly simplifies reasoning about the implementation of monitors compared to reasoning about parallel code that updates a data structure.
Monitors also 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. Monitors also have a mechanism for signaling other threads that such conditions have been met.
Monitors were invented by C. A. R. Hoare
C. A. R. Hoare
Sir Charles Antony Richard Hoare , commonly known as Tony Hoare or C. A. R. Hoare, is a British computer scientist best known for the development of Quicksort, one of the world's most widely used sorting algorithms...
and Per Brinch Hansen
Per Brinch Hansen
Per Brinch Hansen was a Danish-American computer scientist known for concurrent programming theory.-Biography:He was born in Frederiksberg, in Copenhagen, Denmark....
,
and were first implemented in Brinch Hansen's
Per Brinch Hansen
Per Brinch Hansen was a Danish-American computer scientist known for concurrent programming theory.-Biography:He was born in Frederiksberg, in Copenhagen, Denmark....
Concurrent Pascal
Concurrent Pascal
Concurrent Pascal was designed by Per Brinch Hansen for writing concurrent computing programs such asoperating systems and real-time monitoring systems on shared memorycomputers....
language.
Mutual exclusion
As a simple example, consider a monitor for performing transactions on a bank account.monitor class Account {
private int balance := 0
invariant balance >= 0
public method boolean withdraw(int amount)
precondition amount >= 0
{
if balance < amount then return false
else { balance := balance - amount ; return true }
}
public method deposit(int amount)
precondition amount >= 0
{
balance := balance + amount
}
}
While a thread is executing a method of a monitor, it is said to occupy the monitor. Monitors
are implemented to enforce that at each point in time, at most one thread may occupy the monitor.
This is the monitor's mutual exclusion
Mutual exclusion
Mutual exclusion algorithms are used in concurrent programming to avoid the simultaneous use of a common resource, such as a global variable, by pieces of computer code called critical sections. A critical section is a piece of code in which a process or thread accesses a common resource...
property.
Upon calling one of the methods, a thread must wait until no other thread is executing any of the monitor'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.
In a simple implementation, mutual exclusion can be implemented by the compiler equipping each monitor object with a private lock, often in the form of a semaphore
Semaphore (programming)
In computer science, a semaphore is a variable or abstract data type that provides a simple but useful abstraction for controlling access by multiple processes to a common resource in a parallel programming environment....
. This lock, which is initially unlocked, is locked at the start of each public method, and is unlocked at each return from each public method.
Waiting and signaling
For many applications, mutual exclusion is not enough. Threads attempting an operation may need to wait until some condition holds true. A busy waitingBusy waiting
In software engineering, busy-waiting or spinning is a technique in which a process repeatedly checks to see if a condition is true, such as whether keyboard input is available, or if a lock is available. Spinning can also be used to generate an arbitrary time delay, a technique that was necessary...
loop
while not(
) do skipwill not work, as mutual exclusion will prevent any other thread from entering the monitor to make the condition true.
The solution is condition variables. Conceptually a condition variable is a queue of threads, associated with a monitor, on which a thread may wait for some condition to become true. Thus each condition variable
is associated with an assertionAssertion (computing)
In computer programming, an assertion is a predicate placed in a program to indicate that the developer thinks that the predicate is always true at that place.For example, the following code contains two assertions:...
. 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 two main operations on condition variables:
-
wait cis 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. -
signal c(sometimes written asnotify c) is called by a thread to indicate that the assertion
is true.
As an example, consider a monitor that implements a semaphore
Semaphore (programming)
In computer science, a semaphore is a variable or abstract data type that provides a simple but useful abstraction for controlling access by multiple processes to a common resource in a parallel programming environment....
.
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.monitor class Semaphore
{
private int s := 0
invariant s >= 0
private Condition sIsPositive /* associated with s > 0 */
public method P
{
if s = 0 then wait sIsPositive
assert s > 0
s := s - 1
}
public method V
{
s := s + 1
assert s > 0
signal sIsPositive
}
}
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 or Signal and Wait give priority to a signaled thread.
- Nonblocking condition variables or Signal and Continue give priority to the signaling thread.
Blocking condition variables
The original proposals by C. A. R. HoareC. A. R. Hoare
Sir Charles Antony Richard Hoare , commonly known as Tony Hoare or C. A. R. Hoare, is a British computer scientist best known for the development of Quicksort, one of the world's most widely used sorting algorithms...
and Per Brinch Hansen
Per Brinch Hansen
Per Brinch Hansen was a Danish-American computer scientist known for concurrent programming theory.-Biography:He was born in Frederiksberg, in Copenhagen, Denmark....
were for blocking condition variables. Monitors using blocking condition variables are often called Hoare style monitors. 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.
-
eis the entrance queue -
sis a queue of threads that have signaled.
In addition we assume that for each condition variable
, there is a queue
-
.q
All queues are typically guaranteed to be fair (in all futures, each thread that enters the queue will be chosen infinitely often ) 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
.qschedule
block this thread
signal
:if there is a thread waiting on
.qselect 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 monitoror, in the absence of any candidate threads, unlocks the monitor.
The resulting signaling discipline is known a "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
.qselect 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 on 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 contractsDesign by contract
Design by contract , also known as programming by contract and design-by-contract programming, is an approach to designing computer software...
. In these contracts,
is the monitor's invariantInvariant (computer science)
In computer science, a predicate is called an invariant to a sequence of operations provided that: if the predicate is true before starting the sequence, then it is true at the end of the sequence.-Use:...
.
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 thecontents 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 blocking monitor that implements a bounded, thread safe stack
Stack (data structure)
In computer science, a stack is a last in, first out abstract data type and linear data structure. A stack can have any abstract data type as an element, but is characterized by only three fundamental operations: push, pop and stack top. The push operation adds a new item to the top of the stack,...
.
monitor class SharedStack {
private const capacity := 10
private int[capacity] A
private int size := 0
invariant 0 <= size and size <= capacity
private BlockingCondition theStackIsNotEmpty /* associated with 0 < size and size <= capacity */
private BlockingCondition theStackIsNotFull /* associated with 0 <= size and size < capacity */
public method push(int value)
{
if size = capacity then wait theStackIsNotFull
assert 0 <= size and size < capacity
A[size] := value ; size := size + 1
assert 0 < size and size <= capacity
signal theStackIsNotEmpty and return
}
public method int pop
{
if size = 0 then wait theStackIsNotEmpty
assert 0 < size and size <= capacity
size := size - 1 ;
assert 0 <= size and size < capacity
signal theStackIsNotFull and return A[size]
}
}
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 thee queue. There is no need for the s queue.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
.qschedule
block this thread
notify
:if there is a thread waiting on
.qselect 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 eschedule :
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. SeeHoward
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 mustensure 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 cwhere
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 can not 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 {
private int balance := 0
invariant balance >= 0
private NonblockingCondition balanceMayBeBigEnough
public method withdraw(int amount)
precondition amount >= 0
{
while balance < amount do wait balanceMayBeBigEnough
assert balance >= amount
balance := balance - amount
}
public method deposit(int amount)
precondition amount >= 0
{
balance := balance + amount
notify all balanceMayBeBigEnough
}
}
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
Java (programming language)
Java is a programming language originally developed by James Gosling at Sun Microsystems and released in 1995 as a core component of Sun Microsystems' Java platform. The language derives much of its syntax from C and C++ but has a simpler object model and fewer low-level facilities...
language, each object may be used as a monitor. (However, methods that require mutual exclusion must be explicitly marked as 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 notify all operations apply to this queue.
This approach has also been adopted in other languages such as 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 iswait
:precondition
modifies the state of the monitor
postcondition
and History
C. A. R. HoareC. A. R. Hoare
Sir Charles Antony Richard Hoare , commonly known as Tony Hoare or C. A. R. Hoare, is a British computer scientist best known for the development of Quicksort, one of the world's most widely used sorting algorithms...
and Per Brinch Hansen
Per Brinch Hansen
Per Brinch Hansen was a Danish-American computer scientist known for concurrent programming theory.-Biography:He was born in Frederiksberg, in Copenhagen, Denmark....
developed the idea of monitors around 1972, based on earlier ideas of their own and of E. W. Dijkstra.
Brinch Hansen was the first to implement monitors. Hoare developed the theoretical framework and demonstrated their equivalence to semaphores
Semaphore (programming)
In computer science, a semaphore is a variable or abstract data type that provides a simple but useful abstraction for controlling access by multiple processes to a common resource in a parallel programming environment....
.
Monitors were soon used to structure inter-process communication
Inter-process communication
In computing, Inter-process communication is a set of methods for the exchange of data among multiple threads in one or more processes. Processes may be running on one or more computers connected by a network. IPC methods are divided into methods for message passing, synchronization, shared...
in the Solo operating system.
Programming languages that have supported monitors include
- AdaAda (programming language)Ada is a structured, statically typed, imperative, wide-spectrum, and object-oriented high-level computer programming language, extended from Pascal and other languages...
since Ada 95 (as protected objects) - C# (and other languages that use the .NET Framework.NET FrameworkThe .NET Framework is a software framework that runs primarily on Microsoft Windows. It includes a large library and supports several programming languages which allows language interoperability...
) - Concurrent Euclid
- Concurrent PascalConcurrent PascalConcurrent Pascal was designed by Per Brinch Hansen for writing concurrent computing programs such asoperating systems and real-time monitoring systems on shared memorycomputers....
- DD (programming language)The D programming language is an object-oriented, imperative, multi-paradigm, system programming language created by Walter Bright of Digital Mars. It originated as a re-engineering of C++, but even though it is mainly influenced by that language, it is not a variant of C++...
- Delphi (Delphi 2009 and above, via TObject.Monitor)
- JavaJava (programming language)Java is a programming language originally developed by James Gosling at Sun Microsystems and released in 1995 as a core component of Sun Microsystems' Java platform. The language derives much of its syntax from C and C++ but has a simpler object model and fewer low-level facilities...
(via the wait and notify methods) - Mesa
- Modula-3Modula-3In computer science, 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 it has not been adopted widely in industry...
- PythonPython (programming language)Python is a general-purpose, high-level programming language whose design philosophy emphasizes code readability. Python claims to "[combine] remarkable power with very clear syntax", and its standard library is large and comprehensive...
(via threading.Condition object) - RubyRuby (programming language)Ruby is a dynamic, reflective, general-purpose object-oriented programming language that combines syntax inspired by Perl with Smalltalk-like features. Ruby originated in Japan during the mid-1990s and was first developed and designed by Yukihiro "Matz" Matsumoto...
- SqueakSqueakThe Squeak programming language is a Smalltalk implementation. It is object-oriented, class-based and reflective.It was derived directly from Smalltalk-80 by a group at Apple Computer that included some of the original Smalltalk-80 developers...
Smalltalk - Turing, Turing+, and Object-Oriented TuringObject-Oriented TuringObject-Oriented Turing is an extension of the Turing programming language and a replacement for Turing Plus created by Ric Holt of the University of Toronto in 1991. It is imperative, object-oriented, and concurrent...
- μC++
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
POSIX Threads, usually referred to as Pthreads, is a POSIX standard for threads. The standard, POSIX.1c, Threads extensions , defines an API for creating and manipulating threads....
is one such library.
See also
- Mutual exclusionMutual exclusionMutual exclusion algorithms are used in concurrent programming to avoid the simultaneous use of a common resource, such as a global variable, by pieces of computer code called critical sections. A critical section is a piece of code in which a process or thread accesses a common resource...
- Communicating sequential processesCommunicating sequential processesIn computer science, Communicating Sequential Processes 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 process calculi...
- a later development of monitors by C. A. R. HoareC. A. R. HoareSir Charles Antony Richard Hoare , commonly known as Tony Hoare or C. A. R. Hoare, is a British computer scientist best known for the development of Quicksort, one of the world's most widely used sorting algorithms... - Semaphore (programming)Semaphore (programming)In computer science, a semaphore is a variable or abstract data type that provides a simple but useful abstraction for controlling access by multiple processes to a common resource in a parallel programming environment....
External links
- Java Monitors (lucid explanation)
- "Monitors: An Operating System Structuring Concept" by C. A. R. HoareC. A. R. HoareSir Charles Antony Richard Hoare , commonly known as Tony Hoare or C. A. R. Hoare, is a British computer scientist best known for the development of Quicksort, one of the world's most widely used sorting algorithms...
- "Signalling in Monitors" by John H. Howard (computer scientist)
- "Proving Monitors" by John H. Howard (computer scientist)
- "Experience with Processes and Monitors in Mesa" by Butler W. Lampson and David D. Redell
- pthread_cond_wait – description from the Open Group Base Specifications Issue 6, IEEE Std 1003.1
- "Block on a Condition Variable" by Dave Marshall (computer scientist)
- "Strategies for Implementing POSIX Condition Variables on Win32" by Douglas C. SchmidtDouglas C. SchmidtDouglas C. Schmidt is a computer scientist and author known for his works in the fields of object-oriented programming, distributed computing and design patterns. Currently he is working as Associate Chair of Computer Science and Engineering and Professor of Computer Science in Vanderbilt University...
and Irfan Pyarali - Condition Variable Routines from the Apache Portable RuntimeApache Portable RuntimeThe Apache Portable Runtime is a supporting library for the Apache web server. It provides a set of APIs that map to the underlying operating system . Where the OS doesn't support a particular function, APR will provide an emulation...
Library - wxCondition description
- Boost Condition Variables Reference
- ZThread Condition Class Reference
- Wefts::Condition Class Reference
- ACE_Condition Class Template Reference
- QWaitCondition Class Reference
- Common C++ Conditional Class Reference
- at::ConditionalMutex Class Reference
- threads::shared – Perl extension for sharing data structures between threads
- Tutorial multiprocessing traps
- http://msdn.microsoft.com/en-us/library/ms682052(VS.85).aspx
- Monitors in Visual PrologVisual PrologVisual Prolog, also formerly known as PDC Prolog and Turbo Prolog, is a strongly typed object-oriented extension of Prolog. As Turbo Prolog it was marketed by Borland, but it is now developed and marketed by the Danish firm Prolog Development Center that originally developed it...
.