Experience with Processes and Monitors in Mesa

by B. W. Lampson & D. D. Redell @ Xerox

CACM 1980

1. Introduction

Open problems with monitor and answers this paper suggest
Program structure: How should programs be designed when monitors are used?
=> Monitor module and condition variables
Dynamic process creation: Previous work assumed a fixed amount of concurrency
=> Just prefix a function with 'FORK' to create a new process
Dynamic allocation of monitors: Allow the number of monitors in a program or a module to vary dynamically
=> Create an object -> create a monitor -> associate the monitor with the object
The consequence of wait call in a nested monitor call is not clear
=> Deadlock
Exceptions: How should the system handle exceptions when monitors are used?
Exception handler should release the mutex first and then handle the exception
Scheduling: How should monitors interact with process scheduling?
Priority inversion can happen. Suggestion: priority boosting
Input-output: Can and should I/O devices be treated like any other signalling in a system that provides monitors?
Naked notify
Why monitor rather than non-preemptive scheduling or semaphore?
Non-preemptive scheduling does not support MP
Interrupt handling in non-preemptive scheduling tends to be too sluggish
Blocking call should not be used within a critical section -> programming generality hurts
Page faults should not occur within a critical section -> no multiple programming across page faults
Semaphores exert too little structuring discipline on concurrent programs

2. Processes in Mesa

Process creation in Mesa: Any procedure call can be prefixed by 'fork', for example, ReadLine(terminal) -> fork ReadLine(terminal)
Process Return p = fork ReadLine(terminal);
do some other jobs;
char * buffer = JOIN p // rendezvous occurs here automatically
Note: the signature of ReadLine is independent whether it is invoked as a new process or not
Note: ReadLine becomes the root procedure of the new process
Note: variable 'p' is like a pointer. 'p' becomes dangling pointer when the process exits
Processes in Mesa are treated exactly like any other value: they can be passed as arguments, assigned to variables, etc
Strict type checking is possible:
The type of a procedure: signature
The type of process: return type
The cost of creating, destroying, and storing processes is moderate. Don't understand!
Java-like exception handling in Mesa -> Root procedure should catch all the exceptions -> Arbitrary procedure written for sequential call is NOT suitable for forking

3. Monitors

Monitor is an object comprised of:
Shared data
Synchronization mechanism
Methods accessing the shared data
Entry method: public method
Internal method: private method
Only one process can be inside monitor and access the shared data
If the order of calling entry methods does matter, other provisions must be made in the program outside the monitor

3.1 Monitor Modules

A module in Mesa is exactly an object in OO
Monitor modules:
Public method & private method + Entry method & internal method
Shared data should be accessed through entry methods
Other data could be accessed through public methods possibly by multiple processes at the same time
Condition variable: wait & notify
Mutex will not be released when a process in monitor calls a (inside or outside) function
-> If callee is another monitor, deadlock can happen
-> Exception handler can also cause deadlock => resolved so that exception causes releasing the mutex and calls the handler

3.2 Monitors and Deadlock

Kind of independent issue
Monitor is a tool for synchronization and it is the programmer's responsibility to be careful not to cause deadlock
But the tool has to provide a clear interface

3.3 Monitored Objects

Object are created and destroyed dynamically -> monitors for these objects should also be created and destroyed dynamically
In object oriented programming language such as Java, this is simply done by tagging an object as 'monitor' (actually tagging one or more function with 'synchronized')
But this is a kind of headache in a non OO language
Create an object -> create a monitor -> associate the monitor with the object

3.4 Abandoning a Computation

Call chain: P1 -> P2 -> ... -> Pm -> Pn
Pi is an entry (monitor) function
P1 handles exception generated by Pn because none of P2 ... Pm does
P1 should undo P2 ... Pn
how to release the monitor lock that Pi has?
=> User has to provide UNWIND method

4. Condition Variables

'notify' instead of 'signal'

4.1 Alternatives way to resume waiting process

Timeout interval is associated with a condition variable
Timed-out process can do some cleanup and wait again or abort
Like 'kill' in Unix
Aborted process handles the signal by quitting wait or even ignoring
Broadcast: wake all waiter instead of one waiter

4.2 Naked notify

Communication between process and device--for example I/O device--can be implemented by monitor
Place a monitor between the process and device
Device can notify interrupt handler by naked notification that signals some event has happened
Called naked notify because the device has not hold monitor lock -> race condition can happen

5. Priorities

Priority inversion can occur
Processes P1, P2, P3 with P1 the lowest and P3 the highest priority.
P1 grabs monitor lock -> is preempted by P2
P2 is preempted by P3, which tries to grab the same monitor lock
P2 finish -> P1 finish -> P3 finish
Monitor does not prevent priority inversion outright
Proposed and commonly used solution: priority boosting
Raise the priority of the process holding the monitor to M.maxPrio

6. Implementation

6.1 The Processor

6.2 Runtime Support Packages

6.3 Compiler

6.4 Performance

7. Applications

7.1 Pilot: A General-Purpose Operating System

7.2 Violet: A Distributed Calendar System

7.3 Gateway: An Internetwork Forwarder


Pros: This paper deals with many aspects of monitors and provides solutions, almost all of which have blossomed at Java monitor