Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP Path: utzoo!mnetor!seismo!lll-crg!nike!aurora!ames!eugene From: eugene@ames.UUCP (Eugene Miya) Newsgroups: net.arch Subject: Re: paging, virtual memory, and everything... Message-ID: <1658@ames.UUCP> Date: Tue, 16-Sep-86 20:58:35 EDT Article-I.D.: ames.1658 Posted: Tue Sep 16 20:58:35 1986 Date-Received: Wed, 17-Sep-86 01:57:49 EDT References: <826@hou2b.UUCP> <5100132@ccvaxa> Organization: NASA-Ames Research Center, Mtn. View, CA Lines: 378 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 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