Evaluations for CS221

Yang YU (yyu@cs.ucsd.edu)
Wed, 24 May 2000 23:24:14 -0700

The Multics Virtual Memory: Concepts and Design

Overview

All memory appears to be composed of a large number of independent
linear core memories (segments). Each segment has access attributes for
each user who may access the segment; the attributes are checked by
hardware on each access. The segments themselves are composed of pages,
to simplfy core memory management.

Segmentation and Paging

Each process has a desciptor segment (DS). There is a descriptor base
register (DBR) which contains the location of the page table describing
the pages of the DS, as well as the length of this DS. Each word of the
DS describes one segment: the core address of the page table describing
the pages of the segment, the length of the segment, its access rights,
and a "missing segment" switch.

Each process also has a known segment table (KST) which maps symbolic
names to segment numbers (per-process name cache). When a process is
created, its DS is loaded with the supervisor's program and data
segments. Multics' ring protection mechanism is used to cause a program
to become more privileged when it executes supervisor code.

Locating Segments

Some segments are directories. Entries in a directory can be branches
(which contain a name for a segment, the length of the segment, an
access list, a segment map, and an active switch), or links (which
contain a name for the segment, and a pathname to another directory
entry). These work a lot like Unix directories; paths look like ROOT > A
> B > C.

Processes can reference segments by their absolute pathnames or by a
mechanism like $PATH in Unix. The first time a process references a
segment, an unused segment number, s, is picked, and the path name is
recorded in entry s of the process' KST. The missing segment switch in
the corresponding DS entry is set ON.

The processor, when it tries to access a segment with this switch ON,
will generate a missing segment fault, and will run the segment fault
handler in the supervisor.

The segment fault handler checks the active switch in the branch
corresponding to the segment, which says whether there is a page table
for the segment. If not, it activates the segment. In any case, it
connects the DS entry.

Activation

There is one global active segment table (AST). With each AST entry
(ASTE) is associated a page table (PT), each of a fixed size, and of
which there are a fixed number. In order to activate a segment, its
segment map and length are copied from its branch into a free ASTE, the
active switch in its branch is turned ON, and pointers to the ASTE and
PT are stored along with it. A backpointer to the branch is also stored
in the ASTE.

Connection

To connect an active segment, look up the address of its PT in its
branch, and store it in the DS entry (SDW), copy the access rights from
the branch into the SDW, and turn off the missing segment switch in the
SDW. A pointer to the SDW is stored in the ASTE. (This will become a
list if more than one process shares the same segment.)

Page faults

There is a global core map which contains the lists of used and free
pages (each page is 1K words). On a fault from a PT, access the ASTE
associated with the PT, find the addess in secondary memory of the
missing page, and issue the I/O request to load it into memory. Update
the PT entry, store its address in the core map entry, and place the
core map entry in the used list.

Page replacement

Whenever a page is moved from "free" to "used", make sure some preset
number of pages are still free. If not, free one using LRU ("used bits"
are stored in the PT entries). To remove a page, set the missing page
switch ON, store it to secondary memory (possible assigning a secondary
address and updating the segment map entry if the page is new), and move
the block from the used list to the free list.

PT replacement

The number of active segments is limited. To deactivate a segment (in
order to free a PT and ASTE), find the one that has had no pages in core
for the longest time. Disconnect the SDWs in its ASTE list by turning ON
their missing segment switches. Deactivate the ASTE by copying the
segment map and length back to the branch, resetting the active switch
in the branch, and marking the ASTE as free.

The supervisor

The supervisor has three functional modules: directory control (DC),
segment control (SC), and page control (PC). These modules do not care
whether the page/segment they are handling is part of the process or the
supervisor; it should work wither way. Some assumptions need to be made,
so that, for example, you don't page out the pager:

All segments used in PC are always in core and are connected to the
descriptor segment of each process.
All nondirectory segments used in SC and DC are always active and
are connected to the descriptor segment of each process.
The root directory is always active and connected to each process.
The root directory is always known to each process.

Machine-independent VM: Mach

Description of Mach

Mach: a Unix-compatible OS intended for distributed environments.
Primitive elements in Mach: tasks, threads, ports, messages, memory
objects. Provide location-independence.
Mach VM implementation separated into machine-dependent and
machine-independent parts. Most of functionality is in
machine-independent section.
Implementation's data structures: resident page table, address map,
memory object, pmap. Only pmap is machine-dependent.
Features: sparse address spaces, memory-mapped files, more.

What to take away

Kernel VM code can be portably implemented with a minimum of
machine-dependent code. This allows easy porting, and also improves
performance since code isn't targeted for just one canonical processor.
Shared memory uses copy-on-write with shadow pages to reduce memory
footprint. Some additional implementation complexity ensues.
User-level pagers are possible for advanced applications and
sophisticated requirements.
Efficient VM optimizations can make message-based kernels more
reasonable in terms of performance.
The concept of memory objects & associated user-mode pagers (e.g.
the idea that physical memory is just a cache for virtual memory)
enables distributed computing and other nifty functionality.
Performance is still good-- at least as good as Unix-- or so they
claim. Their benchmarks are not very comprehensive or convincing.

Criticisms

More discussion and benchmarks of the distributed computing scenario
would be nice.
The paper made a big point out of how the Mach VM implementation was
mostly machine-independent, and claimed that this ``makes possible an
unbiased examination of the pros and cons of various hardware memory
management schemes''. However, they never did much of a comparison.

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