关于内存管理:虚拟内存精粹

博客原文

虚拟内存精粹

导言

虚拟内存是当今计算机系统中最重要的抽象概念之一，它的提出是为了更加无效地治理内存并且升高内存出错的概率。虚拟内存影响着计算机的方方面面，包含硬件设计、文件系统、共享对象和过程 / 线程调度等等，每一个致力于编写高效且出错概率低的程序的程序员都应该深刻学习虚拟内存。

本文全面而深刻地分析了虚拟内存的工作原理，帮忙读者疾速而粗浅地了解这个重要的概念。

计算机存储器

存储器是计算机的核心部件之一，在齐全现实的状态下，存储器应该要同时具备以下三种个性：

1. 速度足够快：存储器的存取速度该当快于 CPU 执行一条指令，这样 CPU 的效率才不会受限于存储器
2. 容量足够大：容量可能存储计算机所需的全副数据
3. 价格足够便宜：价格低廉，所有类型的计算机都能装备

然而事实往往是残暴的，咱们目前的计算机技术无奈同时满足上述的三个条件，于是古代计算机的存储器设计采纳了一种分档次的构造：

从顶至底，古代计算机里的存储器类型别离有：寄存器、高速缓存、主存和磁盘，这些存储器的速度逐级递加而容量逐级递增。存取速度最快的是寄存器，因为寄存器的制作资料和 CPU 是雷同的，所以速度和 CPU 一样快，CPU 拜访寄存器是没有时延的，然而因为价格昂贵，因而容量也极小，个别 32 位的 CPU 装备的寄存器容量是 32✖️32 Bit，64 位的 CPU 则是 64✖️64 Bit，不论是 32 位还是 64 位，寄存器容量都小于 1 KB，且寄存器也必须通过软件自行治理。

第二层是高速缓存，也即咱们平时理解的 CPU 高速缓存 L1、L2、L3，个别 L1 是每个 CPU 独享，L3 是全副 CPU 共享，而 L2 则依据不同的架构设计会被设计成独享或者共享两种模式之一，比方 Intel 的多核芯片采纳的是共享 L2 模式而 AMD 的多核芯片则采纳的是独享 L2 模式。

第三层则是主存，也即主内存，通常称作随机拜访存储器（Random Access Memory, RAM）。是与 CPU 间接替换数据的外部存储器。它能够随时读写（刷新时除外），而且速度很快，通常作为操作系统或其余正在运行中的程序的长期材料存储介质。

最初则是磁盘，磁盘和主存相比，每个二进制位的成本低了两个数量级，因而容量比之会大得多，动辄上 GB、TB，而毛病则是访问速度则比主存慢了大略三个数量级。机械硬盘速度慢次要是因为机械臂须要一直在金属盘片之间挪动，期待磁盘扇区旋转至磁头之下，而后能力进行读写操作，因而效率很低。

主存

物理内存

咱们平时始终提及的物理内存就是上文中对应的第三种计算机存储器，RAM 主存，它在计算机中以内存条的模式存在，嵌在主板的内存槽上，用来加载各式各样的程序与数据以供 CPU 间接运行和应用。

虚拟内存

在计算机领域有一句如同摩西十诫般神圣的哲言：”计算机科学畛域的任何问题都能够通过减少一个间接的中间层来解决“，从内存治理、网络模型、并发调度甚至是硬件架构，都能看到这句哲言在闪烁着光辉，而虚拟内存则是这一哲言的完满实际之一。

虚拟内存是古代计算机中的一个十分重要的存储器形象，次要是用来解决应用程序日益增长的内存应用需要：古代物理内存的容量增长曾经十分疾速了，然而还是跟不上应用程序对主存需要的增长速度，对于应用程序来说内存还是可能会不够用，因而便须要一种办法来解决这两者之间的容量差矛盾。为了更高效地治理内存并尽可能打消程序谬误，古代计算机系统对物理主存 RAM 进行形象，实现了 虚拟内存 (Virtual Memory, VM) 技术。

虚拟内存

