Memory hierarchy: virtual memory

This article describes the principles and implementations of virtual memory, which is the level of the memory hierarchy between main memory and secondary memories (magnetic disks).

Virtual memory plays a dual role. On the one hand, it provides the user with virtually unlimited memory space, without having to worry about the size and nature (DRAM or disks) of the physical memories actually implemented, while being protected against voluntary or involuntary interactions from other programs, whether their own or those of other users. On the other hand, it carries out, by hardware and software under the control of the operating system, the necessary transfers between the main memory and the secondary memories when the necessary code or data are not in the main memory.

Virtual memory space can be structured or unstructured. Structuring can be achieved in different ways: segmentation in assembler, segmentation as address extension or segmentation of machine systems. Without structuring, the space is said to be "flat". Since 32-bit processors, virtual space, whether segmented or not, is divided into pages of fixed size. Paginated flat systems are first presented, with techniques for address translation (direct page tables, reverse page tables using hashing, TLB to speed up translations) and page-level protection. The various replacement algorithms are explained. Next, systems with segmentation and pagination, characteristic of machine systems, are presented first in the general case, then illustrated in the case of IA-32 architectures, which use a very pure approach to paginated segmentation.

This is followed by a look at how the best-known operating systems implement virtual memory. Multics used paginated segmentation. VAX-VMS, on the other hand, used a flat virtual memory for which the notion of segments corresponded to super-pages used as address space extensions. Windows systems are significant examples of the evolution of virtual memory. From the initial Windows 1 version to Windows Millenium, successive systems used the paginated segmentation implemented in the various IA-32 processors. However, the Windows NT version developed in parallel from 1993 onwards used a flat system, designed to be portable with micronuclei and HAL (hardware adaptation layer), notably on RISC processors which do not use segmentation. Millenium was the last product in the range to use segmentation. 64-bit versions since Windows XP use flat mode. Linux uses flat mode.

The history of virtual memories is the birth, life and death of segmentation. It disappeared in 64-bit versions, replaced by flat addressing.