Virtual memory

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

The program thinks it has a large range of contiguous addresses, but in reality the parts it is currently using are scattered around RAM, and the inactive parts are saved in a disk file.

In computing, virtual memory is a memory management technique developed for multitasking kernels. This technique virtualizes a computer architecture's various hardware memory devices (such as RAM modules and disk storage drives), allowing a program to be designed as though:

• there is only one hardware memory device and this "virtual" device acts like a RAM module.
• the program has, by default, sole access to this virtual RAM module as the basis for a contiguous working memory (an address space).

Systems that employ virtual memory:

• use hardware memory more efficiently than systems without virtual memory.
• make the programming of applications easier by:
  • hiding fragmentation.
  • delegating to the kernel the burden of managing the memory hierarchy; there is no need for the program to handle overlays explicitly.
  • obviating the need to relocate program code or to access memory with relative addressing.

Memory virtualization is a generalization of the concept of virtual memory.

Virtual memory is an integral part of a computer architecture; all implementations (excluding emulators and virtual machines) require hardware support, typically in the form of a memory management unit built into the CPU. Consequently, older operating systems (such as those for the mainframes of the 1960s and early 1970s and personal computer operating systems of the early to mid 1980s such as DOS) generally have no virtual memory functionality, though notable exceptions for mainframes of the 1960s and early 1970s include the Atlas Supervisor for the Atlas, the MCP for the Burroughs B5000, TSS/360 and CP/CMS for the IBM System/360 Model 67, Multics for the GE 645, the Time Sharing Operating System for the RCA Spectra 70/46, and VM/370, OS/VS1, OS/VS2 (SVS), and MVS for IBM System/370 mainframe systems of the early 1970s, and for personal computer operating systems of the 1980s include the operating system for the Apple Lisa.

Embedded systems and other special-purpose computer systems that require very fast and/or very consistent response times may opt not to use virtual memory due to decreased determinism; virtual memory systems trigger unpredictable interrupts that may produce unwanted "jitter" during I/O operations. This is because embedded hardware costs are often kept low by implementing all such operations with software (a technique called bit-banging) rather than with dedicated hardware. In any case, embedded systems usually have little use for complicated memory hierarchies.

History

In the 1940s and 1950s, before the development of virtual memory, all larger programs had to contain logic for managing two levels of storage (primary and secondary); one such management technique is overlaying. The main reason for introducing virtual memory was therefore not simply to extend primary memory, but to make such an extension as easy as possible for programmers to use.

To allow for multiprogramming and multitasking, many early systems already had the ability to divide the memory between multiple programs even without providing virtual memory; for instance, early models of the PDP-10 provided memory access through what are called base and bounds registers.

Paging was first developed at the University of Manchester as an economical way to extend the Atlas Computer's working memory by transparently supplementing its 16 thousand words of primary core memory with the additional 96 thousand words of secondary drum memory. Although the first Atlas was commissioned in 1962, working prototypes of paging had reportedly been developed by 1959. Also, Burroughs independently released in 1961 the first commercial computer with virtual memory, the B5000, which used segmentation rather than 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 numerous problems. Dynamic address translation required expensive specialized hardware that was difficult to build. Moreover, initial implementations slightly slowed down access to memory. There were also worries that new system-wide algorithms utilizing secondary storage would be less effective than previously used application-specific algorithms.

By 1969 the debate over virtual memory for commercial computers was over. An IBM research team led by David Sayre showed that their virtual memory overlay system consistently worked better than the best manually controlled systems. {{citation}}: Empty citation (help)

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

Virtual memory was introduced to the x86 architecture with the protected mode of the Intel 80286 processor; however, its segment swapping technique was discovered to scale poorly to larger segment sizes. The Intel 80386 introduced support for paging underneath the existing segmentation layer, and the page fault exception could be chained with other exceptions without causing a double fault. The 80386 did not have a Translation Lookaside Buffer (TLB), which made loading segment descriptors expensive and caused operating system designers to rely strictly on paging rather than a combination of paging and segmentation.

