操作系统的内存管理机制 Recommended

2月 1, 2021

继续复习操作系统，话说随着 CPU 计算资源的性能开始过剩，压在内存身上的担子越来越重了，堪称新时期的性能瓶颈，对操作系统来说，内存管理机制也要进行近乎极致的优化才可以充分发挥 CPU 的正常水平。

操作系统对内存管理的需求 #

物理内存 #

当前 1T 容量的机械硬盘价格大约是 200 元，而 200 元只能买一个容量为 8G 的内存条。一直以来差不多都是这样的差距，内存的价格永远比硬盘贵，内存的读取速度又比硬盘快得多，如果 CPU 和硬盘直接进行数据交互，理论上可行，实际上计算机的历史早期确实是这么做的，但现在没有公司这么做了，这么做的肯定也倒闭了，因为太影响运行效率，所以必须需要读写速度更快的物理内存这一层来释放 CPU 的计算性能。

虚拟内存 #

有了物理内存，但是其成本还不能太高，不然没有用户买单，那就只能减少内存的容量。这样一来就带来了新的问题，就是绝大多情况下物理内存永远无法同时装下硬盘里的所有程序（也是数据），这是一个持续了几十年的硬件成本导致的架构问题，而且可以预见的未来还会继续存在。

计算机科学家很早就引入了虚拟内存的概念，它是一种技术，通过连续的虚拟地址对物理地址进行映射，虚拟内存的地址范围对应所有硬件的物理地址之和，但就是不占用内存空间，只有在相应的程序（数据）被转入内存运行的时候，那一部分的虚拟地址对应的物理地址才真正的占用了内存空间。除了对硬件设备的 I/O 操作，操作系统中的一切内部操作都是以虚拟内存为标的，CPU 也是通过对虚拟地址的内容进行更新来实现对计算机的硬件设备们进行控制。

Linux 中虚拟内存对进程的管理 #

Linux 系统中，虚拟地址空间分为内核空间和用户空间，其中内核空间的地址一般是 0 到 TASK_SIZE，用户空间是 TASK_SIZE 到 CPU 最大可寻址的地址。各个系统进程之间的用户空间是完全隔离的，而内核空间则是相同的。这么做是为了保护各个系统进程，使之彼此隔离。虚拟地址关系到进程的用户空间和内核空间，而物理地址则用来寻址实际可用的内存。不同进程中可以有同一个虚拟地址，虚拟地址对应的物理地址由进程的页表（下面会提到）决定实际的映射。

地址翻译 #

应用程序使用虚拟地址访问存储在内存中的数据和代码，程序执行时，CPU 会把虚拟地址转换为物理地址，这个过程就是地址翻译，其中 CPU 内部的内存管理单元（Memory Management Unit，MMU），它负责将虚拟地址翻译成物理地址，MMU 是 CPU 的重要组件。同时为了加速地址翻译的过程，现代 CPU 一般都引入了转址旁路缓存（Translation Lookaside Buffer，TLB），TLB 是属于 MMU 内部的单元。

TLB 可以加快 CPU 的寻址速度，它缓存了虚拟页号到物理页号的映射关系，可以通过 TLB 直接完成地址翻译的过程成为 TLB 命中，反之就是 TLB 未命中。由于 TLB 的缓存项的数量有限，需要有效地加以利用，才能尽可能提高 TLB 的命中率。如果 TLB 未命中时，就需要通过页表进行查询，如果 TLB 已满，还会根据硬件预定的策略进行替换。操作系统在切换页表（切换程序）的时候也需要主动刷新 TLB。

支持虚拟内存进行地址翻译的机制主要有两种：分段机制和分页机制，实际的场景中分段和分页可以结合使用。

分段机制 #

在分段机制中，操作系统以“段”（segment）的形式进行物理内存的分配，每一个段由段号和段内地址（偏移量）组成，每个段的大小并不要求完全一样，可以根据实际情况进行分配，比如代码段、数据段等。

段表 #

