Virtual Memory
Virtual Memory
Virtual memory is a model—one of many possible models—for managing the resource of physical memory, or main memory. Such management is necessary because a microprocessor, the heart of a computer, has direct access only to main memory, while all programs and data are stored on permanent media such as hard disks.
Reading or writing main memory is as simple as executing a single computer instruction. In contrast, any access to hard disks, digital versatile discs (DVDs), compact discs-read only memory (CD-ROMs), or floppy disks is indirect and requires relatively complex communication protocols involving dozens to thousands of computer instructions. Therefore, accessing a file or running a program requires that the data on disk first be moved into main memory. Virtual memory is one method for handling this management of data. To illustrate what it is and how it differs from other possibilities, we will compare it to several alternatives.
Memory-Management Alternatives
In the simplest model of program creation and execution, physical addressing, a programmer determines what physical memory is available, reserves it so that no one else uses it, and writes a program to use the reserved memory locations. This allows the program to execute without any runtime support required from the operating system. However, because a program is not likely to use the same physical location on every invocation, this requires a rewrite of the program every time it runs—a tedious task, but one that could be left to the operating system. At process start-up, the operating system could modify every pointer reference in the application (including loads, stores, and absolute jumps such as function calls) to reflect the physical address at which the program is loaded. The program as it resides in main memory references itself directly and so contains implicit knowledge about the structure and organization of the physical memory. This model is depicted in Figure 2. A program sees itself exactly as it resides in main memory.
A second model, base offset addressing, involves writing the program once using pointer addresses that are not absolute but are instead relative offsets from the beginning of the program. If the location of the program in physical memory is a variable stored in a known hardware register, at runtime one can load the program wherever it fits in physical memory and place this location information in the known register so that all memory references first incorporate this base address and are then redirected to the correct physical location. This model is depicted in Figure 3. The process sees itself as a contiguous region or set of contiguous regions, each with its physical location stored in a known hardware register. The advantage is that, as opposed to the previous scheme, knowledge of the memory-system organization is not exposed to the program. The disadvantage is that the program must be divided into a relatively small number of contiguous segments, and each segment must fit entirely in main memory if it is to be used.
A third model, virtual addressing, involves writing the program as if it is loaded at physical memory location zero, loading the program wherever it fits (not necessarily location zero), and using some as-yet-undefined mechanism to translate the program's addresses to the equivalent physical addresses while it is running. If the translation granularity is relatively small (that is, the program is broken down into smaller pieces that are translated independently of each other), the program can even be fragmented in main memory. Bits and pieces of the program can lie scattered throughout main memory, and the program need not be entirely resident to execute. This model is depicted in Figure 4. The advantage of this scheme is that one never needs to rewrite the program. The disadvantage is the potential overhead of the translation mechanism.
Physical addressing can be implemented on any hardware architecture; base offset addressing can be implemented on any architecture that has the appropriate addressing mode or address-translation hardware; and virtual addressing is typically implemented on microprocessors with memory-management units (MMUs). The following paragraphs discuss the relative merits of the three models.
Physical Addressing.
In physical addressing, program execution behaves differently every time the program is executed on a machine with a different memory organization, and it is likely to behave differently every time it is executed on the same machine with the same organization, because the program is likely to be loaded at a different location every time. Physical addressing systems outnumber virtual addressing systems. An example of a physical addressing system is the operating system for the original Macintosh, which did not have the benefit of a memory-management unit. Though later Macintosh systems added an optional virtual memory implementation, many applications require that the option be disabled during their execution for performance reasons. The newest version of the Macintosh operating system, Mac OS X, is based on a UNIX core and has true high-performance virtual memory at its heart.
The advantages of the physically addressed scheme are its simplicity and performance. The disadvantages include slow program start-up and decreased flexibility. At start-up, the program must be edited to reflect its location in main memory. While this is easily amortized over the run-time of a long-running program, it is not clear whether the speed advantages outweigh this initial cost for short-running programs. Decreased flexibility can also lead to performance loss. Since the program cannot be fragmented or partially loaded, the entire program file must be read into main memory to execute. This can create problems for systems with too little memory to hold all the running programs.
Base Offset Addressing.
In base offset addressing, like physical addressing, program execution behaves differently every time the program is executed. However, unlike physical addressing, base offset addressing does not require a rewrite of the program every time it is executed. Base offset systems far outweigh all other systems combined: an example is the DOS/Windows system running on the Intel x86. The Intel processor architecture has a combined memory management unit that places a base offset design on top of a virtual addressing design. The architecture provides several registers that hold "segment" offsets, so a program can be composed of multiple regions, each of which must be complete and contiguous, but which need not touch each other.
The advantages of this scheme are that the code needs no editing at process start-up, and the performance is equal to that of the physical addressing model. The disadvantages of the scheme are similar to physical addressing: A region must not be fragmented in main memory because this can be problematic when a system has many running programs scattered about main memory.
Virtual Addressing.
In virtual addressing, program execution behaves identically every time the program is executed, even if the machine's organization changes, and even if the program is run on different machines with wildly different memory organizations. Virtual addressing systems include nearly all academic systems, most UNIX-based systems such as Mac OS X, and many UNIX-influenced systems such as Windows NT and Windows 2000. The advantages of virtual memory are that a program needs no rewrite on start-up, one can run programs on systems with very little memory, and one can easily juggle many programs in physical memory because fragmentation of a program's code and data regions is allowed. In contrast, systems that require program regions to remain contiguous in physical memory might be unable to execute a program because no single unused space in main memory is large enough to hold the program, even if many scattered unused areas together would be large enough. The disadvantage of the virtual addressing scheme is the increased space required to hold the translation information and the performance overhead of translating addresses. These overheads have traditionally been no more than a few percent.
Now that the cost of physical memory, DRAM , has decreased significantly, the schemes that use memory for better performance—physical and base offset addressing—have become better choices. Because memory is cheap, perhaps the best design is now one that simply loads every program entirely into memory and assumes that any memory shortage will be fixed by the addition of more DRAM. However, the general consensus is that virtual addressing is more flexible than the other schemes, and its overhead is accepted as reasonable. Moreover, it seems to provide a more intuitive and bug-free paradigm for program design and development than the other schemes.
How Are Virtual Addresses Translated?
In the virtual addressing model, programs execute in imaginary address spaces that are mapped onto physical memory by the operating system and hardware. Executing programs generate instruction fetches, loads, and stores using imaginary or "virtual" addresses for their instructions and data. The ultimate home for the program's address space is backing store, usually a disk drive. This is where the program's instructions and data originate and where all of its permanent changes go. Every hardware memory structure between the central processing unit (CPU) and the backing store is a cache— temporary storage—for the instructions and data in the program's address space. This includes main memory. Main memory is nothing more than a cache for a program's virtual address space. Everything in the address space initially comes from the program file stored on disk or is created on demand and defined to be zero. Figure 5 illustrates this.
In Figure 5(a), the program view is shown. A program simply makes data loads stores, and implicit instruction fetches to its virtual address space. The address space, as far as the program is concerned, is contiguous and held completely in main memory, and any unused holes between objects in the space are simply wasted space.
Figure 5(b) shows a more realistic picture. There is no linear storage structure that contains a program's address space, especially since every address space is at least several gigabytes when one includes the unused holes. The address space is actually a collection of fixed-sized "pages" that are stored piecemeal on disk or conjured up out of thin air. The instructions and initialized data can be found in the program file, and when the running program needs extra workspace, the operating system can dynamically allocate new pages in main memory. The enabling mechanism is the page table. This is a database managed by the operating system that indicates whether a given page in a program's address space is found on disk, needs to be created from scratch, or can be found in physical memory at some location. Every virtual address generated by the program is translated according to the page table before the request is sent to the memory system. To speed access to the page table, parts of it are held temporarily in hardware. This is one of the functions of a memory-management unit.
Virtual memory is but one of many models of program creation and execution and one of many techniques to manage one's physical memory resources. Other models include base offset addressing and physical addressing, each of which offers performance advantages over virtual addressing but at a cost in terms of flexibility. The widespread use of virtual memory in contemporary operating systems is testimony to the fact that flexibility is regarded as a valuable system characteristic, outweighing any small amount of performance loss.
see also Generations, Computers; Memory; Operating Systems.
Bruce Jacob
Bibliography
Apple Computer, Inc. Technical Introduction to the Macintosh Family, 2nd ed. Reading, MA: Addison-Wesley, 1992.
——. Inside Mac OS X: System Overview. Cupertino, CA: Apple Computer, Inc., 2000.
Custer, Helen. Inside Windows NT. Redmond, WA: Microsoft Press, 1993.
Duncan, Ray, et al. Extending DOS—A Programmer's Guide to Protected-Mode DOS, 2nd ed. Reading, MA: Addison-Wesley, 1994.
Jacob, Bruce, and Trevor Mudge. "Virtual Memory: Issues of Implementation." IEEE Computer 31, no. 6 (1998): 33–43.
——. "Virtual Memory in Contemporary Microprocessors." IEEE Micro 18, no. 4 (1998): 60–75.