In computing, virtual memory is a memory management technique that is implemented using both hardware
and software.
It maps memory addresses used by a program, called virtual addresses, into physical addresses
in computer memory.
Main storage as seen by a process or task appears as a contiguous address space or collection
of contiguous segments.
The operating system manages virtual address spaces and the assignment of real memory to
virtual memory.
Address translation hardware in the CPU, often referred to as a memory management unit or
MMU, automatically translates virtual addresses to physical addresses.
Software within the operating system may extend these capabilities to provide a virtual address
space that can exceed the capacity of real memory and thus reference more memory than
is physically present in the computer.
The primary benefits of virtual memory include freeing applications from having to manage
a shared memory space, increased security due to memory isolation, and being able to
conceptually use more memory than might be physically available, using the technique
of paging.
Properties Virtual memory makes application programming
easier by hiding fragmentation of physical memory; by delegating to the kernel the burden
of managing the memory hierarchy; and, when each process is run in its own dedicated address
space, by obviating the need to relocate program code or to access memory with relative addressing.
Memory virtualization can be considered a generalization of the concept of virtual memory.
Usage Virtual memory is an integral part of a modern
computer architecture; implementations require hardware support, typically in the form of
a memory management unit built into the CPU.
While not necessary, emulators and virtual machines can employ hardware support to increase
performance of their virtual memory implementations.
Consequently, older operating systems, such as those for the mainframes of the 1960s,
and those for personal computers of the early to mid-1980s, generally have no virtual memory
functionality, though notable exceptions for mainframes of the 1960s include:
the Atlas Supervisor for the Atlas MCP for the Burroughs B5000
MTS, 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 The Apple Lisa is an example of a personal
computer of the 1980s that features virtual memory.
Most modern operating systems that support virtual memory also run each process in its
own dedicated address space.
Each program thus appears to have sole access to the virtual memory.
However, some older operating systems and even modern ones are single address space
operating systems that run all processes in a single address space composed of virtualized
memory.
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 traps 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 rather than with dedicated hardware.
History In the 1940s and 1950s, all larger programs
had to contain logic for managing primary and secondary storage, such as overlaying.
Virtual memory was therefore introduced not only 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 divided memory between
multiple programs without virtual memory, such as early models of the PDP-10 via registers.
The concept of virtual memory was first developed by German physicist Fritz-Rudolf Güntsch
at the Technische Universität Berlin in 1956 in his doctoral thesis, Logical Design of
a Digital Computer with Multiple Asynchronous Rotating Drums and Automatic High Speed Memory
Operation; it described a machine with 6 100-word blocks of primary core memory and an address
space of 1,000 100-word blocks, with hardware automatically moving blocks between primary
memory and secondary drum memory.
Paging was first implemented at the University of Manchester as a way to extend the Atlas
Computer's working memory by combining its 16 thousand words of primary core memory with
an additional 96 thousand words of secondary drum memory.
The first Atlas was commissioned in 1962 but working prototypes of paging had been developed
by 1959.
In 1961, the Burroughs Corporation independently released the first commercial computer with
virtual memory, the B5000, with segmentation rather than paging.
Before virtual memory could be implemented in mainstream operating systems, many problems
had to be addressed.
Dynamic address translation required expensive and difficult to build specialized hardware;
initial implementations slowed down access to memory slightly.
There were 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.
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, but its segment swapping technique scaled poorly to larger segment sizes.
The Intel 80386 introduced paging support underneath the existing segmentation layer,
enabling the page fault exception to chain with other exceptions without double fault.
However, loading segment descriptors was an expensive operation, causing operating system
designers to rely strictly on paging rather than a combination of paging and segmentation.
Paged virtual memory Nearly all implementations of virtual memory
divide a virtual address space into pages, blocks of contiguous virtual memory addresses.
Pages are usually at least 4 kilobytes in size; systems with large virtual address ranges
or amounts of real memory generally use larger page sizes.
Page tables Page tables are used to translate the virtual
addresses seen by the application into physical addresses used by the hardware to process
instructions; such hardware that handles this specific translation is often known as the
memory management unit.
Each entry in the page table holds a flag indicating whether the corresponding page
is in real memory or not.
If it is in real memory, the page table entry will contain the real memory address at which
the page is stored.
When a reference is made to a page by the hardware, if the page table entry for the
page indicates that it is not currently in real memory, the hardware raises a page fault
exception, invoking the paging supervisor component of the operating system.
Systems can have one page table for the whole system, separate page tables for each application
and segment, a tree of page tables for large segments or some combination of these.
If there is only one page table, different applications running at the same time use
different parts of a single range of virtual addresses.
If there are multiple page or segment tables, there are multiple virtual address spaces
and concurrent applications with separate page tables redirect to different real addresses.
Paging supervisor This part of the operating system creates
and manages page tables.
If the hardware raises a page fault exception, the paging supervisor accesses secondary storage,
returns the page that has the virtual address that resulted in the page fault, updates the
page tables to reflect the physical location of the virtual address and tells the translation
mechanism to restart the request.
When all physical memory is already in use, the paging supervisor must free a page in
primary storage to hold the swapped-in page.
The supervisor uses one of a variety of page replacement algorithms such as least recently
used to determine which page to free.
Pinned pages Operating systems have memory areas that are
pinned.
Other terms used are locked, fixed, or wired pages.
For example, interrupt mechanisms rely on an array of pointers to their handlers, such
as I/O completion and page fault.
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 interruptions.
Hence, some part of the page table structures is not pageable.
Some pages may be pinned for short periods of time, others may be pinned for long periods
of time, and still others may need to be permanently pinned.
For example: The paging supervisor code and drivers for
secondary storage devices on which pages reside must be permanently pinned, as otherwise paging
wouldn't even work because the necessary code wouldn't be available.
Timing-dependent components may be pinned to avoid variable paging delays.
Data buffers that are accessed directly by peripheral devices that use direct memory
access or I/O channels must reside in pinned pages while the I/O operation is in progress
because such devices and the buses to which they are attached expect to find data buffers
located at physical memory addresses; regardless of whether the bus has a memory management
unit for I/O, transfers cannot be stopped if a page fault occurs and then restarted
when the page fault has been processed.
In IBM's operating systems for System/370 and successor systems, the term is "fixed",
and such pages may be long-term fixed, or may be short-term fixed, or may be unfixed.
System control structures are often long-term fixed whereas I/O buffers are usually short-term
fixed.
Indeed, the OS has a special facility for "fast fixing" these short-term fixed data
buffers.
Additionally, the OS has yet another facility for converting an application from being unfixed
to being unswappable for an indefinite period, possibly for days, months or even years, however,
this facility implicitly requires that the application first be swapped-out, possibly
from preferred-memory, or a mixture of preferred- and non-preferred memory, and second be swapped-in
to preferred memory where it resides for the duration, however long that might be.
This utilizes a Supervisor Call instruction: SYSEVENT TRANSWAP, and is usually invoked
by the application itself, or by the application's name being "registered" in a special table,
the "program properties" table.
Multics used the term "wired".
OpenVMS and Windows refer to pages temporarily made nonpageable as "locked", and simply "nonpageable"
for those that are never pageable.
Virtual-real operation In OS/VS1 and similar OSes, some parts of
systems memory are managed in "virtual-real" mode, called "V=R".
In this mode every virtual address corresponds to the same real address.
This mode is used for interrupt mechanisms, for the paging supervisor and page tables
in older systems, and for application programs using non-standard I/O management.
For example, IBM's z/OS has 3 modes.
Thrashing When paging and page stealing are used, a
problem called "thrashing" can occur, in which the computer spends an unsuitably large amount
of time transferring pages to and from a backing store, hence slowing down useful work.
The phenomena is associated with the concept of a working set which is the minimum set
of pages that should be in memory in order for useful progress to be made in a task.
Thrashing occurs when there is insufficient memory available to store the working sets
of all active programs.
Adding real memory is the simplest response, but improving application design, scheduling,
and memory usage can help.
Another solution is to reduce the number of active tasks on the system.
This reduces demand on real memory by swapping out the entire working set of one or more
processes.
Segmented virtual memory Some systems, such as the Burroughs B5500,
use segmentation instead of paging, dividing virtual address spaces into variable-length
segments.
A virtual address here consists of a segment number and an offset within the segment.
The Intel 80286 supports a similar segmentation scheme as an option, but it is rarely used.
Segmentation and paging can be used together by dividing each segment into pages; systems
with this memory structure, such as Multics and IBM System/38, are usually paging-predominant,
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; pages there can "page" in and out of main
memory, providing two levels of virtual memory; few if any operating systems do so, instead
using only paging.
Early non-hardware-assisted x86 virtualization solutions combined paging and segmentation
because x86 paging offers only two protection domains whereas a VMM / guest OS / guest applications
stack needs three.
The difference between paging and segmentation systems is not only about memory division;
segmentation is visible to user processes, as part of memory model semantics.
Hence, instead of memory that looks like a single large space, it is structured into
multiple spaces.
This difference has important consequences; a segment is not a page with variable length
or a simple way to lengthen the address space.
Segmentation that can provide a single-level memory model in which there is no differentiation
between process memory and file system consists of only a list of segments mapped into the
process's potential address space.
This is not the same as the mechanisms provided by calls such as mmap and Win32's MapViewOfFile,
because inter-file pointers do not work when mapping files into semi-arbitrary places.
In Multics, a 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 for which an attempt to load the pointer into
a register or make an indirect reference through it causes 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 maps the segment into
the address space, puts the segment number into the pointer, changes the tag field in
the pointer so that it no longer causes a trap, and returns to the code where the trap
occurred, re-executing the instruction that caused the trap.
This eliminates the need for a linker completely and works when different processes map the
same file into different places in their private address spaces.
See also Computer memory
Memory address Address space
Virtual address space
CPU design Page
Page table Paging
Working set Memory management unit
Cache algorithms Page replacement algorithm
Segmentation System/38
Memory management Memory allocation
Protected mode, an x86 mode that allows for virtual memory.
CUDA Pinned memory Further reading
Hennessy, John L.; and Patterson, David A.; Computer Architecture, A Quantitative Approach
Notes
References 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.
External links Operating Systems: Three Easy Pieces, by Remzi
H. Arpaci-Dusseau and Andrea C. Arpaci-Dusseau.
Arpaci-Dusseau Books, 2014.
Relevant chapters: Address Spaces Address Translation Segmentation Introduction to Paging
TLBs Advanced Page Tables Swapping: Mechanisms Swapping: Policies
"Time-Sharing Supervisor Programs" by Michael T. Alexander in Advanced Topics in Systems
Programming, University of Michigan Engineering Summer Conference 1970, compares the scheduling
and resource allocation approaches, including virtual memory and paging, used in four mainframe
operating systems: CP-67, TSS/360, MTS, and Multics.
LinuxMM: Linux Memory Management.
Birth of Linux Kernel, mailing list discussion.
The Virtual-Memory Manager in Windows NT, Randy Kath, Microsoft Developer Network Technology
Group, 12 December 1992 at the Wayback Machine