Virtual memory management

from Wikipedia, the free encyclopedia
Scheme of a virtual memory management:
left: virtual memory area for a running application (or a process ); the memory is linear and unfragmented
right: real memory sources; typically RAM , hard disk, and the like; several, even small, memory fragments can be used; in red the memory usage of other processes, invisible in the virtual memory area

The virtual memory management ( English virtual memory management , short VMM ) is a special memory management in a computer . The translation of the English term represents a hypallage - not the management process, but the memory to be managed is virtual. The virtual memory refers to the actually existing memory independent address space , of a process from the operating system is made available.

The concept originated in the 1950s and is now supported by most processor architectures and used in almost all modern operating systems.

history

The concept of virtual memory management emerged from the separation into primary storage media, to which the processor had direct access (mostly magnetic core storage ), and secondary external storage media (mostly magnetic drum storage ) in the computers of the 1950s and the desire to manage these automatically at the same level .

The concept of virtual memory was developed in 1956 by the physicist Fritz-Rudolf Güntsch at the Technical University of Berlin .

In Great Britain, the concept was demonstrated in a prototype in the Atlas computer project by Tom Kilburn and colleagues in 1959. The computer came on the market in 1962. The concept prevailed in most mainframe operating systems in the course of the 1960s (such as TSOS, the Spectra 70 from RCA or System / 360 (model 67) and their successor, the System / 370 from IBM ). Since new hardware had to be developed for efficient implementation, there was still resistance to full implementation in operating systems in the 1960s. Systematic tests carried out by a team led by David Sayre at IBM in the late 1960s, however, were clearly in favor of the concept of virtual memory. In 1970 Peter J. Denning published an article to clarify the properties of the concept of virtual memory.

The concept also found its way into mini-computers in the 1970s , such as in the VMS operating system from DEC for its VAX computer and in Unix (in the BSD version). With the PC , the concept with the further development of the processors (with Intel with the Protected Mode in the Intel 80286 and the Intel 80386 with Memory Management Unit ) also prevailed in the operating systems, with Microsoft from Microsoft Windows 3.0 .

motivation

The original motivation for an abstraction of the memory addresses with virtual addresses was the standardization of use and the possible combination of different memory sources. This is described by Güntsch in his dissertation from 1957:

“The programmer does not need to take into account the existence of high-speed memories (he does not even need to know that they are available). Because there is only one type of address that can be programmed as if there were only one memory available. "

- Fritz-Rudolf Güntsch

The virtual memory management also enables the implementation of memory protection mechanisms to separate

  • Programs among each other ("horizontal separation"): Programs cannot access the memory of other programs (e.g. in the event of an error);
  • Programs against the operating system (“vertical hierarchy”): The functioning of the operating system must not be endangered by (faulty) application programs.

Another useful property of the virtual address space is the possibility of providing each process with an initially unfragmented , exclusive memory space. Without virtual memory, there would often be memory fragmentation of the (physical) address space (across processes); With virtual memory (per process, and usually significantly larger address space than the physical memory), it can be largely avoided that the address space of one process is fragmented due to another process.

By mapping virtual addresses to physical addresses, a physical area can under certain circumstances also be used by several processes at the same time, which above all allows the efficient use of dynamic libraries . A library integrated in several programs is physically loaded only once. Especially with standard libraries, those that are linked to almost every program, this can bring about a considerable improvement in the loading times of the program and more efficient use of memory. The same applies to programs that are executed several times at the same time; Here too, the program code only needs to be in memory once. For this type of multiple use of physical memory, it is essential that the code of the libraries and programs is only read during execution, i.e. not changed. New physical pages must be reserved for the variables for each instance, which is generally "done automatically" using the copy-on-write process.

functionality

Relationship of the virtual address space to the physical address space for a process ( 32-bit protected mode ). Fragmented physical memory is presented to the process as continuous in the 2 GB virtual address space.

The computer system provides each process with addresses from 0 to n-1 an apparently contiguous local memory area, where n is the size of this memory area. In reality, this memory area consists of individual pages of a defined size ("pages", also obsolete "tiles") within the virtual address space of the process. These virtual pages are in turn mapped to physical pages that are located somewhere in physical memory or even in a swap file . When a process accesses a memory address (a virtual address, the process does not know any other addresses), the system's memory management unit (MMU; usually combined with a TLB ) translates this into the associated current physical address.