每个进程都会有一个段表，当 MMU 进行地址翻译时，会先读取段表基址寄存器得到段表位置，然后根据段号查询段表得到对应的物理内存的起始地址（物理地址），这个起始地址加上虚拟地址中的段内地址，就是最终的物理地址。

碎片问题 #

分段机制，看似在分配的时候可以充分利用内存空间，但是在回收内存的时候问题却非常明显：大小不等的内存被回收后，无法合理适配下一个程序需要的内存大小，故会存在非常多的内存碎片，无论分配算法多么高级，回收再次分配的过程仍然会显著影响性能（时间复杂或空间复杂），严重降低内存再次使用的利用率。

分页机制 #

最初的操作系统普遍使用分段机制，Intel 公司在 8086 处理器上开始引入分段机制，在 80286 处理器上使用分段机制支持虚拟内存，在后期的 x86-x64 架构之后，基于分页机制的虚拟内存已经成为主流，但处理器为了保持向前兼容旧版本操作系统仍然支持分段机制。

分页区别与分段最大的区别是，分页是把应用程序的虚拟地址空间分成连续的、等长的虚拟页（也叫页面，page），同时对应的物理内存也被划分为连续的、等长的物理页（也叫页框，page frame）。Linux 中默认的页大小是 4KB，主存和磁盘之间的数据交换总是以整个页面为单位进行的，即使内存只向磁盘改动了一个字节。

分页按照固定大小分配物理内存，使得物理内存更容易管理，解决了分段的外部碎片问题，但也引入了页内部碎片的问题，页如果设置过大就会浪费内存空间，降低内存利用率。

页表 #

在分页机制下，虚拟地址（也叫逻辑地址）也由两部分组成：虚拟页号（高位部分）和页内偏移量（低位部分）。在具体的地址翻译过程中，MMU 首先解析得到虚拟地址的虚拟页号，然后通过页表基地址寄存器从应用程序的页表中读取到对应的物理页号，最后通过物理页号对应的物理页中的起始地址加上虚拟地址中的页内偏移量得到最终的物理地址。

如果一个进程的所占内存固定，页的空间越小，表示的地址范围也就越小，进程中需要的页的数量就会越多，页表就会越大。很多操作系统至今页的默认大小还是 4KB（$ 2^{12} $），那么如果程序需要 4G（$ 2^{32} $）内存空间，按照上图的单级页表形式，这个进程将会有 100 万个页。

$$ {2^{32} \over 2^{12}} = 2^{20} \approx 100万 $$

而如果这里面每个页都需要 4 字节的页表项（Page Table Entry，PTE）进行映射，则需要一个占用 4MB（$ 2^{20} \times 4 $）的内存空间的页表来维护这些页。按照这个算法，我们现在大多使用的是 64 位操作系统，为了能够表示所有的虚拟内存，即 0 ~ $ 2 ^ {64} $ 字节的范围，这需要一个由 $ 2^{52} $ 个页表项组成的页表，如果每个表项需要 8 字节，那么整个页表就会超过 3000万 GB（30PB），这已经是一个内存中无法放下的大小了。

由于这个问题，现在操作系统不会在内存中保持应用程序的所有页表项，通常会使用倒排页表或多级页表解决这个问题，但是它们都依赖缺页异常机制来进行换页，下面开始详细介绍。

换页 #

当内存中空间不足以放下两个程序时，此时有必要将其中一个程序所占用的内存数据换出到磁盘上，来运行另一个优先级更高的程序。这个过程通常为：

1. 操作系统希望回收程序 A 的物理页 P，把 P 的空间让给程序 B；
2. 操作系统将物理页 P 的内容写到磁盘上的一个位置，并在程序 A 的页表中去除虚拟页 V 的映射；
3. 此时物理页 P 就可以被操作系统回收，并分配给程序 B。

缺页异常 #

