paper evaluations: 05/11

Alejandro Hevia (ahevia@cs.ucsd.edu)
Thu, 11 May 2000 03:10:36 -0700 (PDT)


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

The paper introduces the concept of a monitor as an abstraction of a
resource allocator. A monitor contains some local data (the resources) and
procedures that can be called from outside to access the resources.
Both syntax and semantics of monitors are introduced, including the
concepts of collection of procedures as a single critical section, the
equivalence (of power) of monitors with semaphores, the
wait/signal constructs and the simple condition variables (and their most
sophisticated variations using priorities and boolean expressions). Moreover,
in a pioneering work, the author discusses possible implementations (and
optimizations) of monitors and some basic concepts of provable correctness (by
using module and condition variable invariants).

A very interesting aspect raised on the paper is the problem of a precise
semantic for the signalling process (that is, the famous question about
whether a process must exit or not the monitor right after signaling).

The paper's main contribution is the introduction of an easy-to-visualize,
yet general, abstraction for process synchronization. They support its
applicability by providing several monitor-based solution to (now classical)
problems, like the consumer-producer, buffer allocation, disk head scheduler
and readers-writers problem.

Some aspects of the methodology presented on the paper are suitable for
some criticism. For instance, the paper concludes that, given the complexity
of synchronizing several independent monitors, the most adequate programming
approach would be the 'monolithic' management of resources. This completely
omits settings like multi-processor environments or factors like the
conceptual simplicity of more modular OS designs. On the other hand, the
paper intends to give general directions about "appropriate scheduling" while
considering just a few cases; this is clearly not convincing enough without
further theoretical or experimental that supports it.

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

Evaluation of paper
"Experience with Processes and Monitors in Mesa"
by B.W. Lampson and D.D. Redell

This paper describes the experience of implementing monitors and processes
in the programming language Mesa. It also browses through several practical
(yet unsolved) questions about the behavior of monitors and processes. For example,
it discusses the exact semantics of a "wait" in a nested monitor call (suggesting
not release the lock), how to handle exceptions when in a monitor (again, not
to release the lock) or alternative semantics for the conditional variables
(that is, the "wait" method, allowing waiting processes to act upon
timeouts, the abort exception UNWIND, or to be woken up 'simultaneously' by
a broadcast signal). Other interesting features mentioned in the paper are the
inclusion of the monitor concept on the syntax and semantics of modules and
the 'naked' notify, which is used to implement device interrupts with no
monitors (although it turns to be of limited effectiveness since it lacks the
synchronization of monitors).

Regarding to processes design, the paper also proposes to implement processes
as first-class values and more flexible scheduling strategies based on process
priorities and modules locks (trying to avoid deadlocks because of poor scheduling).

The paper interestingly surveys on the main issues of implementing a good and
efficient programming language support for processes and their synchronization
(using shared memory). Among the weakness of it are its light treatment of
possible deadlocks, starvation and race conditions in Mesa, in particular,
design consideration to avoid those events when using the new proposed semantics
of condition variables.