Experience with Processes and Monitors in Mesa
--- Lampson et al., 1980


- delelopment of Pilot, an operating system, with the objectives:
	
	- local concurrent programming;
	- global resource sharing;
	- replacing interrupts - handled directly by waking up an
	  appropriate process, whithout going through a separate
	  interrupt mechanism;

- concurrency mechanisms are provided by Mesa, a programming language;

* the simplest form of mutual exclusion mechanism for uniprocessors is to use
* a nonpreemptive scheduler; if processes yield the processor voluntarily,
* then mutual exclusion is insured;

- Cooperative scheduling:

	- priority (checked after every instruction!);
	- process blocks: wait, join, page faults;

* since the system supports only one user, we feel that the considerable
* protection offered by the strong typing of the language is sufficient;

- data is protected by monitors and accessed by monitor procedures.  These can
  be of two types: entry procedures and internal procedures;

- entry procedures acquire the monitor lock, while internal procedures may be
  called just when the lock is already taken by the calling process;

- in Mesa, the simplest monitor is an instance of a module, which is the basic
  unit of program structure;

- just one address space!

- modules hay have PUBLIC and PRIVATE procedures and are used to implement ADTs;

- a MONITOR MODULE differs slightly: it has three kind of procedures: entry,
  internal (private), and external (nonmonitor procedures);

* as long as any order of calling the entry procedures is acceptable, no
* additional synchronization is needed among the processes sharing the
* monitor.  If a random order is not acceptable, other provisions must be made
* in the program outside the monitor.  Thus, monitors do not solve all the
* problems of concurrent programming.  They're just basic building blocks;

- if other conditions need to be satisfied (like in the producer/consumer
  case), processes may wait on condition variables.  When a process calls WAIT
  on a condition variable, the monitor lock is released!

- the monitor lock is not released when the monitor calls a procedure outside
  the monitor;

* the monitor maintains an invariant which is always true of its data, except
* when some process is executing in the monitor;  whenever control leaves the
* monitor, this invariant must be established;

- three cases of deadlock that may occur using monitors:

	- inside a single monitor, two processes do a WAIT, each expecting to
	  be awakened by the other;

	- cyclic calling pattern between two monitors;

	- a more serious problem arises if M calls N, and N then waits for a
	  condition which can only be satisfied when another process enters
	  N through M and makes the condition true; however, M is locked.

- a single monitor for a system reduces the maximum concurrency;

* the UNWIND exception is used to abandon computation.  Suppose procedure P1
* calls P2, that calls P3,..., until Pn.  Then if Pn generates an exception
* that is handled by P1 (none of the others has a handler), the exception 
* handler may abandon the computation done in P2...Pn by generating an UNWIND
* exception, giving P2..Pn a chance to handle it and do any necessary cleanup;

* Hoare's definition of monitors requires that a process waiting on a
* condition variable must run immediately when another processes signals that
* variable, AND THAT THE SIGNALING PROCESS RUNS AS SOON AS THE WAITER LEAVES
* THE MONITOR!

* Mesa takes a different view, by notifying the corresponding condition
* variable.  A NOTIFY is regarded as a hint to a waiting process, causing
* execution of some waiting process at some future time;  there is no
* guarantee that another process will not enter the monitor before the waiting
* process;

- therefore, in Mesa style, a WAIT needs to be enclosed by a while statement,
  to verify if the condition still holds then the process is woken up;

* another consequence of Mesa's NOTIFY is that many applications do not
* trouble to determine whether the exact condition needed by a waiter has been
* stablished (they can always verify it when woken up);

- apart from NOTIFY, there are other ways to wake up a process:

	- timeout - a timeout is associated with each condition
 	  variable.  After it, a waiting process will be resumed,
	  even if the condition variable has not been notified;

	- abort - executing Abort[p] will resume p immediately.  
	  The resumed process may ignore the abort entirely;

	- broadcast - causes all the processes waiting on the
	  condition to resume;

* Naked notifies - when a device needs attention, it can NOTIFY a condition
* variable to wake up a waiting process (i.e., the interrupt handler); since
* the device does not actually acquire the monitor lock, its NOTIFY is called
* a naked notify;  the device finds the address of the condition variable in a
* fixed memory location;

- monitors may cause priority inversion, as shown by an example in the paper;


-------
Steven Gribble:

- The problem is to design a concurrency facility suitable for a
  large OS, enabling resource sharing, mutual exclusion,
  multiprocessing, etc. It should also fit naturally into the Mesa
  program language (modules, threads, exception handlers). 

- Implied functionality for monitors includes dynamic monitor
  creation, nesting of monitor waits and calls, \"{u}nwind" within
  monitors, and correct scheduling. 

- Problem: what if we have many instances of a class of object,
  and want to associate monitors with each instance instead of one for
  the class? Solution: well, do just that - condition
  variable per object (inside a structure, potentially).
  Condition variable must be reachable by monitor procedure (argument to
  monitor procedures as one way to do this).

- Benefits of Mesa's notify: less context switching, no constraints on when
  process must run after notify, semantically correct to awaken waiters
  at random times(!), do notify on a generic condition variable rather 
  than associating more context with many specific condition variables. 

- Drawbacks: what about starvation and unfairness? 

- Implementation details: 

       - implementation split between hardware, compiler, and runtime. 
       - 4 process queues: ready, monitor lock. condition variable,
	 fault. 
       - No memory protection in Mesa: language/compiler strong enough. 
	 monitor call roughly 2 times as long as procedure call. 
       - inexpensive context switch (good for broadcasts). 
       - Pilot OS: I/O interrupts done as naked notifies. Lack of
	 mutexes in interupt handling. Bad interactions between 
	 concurrency and exception facilities. (unwinds in entry 
	 procedures due to exceptions).  some fluffy applications. 

- Relevance

The implementation and practical issues with monitors brought forth in
this paper are profound. The Mesa-specific issues and implementation
details are not profound. 

- Flaws

       Cooperative multitasking was used in Pilot. I would love to see
the issues that arise due to preemptive multitasking. (Theoretically,
monitor mechanism is orthogonal to multitasking
       methodology. Is this true in practise?) 
       Weak finish to a strong paper - applications and many of the
implementation details were uninteresting.