虚拟内存的外围原理是：为每个程序设置一段 ” 间断 ” 的虚拟地址空间，把这个地址空间宰割成多个具备间断地址范畴的页 (Page)，并把这些页和物理内存做映射，在程序运行期间动静映射到物理内存。当程序援用到一段在物理内存的地址空间时，由硬件立即执行必要的映射；而当程序援用到一段不在物理内存中的地址空间时，由操作系统负责将缺失的局部装入物理内存并从新执行失败的指令。

其实虚拟内存技术从某种角度来看的话，很像是糅合了基址寄存器和界线寄存器之后的新技术。它使得整个过程的地址空间能够通过较小的虚构单元映射到物理内存，而不须要为程序的代码和数据地址进行重定位。

虚拟地址空间依照固定大小划分成被称为页（Page）的若干单元，物理内存中对应的则是页框（Page Frame）。这两者一般来说是一样的大小，如上图中的是 4KB，不过实际上计算机系统中个别是 512 字节到 1 GB，这就是虚拟内存的分页技术。因为是虚拟内存空间，每个过程调配的大小是 4GB (32 位架构)，而实际上当然不可能给所有在运行中的过程都调配 4GB 的物理内存，所以虚拟内存技术还须要利用到一种 替换（swapping）技术，也就是通常所说的页面置换算法，在过程运行期间只调配映射以后应用到的内存，临时不应用的数据则写回磁盘作为正本保留，须要用的时候再读入内存，动静地在磁盘和内存之间替换数据。

页表

页表（Page Table），每次进行虚拟地址到物理地址的映射之时，都须要读取页表，从数学角度来说页表就是一个函数，入参是虚构页号（Virtual Page Number，简称 VPN），输入是物理页框号（Physical Page Number，简称 PPN，也就是物理地址的基址）。

页表由多个页表项（Page Table Entry, 简称 PTE）组成，页表项的构造取决于机器架构，不过基本上都大同小异。一般来说页表项中都会存储物理页框号、批改位、拜访位、爱护位和 “ 在 / 不在 ” 位（无效位）等信息。

• 物理页框号：这是 PTE 中最重要的域值，毕竟页表存在的意义就是提供 VPN 到 PPN 的映射。
• 无效位：示意该页面以后是否存在于主存中，1 示意存在，0 示意缺失，当过程尝试拜访一个无效位为 0 的页面时，就会引起一个缺页中断。
• 爱护位：批示该页面所容许的拜访类型，比方 0 示意可读写，1 示意只读。
• 批改位和拜访位：为了记录页面应用状况而引入的，个别是页面置换算法会应用到。比方当一个内存页面被程序修改过之后，硬件会主动设置批改位，如果下次程序产生缺页中断须要运行页面置换算法把该页面调出以便为行将调入的页面腾出空间之时，就会先去拜访批改位，从而得悉该页面被批改过，也就是脏页 (Dirty Page)，则须要把最新的页面内容写回到磁盘保留，否则就示意内存和磁盘上的正本内容是同步的，无需写回磁盘；而拜访位同样也是零碎在程序拜访页面时主动设置的，它也是页面置换算法会应用到的一个值，零碎会依据页面是否正在被拜访来感觉是否要淘汰掉这个页面，一般来说不再应用的页面更适宜被淘汰掉。
• 高速缓存禁止位：用于禁止页面被放入 CPU 高速缓存，这个值次要实用于那些映射到寄存器等实时 I/O 设施而非一般主存的内存页面，这一类实时 I/O 设施须要拿到最新的数据，而 CPU 高速缓存中的数据可能是旧的拷贝。

地址翻译

过程在运行期间产生的内存地址都是虚拟地址，如果计算机没有引入虚拟内存这种存储器形象技术的话，则 CPU 会把这些地址间接发送到内存地址总线上，而后拜访和虚拟地址雷同值的物理地址；如果应用虚拟内存技术的话，CPU 则是把这些虚拟地址通过地址总线送到内存治理单元（Memory Management Unit，简称 MMU），MMU 将虚拟地址翻译成物理地址之后再通过内存总线去拜访物理内存：

虚拟地址（比方 16 位地址 8196=0010 000000000100）分为两局部：虚构页号（Virtual Page Number，简称 VPN，这里是高 4 位局部）和偏移量（Virtual Page Offset，简称 VPO，这里是低 12 位局部），虚拟地址转换成物理地址是通过页表（page table）来实现的。

这里咱们基于一个例子来剖析当页面命中时，计算机各个硬件是如何交互的：

• 第 1 步：处理器生成一个虚拟地址 VA，通过总线发送到 MMU；
• 第 2 步：MMU 通过虚构页号失去页表项的地址 PTEA，通过内存总线从 CPU 高速缓存 / 主存读取这个页表项 PTE；
• 第 3 步：CPU 高速缓存或者主存通过内存总线向 MMU 返回页表项 PTE；
• 第 4 步：MMU 先把页表项中的物理页框号 PPN 复制到寄存器的高三位中，接着把 12 位的偏移量 VPO 复制到寄存器的末 12 位形成 15 位的物理地址，即能够把该寄存器存储的物理内存地址 PA 发送到内存总线，拜访高速缓存 / 主存；
• 第 5 步：CPU 高速缓存 / 主存返回该物理地址对应的数据给处理器。

在 MMU 进行地址转换时，如果页表项的无效位是 0，则示意该页面并没有映射到实在的物理页框号 PPN，则会引发一个 缺页中断，CPU 陷入操作系统内核，接着操作系统就会通过页面置换算法抉择一个页面将其换出 (swap)，以便为行将调入的新页面腾出地位，如果要换出的页面的页表项里的批改位曾经被设置过，也就是被更新过，则这是一个脏页 (Dirty Page)，须要写回磁盘更新该页面在磁盘上的正本，如果该页面是 ” 洁净 ” 的，也就是没有被批改过，则间接用调入的新页面笼罩掉被换出的旧页面即可。

缺页中断的具体流程如下：

• 第 1 步到第 3 步：和后面的页面命中的前 3 步是统一的；
• 第 4 步：查看返回的页表项 PTE 发现其无效位是 0，则 MMU 触发一次缺页中断异样，而后 CPU 转入到操作系统内核中的缺页中断处理器；
• 第 5 步：缺页中断处理程序查看所需的虚拟地址是否非法，确认非法后零碎则查看是否有闲暇物理页框号 PPN 能够映射给该缺失的虚构页面，如果没有闲暇页框，则执行页面置换算法寻找一个现有的虚构页面淘汰，如果该页面曾经被批改过，则写回磁盘，更新该页面在磁盘上的正本；
• 第 6 步：缺页中断处理程序从磁盘调入新的页面到内存，更新页表项 PTE；
• 第 7 步：缺页中断程序返回到原先的过程，从新执行引起缺页中断的指令，CPU 将引起缺页中断的虚拟地址从新发送给 MMU，此时该虚拟地址曾经有了映射的物理页框号 PPN，因而会依照后面『Page Hit』的流程走一遍，最初主存把申请的数据返回给处理器。

虚拟内存和高速缓存

后面在剖析虚拟内存的工作原理之时，谈到页表的存储地位，为了简化解决，都是默认把主存和高速缓存放在一起，而实际上更具体的流程应该是如下的原理图：

如果一台计算机同时装备了虚拟内存技术和 CPU 高速缓存，那么 MMU 每次都会优先尝试到高速缓存中进行寻址，如果缓存命中则会间接返回，只有当缓存不命中之后才去主存寻址。

通常来说，大多数零碎都会抉择利用物理内存地址去拜访高速缓存，因为高速缓存相比于主存要小得多，所以应用物理寻址也不会太简单；另外也因为高速缓存容量很小，所以零碎须要尽量在多个过程之间共享数据块，而应用物理地址可能使得多过程同时在高速缓存中存储数据块以及共享来自雷同虚拟内存页的数据块变得更加直观。

减速翻译 & 优化页表

通过后面的分析，置信读者们曾经理解了虚拟内存及其分页 & 地址翻译的根底和原理。当初咱们能够引入虚拟内存中两个外围的需要，或者说瓶颈：

• 虚拟地址到物理地址的映射过程必须要十分快，地址翻译如何减速。
• 虚拟地址范畴的增大必然会导致页表的收缩，造成大页表。

这两个因素决定了虚拟内存这项技术能不能真正地广泛应用到计算机中，如何解决这两个问题呢？

正如文章结尾所说：”计算机科学畛域的任何问题都能够通过减少一个间接的中间层来解决“。因而，尽管虚拟内存自身就曾经是一个中间层了，然而中间层里的问题同样能够通过再引入一个中间层来解决。

减速地址翻译过程的计划目前是通过引入页表缓存模块 — TLB，而大页表则是通过实现多级页表或倒排页表来解决。

TLB 减速

翻译后备缓冲器（Translation Lookaside Buffer，TLB），也叫快表，是用来减速虚拟地址翻译的，因为虚拟内存的分页机制，页表个别是保留在内存中的一块固定的存储区，而 MMU 每次翻译虚拟地址的时候都须要从页表中匹配一个对应的 PTE，导致过程通过 MMU 拜访指定内存数据的时候比没有分页机制的零碎多了一次内存拜访，个别会多消耗几十到几百个 CPU 时钟周期，性能至多降落一半，如果 PTE 碰巧缓存在 CPU L1 高速缓存中，则开销能够升高到一两个周期，然而咱们不能寄希望于每次要匹配的 PTE 都刚好在 L1 中，因而须要引入减速机制，即 TLB 快表。

TLB 能够简略地了解成页表的高速缓存，保留了最高频被拜访的页表项 PTE。因为 TLB 个别是硬件实现的，因而速度极快，MMU 收到虚拟地址时个别会先通过硬件 TLB 并行地在页表中匹配对应的 PTE，若命中且该 PTE 的拜访操作不违反爱护位（比方尝试写一个只读的内存地址），则间接从 TLB 取出对应的物理页框号 PPN 返回，若不命中则会穿透到主存页表里查问，并且会在查问到最新页表项之后存入 TLB，以备下次缓存命中，如果 TLB 以后的存储空间有余则会替换掉现有的其中一个 PTE。

上面来具体分析一下 TLB 命中和不命中。

TLB 命中：

• 第 1 步：CPU 产生一个虚拟地址 VA；
• 第 2 步和第 3 步：MMU 从 TLB 中取出对应的 PTE；
• 第 4 步：MMU 将这个虚拟地址 VA 翻译成一个实在的物理地址 PA，通过地址总线发送到高速缓存 / 主存中去；
• 第 5 步：高速缓存 / 主存将物理地址 PA 上的数据返回给 CPU。

TLB 不命中：

• 第 1 步：CPU 产生一个虚拟地址 VA；
• 第 2 步至第 4 步：查问 TLB 失败，走失常的主存页表查问流程拿到 PTE，而后把它放入 TLB 缓存，以备下次查问，如果 TLB 此时的存储空间有余，则这个操作会汰换掉 TLB 中另一个已存在的 PTE；
• 第 5 步：MMU 将这个虚拟地址 VA 翻译成一个实在的物理地址 PA，通过地址总线发送到高速缓存 / 主存中去；
• 第 6 步：高速缓存 / 主存将物理地址 PA 上的数据返回给 CPU。

多级页表

TLB 的引入能够肯定水平上解决虚拟地址到物理地址翻译的开销问题，接下来还须要解决另一个问题：大页表。

实践上一台 32 位的计算机的寻址空间是 4GB，也就是说每一个运行在该计算机上的过程实践上的虚构寻址范畴是 4GB。到目前为止，咱们始终在探讨的都是单页表的情景，如果每一个过程都把实践上可用的内存页都装载进一个页表里，然而实际上过程会真正应用到的内存其实可能只有很小的一部分，而咱们也晓得页表也是保留在计算机主存中的，那么势必会造成大量的内存节约，甚至有可能导致计算机物理内存不足从而无奈并行地运行更多过程。

这个问题个别通过 多级页表（Multi-Level Page Tables）来解决，通过把一个大页表进行拆分，造成多级的页表，咱们具体来看一个二级页表应该如何设计：假设一个虚拟地址是 32 位，由 10 位的一级页表索引、10 位的二级页表索引以及 12 位的地址偏移量，则 PTE 是 4 字节，页面 page 大小是 2^12 = 4KB，总共须要 2^20 个 PTE，一级页表中的每个 PTE 负责映射虚拟地址空间中的一个 4MB 的 chunk，每一个 chunk 都由 1024 个间断的页面 Page 组成，如果寻址空间是 4GB，那么一共只须要 1024 个 PTE 就足够笼罩整个过程地址空间。二级页表中的每一个 PTE 都负责映射到一个 4KB 的虚拟内存页面，和单页表的原理是一样的。

多级页表的关键在于，咱们并不需要为一级页表中的每一个 PTE 都调配一个二级页表，而只须要为过程以后应用到的地址做相应的调配和映射。因而，对于大部分过程来说，它们的一级页表中有大量空置的 PTE，那么这部分 PTE 对应的二级页表也将无需存在，这是一个相当可观的内存节约，事实上对于一个典型的程序来说，实践上的 4GB 可用虚拟内存地址空间绝大部分都会处于这样一种未调配的状态；更进一步，在程序运行过程中，只须要把一级页表放在主存中，虚拟内存零碎能够在理论须要的时候才去创立、调入和调出二级页表，这样就能够确保只有那些最频繁被应用的二级页表才会常驻在主存中，此举亦极大地缓解了主存的压力。

多级页表的层级深度能够依照需要一直裁减，一般来说，级数越多，灵活性越高。

比方有个一个 k 级页表，虚拟地址由 k 个 VPN 和 1 个 VPO 组成，每一个 VPN i 都是一个到第 i 级页表的索引，其中 1 <= i <= k。第 j 级页表中的每一个 PTE（1 <= j <= k-1）都指向第 j+1 级页表的基址。第 k 级页表中的每一个 PTE 都蕴含一个物理地址的页框号 PPN，或者一个磁盘块的地址（该内存页曾经被页面置换算法换出到磁盘中）。MMU 每次都须要拜访 k 个 PTE 能力找到物理页框号 PPN 而后加上虚拟地址中的偏移量 VPO 从而生成一个物理地址。这里读者可能会对 MMU 每次都拜访 k 个 PTE 示意性能上的担心，此时就是 TLB 出场的时候了，计算机正是通过把每一级页表中的 PTE 缓存在 TLB 中从而让多级页表的性能不至于落后单页表太多。

倒排页表

另一种针对页式虚拟内存治理大页表问题的解决方案是 倒排页表（Inverted Page Table，简称 IPT）。倒排页表的原理和搜索引擎的倒排索引类似，都是通过反转映射过程来实现。

在搜索引擎中，有两个概念：文档 doc 和 关键词 keyword，咱们的需要是通过 keyword 疾速找到对应的 doc 列表，如果搜索引擎的存储构造是正向索引，也即是通过 doc 映射到其中蕴含的所有 keyword 列表，那么咱们要找到某一个指定的 keyword 所对应的 doc 列表，那么便须要扫描索引库中的所有 doc，找到蕴含该 keyword 的 doc，再依据打分模型进行打分，排序后返回，这种设计无疑是低效的；所以咱们须要反转一下正向索引从而失去倒排索引，也即通过 keyword 映射到所有蕴含它的 doc 列表，这样当咱们查问蕴含某个指定 keyword 的 doc 列表时，只须要利用倒排索引就能够疾速定位到对应的后果，而后还是依据打分模型进行排序返回。

下面的形容只是搜索引擎倒排索引的简化原理，理论的倒排索引设计是要简单很多的，有趣味的读者能够自行查找材料学习，这里就不再开展。

回到虚拟内存的倒排页表，它正是采纳了和倒排索引相似的思维，反转了映射过程：后面咱们学习到的页表设计都是以虚拟地址页号作为页表项 PTE 索引，映射到物理页框号 PPN，而在倒排页表中则是以 PPN 作为 PTE 索引，映射到 (过程号，虚构页号 VPN)。

倒排页表在寻址空间更大的 CPU 架构下尤其高效，或者应该说更适宜那些『虚拟内存空间 / 物理内存空间』比例十分大的场景，因为这种设计是以理论物理内存页框作为 PTE 索引，而不是以远超物理内存的虚拟内存作为索引。例如，以 64 位架构为例，如果是单页表构造，还是用 12 位作为页面地址偏移量，也就是 4KB 的内存页大小，那么以最理论化的形式来计算，则须要 2^52 个 PTE，每个 PTE 占 8 个字节，那么整个页表须要 32PB 的内存空间，这齐全是不可承受的，而如果采纳倒排页表，假设应用 4GB 的 RAM，则只须要 2^20 个 PTE，极大缩小内存使用量。

倒排页表尽管在节俭内存空间方面效果显著，但同时却引入了另一个重大的缺点：地址翻译过程变得更加低效。咱们都分明 MMU 的工作就是要把虚拟内存地址翻译成物理内存地址，当初索引构造变了，物理页框号 PPN 作为索引，从原来的 VPN –> PPN 变成了 PPN –> VPN，那么当过程尝试拜访一个虚拟内存地址之时，CPU 在通过地址总线把 VPN 发送到 MMU 之后，基于倒排页表的设计，MMU 并不知道这个 VPN 对应的是不是一个缺页，所以不得不扫描整个倒排页表来找到该 VPN，而最要命的是就算是一个非缺页的 VPN，每次内存拜访还是须要执行这个全表扫描操作，假如是后面提到的 4GB RAM 的例子，那么相当于每次都要扫描 2^20 个 PTE，相当低效。

这时候又是咱们的老朋友 — TLB 出场的时候了，咱们只须要把高频应用的页面缓存在 TLB 中，借助于硬件，在 TLB 缓存命中的状况下虚拟内存地址的翻译过程就能够像一般页表那样疾速，然而当 TLB 生效的时候，则还是须要通过软件的形式去扫描整个倒排页表，线性扫描的形式十分低效，因而个别倒排页表会基于哈希表来实现，假如有 1G 的物理内存，那么这里就一共有 2^18 个 4KB 大小的页框，建设一张以 VPN 作为 key 的哈希表，每一个 key 值对应的 value 中存储的是 (VPN, PNN)，那么所有具备雷同哈希值的 VPN 会被链接在一起造成一个抵触链，如果咱们把哈希表的槽数设置成跟物理页框数量统一的话，那么这个倒排哈希表中的抵触链的均匀长度将会是 1 个 PTE，能够大大提高查问速度。当 VPN 通过倒排页表匹配到 PPN 之后，这个 (VPN, PPN) 映射关系就会马上被缓存进 TLB，以减速下次虚拟地址翻译。

倒排页表在 64 位架构的计算机中很常见，因为在 64 位架构下，基于分页的虚拟内存中即使把页面 Page 的大小从个别的 4KB 晋升至 4MB，仍然须要一个领有 2^42 个 PTE 的巨型页表放在主存中（实践上，实际上不会这么实现），极大地耗费内存。

总结

当初让咱们来回顾一下本文的核心内容：虚拟内存是存在于计算机 CPU 和物理内存之间一个中间层，次要作用是高效治理内存并缩小内存出错。虚拟内存的几个外围概念有：

1. 页表：从数学角度来说页表就是一个函数，入参是虚构页号 VPN，输入是物理页框号 PPN，也就是物理地址的基址。页表由页表项组成，页表项中保留了所有用来进行地址翻译所需的信息，页表是虚拟内存得以失常运作的根底，每一个虚拟地址要翻译成物理地址都须要借助它来实现。
2. TLB：计算机硬件，次要用来解决引入虚拟内存之后寻址的性能问题，减速地址翻译。如果没有 TLB 来解决虚拟内存的性能问题，那么虚拟内存将只可能是一个学术上的实践而无奈真正宽泛地利用在计算机中。
3. 多级页表和倒排页表：用来解决虚拟地址空间爆炸性收缩而导致的大页表问题，多级页表通过将单页表进行分拆并按需分配虚拟内存页而倒排页表则是通过反转映射关系来实现节俭内存的成果。

最初，虚拟内存技术中还须要波及到操作系统的页面置换机制，因为页面置换机制也是一个较为庞杂和简单的概念，本文便不再持续分析这一部分的原理，咱们在当前的文章中再独自拿来解说。

参考 & 延长浏览

本文的次要参考资料是《古代操作系统》和《深刻了解计算机系统》这两本书的英文原版，如果读者还想更加深刻地学习虚拟内存，能够深刻浏览这两本书并且搜查其余的论文材料进行学习。