Virtual memory/rewrite

Virtual memory is a computer system technique that gives an application program the impression it has contiguous working memory, while in fact it is physically fragmented and "may" even overflow on to disk storage. Systems which use this technique make programming of large applications easier and use real physical memory (e.g. RAM) more efficiently than those without virtual memory.

Note that "virtual memory" is not just "using disk space to extend physical memory size". Extending memory is a normal "consequence" of using virtual memory techniques, but can be done by other means such as overlays or swapping programs and their data completely out to disk while they are inactive. The "definition" of "virtual memory" is based on tricking programs into thinking they are using large blocks of contiguous addresses.

All modern "general purpose" computer operating systems from desktops to mainframes use virtual memory techniques for ordinary applications. Such applications include: (desktops) word processors, spreadsheets, multimedia players; (mainframes) transaction processing systems, batch processing, timesharing. Older operating systems, such as DOS of the 1980s, or many mainframe operating systems of the 1960s, had no virtual memory functionality.

Embedded systems and others in which very fast, very consistent response time is essential do not generally use virtual memory.

Implementation techniques

Page tables

Almost all implementations require page tables to translate the virtual addresses seen by the application program into real addresses used by the hardware to process instructions. A " page" is a block of contiguous virtual memory addresses; pages are usually at least 2K bytes in size, and systems with large virtual address ranges or large amounts of real memory (e.g. RAM) generally use larger page sizes. Each entry in a page table contains: the starting virtual address of the page; either the real memory address at which the page is actually stored or an indicator that the page is currently held in a disk file (if the system uses disk files to let applications use amounts of virtual memory which exceed real memory).

Systems can have one page table for the whole system or a separate page table for each application. 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 which use multiple page 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.

Paging

Paging is the process of saving inactive virtual memory pages to disk and restoring them to real memory when required.

Most virtual memory systems enable programs to use virtual address ranges which in total exceed the amount of real memory (e.g. RAM). To do this they use disk files to save virtual memory pages which are not currently active, and restore them to real memory when they are needed. Pages are not necessarily restored to the same real addresses from which they were saved - applications are aware only of virtual addresses. Usually the real memory to which a page is restored contains another virtual memory page which has been used recently, and which miost therefore be saved to disk.

Dynamic address translation

This is done by a hardware component which looks up in the appropriate page table the real address 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 interrupt (special internal signal) which invokes the paging supervisor component of the operating system (see below).

Dynamic address translation mechanisms vary quite widely:
*In some cases they are distinct hardware components of the CPU's interface to real main memory and often make the use of virtual memory transparent even to most of the CPU. They may be parts of a memory management unit which performs other functions such as memory protection and cache control; or they may be relatively stand-alone in systems which have other methods of memory protection and cache control (e.g. IBM System/370). Since data transfer within the CPU is much faster than accessing memory, most dynamic address translation components 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 reading of memory. 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 look up the page tables in memoery and save the result in the TLB.
*In the x86 architecture which is used in most desktop computers, the 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.

Paging supervisor

This part of the operating system creates and manages the page tables. If the dynamic address translation hardware raises a page fault interrupt, the paging supervisor searches the page file(s) (on disk) for the page containing the required virtual address, reads it into real physical memory, updates the page tables to reflect the new location of the virtual address and finally tells the dynamic address translation mechanism to start the search again. Usually all of the real physical memory is already in use and the paging supervisor must first save an area of real physical memory to disk and update the page table to say that the associated virtual addresses are no longer in real physical memory but saved on disk. Paging supervisors generally save and overwrite areas of real physical memory which have been used least recently, because these are probably the areas which are used least often. So every time the dynamic address translation hardware matches a virtual address with a real phyical memory address, it must put a time-stamp in the page table entry for that virtual address.

=Virtual=real operation=

All virtual memory systems have parts which operate in virtual=real mode, where a virtual address is also a real address which refers to a specific location in real memory (e.g. [RAM] ).

Most of the operating system must run in real mode, for example:
*Interrupt mechanisms generally rely on an array of pointers to the handlers for various types of interrupt (I/O completion, timer event, program error, page fault, etc.), and both the pointers and the handlers must reside at fixed locations in real memory.
*The page tables cannot be pageable, so they must reside at at fixed locations in real memory and the paging supervisor must run in real mode.
*Data buffers must be implemented in real mode because; I/O devices and devices which control clusters of peripherals cannot access page tables or the dynamic address translation mechanism; an application may be paged out (saved to disk) while waiting for an I/O operation to complete.

A few types of application program also need to run in real mode, for example:
*Those which use non-standard methods of managing I/O and therefore provide their own buffers and communicate directly with peripherals.
*Those whose operation is very timing dependent and cannot allow the variation in response time which paging causes.