The so-called page table is the table which is used to transform virtual into physical page frames. Using this table, the MMU can translate the virtual addresses into real addresses. It is recorded here

  • for which virtual page which real page should be used;
  • if the virtual page is not used, it is marked that no real page is used for it;
  • in the case of the outsourced page, it is noted that / where in a program or library file or, if applicable,. the content is saved in a swap file and can be reloaded if necessary.

The optimal page size (size of a page) is a compromise between the frequency of page changes and the size of the table (usual sizes: 4 KiB with 32-bit virtual address space, 4 MiB with 64-bit virtual address space).

A virtual address describes a location in the memory of a computer system whose operating system uses virtual memory management for addressing . The entirety of all (possible) virtual addresses (of a process) is also referred to as a virtual address space .

Only operating systems that use virtual memory management can generate a virtual address space and thus memory pages that are not physically connected, or mapped to the programmer the program as a logically contiguous memory area.

definition

Nowadays, the following basic principles are common to virtual storage management:

  1. All addresses used by processes are only treated as virtual addresses.
  2. A memory management unit translates the virtual addresses into real physical addresses.
  3. The virtual address space, which is defined by the entirety of all possible virtual addresses and which forms the virtual memory, is divided into memory sections of equal size just like the physical main memory actually present. The German terms tile , memory page or page frame used for these memory sections are synonymous. In English , this memory section pageFrame called. A page of the virtual address space is mapped onto a page ( pageframe ) of the physical address space.

The various virtual memory managers differ

  1. in the size of the virtual memory space,
  2. in the memory size that a page occupies,
  3. in the way the memory management unit calculates a physical address from the virtual address,
  4. in their page replacement strategy, which specifies the response to a so-called page fault , the addressing of a virtual address not available in physical memory, and
  5. in the handling of possibly outsourced pages.

technology

Operating system placement strategies

If a program requests memory from the operating system, the operating system has the freedom to allocate the requested memory to the program in the virtual memory space of the process. With clever placement strategies, continuous fragmentation of the virtual address space can be reduced, which is very relevant both with a high number of memory requests and releases and when the virtual address space is heavily filled.

Strategies for choosing suitable addresses are:

FirstFit
first sufficient gap
BestFit
smallest sufficient gap. Disadvantage: external fragmentation
NextFit
next free memory; starts at the point at which the last data was inserted (circular browsing)
WorstFit
largest sufficient gap

Paging

Virtual memory segments of the Intel 80286.
Paging of the Intel 80386, with a page size of 4 KB.

In a narrower sense, the term paging simply refers to the process of mapping the virtual addresses to the physical ones. In the broader (erroneous) sense it is used synonymously for swapping .

Swapping

Swapping is the relocation of a real RAM memory area to another, secondary memory, typically in a swap file on a hard disk by the operating system.

The idea behind this is that in typical computers the hard disk is significantly larger than the available electronic memory (RAM): Since the hard disk memory can also be used to service memory requests from programs, requests that go beyond the available RAM can then be over Swap memory for each process can be served with more virtual memory than is physically available.

The disadvantage is that the memory stored on the hard disk can be accessed much more slowly than RAM - however, this procedure enables programs with high memory requirements to function. To mitigate the slow access, operating systems try to use memory monitoring to optimally distribute the RAM and swap memory to the various processes. Memory areas that have not been accessed for reading or writing for a long time are swapped out to the slow swap memory when they are short. Frequently used pages are kept in RAM if possible.

In concrete terms, this works in that, once the RAM is full, special processes (“page stealers”) begin to outsource pages that have not been used for a long time in order to gain additional physical space so that the system can react quickly to a corresponding request. This process is asynchronous to the applications and does not place any particular load on the system. Nevertheless, the access speed of the hard disk is relevant. The most important page replacement strategies are listed below. Usually a combination of several processes is used: First, unread, then unchanged, then unmodified pages are swapped out. If there is a current copy of a page in the swap file, this page can easily be released for overwriting.

A page fault (ger .: page fault ) occurs when a program accesses a page that just is not in the main memory, but has been outsourced. This triggers a program interruption ( trap ). The operating system now ensures that the requested memory area is reloaded into the main memory so that the program can access it. The page can now be physically in a different place than originally; the memory management unit updates the page table accordingly. The virtual address remains unchanged. A page fault does not cause a termination, but an action that then allows the process to continue processing normally.

