Citation:
M. Young et al., "The Duality of Memory and Communication in the Implementation
of a Multiprocessor Operating System", Proceedings of the 11th ACM Symposium on
Operating System Principles, November 8-11, 1987, pp. 63-76.

* Summary

The goals, design, and implementation of Mach and its external memory 
management facility are described. The relationship between memory and 
communication in Mach is examined as it relates to overall performance,
applicability of Mach to new multiprocessor architectures, and the structure
of application programs.

* Mach Design

Program execution in Mach is controlled through the use of tasks and threads.
Tasks are the basic unit of resource allocation, and include a paged virtual 
address space and protected access to system resources. A thread is the basic
unit of computation, and is a lightweight process operating within a task.

IPC in Mach is defined in terms of ports and messages. A port is a 
communication channel, logically a finite length queue of messages protected by
the kernel. Access to ports are controlled using port capabilities. Ports may
have multiple senders but only a single receiver. A message consists of a fixed
length header and a variable-size collection of typed data objects. A single 
message may transfer up to the entire address space of a task, and may contain
port capabilities.

A task's address space consists of an ordered collection of valid memory
regions, each aligned on system page boundaries. Mach supports read/write 
sharing of memory among tasks of common ancestry through inheritance. Copy-on-
write sharing is used to efficiently perform virtual memory copying both during
task creation and during message transfer.

Instead of basing secondary storage on a kernel-supplied file system, Mach 
treats secondary storage objects in the same way as other server-provided 
resources accessible through message passing. The technique is referred to
as external memory management, and is based on the notion of a memory object.
A memory object is an abstract object representing a collection of data bytes
on which several operations are defined. Memory objects are referenced using
ports, and can be created and serviced by user-level data manager tasks. A
data manager is entirely responsible for the initial values of this data and
the permanent storage of the data if necessary. The Mach kernel acts as a
cache manager for the contents of a memory object, and issues requests to the
data manager to perform cache management functions (e.g., handling misses,
selecting victims). The interface between the kernel and data managers is
composed of three parts: (1) calls made by an app to map a memory object into
its addr space, (2) calls made by the kernel on the data manager, and (3) calls
made by the data manager on the kernel to control use of its memory object.

* Implementation Details

Four basic data structures are used in the Mach kernel to implement the
external memory management interface: address maps, memory object structures,
resident page structures, and a set of pageout queues.

A task address map in Mach is a directory mapping each of many valid address 
ranges to memory objects and offsets within memory objects. To account for
sharing through inheritance, address maps are two-level. The first level
consists of references to second-level sharing maps. The first level map
contains per task attributes, while the second-level sharing maps reflect
changes to the virtual memory represented by a map entry. The sharing maps
refer to memory object structures.

For each memory object used in an address map, there is an associated internal
memory object structure, consisting of ports referencing the object, its size,
the number of address map references to the object, and whether the kernel is
permitted to cache the memory object when no references to it remain. A list of
resident page structures is attached to the object.

Page replacement uses several pageout queues linked through the resident page
structures. An active queue contains all of the pages currently in use, in LRU
order. An inactive queue is used to hold pages being prepared for pageout.
Pages not caching any data are kept on a free queue.