Virtual memory

In the 1940s and 1950s , all programs whose size exceeded the amount of RAM should have logic for managing RAM and external memory, such as an overlay . In this regard, virtual memory was introduced not only to increase the amount of RAM, but also in order to make this increase the easiest to use for programmers. ^[4] To support multiprogramming and multitasking in many early computer systems, the separation of memory between several programs was carried out without virtual memory, using segmentation (for example, in PDP-10 computers).

The concept of virtual memory was first introduced in 1956 by the German physicist Fritz-Rudolf Güntsch ( German: Fritz-Rudolf Güntsch ) from the Berlin Technical University in his doctoral dissertation "The logical design of a digital computer with several asynchronous rotating drums and automatic high-speed memory management." It describes a machine with 6 memory blocks on magnetic cores with a capacity of 100 words each and an address space of 1000 blocks of 100 words each. The hardware of the machine automatically moves blocks between the main and external memory on magnetic drums . ^{[5] [6] Page-} paging was first implemented at the University of Manchester as a way to expand the memory of an Atlas computer by combining its main memory with magnetic cores of 16,000 words and memory with magnetic drums with a capacity of 96,000 words. The first delivery of the Atlas machine took place in 1962, but working prototypes of paging were already developed in 1959. ^{[4] [7] [8]} In 1961, Burroughs Corporation independently released the first commercially available B5000 virtual memory computer , using segmentation instead of page paging. ^{[9] [10]} In 1965, virtual memory was implemented in the domestic BESM-6 machine, although the implemented mechanism did not allow expanding the 15-bit address space of the process and limited the convenience of programming. ^[eleven]

Before virtual memory could be used in common operating systems, a number of problems had to be solved. Dynamic address translation required expensive and difficult to manufacture special equipment. The first implementations slowed access to memory. ^[4] There were fears that new system-wide algorithms using external memory would be less efficient than previously used algorithms for specific applications. By 1969, the debate over virtual memory for industrial computers was over: a team of IBM researchers led by David Sayre showed that the virtual memory system they created was superior in every way to the best manual systems. ^{[4] [12]} The first mini-computer to use virtual memory was the Norwegian NORD-1. In the 1970s, virtual memory implementations appeared in other mini-computers, the most famous being VAX , which runs on the VMS operating system.

Virtual memory in the x86 architecture was implemented with the advent of the protected mode of the processor 80286 , however, it used memory segmentation, and the swap segment method did not scale well for large segment sizes. The 80386 processor introduced paging support, which does not lead to a double error if a page error exception occurred during the processing of another exception. On top of the paging system, the existing memory segmentation mechanism worked. However, loading segment descriptors was an expensive operation, forcing operating system developers to rely solely on page paging, rather than a combination of page paging and segmentation.

In most modern operating systems, virtual memory is organized using paging. RAM is divided into pages: memory areas of a fixed length (for example, 4096 bytes ^[13] ), which are the minimum unit of allocated memory (that is, even a request for 1 byte from the application will lead to the allocation of a memory page). The user thread executed by the processor accesses the memory using the virtual memory address, which is divided by the page number and the offset within the page. The processor converts the virtual page number to the address of the corresponding physical page using an associative translation buffer (TLB). If he was unable to do this, then the buffer must be refilled by accessing the page table (the so-called Page Walk ), which can be done either by the processor itself or by the operating system (depending on architecture) ^[14] . If the page was unloaded from RAM, then the operating system pumps the page from the hard disk during the processing of the Page fault event (see swapping , page swapping). When requested to allocate memory, the operating system may “dump” to the hard drive pages that have not been accessed for a long time. Critical data (for example, the code of running and running programs, the code and memory of the system kernel ) are usually located in RAM (exceptions exist, but they do not concern those parts that are responsible for processing hardware interrupts, working with the page table and using the page file).

The mechanism for organizing virtual memory, in which virtual space is divided into parts of arbitrary size - segments. This mechanism allows, for example, to break process data into logical blocks. ^[15] For each segment, as well as for the page, access rights to it of the user and his processes can be assigned. When the process loads, part of the segments is placed in RAM (in this case, for each of these segments, the operating system looks for a suitable piece of free memory), and part of the segments is located in disk memory. Segments of one program can occupy non-contiguous sections in RAM. At boot time, the system creates a table of process segments (similar to the page table), in which for each segment the initial physical address of the segment in RAM, the segment size, access rules, modification sign, sign of accessing this segment for the last time interval and some other information are indicated . If the virtual address spaces of several processes include the same segment, then in the tables of segments of these processes references are made to the same piece of RAM into which this segment is loaded in a single copy. A system with a segmented organization functions similarly to a system with a paged organization: from time to time, interruptions occur due to the lack of the necessary segments in the memory, if it is necessary to free the memory, some segments are unloaded, each time the main memory is accessed, the virtual address is converted to physical. In addition, when accessing the memory, it is checked whether access of the required type to this segment is allowed.

A virtual address in a segmented memory organization can be represented by a pair (g, s), where g is the segment number and s is the offset in the segment. The physical address is obtained by adding the initial physical address of the segment, found in the table of segments by number g, and the offset s.

The disadvantage of this method of memory allocation is fragmentation at the segment level and slower address translation compared to the page organization.

There is also a hybrid pagination organization of virtual memory ^[16] .

• Shared memory
• Cache memory
• Virtual memory manager
• Memory management unit
• Memory leak

• Wachalia J. UNIX from the inside. - St. Petersburg: Peter, 2003. P.844. ISBN 5-94723-013-5
• Irtegov D. Introduction to operating systems. St. Petersburg: Peter, 2002.
• Bruce Jacob, Trevor Mudge. Virtual Memory: Issues of Implementation. - Los Alamitos, CA, USA: IEEE Computer Society Press, 1998. ISSN: 0018-9162
• Lecture 9: Virtual memory. Architectural Tools for Virtual Memory Support / Fundamentals of Operating Systems - Intel Academy, Moscow Institute of Physics and Technology, 2004 - Intuit ISBN 978-5-9556-0044-4

• Virtual Memory: Issues of Implementation / Computer Volume 31 Issue 6, June 1998 doi: 10.1109 / 2.683005
• Bo Brantén, Windows driver examples: SwapFs - A virtual memory driver for Windows using a Linux swap partition
• Paging file FAQ on WinBlog.ru , 2007