Experience with Processes and Monitors in Mesa

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

	If 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 Timeout interval is associated with a condition variable Timed-out process can do some cleanup and wait again or abort
	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

Evaluations

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