...and the crucial role it plays in modern operating systems.
文章译自An introduction to virtual memory
Computers are complex machines designed to perform a simple task: to run programs — browsers, text editors, web servers, video games, ... — that operate on data — photos, music, text files, databases and so on.
When not in use, such programs and data live peacefully in the hard drive, the device responsible for keeping information alive even if your computer is turned off. Running an application means to ask the processor (a.k.a. Central Processing Unit or CPU) to read and execute the machine instructions that make up the computer program, along with any additional data processing.
当不使用时，这些程序和数据会安然地呆在硬盘中，硬盘的责任是确保信息不会丢失，即使你的电脑关闭了。运行应用程序意味着要求 处理器（又名中央处理单元或CPU） 读取和执行构成计算机程序的机器指令，以及任何额外的数据处理。
Hard drives store huge amount of information, yet they are terribly slow. Way slower than the processor: a CPU that reads instructions from a hard drive directly would become a serious bottleneck for the whole system. For this reason, the program and its data are first copied to the main memory (a.k.a. Random Access Memory or RAM), another storage hardware component smaller than a hard drive but much faster, so that the processor can read instructions from there without speed penalties.
The main memory can be seen as a long list of cells, each one containing some binary data and marked with a number called the memory address. Memory addresses span from 0 to N, based on the amount of main memory available in the system. The range of addresses used by a program is called the address space.
主存储器可以看成是一个长长的 单元格列表，每个单元格都包含一些二进制数据，并标有一个称为 内存地址 的数字。内存地址的范围从 0 到 N，是根据系统中可用的主存储器的容量而定的。一个程序使用的地址范围称为 地址空间。
(1. Two programs loaded in memory. Each cell is a memory address. Space between program A and program B might be used by other programs or data. 内存加载的两个程序。每个单元格是一个内存地址。程序A和程序B之间的空间可能被其他程序或数据使用)
In the beginning of the computer history (and also nowadays in embedded systems), programs had access to the entire main memory and its management was left to the programmer. Writing software for those machines was challenging: part of the developer's job was to devise a good way to manage RAM accesses and make sure that the whole program would not overflow the available memory.
Things got trickier with the advent of multitasking, when multiple programs could run on the same computer. Programmers had to face new critical issues:
memory layout — programs located in RAM after the first one would have their address space offset by a certain amount, no longer in the initial range 0 to N. An additional pain point to take care of during development; memory fragmentation —— as things are moved back and forth to memory, the available space becomes fragmented into smaller and smaller chunks. This would make it harder to find available space to load new programs and data in memory; security —— what if program A accidentally overwrites program B's memory? Or, even worse: what if it deliberately reads sensitive data from another program, such as passwords or credit card information?
So it was pretty obvious to hardware architects in the early 1960s that a form of automatic memory management could significantly simplify programming and fix the more critical memory protection problem. Eventually they came up with what is known today as virtual memory.
In virtual memory, a program does not have direct access to physical RAM. Instead, it interacts with an illusory address space called virtual address space. The operating system works together with the processor to provide such virtual address space and convert it, sooner or later, into the physical one.
Every memory access is performed through a virtual address that does not refer to the actual physical location in memory. A program always reads or write the virtual address, and it's completely unaware of what is going on in the underlying hardware.
(2. Two processes with their own virtual address spaces. Notice how the physical memory is not contiguous for process. 两个进程都有自己的虚拟地址空间。注意物理内存对进程来说并不一定是连续的)
In the picture above you can see an example of virtual to physical translation in action, which reveals two main benefits of the virtual memory:
each program has a virtual address space that starts from 0 — this simplifies a lot the programmer's life: no need to manually keep track of memory offsets anymore; virtual memory is always contiguous, even if the underlying physical counterpart isn't — the operating system does the hard job of gathering the available pieces together into a single, uniform virtual memory chunk.
The virtual memory mechanism also solves the problem of a limited RAM: every process is given the impression that it is working with an undefined amount of memory, often larger than the physical one. Moreover, the virtual memory guarantees security: program A can't read or write virtual memory assigned to program B without triggering an operating system error. We will see how all of this magic is possible in the following paragraphs.
The virtual memory mechanism needs a place to store the mapping between virtual and physical addresses. That is, given a virtual address X, the system must be able to find the corresponding physical address Y. However, you can't save such information as a 1:1 relationship: it would require a database as big as the whole RAM!
Modern virtual memory implementations overcome this problem (and many others) by interpreting the virtual and the physical memory as a long list of small, fixed-size chunks. The chunks of the virtual memory are called pages and the chunks of the physical one are called frames. The Memory Management Unit (MMU) is a hardware component in the CPU that stores the mapping information between pages and frames inside a special data structure called page table. A page table is like a database table where each row contains a page index and the frame index it corresponds to. Every running program has a page table in the MMU, as you can see in the picture below.
现代虚拟内存的实现克服了这个问题（以及许多其他问题），它将虚拟内存和物理内存解释为一长串固定大小的小块。虚拟内存的块被称为pages(页)，物理内存的块被称为frames(桢)。内存管理单元（MMU） 是CPU中的一个硬件组件，它将 pages 和 frames 之间的映射信息存储在一个叫做 page table 的特殊数据结构中。page table就像一个数据库表，每一行都包含一个page索引和对应的frame索引。每个运行中的程序在MMU中都有一个 page table，如下图所示。
(3. The MMU mapping in action. Each cell is a process page or a physical memory frame. Some pages may not have a corresponding frame mapped: we will see why in the next paragraphs. MMU映射。每个单元格都是一个进程页或物理内存帧。有些页面可能没有相应的帧映射：我们将在下一段中看到原因。)
A virtual address is made up of two things:
a page index, that tells the page the virtual address belongs to; a frame offset, that tells the position of the physical address inside the frame;
This information is enough for the MMU to perform the virtual to physical conversion. When a program reads or write a virtual address, it wakes up the MMU which in turn grabs the page index (1) and searches for the corresponding frame in the program's page table. Once the frame is found, the MMU makes use of the frame offset (2) to find the exact physical memory address and pass it back to the program. At this point the conversion is done: the program has a physical address in RAM to read or write through the virtual one.
While programs are provided with a continguous, clean and tidy virtual address space, both the operating system and the hardware are allowed to do crazy things in the background with data residing in the physical memory.
For example, the operating system often delays loading parts of a program from the hard drive until the program attempts to use it. Some of the code will only be run during initialization or when a special condition occurs. A program's page table may be filled with entries that point to non-existing or not yet allocated frames. This case is depicted by the image 3. above, where the last two pages map to nowhere.
Tricks like this one are completely transparent to the application, which keeps reading and writing its own virtual address space unaware of the background noise. However, sooner or later the program may want to access one of the virtual addresses that don't map to the RAM: what to do?
A page fault (also known as page miss) occurs when a program accesses a virtual address on a page not currently mapped to a physical frame. More specifically, a page fault takes place when the page exists in the program's page table but points to a non-existent or not yet available frame in the physical memory.
当程序访问没有映射到物理frame上的虚拟地址时，就发生了 page fault（也称为 page miss）。更具体地说，当一个page在程序的page table中存在，但却指向了物理存储器中不存在或尚不可用的frame时，就会发生 page fault。
The MMU detects the page fault and redirects the message to the operating system, which will do its best to find a frame in the physical memory for the mapping. Most of the time this is a straightforward operation, unless the system is running out of RAM.
Paging is another memory management trick: the operating system moves some pages to the hard drive, to make room for other programs or data when there is no more physical memory available. Sometimes it is also called swapping, although not 100% correct. Swapping is about moving the entire process to disk. Some operating systems do this too, when needed.
Paging gives programs the illusion of an unlimited amount of available RAM. The operating system optimistically allows for a virtual memory address space larger than the physical one, knowing that data can be moved in and out the hard drive in case of need. Some systems (e.g. Windows) make use of a special file called paging file for this purpose. Others (e.g. Linux) have a dedicated hard drive partition called swap area (for historical reasons though, modern Linux performs paging instead of swapping).
分页给程序带来了一种假象，以为可用RAM是无限量的。操作系统乐观地允许虚拟内存地址空间大于物理地址空间，因为它知道数据可以在需要的时候向硬盘中移入移出。有些系统（如Windows）为此目的使用了一个叫做 paging file(分页文件) 的特殊文件。其他系统（如Linux）有一个专门的硬盘分区，称为 swap area(swap区)（由于历史原因，现代Linux执行的是paging，而不是swapping）。
Unfortunately the hard drive is way slower than the main memory. So when a page fault occurs and the page was temporarily moved to the hard drive, the operating system has to read data from the sluggish medium and move it back to memory, causing a lag. All in all, less paging means a system that runs more efficiently.
Thrashing occurs when the system spends more time in paging than running applications, triggered by a constant stream of page faults. This is an extreme corner case that happens if you are running too many programs that fill up the entire RAM and/or the paging area on the hard drive is unoptimized. The operating system tries to keep up with the large amount of page fault requests, constantly moving data between the hard drive and the physical memory, grinding the system to a halt. Thrashing can be avoided by increasing the amount of RAM, reducing the number of programs being run or again by adjusting the size of the swap file.
当系统在paging中花费的时间多于运行应用程序本身时，就出现了 Thrashing 现象。如果你运行的程序太多，占用了整个内存，或者硬盘上的分页区域没有经过优化时，就会出现这种极端的情况。操作系统会努力跟上大量的page faults请求，不断地在硬盘和物理内存之间移动数据，使系统陷入停顿。可以通过增加RAM、减少正在运行的程序数量或调整swap file的大小，来避免thrashing现象。
Virtual memory also provides security across running applications: your browser can't peep into your text editor's virtual memory and vice versa without triggering an error. The main purpose of memory protection is to prevent a process from accessing memory that doesn't belong to it.
The memory protection mechanism is usually provided by the MMU and the page tables it manages, while other architectures may use different hardware strategies. When a program tries to access a portion of virtual memory it doesn't own, an invalid page fault is triggered. The MMU and the operating system catch the signal and raise a failure condition called segmentation fault (on Unix) or access violation (on Windows). The operating system usually kills the program in response.
内存保护机制通常由MMU和它所管理的page tables提供，而其他架构可能使用不同的硬件策略。当程序试图访问不属于自己的虚拟内存时，就会触发 invalid page fault(无效页故障)。MMU和操作系统会捕捉到这个信号，并发出一个称为segmentation fault(分段故障,在Unix上）或access violation(访问违规,在Windows上）的故障条件。作为响应，操作系统通常会杀死该程序。
Segmentation faults and access violations are also often raised by mistake. Programming languages that perform manual memory management give you the ability to set aside portions of memory to be used to store program data: the operating system will provide you with a nice chunk of free memory (a.k.a. a buffer) to read and write according to your program's needs. However, nothing prevents you to read or write outside the buffer boundaries, accessing memory that doesn't belong to your program or simply doesn't exist. The operating system would detect the illegal access and raise the usual violation signal.
Segmentation faults 和 access violations 也常常因疏忽而产生。执行手动内存管理的编程语言允许你预留一部分内存用于存储程序数据：操作系统会给你提供一块不错的空闲内存（又名buffer(缓冲区)），让你根据程序的需要进行读写。但是，没有任何东西可以阻止你在缓冲区边界之外进行读写，访问不属于你的或根本不存在的内存。操作系统会检测到非法访问，并发出通常的违规信号。
Virtual memory paves the road for many other interesting topics. For example, memory-mapped files are a powerful abstraction over the traditional way of reading and writing files. Instead of manually copying data into memory in order to operate on it, memory mapping allows a program to access a file directly from the hard drive as if it was already fully loaded in RAM. The virtual memory mechanism will take care of moving data from the hard drive to RAM as usual, when necessary. Memory-mapped files simplify the programmer's work and usually speed up file access operations. More information here.
Virtual memory also makes more difficult to reason about memory consumption. Suppose one of your programs is taking up 300 megabytes of memory: is it virtual or physical? Is part of that space paged to disk? And if it is, will the paging operations be fast enough? Also, tuning the paging file/swap area is an important step if you want to keep your system in a good shape. Operating systems provide many tools to measure and adjust memory: more information here and here.
Computer Hope — Memory
Peter J. Denning — Before memory was virtual
Android Authority — What is virtual memory?
Kernel.org — Memory Management
Operating Systems: Three Easy Pieces — Chapter 18: Paging
Philippe's Oppermann — Introduction to Paging
Computer Science from the Bottom Up — Chapter 6. Virtual Memory
Dr. John T. Bell — Operating systems, Virtual Memory
StackOverflow — Do modern OS's use paging and segmentation?
StackOverflow — What is thrashing? Why does it occur?
Wikipedia — Memory address
Wikipedia — Paging
Wikipedia — Address space
Wikipedia — Virtual memory
Wikipedia — Virtual address space
Wikipedia — Thrashing
Wikipedia — Segmentation fault
ITPro Today — Paging Performance
Aleph One — Smashing The Stack For Fun And Profit