Retrieving such pages is a process that takes significantly longer than just accessing a main memory address. Therefore, when large amounts of page faults occur, they slow down the program speed considerably. The computing power can drop sharply if, due to a large memory shortage, frequently required pages have to be swapped out and the system mainly has to deal with the handling of page errors. Page stealer and the traps both access the swap file and at a certain point use up the affected hard disks completely. This effect is known as side flutter or thrashing .

Operating system page replacement strategies

Typical strategies to optimize the use of RAM and slower secondary storage for all processes are:

not recently used (NRU)
Divides pages into four classes based on the use bit and dirty bit from the page table and randomly removes one from the lowest, non-empty class.
first in, first out (FIFO)
Each side receives a time stamp and is managed according to FIFO : "oldest out, in back, out front"
Second chance algorithm
Variant of FIFO that prevents pages that are still frequently used from being swapped out.
least frequently used (LFU)
Each page has a field that provides information about the last use; in the event of a page fault, all pages must be searched for a previously unused time
Working set algorithm
Replaces the entire working set of a process. It's a prepaging strategy because pages are loaded before they are needed.
Clock algorithm
Functioning analogous to the second-chance algorithm. The sides are shown in the form of a virtual clock with pointers. In the case of displacement, the clock hand is switched forward by one element until a page with a reset R bit is found. Pages with a set R bit are reset when the pointer is crossed. If there are a large number of main memory pages, this process is too slow. Therefore z. B. BSD - Unix uses two pointers with constant distance to improve runtime. The front pointer resets the R bit in the page descriptor, the rear pointer checks the R bit and, if the bit is reset, performs the displacement.
Belady's theorem of optimal displacement
The pages that will not be referenced for the longest time will be suppressed. Mostly not feasible, as the program behavior cannot generally be predicted.

Memory fragmentation

In systems without virtual memory management, there is a potential for continuous fragmentation of the real memory space over the runtime. In other words, the successful functioning of a newly started program is not guaranteed deterministically and depends on the fragmentation status of the physical memory. Without virtual memory management, it can happen that with several program runs despite constant memory requirements, these sometimes cannot be served due to fragmentation, although there is always enough memory free.

For example, MS-DOS , an OS without virtual memory management, has a similar problem with drivers and TSR programs; an attempt was made to minimize the problem with complicated memory optimizers ( EMM386.EXE , QEMM etc.). With these memory optimizers, an attempt was made (among other things) to place device drivers and TSR programs in the physical memory as unfragmented as possible using an iteratively determined optimal load sequence in order to be able to provide the largest possible memory blocks to subsequent programs.

Virtual memory management offers every starting program the same, unfragmented memory space.

However, programs with virtual memory management can fragment their virtual memory space themselves through continuous explicit memory allocation and deallocations ( malloc(), free()) or clumsily fixed program libraries (DLLs) and thus also run in runtime-dependent "out-of-memory" situations. This emerged as a practical problem in the 2000s at the end of the 32-bit PC era ( 4 GB limit ); the virtual address space was no longer significantly larger than the typical physical RAM expansion; more and more programs were using a correspondingly large amount of RAM. For memory-intensive applications such as For example, scientific simulations (e.g. with Matlab ) or complex 3D computer games (such as Gothic 3 , Supreme Commander ) led to increased out-of-memory problems, despite “sufficient” physical and virtual (total) memory.

However, if the virtual memory space is significantly larger than the requirements of the process, fragmentation of the virtual memory space is not a practical problem, since there are enough alternative unfragmented addresses and address ranges. With the 64-bit x86 AMD64 architecture, the virtual address space sizes were increased significantly (also to counter this problem), and for the foreseeable future, fragmentation of the virtual memory space should not play a role for PC programs.

Assignment of virtual pages to real page frames

In multiprocessor systems , the actually available main memory is often connected according to the NUMA principle. The operating system should then advantageously assign the virtual pages of a thread to those real page frames that are connected to the processor that is calculating the thread.

