Review: “The Multics Virtual Memory: Concepts and Design”

Papers

Summary

These papers talk about the design and implementation of
segmentation and sharing in the Multics operating system. Its virtual
memory is designed with two main goals: first all on-line information
stored in the system have to be addressed directly by the processor so
that copying information is no more needed, and second it must be
possible to control access on a per-reference basis to all on-line
information in the system.

With the use of segmentation Multics provides direct hardware
addressing by user and system programs of all information independently
from its physical storage location. The information is stored in
segments. Each of them is sharable and has independant attributes for
its size and access privileges. Segmentation offers richer protection
mechanisms than a purely page-based virtual memory system and better
opportunities for data sharing. Processes create segments which may be
shared by other processes, hence avoiding data copy.
The paper also describes user and supervisor issues when implementing this virtual memory scheme.

The second paper (“Multics Virtual Memory: Tutorial and
Reflections”) explains, beside segmentation and paging, the different
hardware used with Multics and how it provided an effecient way to have
8 level of protection (rings of privileges).

Contributions

The authors were able to describe and provide a system that
satisfies the two main design goals, which are that all on-line
information have to be addressed directly by the processor and that it
is possible to control access on a per-reference basis to all on-line
information. This is achieved by using segmentation which basically
provides sharing and access control while paging supports linear
address space and protection. They present in this paper a description
of an effective implementation of the design goals.

Novel and cool ideas

Multics combines segmentation and paging: this results in a very
flexible virtual memory system. Multics was “ahead of time”. One thing
that I found really interesting is that the file system is an implicit
part of the segmentation functionality.

Multics organized memory segments and files in a tree structure in
order to ease data organization. I see it as a big step forward.
Another aspect of Multics is really interesting: dynamic linking. I
presume that not all systems at that time had such a feature.

Good and bad points

Some good points:

  • By combining segmentation and paging they provide a very flexible virtual memory system
  • Segmentation is a mix between common memory segmentation and file
    system. The data are fetched automatically from the scondary store and
    written back after having been modified. There is no explicit
    input/output system call. However, this is also a bad point
  • Data organization in a tree structure
  • In the Multics implementation the supervisor followed the same segment/page organization as the user

Bad points:

  • It seems that the segment management is too complicated, introducing some overhead.
  • As files and segments are identical the system is not able to make
    the difference between temporal and persistent data. For example,
    several temporal data don’t need to be stored in the secondary storage.
    Another drawback happens for sophisticated software such as DBM: one
    can not guarantee the integrity of the data, because one doesn’t have
    control when input/output happens.

Analysis

Several good ideas such as dynamic linking, flexible virtual memory,
security by design, hierarchical file system are used in all nowadays
operating systems. Multics is also the first operating system written
in a high level language.
But there is a severe drawback of providing powerful facilities such as
virtual memory: it becomes easy for a programmer to unintentionally
trigger very expensive operations.