Information about Virtual Memory

This article is about the computer term. For the TBN game show, see Virtual Memory (game show).

Virtual memory is an abstraction implemented in a computer that gives an application program the impression it has contiguous working memory, while in fact it is physically fragmented, and may even overflow onto disk storage. While virtual memory is a revolutionary approach for programmers, the benefits for an end-user are only indirect, including quickly developed, more flexible, and simpler programs. All modern general purpose computer operating systems provide virtual memory for ordinary applications, like word processors, spreadsheets, multimedia players, etc. Older operating systems, such as DOS of the 1980s, or mainframe operating systems of the 1960s, had no virtual memory functionality.

Memory is called "virtual" due to an analogy with optics: virtual images in optics (such as the image in a mirror) appear to be real but actually don't exist.

An important note is that virtual memory is not just "using disk space to extend physical memory size". Such goal is now often achieved with paging technique, and in the past with overlay technique, but it is not a core of a virtual memory concept.

Technically, virtual memory is an addressing scheme implemented in hardware and software that allows non-contiguous memory to be addressed as if it were contiguous. All current implementations of virtual memory support two operating system features:

1. Residency on reference - A memory location can be addressed that does not currently reside in physical memory. The hardware and operating system will load the required data from auxiliary storage automatically, in a manner completely invisible to the program addressing the memory. This allows a program to naturally reference more main memory than actually exists in the computer.
2. Isolation - A multi-tasking system can provide multiple virtual address spaces with total memory isolation between them. Every task (except the lowest level operating system) can have its own private address space and thus can be naturally isolated from other tasks altering the memory contents. Isolation increases reliability by isolating faults within a specific task and preventing a task from interrupting other tasks.

Overview

In x86 architecture, hardware has two methods of addressing RAM, real and virtual.

• In real mode, memory address registers contain an integer that addresses a word or byte of RAM. The memory is addressed sequentially: if a program increments the address register by n, the location of the memory being addressed moves forward by n.
• In virtual mode, memory is divided into pages, usually 4096 bytes long. These pages may reside in any available RAM location that can be addressed in virtual mode. Memory address registers are divided into an index and an offset: the high-order bits represent the index, and the lower-order bits represent the offset. The index is an offset within the page-mapping table (which resides at a known address in memory), each of whose entries contains the starting real addresses of the corresponding page. The offset represents a location within the page specified by the offset, and can range from 0 to 1 less than the page size (with a page size of 4096, between 0 and 4095). The virtual address is resolved by looking up the index in the page table -- yielding a physical page address -- and then adding the offset to the physical address.

The size of the tables is governed by the architecture and amount of RAM. All virtual addressing schemes require the page tables to start at either a fixed location or one identified by a register. In a typical computer, the first table is an array of addresses, each of which denotes the start of the next array. The index into the first array is determined by certain high-order bits of the contents of the memory address register. Depending on the architecture, each array entry can be any size the computer can address. The next bits in the memory address register are an index into the array denoted by the first index. This set of arrays of arrays can be repeated, limited by the size of the memory address register. The number of tables and the size of the tables vary by architecture, but the overall goal of virtual addressing is to transform the high order bits of the virtual address in the memory address register into an entry in the page table that either points to the location of the page in physical memory or to a flag that indicates the page is not available.

Paging

Main article: Paging

Paging, in a meaning narrower than implementing the paged memory concept, refers to moving pages between memory and disk. If a program references a memory location within a page that is not available, the hardware generates a page fault. When this occurs, the memory management hardware invokes an operating system routine that loads the required page from auxiliary storage (e.g., a paging file on disk) and turns on the flag that indicates the page is available. The hardware then adds the offset denoted by the low-order bits in the address register to the start location of the physical page, accesses the requested memory location, and returns control to the application that originally tried to access the memory. This process takes place transparently to the application addressing the memory.

Historically, a number of systems implemented virtual memory without paging, most notably the PDP-11, but also machines like the GE-645, which supported both paged and unpaged segments. It is also theoretically possible to build a system with paged memory but without virtual memory. Pages would be used simply for memory allocation and accessed with physical, non-translated address.

Translating the memory addresses

To minimize the performance penalty of address translation, most modern CPUs include an on-chip memory management unit (MMU) and maintain a table of recently used virtual-to-physical translations, called a Translation Lookaside Buffer (TLB). Translating an address that has an entry in the TLB requires no additional memory reference (and therefore time). However, the TLB can only contain a limited number of mappings between virtual and physical addresses. When the translation for the requested address is not resident in the TLB, the hardware will have to perform the translation and load the result into the TLB.

On some processors, address translation is performed entirely in hardware; the MMU has to make additional memory references to load the required translations from the translation tables, but no other action is needed. In other processors, assistance from the operating system is needed: the hardware raises an exception, and the operating system handles it by replacing a TLB entry with an entry from the primary translation table, and the instruction that made the original memory reference is restarted.

