Virtual memory

Virtual memory is a computer design feature that permits software to use more main memory (the memory which the CPU can read and write to directly) than the computer actually physically possesses.

Most computers possess four kinds of memory: registers in the CPU, caches both inside and adjacent to the CPU, physical memory, generally in the form of RAM which the CPU can read and write to directly and reasonably quickly; and disk storage, which is much slower, but also much larger. Many applications require access to more information (code as well as data) than can be stored in physical memory. This is especially true when the operating system allows multiple processes/applications to run seemingly in parallel. The obvious response to the problem of the maximum size of the physical memory being less than that required for all running programs is for the application to keep some of its information on the disk, and move it back and forth to physical memory as needed, but there are a number of ways to do this.

One option is for the application software itself to be responsible both for deciding which information is to be kept where, and also for moving it back and forth. The programmer would do this by determining which sections of the program (and also its data) were mutually exclusive, and then arranging for loading and unloading the appropriate sections from physical memory, as needed. The disadvantage of this approach is that each application's programmer must spend time and effort on designing, implementing, and debugging this mechanism, instead of focusing on their application; this hampered programmers' efficiency. Also, if any programmer could truly choose which of their items of data to store in the physical memory at any one time, they could easily conflict with the decisions made by another programmer, who also wanted to use all the available physical memory at that point.

The alternative is to use virtual memory, in which a combination of special hardware and operating system software makes use of both kinds of memory to make it look as if the computer has a much larger main memory than it actually does. It does this in a way that is invisible to the rest of the software running on the computer. It usually provides the ability to simulate a main memory of almost any size (as limited by the size of the addresses being used by the operating system and cpu; the total size of the Virtual Memory can be 2³² for a 32 bit system, or approximately 4 Gigabytes, while newer 64 bit chips and operating systems use 64 or 48 bit addresses and can index much more virtual memory).

This makes the job of the application programmer much simpler. No matter how much memory the application needs, it can act as if it has access to a main memory of that size. The programmer can also completely ignore the need to manage the moving of data back and forth between the different kinds of memory.

In technical terms, virtual memory allows software to run in a memory address space whose size and addressing are not necessarily tied to the computer's physical memory. While conceivably virtual memory could be implemented solely by operating system software, in practice its implementation almost universally uses a combination of hardware and operating system software.

Basic operation

When virtual memory is used, or when a main memory location is read or written to by the CPU, hardware within the computer translates the address of the memory location generated by the software (the virtual memory address) into either:

• the address of a real memory location (the physical memory address) which is assigned within the computer's physical memory to hold that memory item, or
• an indication that the desired memory item is not currently resident in main memory (a so-called virtual memory exception)

In the former case, the memory reference operation is completed, just as if the virtual memory were not involved. In the latter case, the operating system is invoked to handle the situation, since the actions needed before the program can continue are usually quite complex.

The effect of this is to swap sections of information between the physical memory and the disk; the area of the disk which holds the information which is not currently in physical memory is called the swap file, page file, or swap partition (on some operating systems it is a dedicated partition of a disk).

Details

The translation from virtual to physical addresses is implemented by an MMU. This may be either a module of the CPU, or an auxiliary, closely coupled chip.

The operating system is responsible for deciding which parts of the program's simulated main memory are kept in physical memory. The operating system also maintains the translation tables which provide the mappings between virtual and physical addresses, for use by the MMU. Finally, when a virtual memory exception occurs, the operating system is responsible for allocating an area of physical memory to hold the missing information, bringing the relevant information in from the disk, updating the translation tables, and finally resuming execution of the software that incurred the virtual memory exception.

In most computers, these translation tables are stored in physical memory. Therefore, a virtual memory reference might actually involve two or more physical memory references: one or more to retrieve the needed address translation from the page tables, and a final one to actually do the memory reference.

To minimize the performance penalty of address translation, most modern CPUs include an on-chip MMU, and maintain a table of recently used virtual-to-physical translations, called a Translation Lookaside Buffer, or TLB. Addresses with entries in the TLB require no additional memory references (and therefore time) to translate, However, the TLB can only maintain a fixed number of mappings between virtual and physical addresses; when the needed translation is not resident in the TLB, action will have to be taken to load it in.

On some processors, this is performed entirely in hardware; the MMU has to do 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; an exception is raised, and on this exception, the operating system replaces one of the entries in the TLB with an entry from the translation table, and the instruction which made the original memory reference is restarted.

The hardware that supports virtual memory almost always supports memory protection mechanisms as well. The MMU may have the ability to vary its operation according to the type of memory reference (for read, write or execution), as well as 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 application program and to protect application programs from each other and (to some extent) from themselves (e.g. by preventing writes to areas of memory which contain code).

Paging and virtual memory

Virtual memory is usually (but not necessarily) implemented using paging. In paging, the low order bits of the binary representation of the virtual address are preserved, and used directly as the low order bits of the actual physical address; the high order bits are treated as a key to one or more address translation tables, which provide the high order bits of the actual physical address.

