The Duality of Memory and Communication in the Implementation of a
Multiprocessor Operating System

Young, Tevanian, Rashid, Golub, Eppinger, Chew, Bolosky, Black, and Baron

One-line summary: This paper discusses Mach's object-oriented
semi-user-extensible memory system .

Overview/Main Points

   * High Level Details:

        o This is an attempt to create an extensible operating system that
          can provide the functionality of UNIX when desired but is
          generally lighter weight.

        o Communication and virtual memory can play complementary roles in
          both distributed and parallel applications as well as in the
          implementation of the operating system kernel. Memory management
          can be performed by user programs, and performance can be improved
          for multiprocessors.

        o Memory Objects: In the object-oriented Mach system, memory is
          represented as an abstract object (containing a collection of data
          bytes) upon which several operations are defined. A data manager
          (which can be separate from the kernel) handles initial values and
          permanent storage.

        o Mach inherits Accent's single level store, in which primary memory
          acted as a cache of secondary storage. File data can be read in
          directly from memory instead of from disk.

        o Mach also inherits from Accent the ideas of tasks, threads, ports
          and messages. Each object has an associated port, through which
          its functionality may be accessed using messages (Messages can be
          used to transport data, pointers, or to make remote procedure
          calls). Each task (similar to a UNIX process) can have multiple
          threads running in its address space (made up of memory objects).
          Tasks and threads use their associated ports to communicate with
          the objects that they need.

        o Virtual Memory: Tasks allocate regions of memory by allocating
          memory objects and mapping them into their space. The kernel
          maintains control of paging and cache management. For instance, on
          page faults, the kernel makes a call to the memory object
          requesting the new data, and on write-back, the kernel makes a
          call prompting the object to flush the page to secondary storage.
          There is a detailed API given in the paper for all of the kernel
          and manager calls.

        o External memory management makes secondary storage objects
          accessible through message passing.

   * Lower Level Details:

        o Mach uses address maps, memory object structures, resident page
          structures, and a set of page-out queues. The address map maps the
          valid address ranges to memory objects. The other structures
          contain things like object-specific info, physical mappings, and
          status info.

        o The kernel page fault handler is still responsible for validity
          and protection, page lookup, copy on write, and hardware
          validation.

        o Problems included blocking on user tasks, failure to release
          memory, malicious data changes, deadlock, and maintaining
          sufficient memory for the kernel pager (there must be available
          memory to send messages to request memory...).

        o Different types of multiprocessor architectures were presented.
          Uniform Memory Access (UMA) share all memory. Non-uniform Memory
          Access (NUMA) share all memory, but have associate memory with
          individual CPUs that takes longer for other CPUs to access. No
          Remote Memory Access (NORMA) machines are similar to NUMAs but
          provide no hardware supplied mechanism for remote memory access
          (ie NOW). Mach can do shared-memory (example) using message
          passing.

        o Several examples and sample applications are given in the paper.
          Since we have already seen the benefits of active messages,
          exokernel, and SPIN, I won't waste paper on the pluses here.

Conclusions

I can't decide whether this paper was brilliant (as an early predecessor of
exokernel and SpinOS) or an utter waste of time (because of its
rambling-string-of-details-with-no-conclusion organization). The idea of an
extensible OS was a good one. The interface and implementation detail given
were not particularly interesting.

Questions

"The use of multiple threads to handle data requests also aids in deadlock
prevention; one thread within a task may service a data request for another
thread in that task" (p215). If there is deadlock on resources, how is
another thread going to help?

Their performance information was completely unsupported. They stated how
their cache could be useful in improving the performance (UNIX only uses 10%
of mem to cache). However, they gave no comparison numbers, nor did they
give any load information (upon which the results would depend heavily).
  ------------------------------------------------------------------------
Back to index