Monitor (synchronization)

Encyclopedia : M : MO : MON : Monitor (synchronization)

A monitor is an approach to synchronizing two or more computer tasks that use a shared resource, usually a hardware device or a set of variables.

Contents

1 Mutual exclusion
2 Condition variables
3 History
4 External links

Mutual exclusion

A monitor consists of:

a set of procedures that allow interaction with the shared resource
a mutual exclusion lock
the variables associated with the resource
a monitor invariant that defines the assumptions needed to avoid race conditions

A monitor procedure takes the lock before doing anything else, and holds it until it either finishes or waits for a condition (explained below). If every procedure guarantees that the invariant is true before it releases the lock, then no task can ever find the resource in a state that might lead to a race condition.

As a simple example, consider a monitor for performing transactions on a bank account.

monitor account 

function deposit(int amount) 
}

The monitor invariant in this case simply says that the balance must reflect all past operations before another operation can begin. It is usually not stated in the code but may be mentioned in comments. There are however programming languages like Eiffel, which can check invariants. The lock is added by the compiler. This makes monitors safer and more reliable than approaches that require the programmer to insert locking and unlocking operations by hand, since the programmer can forget them.

Condition variables

To avoid entering a busy waiting state, processes must be able to signal each other about events of interest. Monitors provide this capability through condition variables. When a monitor function requires a particular condition to be true before it can proceed, it waits on an associated condition variable. By waiting, it gives up the lock and is removed from the set of runnable processes. Any process that subsequently causes the condition to be true may then use the condition variable to notify a process waiting for the condition. A process that has been notified regains the lock and can proceed.

The following monitor uses condition variables to implement an interprocess communication channel that can store only one integer value at a time.

monitor channel 

function receive() 
}

Note that since waiting on a condition forfeits the lock, the waiter must make sure the monitor invariant is satisfied before it waits. In the example above, the same is true for notifying.

In early monitor implementations, notifying a condition variable caused a waiting process to receive the lock and run immediately, thereby guaranteeing that the condition would still be true. Implementing this behavior is complicated and has a high overhead. It is also incompatible with schedulers that can interrupt a process arbitrarily. For these reasons, researchers have considered various other semantics for condition variables.

In most modern implementations, notifying does not take control away from the running process, but merely makes some waiting process runnable. The notifying process continues to hold the lock until it leaves the monitor function. The side effects of this approach are that the notifying process does not have to set up the monitor invariant before notifying, and the waiting process must double-check the condition it was waiting for. Specifically, if a monitor function includes the expression if test then wait(cv), another process could enter the monitor after the notification and make the condition untrue again before the waiting process runs. The expression must be rewritten as while test do wait(cv) so that the condition is re-checked before the process continues.

Implementations also provide a "notifyAll" or "broadcast" operation that notifies every process waiting on a given condition. This operation is useful, for example, when several processes are waiting for different amounts of storage to become available. Releasing storage can enable any number of these processes to proceed, but the scheduler does not know which ones.

History

Per Brinch Hansen was the first to describe and implement monitors, basing them on ideas from C. A. R. Hoare. Hoare subsequently developed the theoretical framework and demonstrated their equivalence to semaphores (when using the original semantics).

Programming languages that have supported monitors include

Concurrent Pascal
Java
Mesa

C# does not have monitors as a feature of the language, although the .NET framework has a class that facilitates implementation of Java-style monitors by hand. The POSIX pthreads interface also supports the implementation of monitors.

External links

"[Monitors: An Operating System Structuring Concept]" by Charles Antony Richard Hoare
"[Signalling in Monitors]" by John H. Howard
"[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
"[Documentation of Condition Variable and Mutex Implementation and Use]" by Claude van Ham
"[Block on a Condition Variable]" by Dave Marshall
"[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]
[boost::condition class description]
[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

From Wikipedia, the Free Encyclopedia. Original article here. Support Wikipedia by contributing or donating.
All text is available under the terms of the GNU Free Documentation License See Wikipedia Copyrights for details.