Notes on Monitors

Extra Notes On Monitors: (first created on 10/01/2004, last updated on .... )

I'll go over and quote from the classic papers on monitors. Papers that I discuss here are available on-line (you can search for them on google). There are many other important classic papers that are not on the Web.

Please note, these papers frequently use "processes", instead of "threads", as the entities that require synchronizations. Also, "entering and leaving a monotor" can be read as acquiring and releasing a lock for mutual exclusion.

C. A. R. Hoare, "Monitors: an operating system structuring concept", Commun. ACM 17(10): 549-557 (1974)

In this paper, he writes at one point (quoting):

a "signal" operation... causes exactly one of the waiting programs to be resumed immediately. In order to enable other programs to release resources during a "wait", a "wait" operation must relinquish the exclusion which would otherwise prevent entry to the reseasing procedure. However, a "signal" operation must be followed immediately by resumption of a waiting program, without possibility of an intervening procedure call from yet a third program. In is only in this way that a waiting program has an absolute guarantee that it can acquire the resource just released by the signaling program without any danger that a third program will interpose a monitor entry and seize the resource instead.....

Later in the same paper, he writes: "Dahl suggests that "signal" should be the last operation of a monitor procedure...."

He shows how (Hoare) monitors can be implemented using semaphores.

Per Brinch Hansen, "Structured Multi-programming", Commun. ACM 15(7): 574-578 (1972)

In this paper, instead of having two functions, "wait" and "signal", Hansen proposed a primitive called "await (condition)". The OS delays a process until the specified condition is met.

B. Lampson and D. Redell, "Experience with Processes and Monitors in Mesa", Commun. ACM 23(2): 105-117 (1980)

In this paper, the authors discuss synchronization primitives included in the programming language called "Mesa". In Mesa (quoting):

When one process establishes a condition for which some other proces may be waiting, it notifies the corresponding condition variable. A "notify" (a term used in paper, but it is the same as a "signal") is regarded as a hint to a waiting process; it causes execution of some process waiting on the condition to resume at some convenient future time. When the waiting process remuses, it will reacquire the monitor lock. There is no guarantee that some other process will not enter the monitor before the waiting process. Hence nothing more than the monitor invariant may be assumed after a "wait".

J. Howard, "Signaling in Monitors", IEEE International Conference on Software Engineering, pp 47-52 (1976)

This paper has a nice classification of different monitor semantics (quoting the paper):

"Signal and wait". The signaled process gains immediate access to the monitor. The signaler rejoins the set of processes awaiting entry to the monitor.
"Signal and urgent wait". Intuitively, signalers should have priority over new procedure calls for access to the monitor. Rather than joining the monitor's entry queue. signalers are placed in the "urgent" queue; when a (waiting) procedure exits (returns or waits) a signaler is restarted from the urgent queue. In this paper, this defines "Hoare monitors".
"Signal and return". Often "signal" operations occur immediately prior to procedure returns. In such cases it seems pointless to make signalers wait to do nothing by return. They might as well return from the monitor call immediately after signalling. In this paper, this defines "Brinch Hansen monitors".
"Automatic signaling". This is a case where this is no "signal". Instead, whenver a monitor procedure returns or waits, each "waiting condition" is evaluated, if one is true, a process from the waiting queue associated with that condition is restarted and given control of the monitor.
"Signal and Continue". The last alternative is to allow the signaler to continue; a "signal" operation leaves a reminder that a process from the queue waiting on the condition variable should be restarted when the currently active monitor procedure returns or waits. This is "Mesa monitor".

In this paper, Howards shows that all these semantics are equivalent. He shows how to implement each semantic with the other one.

Another comprehensive survey paper on different monitors is by P. Buhr, M. Fortier, and M. Coffin "Monitor Classification", ACM Computing Surveys 27(1): 63-107 (1995)