虚拟内存原理

按需调页

虚拟内存（Virtual Memory）是一个或多个逻辑地址空间的集合。其中每个逻辑地址空间的大小可以超过物理内存空间。这样的逻辑地址被称为虚拟地址。通常来说，每个程序都有自己的虚拟内存，这些虚拟内存的页（Page）要通过加载到物理内存的帧（Frame）中才能被使用。由于虚拟内存要比物理内存大得多，操作系统要有一套完善的调度体系来维持内存的合理利用。

按需调页（Demand Paging）是加载页的一个原则，它规定了只有在需要的时候，内存才会加载页，而不是一次性将所有页加载进物理内存。这就需要一个标记符号。有效-无效位（Valid-Invalid Bit），有时候也叫存在位（Present Bit），被用于表示一个页是在磁盘还是内存中。当一个页在物理内存中的时候，它是 1，否则是 0。当一个进程试图访问那些在内存中不存在的页的时候，页错误（Page Fault，又称缺页中断）就会产生。

我们要在常规页表的基础上加上有效-无效位，用于表示一个页是否在物理内存中。如果进程执行到了某个存在位是 0 的页，页错误就会产生。这时，这个没有被加载的页就会从磁盘（虚拟内存存储介质）被加载到物理内存中，页表的存在位也会相应的变成 1。这样，这个页就能被访问了。

存在位示意图

如上图所示，在页表上加入了一个存在位。存在位表示该页是否加载到了内存中。比如 P3 的存在位是 0，这表示该页没有被加载到内存中。这个时候系统就要将这个没有被加载到物理内存中的页加载进来。

需要注意的是，页表的任务只是将页和帧对应起来。一个程序被分配到的逻辑内存是固定的，但是它占用的页不是整个逻辑内存空间。所以加载哪一个页不是由页表决定的，反而是系统决定加载了哪一个页之后更新这个页表的存在位（见下图）。

存在位更新示意图

页置换

虚拟内存比物理内存要大得多。当所有的帧都被使用，且新的页错误产生的时候，其中一个在物理内存的页一定要被移出内存以释放空间给新的帧。页置换（Page Replacement）的概念便是更换一个在内存中的页到另一个页的过程。

在内存和磁盘之间移动这些页十分地耗费时间，必须要有一个方法来减少这样的损失。如果一个页被移出内存，而且它在内存的过程中没有被修改过（即与磁盘上的内容一致），那么就不需要将它复制回磁盘中。这个方法好用，不过我们需要一个修改位（Modified-Bit，通常称为 Dirty Bit，D位或 M位）来记录一个页是否被修改过。如果修改位为 1，则修改位对应的页被修改过，否则没有。

修改位示意图

多层页表

我们说过一个虚拟内存可以是很大的，它甚至可以比物理内存的大小还要大出许多。并不是所有的程序都需要很大的地址空间的，这样一来虚拟内存的页表就浪费了（存在大量空项）。为了能够节省这种浪费，我们要在之前的页表前加上一级页表。如此一来，逻辑地址的映射关系就从二级拓展到了多级，例如从 $(p, w)$ 变成了 $(p1, p2, w)$。

多层页表结构图

这也就是说，当需要将物理内存某个帧置换的时候，首先要找到该帧所对应的二级页表 $p2$，然后再根据 $p2$ 找到一级页表 $p1$，依此类推找到完整的映射关系并且核验过大小一致之后才能将内容写入磁盘。

固定帧的页置换算法

系统只有固定的帧数，一个给多个进程分享帧的方法是分配一段固定的帧给这些进程。当出现页错误，并且没有空闲的帧出现的时候，操作系统要将其中一个在内存中的页换掉。引用串（Reference String，又称访问串）是某个时刻，正在运行的程序调用的一组页码。通过比较页错误次数，引用串被用于比较不同页置换算法的优劣。比如上面我们说页表的那张图，里面有两个程序。程序 1 的引用串是 $P1, P3$；程序 2 的引用串是 $P1, P2, P5$。这只是在某一个时刻它们页调用的情况。下面我们利用引用串来说明几个置换算法。

最优置换算法

最优置换算法（Optimal Page Replacement Algorithm, OPT）会选择替换掉在未来最长时间内不会被调用的页。这个算法是所有置换算法中产生页错误最少的。

先进先出置换算法

先进先出置换算法（FIFO Page Replacement Algorithm）会选择替换掉在内存停留最长时间的页。不要混淆了，最优置换是换掉未来最不可能用到的页，而这个算法是换掉“最老”的页。

最近最少使用算法 (LRU)

最近最少使用算法，或者 LRU 算法（Least-Recently-Used Page Replacement Algorithm），会替换掉最长时间没有被引用的页。这个算法在硬件实现上通常需要一个长度为 $n$ 的栈或队列，其中 $n$ 是内存中帧的帧数。这个结构包含了所有在内存中的页。

