eval11.txt

Yu Xu (yxu@cs.ucsd.edu)
Thu, 11 May 2000 01:08:25 -0700

Evaluation of "Monitors: An Operating System Structuring Concept" by C.A.R Hoare

This paper introduces monitors as a method to structure operating system and achieve synchronization. It describes a method of implementation in terms of semaphores. It gives several examples and shows the methods to solve them using monitors. These examples include a single resource scheduler, a bounded buffer, and alarm clock, a buffer pool, a disk head optimizer, and a version of the problem of readers and writes.
One big feature of monitor is that at any time only one program can succeed in entering a monitor procedure. The paper use condition variable to represent the reason why a program might have to wait. A condition variable is represented by a queue of processes that are currently waiting on the condition. But the queue is invisible to waiters and signalers. One important thing is that the paper requires that a process waiting on a condition variable must run immediately when another process signals that variable, and that the signaling process in turn runs as soon as the waiter leaves the monitor.
The paper gives two proof rules:
Proof rule for waits: ^&{b.wait} ^&B
Proof rule for a signal : ^&B {b.signal} ^
The illustrative examples are quite standard ones in operating system areas. The question whether the signal should always be the last operation of a monitor procedure is discussed and is said to be an open question.
Finally, the possibility of constructing separate monitors for different purposes, and of separating the scheduling decisions from the checking , that may justify monitors are an appropriate concept for the structuring of an operating system.
I think this paper is the first one to formally propose using monitors to construct operating system. So it mainly talks about concurrency and synchronization, issues about use of monitors in a big, realistic system are not mentioned in this paper. They are discussed in the second paper.

Evaluation of " Experience with processes and monitors in Mesa" by Bulter W. Lampson, David D. Redell

This paper discusses the processes and monitors facilities in Mesa for concurrent programming, which address problems like priority scheduling, handling of timeouts, aborts and other exceptional conditions, interactions with process creation and destruction. Then the authors use three substantial applications: Pilot, Violet, Gateway to show the validity of their solutions.
The purposes of the facilities include: local concurrent programming, global resource sharing, replacing interrupts.
Mesa casts the creation of a new process as a special procedure activation which executes concurrently with its caller. Mesa treats a process as a first-class value in the language.
A MONITOR module has three kinds of procedures: entry , internal, and external(nonmonitor procedures). In Mesa monitored objects can be used to serialize access to each object. Hoare's definition of monitors requires that a process waiting on a condition variable mush run immediately when another process signals that variable, and that the signaling process in turn runs as soon as the waiter leaves the monitor. Mesa takes a different view: Notify is used and the result is that there is no guarantee that some other process will not enter the monitor before the waiting process.
To resume a waiting process, three additional ways can be used: timeout, about, broadcast. Input/output devices can use naked notify to wake up a waiting process.
Finally, the implementation of processes and monitors is divided among the Mesa compiler, the runtime package, and the underlying machine.