Notes on "The Multics Virtual Memory: Concepts and Design"

While “Virtual Memory, Processes, and sharing in MULTICS” explored the details of how Multics’ segmented virtual memory works, this paper focuses on how users interact with segments and how Multics implements virtual memory using the Supervisor. The paper motivates Multics’ approach to segmented memory by comparing against several other systems:

Virtual Memory

Multics users access segments with a (symbolic name, index) pair where index corresponds to the number of words to index into the segment. Upon first reference to a segment, the Multics dynamic linker maps the (symbolic name, offset) pair to a generalized address (segment number, index). This seems to be stored in a table. First reference is relatively expensive as Multics must search for the symbolic name.

Upon accessing and address, Multics checks a user’s authorization with the following algorithm (page faults omitted for brevity):

if descriptor.length() < segment_number:
    raise FAULT
segment_descriptor = descriptor[segment_number]
if segment_descriptor.missing_segment():
if segment_descriptor.segment_length() < index:
    raise FAULT
if segment_descriptor.access_rights_incompatible():
    raise FAULT
return lookup(segment_descriptor.absolute_core_address + index)

Note that each process has an associated descriptor segment whose location is stored in a register. The descriptor segment stores metadata on other segments accessed by the program.

Paging and Supervisor

Segments are implemented on top of demand paging. Segments may span multiple pages which are loaded into memory upon a page fault. Multics maintains a used list and a free list of page tables. If possible, the Supervisor tries to allocated a page from the free list. If the length of the free list is smaller than some minimum value, used pages are swapped to secondary storage and added to the free list via an LRU eviction policy.

The active segment table is part of the core memory is reserved for recording attributes needed by the page fault handler (e.g. segment map and segment length). Segments are made active when they are inserted into the active segment table, and can be deactivated as well. The paper describes the bookkeeping Multics performs so that the Supervisor runs correctly.

In addition, the supervisor performs operations on segment attributes, maps path names into segment numbers, and performs segment fault handling.

More on Multics is a well-maintained resource documenting Multics from a technical and historical perspective.