接上面的例子，当再次访问程序 A 的虚拟页 V 时，会发现 V 处于已分配但未映射至物理内存，就会触发缺页异常。这时 CPU 会运行操作系统的缺页异常处理函数，该函数会找到一个空闲的物理页，将之前写入到磁盘的数据内容重新加载到物理页中（可能还是换页的方式），并在程序 A 的页表中填写虚拟页号对应的物理页号。

可见操作系统应尽可能地减少触发缺页异常，通常会采用预取机制，在页换入的时候预测还会有哪些页可能即将被访问，从而提前读入到物理内存。

另外操作系统也可以在分配内存的时候，只分配虚拟内存，并不为虚拟内存分配对应的物理内存，从而减少多余的内存占用，只在真正需要物理内存的时候，通过触发缺页异常来读取磁盘的数据，从而提高资源利用率。

多级页表 #

接上面计算的例子，如果每个页都需要 4 字节的表项进行映射，内存占用 4G 的程序就需要一个 4MB（$ 2^{20} \times 4 $）内存空间的页表，而 4MB 的内存空间又可以由 $ 2^{10} $（$ {4MB \over 4KB} = {2^{22} \over 2^{12}} $）个页表项组成的一个大小为 4KB 的根页表来表示，这样就形成了一个两级的多级页表：4KB 的根页表表示 4MB 的物理页号映射表，4MB 的物理页号映射表示 4GB 的内存数据映射。为了支持现在 64 位的操作系统，实际情况可能会有更多层级映射，比如 Linux 就采用了四级页表，而由于多级页表的存在，大多情况下，一个页表的最大长度也被限制为一页。

倒排页表 #

对于 32 位的虚拟地址空间，多级页表还可以很好的发挥作用，但是随着 64 位计算机的普及，情况发生了彻底的变化，多级页表也不可避免得多了太多级了。于是更多的操作系统使用了倒排页表（Inverted Page Table）方案。

在倒排页表中，每一个页框有一个页表项，而不是每一个虚拟页面有一个页表项。表项记录了该页框对应了哪一个虚拟页面、进程。因为虚拟地址总是比主存的物理地址多出好几个数量级，所以倒过来映射后，页表项的数量也会显著减少，从而节省了大量的页表空间，但是也带来了新的问题。

最显著的问题是，CPU 负责地址翻译的组件 MMU 的工作会很困难，它必须搜索整个倒排页表来确定虚拟地址对应的物理地址。改善这个问题的办法就是使用 MMU 的 TLB 单元，如果 TLB 能够记录这些频繁使用的页面，地址转换的工作就会像“正排页表”一样快，但是当 TLB 失效时，就会非常麻烦。改善 TLB 失效这个问题的办法就是再引入一张散列表，key 为虚拟地址的散列值，value 为 虚拟地址+页框 组成的链表，大多情况下这个链表长度就是 1，有了这张散列表，就可以大大提高查找速度。

换页策略 #

换页操作可以决定必要时哪些页要被换入换出，有了多级页表和缺页异常等机制的支持，一个程序运行时不必把全部页加载到内存，用到时再加载也可以，而如果某些页被频繁的换入和换出，势必会影响性能。所以换页策略的好坏对操作系统非常重要，换页策略有的地方也叫页替换策略、页面置换算法。

随机更换策略 #

随机更换非常好理解，关于随机算法的理论有效性可以看一个大猩猩扔飞镖选股的故事，看起来好像确实有效，所以会有这个算法。但是实际上，相比下面其他的策略，随机更换策略可以说是最差的一种策略了。

FIFO 策略 #

倒数第二差的就是 FIFO（First-In First-Out，先进先出）策略了，也是最简单的换页策略之一，该策略优先换出当初最先换入的页，这种方式只需要维护一个用于记录物理页号的队列，每换入一个物理页就把其页号加到队尾，因此最先换出的也就是队头位置。算法复杂度很低，看似公平合理，但也可以说没有优化可言，所以现在 FIFO 策略实际使用中，往往效率还是偏低，需要进行改进。

Second Chance 策略 #