Examples

  • AMD64 architecture: 48 bits of the 64 bits of the virtual memory addresses are physically implemented in the first generation of CPUs for virtual memory management (the first 16 bits of the virtual address must be a repetition of the 48th bit, i.e. 0000 hex or FFFF hex ) . Since only 48 bits are possible, the virt. Address space limited to 2 ^ 48 bytes. A four-level page table is used for this. The 48 bits are divided into 9 bits each for the four page tables plus a 12-bit offset .
  • IA-32 architecture: A virtual address is 32 bits long. A two-tier page table is used. The 32 bits are divided into 10 bits each for the two side tables plus a 12-bit offset.
  • IA-32 architecture with PAE : A virtual address is 32 bits long. A three-level asymmetric page table is used. The 32 bits are divided into 2 bits for the first page table and 9 bits each for the two other page tables plus a 12-bit offset.

In the IA-32 architecture, the main memory is divided into memory pages, the possible sizes and starting addresses of which are specified by the hardware. If an address is accessed that is currently not assigned a physical memory page, the operating system must instruct the memory management unit to show a specific free memory page at this point. If there is no more free memory page available, another memory page must be made free. B. is swapped out to the hard drive . This process is known as paging . The size of the virtual address space can be calculated from the definition of the virtual address. For example, in an IA-32 architecture, a virtual address is 32 bits wide, twice 10 bits each for a two-level page table and 12 bits for the offset. This means that 2 10 × 2 10 × 2 12 bytes can be addressed. That is 2 32 bytes, i.e. 4 GiB.

See also

Web links

Individual evidence

  1. ↑ For the boot process / initialization, an initialization with special table entries or a non-virtual mode may be necessary.
  1. ↑ Peter J. Denning Before memory was virtual , 1996, pdf ( memento of the original from February 24, 2012 in the Internet Archive ) Info: The archive link was inserted automatically and has not yet been checked. Please check the original and archive link according to the instructions and then remove this notice. @1@ 2Template: Webachiv / IABot / cs.gmu.edu
  2. ^ E. Jessen: Origin of the Virtual Memory Concept. IEEE Annals of the History of Computing. Volume 26. 4/2004, p. 71 ff.
  3. ↑ a b Eike Jessen: The development of the virtual memory . In: Springer Berlin / Heidelberg (ed.): Computer science spectrum . 19, No. 4, 1996, ISSN  0170-6012 , pp. 216-219. doi : 10.1007 / s002870050034 .
  4. ↑ History of Virtual Memory, George Mason University ( Memento of the original from April 30, 2012 in the Internet Archive ) Info: The archive link was automatically inserted and not yet checked. Please check the original and archive link according to the instructions and then remove this notice. @1@ 2Template: Webachiv / IABot / www.cs.gmu.edu
  5. ↑ Peter J. Denning Performance modeling- experimental computer science at its best , 1981, pdf ( Memento of the original from September 28, 2011 in the Internet Archive ) Info: The archive link was inserted automatically and has not yet been checked. Please check the original and archive link according to the instructions and then remove this notice. @1@ 2Template: Webachiv / IABot / cs.gmu.edu
  6. ↑ Denning, Virtual Memory, Computing Surveys, Volume 2, 1970, pp. 153-189
  7. ^ Fritz-Rudolf Güntsch: Logical design of a digital computing device with several asynchronously running drums and automatic quick storage operation . Dissertation, Technical University of Berlin, D83. Berlin 1957. Quoted from Jessen (1996)
  8. ↑ Brett Shoelson: Is your memory fragmented? What can you do about it? ( English ) mathworks.com. May 8, 2009. Retrieved July 14, 2012.
  9. ↑ VIII. Community Patch v1.6 ( English ) madvulture.de. Retrieved September 5, 2012: " Fixed some memory fragmentation for performance improvements. "
  10. ↑ Ryan Smith: A Messy Transition: Practical Problems With 32bit Addressing In Windows - A Case Study: Supreme Commander ( English ) anandtech.com. S. 4. July 12, 2007. Retrieved on September 5, 2012: “ Finally at 22 minutes in to the game, the game crashes as the virtual size has reached the 2.6GB barrier we have reconfigured this system for. Perhaps the most troubling thing at this point is that Supreme Commander is not aware that it ran out of user space in its virtual address pool, as we are kicked out of the game with a generic error message. "
  11. ↑ AMD64 Architecture Programmer's Manual Volume 2: System Programming ( Memento of the original from March 3, 2016 in the Internet Archive ) Info: The archive link was inserted automatically and has not yet been checked. Please check the original and archive link according to the instructions and then remove this notice. Page 4: Canonical Address Form, 2013, pdf @1@ 2Template: Webachiv / IABot / developer.amd.com