Evaluations

Yang YU (yyu@cs.ucsd.edu)
Wed, 10 May 2000 18:18:04 -0700

Experience with Processes and Monitors in Mesa

MainPoints: There are many practical issues associated with monitors
that are not dealt with in the
textbook descriptions

Requirements and difficulties:

The problem is to design a concurrency facility suitable for a large
OS, enabling resource sharing, mutual
exclusion, multiprocessing, etc. It should also fit naturally into
the Mesa program language (modules, threads,
exception handlers).

Implied functionality for monitors includes dynamic monitor
creation, nesting of monitor waits and calls,
"unwind" within monitors, and correct scheduling.

Stated without proof that monitors and message passing are
equivalently powerful. (Can implement one with
the other.)

Monitors:

Hoare's definition of monitors: code, data, and condition variables
colocated in a monitor. Monitor consists of
entry procedures, internal procedures, and external procedures.
Serialization done on access to monitor
procedures (entry + internal). notify and wait operations: signal
immediately relinquishes control to one
wait, and regains control once that wait leaves the monitor (many
context switches).

Monitors don't solve all concurrency problems - allowable ordering
of entry procedure calls must be
determined and enforced externally to the mechanism (eg tape drive
operations).

Wait will clear the monitor lock, even if done inside an internal
procedure. The monitor lock is not cleared
when an external procedure is called. This ensures that the monitor
invariant is mantained whenever the lock
is not set: invariant must be established before lock is released.
Deadlock:

Three pairwise deadlocks:
1.Two processes do wait, each expects signal from other. Solution:
debug your program.
2.Cyclic calling between 2 monitors: monitor M calls entry proc in
N, monitor N calls entry proc in monitor
M. Solution: impose partial ordering on monitors as resources,
then mutually recursive monitors must be
avoided.
3.Implicit cycle: M calls N, N waits for a condition that can only
be set by X calling something in N through
M. Then N is free (since N is waiting), but M is locked so X
can't get to it.

Objects:

Problem: what if we have many instances of a class of object, and
want to associate monitors with each
instance instead of one for the class? Solution: well, do just that
- condition variable per object (inside a
structure, potentially). Condition variable must be reachable by
monitor procedure (argument to monitor
procedures as one way to do this).

Notification styles:
Hoare: a notify awakens one wait immediately. The awakened
process then knows that notify just occured
- more information than just that invariant established.
Mesa: notify as hint, awakening may not happen immediately.
awakened process must verify that the
condition of interest is true each time it is awoken; awakening
may happen after some arbitrary other
code (including other processing going into monitor).

Benefits: less context switching, no constraints on when process
must run after notify, semantically
correct to awaken waiters at random times(!), do notify on a
generic condition variable rather than
associating more context with many specific condition variables.
Drawbacks: what about starvation and
unfairness?
Timeout: awaken after some timer expires.
Abort: abort waiter on exceptional condition
Broadcast: awaken all processes waiting on condition variable.
Naked notify: communication with I/O - I/O device does notify
even though it can't wait around to get
into a monitor. Can be race conditions.

Priority inversion: Consider process p1, p2, p3 (increasing
priority), monitor M. p1 enters M, prempted by p2.
p2 prempted by p3. p3 blocks entering M. p2 runs arbitrarily long,
prevents p3 from getting into M because p1
never resumed. Solution: associate with monitor the highest priority
of process entered or waiting on monitor.

Implementation details:

implementation split between hardware, compiler, and runtime.
4 process queues: ready, monitor lock. condition variable, fault.
No memory protection in Mesa: language/compiler strong enough.
monitor call roughly 2 times as long as procedure call.
inexpensive context switch (good for broadcasts).
Pilot OS: I/O interrupts done as naked notifies. Lack of mutexes in
interupt handling. Bad interactions between
concurrency and exception facilities. (unwinds in entry procedures
due to exceptions).
some fluffy applications.

Relevance

The implementation and practical issues with monitors brought forth in
this paper are profound. The Mesa-specific
issues and implementation details are not profound.

Monitors: An Operating System Structuring Concept

Main Points:
developes Brinch-Hansen's concept of a monitor

Motive:
A primary task of operating system designer is to construct resource
allocation scheduler for various resources.

Definition of Monitor:
Each scheduler will consist of a certain amount of administrative
data and procedures. The collection of data and procedures is a monitor,
(sounds like instance of a class)

Equivalence between monitor and semaphore
Proved in this paper that semaphores can be implemented by monitors,
and vice versa.

Yang Yu
Department of Computer Science and Engineering
University of California, San Diego