The Multics Virtual Memory: Concepts and Design

Bensoussan, Clingen, Daley

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: