冯-诺依曼老爷子告诉过我们，算术逻辑单元和控制器单元组成的 CPU 负责进行运算以及程序流程的控制。运算所需要的指令和数据由 内存 来提供。
那么，如果让你作为操作系统的顶层设计者，你会提供一种什么机制，让 CPU 可以从内存中获取指令和数据呢？
用 C 语言写一个 Hello World，通过 objdump 查看汇编代码。我随便截取一行。
mov 0x200aed(%rip),%rax # 200fe8 <__gmon_start__> 复制代码
这一行汇编代码中包含了一个内存地址。这个内存地址是物理内存中的真实地址吗？
我们假设它就是真实的物理地址，但是程序员在编程时是无法得知要运行的设备的内存信息的，所以针对不同的操作系统，得在编译期将程序中的地址转换为真实物理地址。这在单道编程的情况下可行，对于多道编程呢？不同的程序之间如何确定各自在内存中的位置？
从单道编程到多道编程是计算机发展前进的一大步。CPU 通过轮询时间片的方式让多个程序仿佛在同时运行。显然，在程序中使用真实的物理地址会打破这一幻像，不同的程序之间不得而知对方用的是哪一块物理内存，各自的内存完全无法得到保护。
所以，程序中的地址不能是真实的物理地址，但又要与真实的物理地址存在一定的映射关系 。我们把程序中的地址称为 虚拟地址 ，它至少应该具备以下特性：
- 能通过一定的机制映射到真实的物理地址
- 保证不同的程序(进程) 映射的真实物理地址之间互相独立
- 它应该是自动工作的，对于程序开发者来说是透明的
基于这三个特性，我们一起来探究一下 虚拟内存 的工作方式。
一个萝卜一个坑，分段
最直观的解决方案，给每个程序分配一块独立的内存空间，如下图所示。
对于每个程序来说，它的虚拟内存空间都从 0 开始，基址寄存器 中存储其在物理内存空间的起始地址。所以，物理地址和虚拟地址之间就存在这样的关系：
物理地址 = 虚拟地址 + 基址 复制代码
这样的地址转换由叫做 内存管理单元(Memory Management Unit，MMU) 的硬件负责完成。
界限寄存器 可以存储程序占用内存的大小，也可以存储界限的物理地址，它提供基本的内存访问保护。如果 MMU 转换出的物理地址超过了界限，将会触发异常。每个 CPU 都有一对基址寄存器和界限寄存器，当发生进程切换时，更新寄存器的值，这样就做到了进程间内存独立。
乍一看，基本满足了虚拟内存的三个特性，但事实上基本没有操作系统会这么干。由于它需要在虚拟内存和物理内存中分别分配一块连续的内存空间，再进行内存映射。这样的缺点很明显。
第一，容易造成内存碎片。假设内存经过一段时间的使用，还剩下两块 128 MB 的小块，但此时用户需要运行一个内存占用 129 MB 的程序，在此机制下就无法成功分配内存。虽然可以通过内存交换，将内存拾掇拾掇，和磁盘换来换去，把空余内存拼接起来，但是这么大一块数据，磁盘读写的速度实在太慢了，性能上根本无法接受。
第二，浪费了很多内存空间。如果把二八法则搬到计算机上，一个程序最经常运行的代码可能两成都占不到。而上面的方案在一开始就要分配好整个程序需要的内存空间，堆和栈之间有一大块的内存是空闲的。
上面的方案暂且可以看成一种特殊的 “分段”。我们可以试着把段分的更细一些。
典型的 Linux 进程用户空间内存包含栈、共享库、堆、数据、代码等。我们可以按这些基本类型来分段，为了方便演示，下图中仅分为 栈、堆、代码 三个段。
将程序按逻辑分为一段一段，放入内存中对应的段区域内，这样避免了之前的方案中堆和栈之间的空间浪费，真正需要内存的时候才会去申请。同时顺带实现了共享。对于一些可以公用的系统基本库，在之前的方案中仍然需要拷贝到各个进程独立的空间中。而分段的方案中，只需要一份拷贝就行，不同进程间的虚拟地址映射到这一份物理拷贝就可以了。
但是由于各个段的大小不一致，内存碎片的问题可能并不比上一个方案好到哪里去。
另外，上面提到的所有方案都没有考虑到程序大小的问题。如果程序大小大于物理内存，你再怎么分段也没有办法解决问题。
把段再分细一点，分页
为了解决分段产生的内存碎片问题，我们把段分的再细一些，细成一个一个固定大小的页面，虚拟内存和固定内存都是如此。这个固定大小在当前主流操作系统中一般是 4 KB ，部分系统也支持 8 KB、16 KB、64 KB。
将虚拟页和物理页一一对应起来，虚拟地址到物理地址的转换就不是难事了。
不论是虚拟内存还是物理内存，在分页之后，给每页拟定一个 页号，再根据 页内偏移量 就可以取到数据了。由于虚拟页和物理页的页大小是一致的，所以页内偏移量无需转换，只需要把虚拟页号转换为物理页号就可以了。
而虚拟地址正是由 虚拟页号 和 页内偏移量 组成。
操作系统将虚拟页号到物理页号的映射关系保存在 页表 中，页表是一个 页表项(PTE) 的数组，页表项包含了有效位，物理地址等数据。页表直接使用虚拟页号作为索引，找到对应的页表项。
上图中的第 3 个虚拟页被映射到了第 2 个物理页。其实 虚拟页可以被映射到任意物理页，连续的虚拟页也不需要对应连续的物理页，这给了操作系统很大的自由。不仅相对减少了内存碎片的产生，也能更方便的实现进程间的数据共享，只要将不同进程的虚拟页映射到同样的物理页就行了。
为了能直接使用虚拟页号作为索引检索到页表项，页表中的所有页表项必须连续的，并且要提前创建好。那么问题来了，页表有多大？
以 32 位操作系统为例，最大寻址空间为 2 ^ 32 = 4 GB，页的大小为 4 KB，所以共需要 1 M 个页表项。每个页表项大小为 4 个字节，所以一个页表的大小为 1 M * 4 B = 4 MB 。为实现进程隔离，每个进程又必须有自己独立的页表。顺手看一下你的操作系统，至少都得有上百个进程在同时运行，光页表就得占用几百兆内存，这显然是不合适的。
实际上，对大多数程序来说，并不需要占用全部的 4 GB 虚拟内存，所以没有必要在一开始就分配完整个页表。使用多级页表可以解决这个问题。
时间换空间，多级页表
还是以 32 位操作系统为例，来看个简单的二级页表。
第一级叫 页目录项 ，共有 1 K 项。每一个页目录项又对应着 1 K 个 页表项，总共 1 K * 1 K = 1 M 个页表项，正好对应着 4 GB 的寻址空间。
对于 32 位的虚拟地址来说，正好 10 位对应着 1 K 个页目录项索引，10 位对应着指定页目录项下的 1 K 个页表项索引，剩下 12 位正好对应页大小 4 KB 的页内偏移量。
算一下二级页表的大小。1 K 个一级页目录项一共 4 KB，1 M 个二级页表项一共 4 MB ，加起来一共 4.004 MB 。
所以，二级页表比普通页表占用的内存还要大？其实并不然。
首先得明确一点，不管是几级页表，都必须要能覆盖整个虚拟空间。对于只有一级的普通页表来说，一上来就得初始化所有页表项，才能覆盖到整个虚拟空间地址。而对于二级页表来说，1 K 个一级的页目录项就可以足以覆盖，二级页表项只有在需要的时候才被创建。这样就可以节省相当一部分内存。
另外，二级页表可以不存储在内存中，而是存在磁盘中。这倒并不是专门为多级页表而设计的，这是虚拟内存分页的特性，也正因如此，程序的大小可以大于实际物理内存的大小。
页命中和缺页
回想一下之前描述的寻址过程。虚拟地址经过内存管理单元 MMU 的处理，找到对应的页表项 PTE ，转换为物理地址，然后在物理内存中定位到对应的数据。这种理想的情况叫做 页命中 ，根据虚拟地址直接就可以在内存中获取到数据。
但是，并不是任何时候都可以直接根据 PTE 在内存中拿到数据的。最典型的情况，程序的大小大于物理内存，必然会有数据不存在内存中。另外，由于多级页表并不是开始就创建，所以 PTE 对应的数据可能也不在内存中。
在任意时刻，虚拟内存页都可以分为三个状态：
- 未分配的：还未分配（或创建）的页。没有任何数据与其关联，不占用任何磁盘空间
- 已缓存的：当前已缓存在物理内存中的已分配页
- 未缓存的：未缓存在物理内存中的已分配页
只有已缓存的虚拟页可以发生页命中，实际上 PTE 会有一个有效位来表示页表是否有效，假设 0 表示有效，1 表示无效。
有效位为 0，表示 PTE 可用，直接读数据即可。有效位为 1，在不考虑非法内存地址的情况下，可以认为是未分配或者未缓存，无法直接从内存中读取数据，这种情况称为 缺页 。
一旦发生缺页，将由系统的缺页异常处理程序来接管，它会根据特定算法从内存中寻找一个 牺牲页，如果该牺牲页数据被修改过，要先写回磁盘，然后将需要的页换到该牺牲页的位置，并更新 PTE。当异常处理程序返回时，它会重新执行之前导致缺页的命令，也就是之前的寻址操作，这次就直接页命中了。
看到这，你会发现缺页是一个非常昂贵的操作，操作系统必须尽量减少缺页的发生，所以如何寻找合适的牺牲页是个大问题。如果你替换了一个即将要访问的页，那么一会又得把它换回来，这样频繁的换来换去是无法接受的。关于具体的替换算法，可以阅读 《操作系统导论》第22章 超越物理内存：策略 。
给页表加一层缓存，TLB
再说回到页表，将虚拟地址转换为物理地址，如果使用未分级的普通页表只需要一次内存访问，但占用内存较大。大多数操作系统使用的是多级页表，例如目前的 64 位 Linux 操作系统，使用的是 四级页表，内存占用小了很多，但付出的代价是要访问四次内存。其实这就是一个 时间换空间 的策略。
另外，程序执行时的一连串指令的虚拟地址是连续的，相连几个虚拟地址通常是在一个虚拟页中，自然而然它们都对应着同一个物理页。但是无论页表如何设计，访问相邻的虚拟地址，每次仍然都要去访问页表。这里是一个可以优化的点。
计算机科学领域里的任何问题，都可以通过引入一个中间层来解决。
既要保留多级页表的低内存特性，又要避免多余的内存访问，那就再加一层 缓存 吧。
TLB（Translation Lookaside Buffer） ，有的资料翻译成 翻译后备缓冲器，有的翻译成 地址变换高速缓存，且不纠结这个名字。TLB 是封装在 CPU 里的一块缓存芯片，它就是页表的缓存，存储了虚拟地址和页表项的映射关系。
当进行地址转换时，第一步就是根据虚拟地址从 TLB 中查询是否存在对应的页表项 PTE 。如果 TLB 命中，就不用访问页表了，直接根据 TLB 中缓存的物理地址去 CPU Cache 或者内存取数据。如果 TLB 未命中，和缺页的处理流程类似，通过抛出一个异常，让 TLB 的异常处理程序来接手，它会去访问页表，找到对应的页表项，然后更新 TLB 。当异常处理程序执行完后，会再次执行原来的指令，这时候会命中 TLB 。可想而知， TLB 的命中率直接影响了操作系统运行的效率。
总结
先说说为什么写了这么一篇文章。
最近在读 《深入理解 Android 内核设计思想》Binder 相关章节的时候，发现对 mmap 没有一个深度认识的话，就很难理解 Binder 只复制一次的底层逻辑。而如果对虚拟内存机制又没有一个很好的理解的话，也很难去理解 mmap 的实现原理。算是一环扣一环，倒逼学习了一波。
其实编程领域的很多问题，归根到底都是针对计算机操作系统的特性，做出的解决方案和妥协。打好操作系统的扎实基础，对学习任何编程相关的知识，都是大有裨益的。但另一方面，操作系统的知识也多且杂，我也不敢保证我这篇文章没有任何错误。如果你对上面的内容有不同意见，欢迎评论区和我探讨。
最后，一张图总结虚拟内存的工作机制。
