The Multics Virtual Memory: Concepts and Design

A. Bensoussan, C. T. Clingen, and R. C. Daley @ MIT

Communications of the ACM, May 1972, pages 308-318

Introduction

Design Principles
it must be possible for all on-line information stored in the system to be addressed directly by a processor and hence referenced directly by any computation
it must be possible to control access, at each reference, to all on-line information in the system
Advantage of direct addressability
A procedure can directly call another procedure which is stored in disk!
Dynamic Linking Library becomes possible as a natural consequence
Space saved!
Static binding means having multiple copies of the same procedure for different program
Provide programmers a great level of abstraction and uniform view of all data:
In stead of opening, reading, and closing a file, she just needs to read the file data addressed by the combination of segment and offset

Segmentation: Abstraction, User Interface, whatever

File sharing on non-fully-segmented system

open file by multiple processes

each process works on its private copy of the file

explicit fsync is required to update the real file

The difficulty of access control in non-segmented system

each process is given a logically contiguous memory

possibly synthesized from multiple objects with different access policy

each object loses its identity

this makes access control on each original object almost impossible

Suppose that multiple processes share a copy of compiler

Processes should not be able to alter compiler code

As a result, compiler should be called like a system call

Multics Model

Segment creation: system call to create a segment

arguments

segment name: symbolic name

ACL: access rights to the segment for users

return: segment descriptor

File is created as a segment with the same call

Segment reference: done by (segment name, i-th word)

Segment and Paging in Honyewell 645

Virtual address(32 bits) is composed of sp, sw, ip, iw
see Fig. 3
TLB is implemented as an associative memory

Implementation of Multics Model on Honyewell 645

Process and Kernel

Each process is given
a Known Segment Table: mapping symbolic names of segments to the segment numbers
a Descriptor Segment: mapping segment numbers to the addresses of page tables
Kernel itself is implemented using segment addressing
Not all of kernel needs be memory resident
Kernel code and data is shared among processes and executed in the context of a process as in Unix
Ring protection mechanism is used to protect kernel code from user processes
Similar to user-mode & kernel-mode of modern architecture

Directory Hierarchy

Pretty much like Unix directory hierarchy
Symbolic links (called link in Multics) are also introduced by Multics
The only difference is that directory is itself a segment
Each entry (called Branch in Multics) in directory segment has:
name
length of the segment
ACL: access lists to the segment
inode (called segment map in Multics)
active: indicate whether there is a page table for this segment or not
Segment name = path name
User may give out the last part of the path name
Dynamic linker automatically searches the predefined paths and makes up the full path name

Segment Creation

Similar to Unix: just adding an entry to the directory segment
name: given by the user
length of the segment = 0
ACL: given by the user
inode: all entries are NULL
active = inactive

Segment Access

Making a segment known to a process
When a process first refers a segment with pathname, new segment number is allocated by the kernel. Then the mapping (pathname, segment number) gets recorded to the KST[segment number] of the process
Each KST entry KST[i] contains--note that i = segment number allocated by the kernel:
pointer to the segment descriptor
actually the segment descriptor is tagged as missing segment
later access to this segment will trap "missing segment fault" and segment fault handler will handle it
pointer to the directory entry (= branch)
Now on the process can access the segment by segment number
Process refers a word by (segment number, offset in words). If DS[segment number] has "missing segment" tag on, a trap will be issued and segment fault handler will be called. Procedure:
index into KST[segment number]
follow the pointer to directory entry
populate the DS[segment number] with the values of the directory entry
if page table has not been made for the segment
create a new page table
register [segment, page table] entry to active segment table
inode also copied to the active entry
the size of active segment table is fixed and maybe an existing entry should be kicked out of the table to make a room for the new segment being activated
segment which has had no pages in main memory for the longest time is the victim
update directory entry so that it points the [segment, page table] entry
DS[segment number].page_table = pointer to the page table
=> every information for page fault handler is in main memory
Note that each process has its own DS and KST, but active segment table and page table are shared by all processes