* Experiences with Processes and Monitors in Mesa
* Authors: Butler W. Lampson, David D. Redell
* Field: OS/Concurrency 
* Reference: Communications of the ACM, Vol. 23, No. 2, February 1980

* Theme: Concurrency is hard, and though monitors help contain the
effects of concurrency, they do not completely hide it.  This paper is
a collection of design issues encountered when implementing and using
monitors to manage concurrency.

* Implementation: The authors found that the following issues needed
to be resolved to implement and use monitors robustly:

a. Program structure - modules coincide with monitors nicely
(i.e. synchronized classes in Java).  Public procedures in a module
may be synchronized or unsynchronized.  Private procedures never grab
the monitor lock, as it is already grabbed by the public procedure if
needed.  Exceptions thrown inside the monitor run holding the monitor
lock; a mechanism is provided to raise an exception immediately after
leaving the monitor.

b. Creating processes - Processes created using procedure call syntax.
Processes are first-class objects which can be used like other
variables.  The root procedure of a process must be able to handle all
exceptions that occur, so not every procedure is suitable for forking.

c. Creating monitors - Each monitored object (record) has a lock
variable; this allows the number of locks to vary with the amount of
data instead of being fixed by the syntactic structure of the code.
In essence, this is the same as changing the lock from a class
variable to an object variable.

d. WAIT in nested monitor call - WAIT releases the monitor lock and
reacquires it when the process reenters the monitor.  A call to a
procedure outside the monitor module does *not* release the lock, even
if that procedure is in another monitor and does a WAIT.  If a WAIT
released all monitor locks, a monitor invariant would have to be
established before every call to an outside procedure, making calling
such procedures too cumbersome.

e. WAIT semantics - A SIGNAL on a condition variable in Mesa doesn't
guarantee that a process waiting on that condition variable will
immediately run after the signalling process exits the monitor.
Therefore the waiting process should sit in a loop until it is awaken
with the condition being true.  This prevents the necessity of a
context switch immediately upon a signal, thus saving one context
switch (A signals B and cswitch to B, then B finishes and cswitch to
A).

f. Exception interactions - 2 logical exceptions are generated for
every exception thrown.  The first is an UNWIND exception which allows
procedures to do cleanup before the activation record is destroyed;
the actual exception thrown returns control to the first enclosing
activation which handles it.  Entry procedures must have an exception
handler for UNWIND in order to restore the monitor invariant; if none
is provided, Mesa doesn't release the monitor lock when exception
occurs.  This causes an easy-to-diagnose deadlock (how?).

g. Scheduling interactions - Priority inversion problem.  3 processes,
Low, Med, High priorities.  L enters monitor and then M arrives and
starts running.  H arrives and trumps M, but must wait for the monitor
lock that L holds.  Thus M can prevent H from running, which is
priority inversion.  Can avoid by temporarily giving L the highest
priority of the processes waiting for its monitor lock.  Solving this
is neither free nor always necessary (i.e. no M priority processes
using a monitor).

h. Input-output interactions - I/O exceptions are handled by using a
"naked notify" which is a notify to a monitor without a acquiring a
monitor lock.  A race condition may occur but is circumvented with
another mechanism (unfamiliar to me).

i. Deadlocks - three patterns of pairwise (2-process) deadlock.  1) In
a single monitor, 2 procsses do a WAIT, expecting the other to wake
them up.  This is just a local bug in the monitor itself.  2) 2
monitors, each process is in one monitor and calls an entry procedure
in the other.  Occurs independently of monitor mechanism; caused by
cyclic dependencies.  Avoid by not making mutually recursive monitors
(i.e. impose an ordering on monitor lock acquisition).  3) 2 monitors;
if all entries to A occur through B, then a wait in A will not release
lock on B, thus preventing another process from entering B and then A
to make the condition true.  Solve by making a non-monitor module O
which implements the abstraction of B, using B only for manipulation
of shared data; only O can call A, so there are no locks held when A
is called.