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 .
- High Level Details:
- This is an attempt to create an extensible operating system that can
provide the functionality of UNIX when desired but is generally lighter
- 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.
- 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.
- 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.
- 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.
- 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.
- External memory management makes secondary storage objects
accessible through message passing.
- Lower Level Details:
- 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.
- The kernel page fault handler is still responsible for validity and
protection, page lookup, copy on write, and hardware validation.
- 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
- 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
- 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.
ConclusionsI 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).