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):
Later in the same paper, he writes: "Dahl suggests that "signal" should
be the last operation of a monitor procedure...."
- 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.....
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):
In this paper, Howards shows that all these semantics are equivalent.
He shows how to implement each semantic with the other one.
- "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
- "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".
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)