Experience with Processes and Monitors in Mesa

One-line summary: There are many practical issues associated with monitors that are not dealt with in the textbook descriptions - these issues are described in this paper.

Overview/Main Points

• 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

Flaws

• Cooperative multitasking was used in Pilot. I would love to see the issues that arise due to preemptive multitasking. (Theoretically, monitor mechanism is orthogonal to multitasking methodology. Is this true in practise?)
• Weak finish to a strong paper - applications and many of the implementation details were uninteresting.