Second Chance 策略是对 FIFO 策略的改进，在此算法中，会为队列中的页号再维护一个访问标志位，有值时表示该页被再次使用过。当需要换出队首的页时，如果页的访问标志位有值，就会把这个页放入队尾并将标志位清零，然后继续从队首寻找要换出的页，相当于给了第二次机会，故称 “Second Chance”。

这个算法，本身也不复杂，而且减少了多次使用的页换入换出的频率，有效提高了内存使用效率。

时钟算法策略 #

Second Chance 策略在每次换页时移动队列中的元素也会造成链表插入和删除的开销，时钟算法策略就可以解决移动链表元素的问题。在时钟算法里，原来的链表队列就像是一个环形的时钟，另外还有一个指针，指向了访问标志位为 0 的位置，意味着下一次换页的首选。当指针指向的物理页被换出后，指针会顺时针继续检查下一个物理页的访问标志位，如果不为 0，则置为 0；如果为 0，就停止检查。

时钟算法策略通过只增加一个指针的方式，就避免了每次换页时对链表元素的移动，实现了和 Second Chance 一样的效果。

LRU 策略 #

LRU（Least Recently Used，最近最少使用）策略会优先选择队列中最少被使用的页换出，该策略的假设是：频繁使用的页在以后也会被频繁使用。LRU 策略实现时，需要操作系统维护一个链表，每次物理页被访问后，将该页的页号插入在链表末尾，这样一段时间后，最久未访问的页号就会在链表首部，最近访问的页号在链表尾端。可以发现，遍历链表的时间和空间复杂度都是 O(n)，如果真要操作系统实现这套精细管理的逻辑，遍历开销往往就会很大。

实际情况除了链表，操作系统中 LRU 策略还有其他的实现方式，比如使用矩阵、使用移位寄存器等方法。

NRU 策略 #

NRU（Not Recently Used，最近未使用）策略是针对 LRU 算法实现复杂的一个“低配版”替代，由于精确记录最少被使用的要求在实现上复杂度很高，这样的投入换来的效率提升也就不会太明显，所以在 NRU 算法中，不会去花费精力维护一个全局确定的有最少被使用顺序的链表。它基于的假设会宽松一些：只要不是换出最近使用过的页就好。这个“最近”的时间粒度一般为一个时钟中断周期（典型的时间是 20ms）。

NRU 策略使用了页在页表项上的访问位（R 位）和控制位（M 位）。当启动一个进程时，它的所有页的这两个位都为 0，当页被访问时 R 位置为 1，当页被修改时，M 位置为 1，另外 R 位会被定期（每个时钟中断）置为 0。由此页可被分为 4 类：

在需要换页时，会按照 1、2、3、4 优先级的顺序，从这些类型里依次寻找并替换。通过这种方式，粗略地实现了换出最近一段时间内最少被访问的页。

MRU 策略 #

MRU（Most Recently Used）策略与 LRU 基于的假设相反：程序不会反复地访问相同的地址。所以在实现时，会优先换出最近访问的内存页，这个场景现实中也有很多例子，比如视频播放器播放电影，程序通常每一帧数据只会读取一次。

MIN 策略 #

MIN（Minimum）策略又称为最优策略（Optimal 策略、OPT 策略）。它指的是在已知未来的页使用顺序的情况下，得出一个确定的最优的结果。然而现实情况是不会有一个确定的最优解，最优解只存在于理论情况下，因为 CPU 没法预测用户下一步的真正操作，我们只能在操作之后进行复盘，这个 MIN 的结果主要就是用于衡量其他策略的优劣。

工作集模型 #

在选择和实现页替换策略的时候，操作系统的原则是以最小的算法开销达到尽可能接近 MIN 策略的效果。而如果换页的开销比实际运行程序的工作量还大，就适得其反，可能导致系统效率严重下降，造成颠簸现象（或称抖动现象）。操作系统为了降低缺页率、颠簸的问题，引入了工作集模型。