For this reason a range of consecutive addresses in the virtual address space whose size is a power of two will be translated in a corresponding range of consecutive physical addresses. The memory referenced by such a range is called a page. The page size is typically in the range of 512 to 8192 bytes (with 4K currently being very common), though page sizes of 4 megabytes or larger may be used for special purposes. (Using the same or a related mechanism, contiguous regions of virtual memory larger than a page are often mappable to contiguous physical memory for purposes other than virtualization, such as setting access and caching control bits.)

The operating system stores the address translation tables, the mappings from virtual to physical page numbers, in a data structure known as a page table,

If a page that is marked as unavailable (perhaps because it is not present in physical memory, but instead is in the swap area), when the CPU tries to reference a memory location in that page, the MMU responds by raising an exception (commonly called a page fault) with the CPU, which then jumps to a routine in the operating system. If the page is in the swap area, this routine invokes an operation called a page swap, to bring in the required page.

The page swap operation involves a series of steps. First it selects a page in memory, for example, a page that has not been recently accessed and (preferably) has not been modified since it was last read from disk or the swap area. (See page replacement algorithms for details.) If the page has been modified, the process writes the modified page to the swap area. The next step in the process is to read in the information in the needed page (the page corresponding to the virtual address the original program was trying to reference when the exception occurred) from the swap file. When the page has been read in, the tables for translating virtual addresses to physical addresses are updated to reflect the revised contents of the physical memory. Once the page swap completes, it exits, and the program is restarted and continues on as if nothing had happened, returning to the point in the program that caused the exception.

It is also possible that a virtual page was marked as unavailable because the page was never previously allocated. In such cases, a page of physical memory is allocated and filled with zeros, the page table is modified to describe it, and the program is restarted as above.

Additional details

One additional advantage of virtual memory is that it allows a computer to multiplex its CPU and memory between multiple programs without the need to perform expensive copying of the programs' memory images. If the combination of virtual memory system and operating system supports swapping, then the computer may be able to run simultaneous programs whose total size exceeds the available physical memory. Since most programs have a small subset (active set) of pages that they reference over significant periods of their execution, the performance penalty is less than that which might be expected. If too many programs are run at once, or if a single program continuously accesses widely scattered memory locations, then page swapping becomes excessively frequent and overall system performance will become unacceptably slow. This is often called thrashing (since the disk is being excessively overworked - thrashed) or paging storm, which corresponds to accessing the swap medium being three orders of magnitude slower compared to main memory access.

Note that virtual memory is not a requirement for precompilation of software, even if the software is to be executed on a multiprogramming system. Precompiled software loaded by the operating system has the opportunity to carry out address relocation at load time. This suffers by comparison with virtual memory in that a copy of program relocated at load time cannot run at a distinct address once it has started execution.

It is possible to avoid the overhead of address relocation using a process called rebasing, which uses metadata in the executable image header to guarantee to the run-time loader that the image will only run within a certain virtual address space. This technique is used on the system libraries on Win32 platforms, for example.

In embedded systems, swapping is typically not supported.

Systems with a large amount of RAM can create a virtual hard disk within the RAM itself. This does block some of the RAM from being available for other system tasks but it does considerably speed up access to the swap file itself.

Windows example

Virtual memory has been a feature of Microsoft Windows since Windows 3.1 in 1992. 386SPART.PAR (or "WIN386.SWP") is a hidden file created by Windows 3.1 for use as a virtual memory swap file. It is generally found in the root directory, but it may appear elsewhere (typically in the WINDOWS directory). Its size depends on how much virtual memory the system has set up under Control Panel - Enhanced under "Virtual Memory." If a user moves or deletes this file, Windows will complain the next time it is started with a "Swap File error."

Windows 95 uses a similar file, except it is named WIN386.SWP, and the controls for it are located under Control Panel - System - Performance tab - Virtual Memory. Windows automatically sets the page file to be 1.5 x physical memory. If you run memory intensive applications on a low physical memory system it is preferable to manually set the size to a value higher than default. Additionally, fixing the size of the swap file will prevent it from being dynamically resized by Windows. This resizing causes the swap file to become fragmented, resulting in reduced performance.

See also

• CPU design
• computer
• memory management

References

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

External links

• How Virtual Memory Works (http://computer.howstuffworks.com/virtual-memory.htm)
• Linux swap partition (http://am.xs4all.nl/phpwiki/index.php/swap)
• Windows swap file management (http://www.pcnineoneone.com/howto/swpfile1.html)he:זיכרון וירטואלי

da:Virtuel hukommelse de:Virtuelle Speicherverwaltung fi:Näennäismuisti fr:Mémoire virtuelle it:Memoria virtuale lt:Virtualioji atmintis nl:Virtueel geheugen ja:仮想記憶 ko:가상메모리 pl:Pamięć wirtualna pt:Memória virtual ru:Файл подкачки es:Memoria virtual