当一个驻在内存中的页被引用，它会被挪到栈顶（或队列头），这保证了结构永远都让最近被使用的页排在最前面。当一个没有驻在内存中的页被引用（发生页错误），它会被放在栈顶（或队列头），如果此时结构已满，那么栈底（或队列尾）的页需要被挪出。

近似 LRU 算法

标准的 LRU 算法要求每次内存中出现调用的时候就更新队列，这样的算法复杂度（硬件开销）十分高，通常来说这不是一个好的实践。一些其他算法被用来趋近 LRU 的效果。

老化页置换算法

引用位（Referenced Bit，R位）被用于记录页面的调用，这个引用位是在硬件层面实现的。

老化寄存器（Aging Register）被用于和页连接。除非最高有效位（MSB）被设为 1，否则它会周期性地向右位移 1 个比特。页会随着寄存器向右位移逐渐老化。

老化置换算法（Aging Replacement Algorithm）不需要维护一个排序方式和 LRU 一致的队列，它只将那些在一个周期内引用位标记为 1 的页组起来。老化寄存器移动一位即为一个周期。

这个算法的步骤如下，它会在每次有 $d$ 个页被引用的时候（或者固定的时钟中断）执行：

  1. 所有的老化寄存器向右移动一位，丢掉最低有效位（LSB）。
  2. 将引用位（R）复制到老化寄存器的最高有效位（MSB）。
  3. 重置引用位（R）为 0。

当一个页错误出现的时候：

  1. 选择持最小老化寄存器数值的页，并替换它。
  2. 如果多个页都是最小的值，那么就随机选择一个。

做 gif 很麻烦，将就着看吧。

老化置换算法演示

二次机会算法

二次机会算法（Second-Chance Page Replacement Algorithm）是另一个近似 LRU 算法，它使用 R位将页分为两类：最近被调度，最近没有被调用。这个算法会从最近没有被调用的页中找一个并替换掉它。

和 FIFO 算法类似，这个算法需要维护一个指针（类似于钟表指针）循环遍历所有帧来寻找适当的页并取代它。因为这样的一种循环，这个算法也被称为时钟算法（Clock Algorithm）。

当一个页错误出现的时候，这个算法会重复下面的步骤直到一页被选择并被取代：

  1. 如果指针指在一页 $P$ 上，并且该页的 R位是 0，那么就置换 $P$，并将该指针移动到下一页。
  2. 否则（R位是 1），就重置 R位为 0，并将指针继续往前搜索。

二次机会算法演示

三次机会算法

在二次机会算法上加多了一次机会，所以这次需要计数的是两位（$2^2 = 4$）引用状态。三次机会算法（Third-Chance Page Replacement Algorithm）也被称为非最近使用页置换算法（Not Recently Used, NRU）。它利用 R位和 M位（修改位）将页分为四种状态。

当一个页错误出现的时候，该算法重复以下步骤直到有某页被选择并被替换为止。

  1. 如果指针指向了一页，并且该页的引用位 (R, M) 都为 (0, 0)，那么就选择该页并向前挪动指针。
  2. 否则，根据如下状态表设置 (R, M)。
状态转移 类型
(1, 1) -> (0, 1) 最近被引用且被修改过的页
(0, 1) -> (0, 0) 最近未被引用但被修改过的页
(1, 0) -> (0, 0) 最近被引用但未被修改过的页

工作集模型

某个程序总是需要调用固定的几个驻内存页来运行。当没有足够的帧时，就会频繁出现页错误。如果频繁地将这些页替换，效率将会大大减小。

一个进程的最优工作集（Optimal Working Set）指的是那些它需要马上调用的页，这些页要提前被挪进物理内存中。一个进程的最优工作集大小根据进程的需要而不同。想要知道一个进程的最优工作集在时间 $t$ 的时候是什么，一个大小为 $\Delta$（Delta）的窗口（Working-Set Window）将会被插入到引用串中。那些出现在该范围内的页就是这个集合的元素。集合的大小和它的元素随着时间的推移而改变。一个窗口的大小是由其对应的程序决定的，在程序第一次被加载的时候，它的行为决定了窗口的大小。

最优工作集演示

工作集置换算法

最优工作集在现实生活中是无法预测的，我们永远都不知道下一个进来的页是什么。所以我们要用次优方案。虽然不能知道未来有什么页输入进来，但是我们知道过去引用了哪些页。进程的工作集（Working Set, WS）是指这个进程过去 $\Delta$ 个内存操作所用到的页。工作集置换算法（Working Set Page Replacement Algorithm），或者叫 WS 算法，用一个大小为 $\Delta$ 的窗口，一边监测引用串，一边改变工作集合的大小及其元素。

随着时间 $t$ 的推移，工作集算法的工作如下：

  1. 挪动 1 单位的窗口来概括目前的引用串。
  2. 只将该窗口包含的页留在内存中，释放不在窗口内的页。

工作集算法演示

和最优工作集不同，工作集算法看的是过去用过哪些页。在上面的例子中，在 $t$ 为 -1 和 0 的时候，工作集算法还不会启动，待窗口能装满所需的页之后才会开始记录。

页错误率置换算法

