eugene@ames.UUCP (Eugene Miya) (09/17/86)
I don't have a lot of time, but I just happened to have a conversation
with Peter Denning, and I noted the current discussion. He asked that
I forward the articles posted (you guys). Here is his response:
Received: from hydra.riacs.edu by ames-nas.ARPA; Tue, 16 Sep 86 17:24:11 pdt
From: Peter Denning <pjd@riacs.edu>
Message-Id: <8609170024.AA01249@hydra.riacs.edu>
To: eugene@riacs.edu
Subject: Virtual Memory
Status: R
Eugene,
Here is the text of a short article defining virtual memory
written for Ralston's Encyclopedia in 1976 and revised for
the edition of 1983. It answers many of the questions your
friends have raised in net.arch and responds to the (old)
objections that virtual memory is not needed in view of the
impending arrival of boundless real memory. The pictures
cannot be included here, but the text is descriptive enough.
---------------------------------------------------------
VIRTUAL MEMORY
Peter J. Denning
This is the text of an article from
Encyclopedia of Computer Science
Second Edition
Ralston & Reilly, Eds.
Van Nostrand, 1983, pages 1560-63
The term virtual memory (or virtual storage)
denotes the memory of a virtual (i.e., simulated)
computer. An address (or name) space N of a pro-
gram is the set of all addresses that can be gen-
erated by the processor as it executes the pro-
gram; if the processor generates a-bit addresses,
N contains at most 2**a bytes (or words). The
name space N is frequently referred to as the
``virtual address space'' or the ``virtual
memory'' within which the processor operates. The
memory space M of the machine is the set of all
real location addresses recognized by the main
memory hardware; if this hardware recognizes b-bit
addresses, M contains 2**b bytes (or words).
As shown in Figure 1, an address transla-
tion mechanism is interposed between the processor
and memory. This mechanism uses a mapping table,
f, that specifies the correspondence between vir-
tual addresses (in N) and real addresses (in M).
If the mapping table entry for a given virtual
address is marked as ``undefined'', the mapper
will generate an addressing fault in case the pro-
cessor attempts reference to that address. The
fault handler will locate the missing information
in the auxiliary memory, move it into main memory
(perhaps also moving out other information to make
room), and update the table f to show the changes.
Then, when the interrupted program is resumed, it
will find the required table entry defined and can
proceed.
An example of the scheme of Figure 1 is
the core/drum configuration, in which M is a core
memory and A is a drum. Another example is the
cache/core configuration, in which M is a high-
speed semiconductor register memory (called a
cache) and A is a core memory or a slow-speed sem-
iconductor memory.
Virtual memory solves the relocation prob-
lem because it permits program pieces to be moved
around in memory without altering their virtual
addresses. It solves the memory protection prob-
lem because each program piece can have its own
access mode. In case the size of N exceeds the
size of M, the virtual memory system also solves
the memory management problem by determining which
subset of N will reside in M. The CDC 6000 series
illustrates that N can be smaller than M, although
in this case N is not called ``virtual memory''.
IMPLEMENTATION. The map f is usually a
directly indexed table. Its entries correspond to
program blocks rather than individual virtual
addresses. The blocks are normally used both as
units of auxiliary memory storage and as units of
transfer. Each block of N is a set of contiguous
addresses with a base address and a length. A
virtual address x must be represented (or
translated to) the form (b,w), where b is a block
index and w is an offset (relative address) in
block b. The mapping table's entry for block b,
denoted f(b), gives the base of the block of M
containing b. The translation process consists of
three steps:
x --> (b,w) --> (f(b),w) --> f(b)+w,
as shown in Figure 2. The translation of x to
(b,w) takes time T1; the translation of (b,w) to
(f(b),w) takes time T2; (the time to look up f(b)
in the table); and the translation of (f(b),w) to
f(b)+w takes time T3.
The translation function would be imprac-
tical unless the total translation time T1+T2+T3
can be made small compared to the main memory
reference time. Because the time to add two
numbers is small, the efficiency of the transla-
tion operation actually depends on T1+T2.
The two most common methods of making T1
negligible or zero are segmentation and paging. A
segmented name space is partitioned into blocks of
various sizes (segments), usually corresponding to
logical regions. In the Burroughs B5000 and later
series, for example, the Algol compiler creates
segments corresponding to the block structure of
the language and the organization of the data.
(Organick, 1973) The Honeywell 6180 (which
implements a segmented name space under Multics)
requires the programmer to define the segments and
refer to operands by symbolic two-part addresses
of the form (segment-name, offset-name). (Organ-
ick, 1972) A paged name space is partitioned into
blocks of the same size (pages). Since the page
boundaries bear no prior relation to logical boun-
daries in the name space, the programmer is not
generally apprised of the pagination of his name
space; however, the compiler or loader may be
designed to reorganize information among pages to
improve performance when the cost of such reorgan-
ization (which is high) can be justified.
Paging's principal attraction has been its simple
design.
Under segmentation, the address space is
partitioned into regions by the programmmer or
compiler; each region becomes a block. In this
case all virtual memory references are programmed
or compiled in the form of pairs (b,w). Thus,
T1=0 when segmentation is used.
Under paging, the address space is parti-
tioned into blocks all of the same size, say s
bytes. All addresses compiled in the program are
linear offests relative to the base of the name
space. The computation x --> (b,w) is specified
by
(b,w) = ([x/s], x mod s),
where the brackets denote ``integer part of''
and x mod s denotes the remainder in dividing x by
s 0 <= x mod s < s. If s=2**q (for some q>=0) and
binary arithmetic is used, this computation is
trivial: w is specified by the q low-order bits of
the register containing x and b is specified by
the remaining bits. Thus T1=0 when paging is
used.
This leaves T2 as the only time of signifi-
cance in a paging or segmentation scheme. Most
systems do not provide special, high-speed memory
for storing the entire mapping table. Accord-
ingly, the time T2 would seem to be comparable
with the main memory reference time, and the
objective of making T1+T2. small would seem to be
unrealizable. An ingenious solution has been
found. A small associative memory, typically con-
taining at most 16 cells, is included in the map-
ping mechanism. Its reference time is much faster
than the main memory's. Each associative cell
contains an entry of the form (x, f(x)). When the
block number b of an address is determined, all
the cells of the associative memory are searched
in parallel using b as a key. If an entry (b,
f(b)) is found, the base address f(b) of the block
is available immediately without reference to the
mapping table in main memory. Otherwise the map-
ping table is accessed and an entry (b, f(b))
replaces the least recently used entry in the
associative memory. Experience has shown that the
mean address translation time is typically in the
range 1% to 3% of the main memory reference time
with the associative memory in operation.
Most commercial virtual memory systems
employ paging. This is because the addressing
mechanism is especially simple and because manag-
ing block allocation and transfer in both the main
and auxiliary memories is especially easy if all
blocks are of the same size. However, the page
size must be chosen carefully. Too small a page
size will produce large mapping tables and a
greater rate of page transfer between main and
auxiliary memory. Too large a page size will pro-
duce poor storage utilization, since only a por-
tion of the bytes on a page are likely to be
referenced during its residence in main memory.
Paging alone, even if properly designed, does not
alter the linearity of the name space, and thus
cannot offer the programmer the significant pro-
gramming advantages possible in a segmented name
space. A compromise using both segmentation and
paging can be implemented for this purpose (see
Denning 1970).
Memory protection is easily implemented
within a virtual memory mechanism. This is, in
fact, one of the main attractions of virtual
memory. No program can access any information
other than what is in its address space because
each and every reference is translated with
respect to the mapping table of the currently run-
ning program. Also, each entry of the mapping
table is actually of the form
b: (d, f(b), pc, L),
where d is a single bit set to 1 if and only if
f(b) is defined, pc is a protection code indicat-
ing which types of access are permitted to block b
(e.g., read or write), and L is the length of
block b (omitted in paging systems). If the
offset portion w of the (b,w) address does not
satisfy 0<=w<L, or if the type of access being
attempted is not authorized by pc, a protection
interrupt is generated by the mapping mechanism.
(See Wilkes 1975.)
PERFORMANCE. The associative memory prevents
address translation time from being an important
factor in the efficiency of program execution in a
virtual memory. The factors that affect perfor-
mance are, in decreasing order of their signifi-
cance, the size of the main memory space allocated
to the program, locality of reference of the pro-
gram, and the memory policy used (the paging algo-
rithm in a paging system). The first and third
factors are under the system's control, whereas
the second is under the programmer's control.
(Sometimes the compiler can assist in improving
the second factor.) Most memory management poli-
cies tend to keep the most recently referenced
blocks of the name space N in the main memory
space allocated to a program, and to adjust the
size of this space to be as small as possible
without causing an undue rate of addressing
faults.
Although it is true that most virtual
memory systems present the programmer with a large
linear name space and handle the memory management
for him, it is not true that the virtual memory
behaves as a random access store. The nature of
the memory management policies causes the access
time to an object in the virtual memory to be
short when the object or a neighbor has been
referenced recently, and long otherwise. The pro-
grammer, therefore, can be confident of highly
efficient operation of his program in a virtual
memory only if he has successfully organized his
algorithm and data to maximize ``locality of
reference.'' (This means that references are
clustered to small groups of objects for extended
intervals.)
HISTORY AND PROSPECTS. Virtual memories have been
used to meet one or more of four needs:
1. Solving the overlay problem that arises
when a program exceeds the size of the main
store available to it. Paging on the Atlas
machine at the University of Manchester
(1959) was the first example.
2. Storing variable-size program objects off
the run time stack. The size of local arrays
in Algol, for example, may not be known at
compile time; storing them in segments else-
where, with fixed-size descriptors on the
stack, permits the compilation of addresses.
Segmentation on the Burroughs B5500 (1963)
was the first example.
3. Long term storage of files and segments
forces the programming of information
transfers between the file system and the
virtual memory. The Multics virtual memory
(1968) eliminated this by merging the two
storage systems. Users can declare their own
segments and keep them indefinitely in the
address space.
4. Memory protection requires that references
to segments be in range and conform to
enabled access modes (read, write, or exe-
cute). These constraints are easily checked
by the hardware in parallel with the main
computation. Several experimental machines
have been designed explicitly to study
descriptor-based addressing as a means of
memory protection and improved software reli-
ability (Myers, 1978).
It is sometimes argued that advancing memory
technology will soon permit us to have all the
real memory we could possibly want and, hence, we
will soon be able to dispense with virtual memory.
It has long been a favorite assumption of operat-
ing systems prognosticators that resources will by
next year be plentiful. Users' ambitions for new
ways of using resources have, however, continually
defied this assumption. It is unlikely that
today's predictions of the passing of the overlay
problem will prove to be any more reliable than
similar predictions made in 1960, 1965, 1970, and
1975.
What is true is that paged virtual stores,
which were invented as a simple solution to the
overlay problem, will diminish in utility as the
last three needs in the list above become critical
parts of programming environments. Virtual
memories of the future will rely more on segmenta-
tion and tagged memory to achieve greater software
error tolerance and to narrow the semantic gap
between concepts of programming languages and con-
cepts embodied in hardware.
REFERENCES
1970. Denning, P. J., ``Virtual memory,'' Comput-
ing Surveys 2, 3 (September), 153-189.
1972. Organick, E. I., The Multics System: An
Examination of Its Structure, MIT Press.
1973. Organick, E. I., Computer System Organiza-
tion: The B5700/B6700 System, Academic Press.
1975. Wilkes, M. V., Time Sharing Computer Sys-
tems (3rd Ed.), Elsevier/North-Holland.
1976. Denning, P. J., ``Fault tolerant operating
systems,'' Computing Surveys 8, 3 (December).
1978. Myers, G. J., Advances in Computer Archi-
tecture, Wiley.
_______________________________________
Have fun.
From the Rock of Ages Home for Retired Hackers:
--eugene miya
NASA Ames Research Center
com'on do you trust Reply commands with all these different mailers?
{hplabs,ihnp4,dual,hao,decwrl,tektronix,allegra}!ames!aurora!eugene
eugene@ames-aurora.ARPA
"Fill this space with your favorite Woody Allen quote." 8-)