The Multics Virtual Memory: Concepts and Design
Bensoussan, Clingen, Daley
OverviewAll 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 PagingEach 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 SegmentsSome 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.
ActivationThere 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.
ConnectionTo 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 faultsThere 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 replacementWhenever 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 replacementThe 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 supervisorThe 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.