Memory protection

Hardware that supports virtual memory almost always in addition implements memory protection mechanisms. The MMU may have the ability to vary its operation according to the type of memory reference (for read, write or execution) and the privilege mode of the CPU at the time the memory reference was made. This allows the operating system to protect its own code and data (such as the translation tables used for virtual memory) from corruption by an erroneous or malicious program, to protect programs from each other, and (to some extent) to protect programs from themselves (e.g. by preventing writes to areas of memory that contain code).

History

In the 1940s and 1950s, before the development of a virtual memory, all larger programs had to contain logic for managing two-level storage (primary and secondary, today's analogies being RAM and hard disk), such as overlaying techniques. Programs were responsible for moving overlays back and forth from secondary storage to primary.

The main reason of introducing virtual memory was therefore not simply extend a primary memory, but to make such extension as easy to use for programmers as possible.

Many systems already had the ability of dividing the memory between multiple programs (required for multiprogramming and multiprocessing), provided for example by "base and bounds registers" on early PDP-10 and System/360, without in any way providing virtual memory. Some systems provided a memory protection in the same way, preventing one process from modifying another's code or data.

Systems also had also the ability to relocate a program, as opposed to compiling a program to use one fixed physical memory location only. For example the KA-10 model of the PDP-10, which gave each program a private address space starting at location 0, but had no support for virtual memory.

Virtual memory was developed in approximately 1959–1962, at the University of Manchester for the Atlas Computer, completed in 1962. However, Fritz-Rudolf Güntsch, one of Germany's pioneering computer scientists and later the developer of the Telefunken TR 440 mainframe, claims to have invented the concept in 1957 in his doctoral dissertation Logischer Entwurf eines digitalen Rechengerätes mit mehreren asynchron laufenden Trommeln und automatischem Schnellspeicherbetrieb (Logic Concept of a Digital Computing Device with Multiple Asynchronous Drum Storage and Automatic Fast Memory Mode).

In 1961, Burroughs released the B5000, the first commercial computer with virtual memory.^[1] It was based on the segmentation, not paging.

Like many technologies in the history of computing, virtual memory was not accepted without challenge. Before it could be implemented in mainstream operating systems, many models, experiments, and theories had to be developed to overcome the numerous problems with virtual memory. Specialized hardware had to be developed to translate virtual addresses to physical addresses in primary or secondary memory. Some worried that this process would be expensive, hard to build, and take too much processor power to do the address translation.^[2]

By 1969 the debate over virtual memory for commercial computers was over.^[2] An IBM research team led by David Sayre showed that the virtual memory overlay system consistently worked better than the best manually controlled systems.

Possibly the first minicomputer to introduce virtual memory was the Norwegian NORD-1 minicomputer. During the 1970s, other minicomputer models such as VAX models running VMS implemented virtual memories.

The difference between virtual memory implementations using pages and using segments is not only about the memory division with fixed and variable sizes, respectively. In some systems, e.g. Multics, or later System/38 and Prime machines, the segmentation was actually visible to the user processes, as part of the semantics of a memory model. In other words, instead of a process just having a memory which looked like a single large vector of bytes or words, it was more structured. This is different from using pages, which doesn't change the model visible to the process. This had important consequences.

It wasn't just a "page with a variable length", or a simple way to lengthen the address space (as in Intel 80286). In Multics, the segmentation was a very powerful mechanism that was used to provide a single-level virtual memory model, in which there was no differentiation between "process memory" and "file system" - a process' active address space consisted only a list of segments (files) which were mapped into its potential address space (both code and data). It is not the same as the later mmap in Unix, because inter-"file" pointers (both code and data) don't work if people are mapping files into semi-arbitrary places, at least not without a lot of extra instructions as overhead. Multics could perform relocated inter-segment references as an built-in addressing mode on most instructions, that worked even if different processes mapped the same file into different places in different private address spaces (see the "Multics" book by Organick).

Virtual memory was introduced to the x86 architecture with the protected mode of the Intel 80286 processor. At first it was done with segment swapping, which became inefficient with larger segments. The Intel 80386 introduced support for paging underneath the existing segmentation layer. The page fault exception could be chained with other exceptions without causing a double fault.

See also

• Physical memory and its physical address
• Memory address
• Address space
• CPU design
• Virtual address space
• Page (computing)
• Page table
• Paging
• Working set
• Segmentation (memory)
• Memory management
• Memory management unit
• Memory allocation
• System/38
• Protected mode, a x86's name of virtual memory addressing

References

• John L. Hennessy, David A. Patterson, Computer Architecture, A Quantitative Approach (ISBN 1-55860-724-2)
• Virtual Memory Secrets by Murali

External links

• Linux Memory Management
• Linux Kernel Mailing List Discussion
• Pointers to virtual memory visualizations

This article was originally based on material from the Free On-line Dictionary of Computing, which is licensed under the GFDL.