Paper Evaluations: 05-10-2000

Flavio P JUNQUEIRA (flavio@cs.ucsd.edu)
Wed, 10 May 2000 23:04:47 -0700 (PDT)

Title: "Monitors: An Operating System Structuring Concept"

This paper develops the concept of a monitor as a method of
structuring an operating system. A monitor is collection of associated
data and procedures, which are called by programs wishing to acquire
and release resources. Because access to resources is concurrent, it
is essential that only one program at a time succeed in entering a
monitor procedure, and any subsequent call must be held up until the
previous call has been completed.

It is suggested in this paper the use of conditional variables. A
process executing a monitor procedure and requiring a delay issue a
wait operation on a conditional variable. This operation causes the
process to sleep in the queue associated with the conditional variable.
Whenever the expected condition holds, another process executing a
monitor variable issues a signal operation. This operation wakes up a
process in the conditional variable queue, according to a scheduling
policy as FIFO or priority scheduling. Note that a conditional
variable has no value associated, only a queue of waiting processes.
As a enhancement, it is proposed in one of the examples in the paper a
function which checks whether the queue of a conditional variable is
empty or not.

For monitor programming, it is usually useful to associate an
invariant with the local data representation of a monitor to describe
some condition which will be true for the monitor data. The invariant
will be true before and after a monitor procedure call. Moreover, the
invariant will be true before a wait is issued and after a waiting
process is resumed. An invariant can be used to check the correctness
of a implementation.

An important result of this paper is the demonstration of the
equivalence between monitors and semaphores. Since monitors can be
implemented with semaphores and vice-versa, both can express the same
computations.

In order to show how the proposed monitors can be used to structure an
operating system, some common mutual exclusion problems and their
solutions were considered, as: the bounded buffer, scheduled waits,
buffer allocation, disk head scheduling, and readers and writers.

Nevertheless, I think that these problems are not sufficient to
demonstrate whether the structuring of an operating system using
monitors should succeed. Indeed, it seems that there was no experience
in programming with monitors at that time, and hence issues, as
deadlocks, are only briefly mentioned. On the other hand, the monitor
proposal is very interesting, not only for being a powerful concurrent
programming construct, but also because it is still used in
operating systems like Solaris and programming languages like Java.

----------------------------------------------------------------------

Title: "Experience with Processes and Monitors in Mesa"

This paper describes the design decisions to integrate monitors in the
Mesa language. This language was used to implement the Pilot operating
system and the application programs it supports. Thus, including
monitors in Mesa permits that both the operating system and
applications use this language construct for the synchronization of
concurrent processes.

In Mesa, procedures might be called using the FORK operation, what
causes the creation of a new process. The procedure is then executed
in this new process concurrently with its caller. If the parent
process issues a JOIN operation on the created process, then they can
synchronize again after the new process finishes its execution.

Mesa procedures are implemented inside modules. A monitor is a special
type of module and has three different types of procedures, namely
entry procedures, internal procedures, and external procedures. Only
the entry procedures are visible to other modules. External procedures
are visible, but they are not considered part of the monitor, because
they don't hold the monitor lock while they are executed. A special
monitor which stores data and has a monitor lock is called monitored
record. A monitored record is used when multiple monitors are
necessary for a class of objects. The redundant information that would
be stored in each monitor is stored instead in a monitored record.

Situations as monitors locked in a cyclic wait and two waiting
processes which turn out to wait on each other constitute deadlocks.
Some of those situations are described in the paper with their
respective solutions. The solutions basically depends on the
programmer discipline. For instance, it is suggested the use of
partial order in the access of the resources in order to avoid
monitors locked in a cyclic wait.

An important feature of the Mesa language is the support to generate
and handle exceptions. If a procedure throw an exception, then the
ordering established by procedure calls is used to control the
processing of exceptions. The first procedure in this order has the
option to abandon the computation by generating an unwind exception.
Hence, entry procedures should provide handlers for this exceptions
to restore the monitor invariant.

The most interesting aspect of the paper is the proposal for condition
variables. Different from Hoare's proposal, when a process establishes
a condition, it notifies some other process waiting on the condition
variable. The waiting process can resume at any convenient time in the
future. Therefore, there is no guarantee that some other process will
enter the monitor before the waiting process, and then he process has
to check every time it wakes up whether the condition still
holds. Other ways of resuming a process are: timeout, abort, and
broadcast. Notifies are also used for the communication with I/O
devices. Devices notify a condition variable to wake up their
handlers. Since the devices cannot actually acquire the monitor lock,
this is a special type called naked notify.

In the case that applications require the use of priority scheduling
discipline a scheme is proposed to avoid priority inversion. The
priority of the highest-priority process which ever enters a monitor
is associated to that monitor. Then whenever a process enters a
monitor, its priority is temporarily increased to the monitors
priority.

In terms of performance, it seems that the implementation is
efficient. Most of the constructs were implemented in the underlying
machine. The exception is the FORK+JOIN construct. In addition, it is
interesting that they had race conditions due to lack of mutual
exclusion in the handling of interrupts. In a previous section, they
said that this problem would be avoided by providing wakeup-waiting
switch.

In my opinion, the paper describes several important aspects related
to the integration of monitors as a synchronization construct to a
programming language. Since the Mesa language was used to implement
the Pilot, the details described are also useful in the implementation
of operating systems. My only complain about the paper refers to
"Applications". In general, this section does not add much to the paper.

--Flavio Junqueira.

------------------------------------------------------------
Flavio Paiva Junqueira, PhD Student
Department of Computer Science and Engineering
University of California, San Diego

Office location: AP&M 4349 e-mail: flavio@cs.ucsd.edu
------------------------------------------------------------