工作集算法能很好地将页错误率保持在一个很低的水平，但仍旧不够高效。想想看，每次窗口移动都伴随着对集合的更新。一个更好的方法去解决这个问题是使用页错误率置换算法（Page-Fault-Frequency Replacement Algorithm, PFF）。它通过调整常驻页集，直接控制页错误率（Page Fault Frequency）。这个算法只在出现页错误的时候被激活。

在页错误出现的时候，这个算法做如下操作：

  1. 将需要的页添加到常驻集中。
  2. 如果距上次页错误的时间大于 $d$（一个提前预设的阈值），将所有自上次页错误以来没有被引用的页（R位为 0），从常驻集中移除。

这里有必要说明一下常驻集（Resident Set），它指的是在某个时刻 $t$，被加载到物理内存中的页。

我们来看一个例子：

PFF算法示意图

上图中，红色的柱状体表示该引用发生了页错误。在时间为 1 和 2 的时候都发生了页错误，但是由于它们距离上一次发生页错误的时间都小于 2，所以页错误率置换算法不被激活。到时间 4 的时候，调用 P3 导致了页错误，并且距离上一次发生页错误的时间大于 2。页错误率置换算法被激活，但是由于在这个区间所有页 P1, P2 都有被使用过（R位为 1），所以保留它们。在时间 7 的时候，调用 P4 触发页错误和页错误率算法。距离上一次页错误到现在（时间 4 到时间 7）只有 P3 被引用，所以 P1, P2 被挪出常驻集。剩下的两个时间（8, 9）都因为距离上一次页错误的时间不超过 2 没有激活算法。

这个算法比工作集算法好的地方是它只有在出现页错误的时候才会发生，而且每次发生的时候都会移除最长时间没有被调用的页，从而保证了每次都清理出理想的内存空间给将来加载的页使用。

虚拟内存的时间和空间复杂度

按需调页的代价

虚拟内存要在时间和空间复杂度中取舍。让虚拟内存比物理内存大的代价是其出现的页错误。一个页错误的出现伴随着对内存和磁盘的读写。磁盘的读写要比内存的读写慢得多，所以将页错误率降得越低越好。

局部控制与颠簸

当我们说局部控制（Local Control，又称多道程序度的调节）的时候，我们在说在某个时刻对“应该有多少进程应该被同时执行”的定夺。当我们需要频繁地进行页调度，颠簸（Thrashing，又称系统抖动）就出现了。试想一下，如果没有做好局部控制，某个进程在执行到一定程度的时候需要更多帧，页错误因此发生，如果物理内存已被占满，系统就要调度其它进程的帧来解决页错误。其他进程在执行的阶段也需要更多帧，所以它们互相抢夺内存的帧，这样的页错误数量就会居高不下，系统效率急剧下降。

CPU利用率与颠簸示意图

如上图，当只有一个进程在运行，页调用引起 I/O 操作导致了低 CPU 利用率。随着越来越多的程序被加载到内存运行，CPU 的利用率就会稳定增长，但是这个增长不是一直持续的，因为物理内存有限。CPU 的利用率跟着进程的数量（多道程序度）一起上到一定的高度后会急剧下降。这是因为进程越多，发生颠簸的概率越大，大部分进程都在等待 I/O 操作，CPU 的利用率趋近于 0。

要执行的程序变多，页错误率就上涨。系统需要在页错误的数量和 CPU 利用率之间取舍。当页错误的间隔时间 $L$ 等于它解决页错误的时间 $S$ 的时候（$L=S$），CPU 的利用率最高（这是一个经验法则）。 操作系统可以利用这一原理来决定多少个程序可以在内存中。当 $L < S$ 的时候，操作系统无法及时处理页错误，必然需要相应地减少内存中的程序；当 $L > S$ 的时候，页错误之间的时间很长，操作系统可以增加同时运行在内存中的程序（提高多道程序度）来提高 CPU 的利用率。

页大小的确定

页的大小（Page Size）对时间和空间有着很大的影响。有些进程需要大一点的页，另一些需要小的页。确定不好这个大小会对页错误产生很大的影响。最常见的页大小是 512B 到 4096B（4KB），但是近些年这个数正在逐渐变大。为了满足不同程序的需求，有的操作系统甚至支持多种页大小。

页的大小对空间有什么影响？

假设本来每页的大小是 4 个字（8字节），一个页表刚好装得下这 4 个字（1页）。现在我们重新设置一页的大小为 2 个字，那么页表项（Page Table Entries, PTEs）的数量也要相应的加大一倍来装住现在的两页了。所以页越小，页表自身需要的内存空间越大。

页的大小对时间有什么影响？

假设从磁盘中读取 1 页的时间为 $m$，现在我们将页的大小减半，页的数量翻一倍。由于页的数量增加，页错误的次数大概率会增加，系统对磁盘的总体读取时间（I/O 时间）也会增加。所以页越小，总体需要的 I/O 时间可能越长（尽管单次 I/O 时间略短，但开销主要在寻道和旋转延迟上）。