在工作集模型中，一个进程当前正在使用的页面的集合称为它的工作集，除非整个进程没有触发过缺页异常，这个工作集的页面集合一般都是随着程序的运行持续变化的。如果有一种算法，能够大致维持这个工作集的内容保持稳定不变，那么这对内存资源的利用就是非常高效的，这种算法一般被称为基于工作集的页面置换算法。

算法的基本思路是在必要时找出一个不在工作集中的页面并淘汰它。与上面的 NRU 策略类似，工作集算法同样利用了页表项的 R 位和 M 位，并且在此基础上又增加了一个表示 上次使用时间 的域 T。读取页时，会将 R 置为 1，并将当前时间写入 T，那么这个页就会进入工作集。

在定期的检查中，也会清除每个页 R 位的值。当触发了缺页异常时，如果 R 是 0，表示在当前周期内没有被访问过，这时需要计算它的生存时间，即

$$ 生存时间 = 当前时间 - T $$

（1）如果生存时间大于每个时钟中断周期，那么这个页面就不应再在工作集中，就可以用新的页面替换它，然后继续扫描直到换入足够的页面。

（2）而如果 R 是 0，且生存时间小于时钟中断周期，则该页面仍然在工作集。

在这个算法中，同样需要扫描整个页表才能确定被淘汰的页面，于是有一种优化，基于上面介绍过的时钟策略，叫做工作集时钟（WSClock）算法。与时钟算法一样，所需的数据结构是一个以页框为元素的循环表，形似时钟，也会有一个指针。每次缺页中断时，首先检查指针指向的页面，如果 R 为 1，表示该页面在最近一个周期内被使用过，不适合淘汰，这时会把 R 置为 0，并让指针指向下一个页面继续检查，指针最终会停留在一个符合“不在工作集”条件的页上面，即可以淘汰的页。

虚拟内存管理 #

虚拟内存通过抽象出一个独立的、连续的内存地址空间，再通过页表和 MMU 硬件的配合，在对应用程序透明的前提下实现虚拟地址到物理地址的翻译。除此之外，虚拟内存的抽象还带来了以下的高级功能。

共享内存 #

共享内存机制是指同一个物理页在同一时间允许不同的应用程序之间共享，共享内存的基本用途是让不同程序之间互相通信、传递数据。基于共享内存，又衍生出了写时拷贝、内存去重等功能。

写时拷贝 #

在 Linux 中复制进程，也就是使用 fork() 函数时，为了节省空间，大部分内存空间都不会被复制，写时复制技术只是装作已经复制了内存空间，实际上是将内存空间共享了。当我们对共享内存空间进行写入时不能直接重写共享内存，因为从其他程序访问时会发生数据不一致的情况，而是会通过触发缺页异常换入新的页拷贝一份再写入。复制后只访问这个私有空间，不访问共享内存。

内存去重 #

有了写时拷贝机制，操作系统可以进一步扫描具有相同内容的物理页，并在页表中找到对应物理页的虚拟页，然后保留一个物理页，释放另一个物理页，这个功能就是内存去重。Linux 实现了这个功能，叫做 KSM（Kernel Same-page Merging）。内存去重是操作系统主动发起的，可能也会对正常运行的程序访问内存数据的效率造成影响。

内存压缩 #

将物理页换出到磁盘会比较慢，相比之下，将物理页的内容直接进行压缩，也可以腾出空闲的内存空间。恢复时（类似换入）不需要从磁盘写入，也可以获得比较快解压的速度。

物理内存管理 #

物理内存管理的核心工作就是对内存的分配和回收，这两者是紧密配合的，不过其需要的理论基础还会更多一些，其功能在字面意义上已经非常好理解，所以具体的分配和回收算法我会在 常见的垃圾回收算法 中进行详细介绍。

参考 #

讲理论的书非常多，列在了下面，另外源码级的内核研究特别推荐 深入 Linux 内核架构。

操作系统之哲学原理

现代操作系统：原理与实现，这本书的勘误和反馈在这里，可以参考。

现代操作系统（第 13 章的操作系统设计，特别值得一读）

操作系统 – 精髓与设计原理

操作系统导论