Paper Evaluations: 05-24-2000

Flavio P JUNQUEIRA (flavio@cs.ucsd.edu)
Wed, 24 May 2000 23:32:32 -0700 (PDT)

Title: "The Multics Virtual Memory: Concepts and Design"

The Multics virtual memory was designed with two main goals: all
on-line information can be accessed by the processor and consequently
by any computation, and it must be possible to control access to
on-line information on a per-reference basis. In Multics, all on-line
information is referenced as variable-size segments. Each segment is
visible to all processes, but the right to access the data in the
segment depends on its attributes. In this way, processes create
segments which may be shared by other processes, thereby avoiding data
copying.

Because all segments existing in a given moment may not fit in memory,
it is necessary to have a backing store to swap data with main memory.
The segment, however, is not the unit used to swap to the backing
store. Segments are divided in fixed-size pages and the pages are the
units swapped to the backing store. This approach avoids external
fragmentation, since the space required to bring a page from the
backing store is the same as the space used by the page removed from
main memory. Moreover, it promotes locality of reference.

Since the processes reference segments and not pages, a mechanism has
to be provided so that segment references are translated to page
references. This mechanism is supported by the underlying hardware
used in the experiments with Multics. The segments are created with
symbolic names. Each symbolic name represents a pathname, which
determines a path in a directory hierarchy. The directory hierarchy is
organized as a tree structure and it is used to store the attributes of
the segments. An important aspect of this approach is that all the
symbolic names are unique in the system. Each process knows how to map
symbolic names to segment numbers. Thus, in each reference, a symbolic
name and an index are provided. The segment number associated with the
symbolic name is used to determine the correct segment descriptor
entry. After this entry is determined, the index is used to determine
the correct page and the position in this page that corresponds to
the data being accessed.

Segments are also used by the Multics supervisor to provide services
to the various processes. Every process knows the supervisor segments,
and hence have controlled access to supervisor functions. Among these
functions provided is the manipulation of segment attributes. Another
important service provided by the supervisor is segment and page fault
handling. Several data structures are required to keep track of the
current status of processes in the system, to determine the active
segments, and to decide the pages that are swapped to disk during page
faults.

In my opinion, the paper is very dense, in the sense that in some
parts it is difficult to understand how the mechanism works because of
the number of elements being described. In terms of performance, it
seems that the data structures required in the virtual memory
subsystem increases the overhead of the operating system. Therefore, a
evaluation is necessary to determine the overall impact of this
overhead.

--------------------------------------------------------------------------

Title: "Machine-independent Virtual Memory Management for Paged
Uniprocessor and Multiprocessor Architectures"

This paper describes virtual memory design and implementation in the
Mach operating system. The virtual memory subsystem in Mach was
designed to be independent of the underlying hardware, so that the
system can be easily ported to different architectures. Moreover, the
virtual memory subsystem was designed to be portable for both
uniprocessor and multiprocessor architectures.

In Mach, a large address space is provided for each task. A task is an
execution environment for a set of threads. Two threads can
communicate by sending messages to each other port. Mach inherited this
message-passing facility from its predecessor Accent. Compared to
other systems, message-passing is efficient in Mach due to the
integration of the VM subsystem and the message-oriented communication
facility. In addition, Mach provides the abstraction of memory
object. Memory objects are collections of data, which implement the
backing store. Because some memory objects may be permanent, they also
implement memory-mapped files. Every memory object has a port
associated, so that operation requests can be delivered to it.

Compared to other systems, allocation in the large address space of a
task can be sparse due to the mapping of virtual addresses. Virtual
addresses are mapped to memory objects by a double-linked list in each
task called address map. A pager is associated with each memory object
and it is responsible for handling page faults and page-out
requests. Pagers are tasks executing at the user level, thereby
following the modular approach promoted by Mach.

Different tasks may share memory objects. If a memory object is copied
from a task to another, copy-on-write can be used to improve
performance. Since the unit of management is a memory object, it is
necessary to create shadow objects, which contain the modified pages
of a memory object copied using copy-on-write. In the case that tasks
share a memory region, the memory object data structure is not
appropriate for managing the memory region, because it may involve
mapping of several memory objects. Thus, sharing maps are used
instead.

In my opinion, the proposal of a portable VM subsystem is very good.
The paper, however, is not well written. It is very difficult to
understand how the mechanisms are implemented and the relation between
the parts of the system. In several parts, we have to guess what the
authors are trying to say, since they do not provide sufficient
information. On the other hand, it is interesting the observation that
the VM subsystem proposed does not degrade system performance. Compared
to Unix, Mach VM subsystem performed even better.

--Flavio Junqueira.

------------------------------------------------------------
Flavio Paiva Junqueira, PhD Student
Department of Computer Science and Engineering
University of California, San Diego

Office location: AP&M 4349 e-mail: flavio@cs.ucsd.edu
------------------------------------------------------------