Paged virtual memory

Almost all implementations of virtual memory divide the virtual address space of an application program into pages; a page is a block of contiguous virtual memory addresses. Pages are usually at least 4 KiB (4×1024 bytes) in size, and systems with large virtual address ranges or large amounts of real memory generally use larger page sizes.

Page tables

Almost all implementations use page tables to translate the virtual addresses seen by the application program into physical addresses (also referred to as "real addresses") used by the hardware to process instructions. The hardware that handles this specific translation or mapping function between logical addresses and physical addresses is often known as the Dynamic Address Translation (DAT) box or as the Memory Management Unit (MMU). Each entry in the page table contains a mapping for a virtual page to either a subsidiary page table, the real memory address at which the page is stored, or an indicator that the page is currently held in a disk file. (Although most do, some systems may not support use of a disk file for virtual memory.)

Systems can have one page table for the whole system, a separate page table for each application, a separate page table for each segment, a tree of page tables for large segments or some combination of these. If there is only one, different applications which are running at the same time share a single virtual address space, i.e. they use different parts of a single range of virtual addresses. Systems that use multiple page or segment tables provide multiple virtual address spaces—concurrent applications think they are using the same range of virtual addresses, but their separate page tables redirect to different real addresses.

Dynamic address translation

If, while executing an instruction, a CPU fetches an instruction located at a particular virtual address, or fetches data from a specific virtual address or stores data to a particular virtual address, the virtual address must be translated to the corresponding physical address. This is done by a hardware component, sometimes called a memory management unit, which looks up the real address (from the page table) corresponding to a virtual address and passes the real address to the parts of the CPU which execute instructions. If the page tables indicate that the virtual memory page is not currently in real memory, the hardware raises a page fault exception (special internal signal) which invokes the paging supervisor component of the operating system (see below).

Paging supervisor

This part of the operating system creates and manages page tables. If the address translation hardware raises a page fault exception, the paging supervisor accesses secondary storage, returns the page containing the required virtual address, updates the page tables to reflect the physical location of the virtual address and finally tells the dynamic address translation mechanism to restart the request. When all physical memory is already in use as is typical, the paging supervisor must free an area in primary storage to hold the swapped-in page. Freeing memory minimally requires updating the paging table to say that the page is in secondary storage. The supervisor saves time by not re–swapping pages that are already present in secondary storage.

Paging supervisors generally choose the page that has been least recently used, guessing that such pages are less likely to be requested. Every time the dynamic address translation hardware matches a virtual address with a real physical memory address, it time-stamps the page table entry for that virtual address.

Permanently resident pages

Operating Systems have memory areas that are "pinned" — i.e., never swapped to secondary storage. For example:

• Interrupt mechanisms generally rely on an array of pointers to their handlers (I/O completion, timer event, program error, page fault, etc.). If the pages containing these pointers or the code that they invoke were pageable, interrupt-handling would become far more complex and time-consuming; particularly in the case of page fault interrupts.
• At least some part of the page table structures are almost always not pageable.
• Data buffers that are accessed directly, for example by peripheral devices that use direct memory access (DMA) or by I/O channels. Usually such devices and the buses (connection paths) to which they are attached use physical memory addresses rather than virtual memory addresses. Even on buses with an IOMMU, which is a special memory management unit that can translate virtual addresses used on an I/O bus to physical addresses, the transfer cannot be stopped if a page fault occurs and then restarted when the page fault has been processed. So pages containing locations to which or from which a peripheral device is transferring data are either permanently pinned down or pinned down while the transfer is in progress.
• Timing-dependent kernel/application areas cannot tolerate the varying response time caused by paging. In particular the paging supervisor code or drivers for secondary storage devices must not be swapped out.

Virtual=real operation

In OS/VS1, OS/VS2 (SVS), MVS, z/OS, and similar OSes, some parts of systems memory are managed in virtual=real mode, where every virtual address corresponds to a real address. Those are:

• interrupt mechanisms
• paging supervisor and page tables, in older systems
• application programs that use non-standard methods of managing I/O, e.g., reading into an active channel program.

IBM's z/OS has 3 modes, V=V (virtual=virtual; fully pageable), V=R and V=F (virtual = fixed, i.e. "pinned down" but with DAT operating).

Segmented virtual memory

Some systems, such as Burroughs B5500, do not use paging to implement virtual memory. Instead, they use segmentation, that divide virtual address spaces into variable-length segments. A virtual address consists of a segment number and an offset within the segment.

Notably, the Intel 80286 supports a similar segmentation scheme as an option, but it is little used.

It is possible to combine segmentation and paging, dividing each segment into pages. In systems that combine them, such as Multics, IBM System/38 and IBM System i machines, virtual memory is usually implemented with paging, with segmentation providing memory protection.

In the Intel 80386 and later IA-32 processors, the segments reside in a 32-bit linear, paged address space. Segments can be moved in and out of that space, and pages in that space can "page" in and out of main memory, providing two levels of virtual memory; however, few if any operating systems do so. Instead, they use only paging. Early x86 virtualization solutions (non-hardware-assisted) combined paging and segmentation because x86 paging offers only two protection domains, whereas a VMM / guest OS / guest applications stack (typically running on rings 0 / 1 / 3) needs three memory protection domains.

The difference between paging and segmentation systems is not only about memory division. In Multics, System/38 and Prime machines, segmentation is visible to user processes, as part of memory model semantics. In other words, instead of memory that looks like a single large vector, memory is structured into multiple spaces.

This difference has important consequences; a segment isn't just a "page with a variable length", or a simple way to lengthen the address space (as in Intel 80286). In Multics, segmentation that can provide a single-level memory model, in which there is no differentiation between "process memory" and "file system". I.e., a process's active address space for both code and data consists of only a list of segments (files) which are mapped into the process's potential address space.

This is not the same as the mechanisms provided in TENEX and TOPS-20 (PMAP), modern Unix-like systems (mmap), and Win32 systems (MapViewOfFile), because inter-file pointers don't work when mapping files into semi-arbitrary places. In Multics, a file (or a segment from a multi-segment file) is mapped into a segment in the address space, so files are always mapped at a segment boundary. A file's linkage section can contain pointers that are "unsnapped links"; an attempt to load the pointer into a register or make an indirect reference through it causes a trap (a field in the pointer can have a value that specifies that an attempt to dereference it should cause a trap). The unresolved pointer contains an indication of the name of the segment to which the pointer refers, and an offset within the segment; the handler for the trap will "snap the link" the pointer by mapping the segment into the address space, putting the segment number into the pointer, and changing the tag field in the pointer so that it no longer causes the trap), and return to the code where the trap occurred, re-executing the instruction that caused the trap. This eliminates the need for a linker completely. This also works when different processes map the same file into different places in their private address spaces.

Avoiding thrashing

When paging is used a potential problem called "thrashing" can occur, in which the computer spends a disproportionate amount of its capacity swapping pages to and from a backing store and therefore performs useful work more slowly. Adding real memory is the simplest response, although improving application design, scheduling, and memory usage can help.

See also

• Computer memory
• Memory address
  • Address space
  • Virtual address space
• CPU design
• Page (computing)
  • Page table
  • Paging
  • Working set
  • Memory management unit
  • Cache algorithms
  • Page replacement algorithm
• Segmentation (memory)
  • System/38
• Memory management
• Memory allocation
• Protected mode, an x86 mode that allows for virtual memory.

Further reading

• Hennessy, John L.; and Patterson, David A.; Computer Architecture, A Quantitative Approach (ISBN 1-55860-724-2)

External links

• Linux Memory Management
• Linux Kernel Mailing List Discussion
• Pointers to virtual memory visualizations
• The Virtual-Memory Manager in Windows NT

This article is based on material taken from the Free On-line Dictionary of Computing prior to 1 November 2008 and incorporated under the "relicensing" terms of the GFDL, version 1.3 or later.