1. 概述
- 当发生缺页异常时，操作系统会选择一个页面进行换出从而为新进来的页面腾出空间。如果要换出的页面在内存中已经被修改，那么必须将其写到磁盘中以使磁盘副本保持最新状态。如果页面没有被修改过，并且磁盘中的副本也已经是最新的，那么就不需要进行重写。那么就直接使用调入的页面覆盖需要移除的页面就可以了
- 当发生缺页中断时，虽然可以随机的选择一个页面进行置换，但是如果每次都选择一个不常用的页面会提升系统的性能。如果一个经常使用的页面被换出，那么这个页面在短时间内又可能被重复使用，那么就可能会造成额外的性能开销。在关于页面的主题上有很多页面置换算法(page replacement algorithms)，这些已经从理论上和实践上得到了证明
- 需要指出的是，页面置换问题在计算机的其他领域中也会出现。例如，多数计算机把最近使用过的 32 字节或者 64 字节的存储块保存在一个或多个高速缓存中。当缓存满的时候，一些块就被选择和移除。这些块的移除除了花费时间较短外，这个问题同页面置换问题完全一样。之所以花费时间较短，是因为丢掉的高速缓存可以从内存中获取，而内存没有寻找磁道的时间也不存在旋转延迟
- 第二个例子是 Web 服务器。服务器会在内存中缓存一些经常使用到的 Web 页面。然而，当缓存满了并且已经引用了新的页面，那么必须决定退出哪个 Web 页面。在高速缓存中的 Web 页面不会被修改。因此磁盘中的 Web 页面经常是最新的，同样的考虑也适用在虚拟内存中。在虚拟系统中，内存中的页面可能会修改也可能不会修改。下面我们就来探讨一下有哪些页面置换算法
2. 最优页面置换算法
- 最优的页面置换算法很容易描述但在实际情况下很难实现。它的工作流程如下：在缺页中断发生时，这些页面之一将在下一条指令（包含该指令的页面）上被引用。其他页面则可能要到 10、100 或者 1000 条指令后才会被访问。每个页面都可以用在该页首次被访问前所要执行的指令数作为标记
- 最优化的页面算法表明应该标记最大的页面。如果一个页面在 800 万条指令内不会被使用，另外一个页面在 600 万条指令内不会被使用，则置换前一个页面，从而把需要调入这个页面而发生的缺页中断推迟。计算机也像人类一样，会把不愿意做的事情尽可能的往后拖
- 这个算法最大的问题时无法实现。当缺页中断发生时，操作系统无法知道各个页面的下一次将在什么时候被访问。这种算法在实际过程中根本不会使用
3. 最近未使用页面置换算法
为了能够让操作系统收集页面使用信息，大部分使用虚拟地址的计算机都有两个状态位，R 和 M，来和每个页面进行关联。每当引用页面（读入或写入）时都设置 R，写入（即修改）页面时设置 M，这些位包含在每个页表项中，就像下面所示
因为每次访问时都会更新这些位，因此由硬件来设置它们非常重要。一旦某个位被设置为 1，就会一直保持 1 直到操作系统下次来修改此位
如果硬件没有这些位，那么可以使用操作系统的缺页中断和时钟中断机制来进行模拟。当启动一个进程时，将其所有的页面都标记为不在内存；一旦访问任何一个页面就会引发一次缺页中断，此时操作系统就可以设置 R 位(在它的内部表中)，修改页表项使其指向正确的页面，并设置为 READ ONLY 模式，然后重新启动引起缺页中断的指令。如果页面随后被修改，就会发生另一个缺页异常。从而允许操作系统设置 M 位并把页面的模式设置为 READ/WRITE
可以用 R 位和 M 位来构造一个简单的页面置换算法：当启动一个进程时，操作系统将其所有页面的两个位都设置为 0。R 位定期的被清零（在每个时钟中断）。用来将最近未引用的页面和已引用的页面分开
当出现缺页中断后，操作系统会检查所有的页面，并根据它们的 R 位和 M 位将当前值分为四类：
- 第 0 类：没有引用 R，没有修改 M
- 第 1 类：没有引用 R，已修改 M
- 第 2 类：引用 R ，没有修改 M
- 第 3 类：已被访问 R，已被修改 M
尽管看起来好像无法实现第一类页面，但是当第三类页面的 R 位被时钟中断清除时，它们就会发生。时钟中断不会清除 M 位，因为需要这个信息才能知道是否写回磁盘中。清除 R 但不清除 M 会导致出现一类页面
NRU(Not Recently Used) 算法从编号最小的非空类中随机删除一个页面。此算法隐含的思想是，在一个时钟内（约 20 ms）淘汰一个已修改但是没有被访问的页面要比一个大量引用的未修改页面好，NRU 的主要优点是易于理解并且能够有效的实现
4. 先进先出页面置换算法
另一种开销较小的方式是使用 FIFO(First-In,First-Out) 算法，这种类型的数据结构也适用在页面置换算法中。由操作系统维护一个所有在当前内存中的页面的链表，最早进入的放在表头，最新进入的页面放在表尾。在发生缺页异常时，会把头部的页移除并且把新的页添加到表尾
还记得缺页异常什么时候发生吗？我们知道应用程序访问内存会进行虚拟地址到物理地址的映射，缺页异常就发生在虚拟地址无法映射到物理地址的时候。因为实际的物理地址要比虚拟地址小很多（参考上面的虚拟地址和物理地址映射图），所以缺页经常会发生
先进先出页面可能是最简单的页面替换算法了。在这种算法中，操作系统会跟踪链表中内存中的所有页。下面我们举个例子看一下（这个算法我刚开始看的时候有点懵逼，后来才看懂，我还是很菜）
- 初始化的时候，没有任何页面，所以第一次的时候会检查页面 1 是否位于链表中，没有在链表中，那么就是 MISS，页面1 进入链表，链表的先进先出的方向如图所示
- 类似的，第二次会先检查页面 2 是否位于链表中，没有在链表中，那么页面 2 进入链表，状态为 MISS，依次类推
- 我们来看第四次，此时的链表为 1 2 3 ，第四次会检查页面 2 是否位于链表中，经过检索后，发现 2 在链表中，那么状态就是 HIT，并不会再进行入队和出队操作，第五次也是一样的
- 下面来看第六次，此时的链表还是 1 2 3，因为之前没有执行进入链表操作，页面 5 会首先进行检查，发现链表中没有页面 5 ，则执行页面 5 的进入链表操作，页面 2 执行出链表的操作，执行完成后的链表顺序为 2 3 5
5. 第二次机会页面置换算法
我们上面学到的 FIFO 链表页面有个缺陷，那就是出链和入链并不会进行 check 检查，这样就会容易把经常使用的页面置换出去，为了避免这一问题，我们对该算法做一个简单的修改：我们检查最老页面的 R 位，如果是 0 ，那么这个页面就是最老的而且没有被使用，那么这个页面就会被立刻换出。如果 R 位是 1，那么就清除此位，此页面会被放在链表的尾部，修改它的装入时间就像刚放进来的一样。然后继续搜索
这种算法叫做 第二次机会(second chance)算法，就像下面这样，我们看到页面 A 到 H 保留在链表中，并按到达内存的时间排序
- 按照先进先出的方法排列的页面
- 在时刻 20 处发生缺页异常中断并且 A 的 R 位已经设置时的页面链表
假设缺页异常发生在时刻 20 处，这时最老的页面是 A ，它是在 0 时刻到达的。如果 A 的 R 位是 0，那么它将被淘汰出内存，或者把它写回磁盘（如果它已经被修改过），或者只是简单的放弃（如果它是未被修改过）。另一方面，如果它的 R 位已经设置了，则将 A 放到链表的尾部并且重新设置装入时间为当前时刻（20 处），然后清除 R 位。然后从 B 页面开始继续搜索合适的页面
寻找第二次机会的是在最近的时钟间隔中未被访问过的页面。如果所有的页面都被访问过，该算法就会被简化为单纯的 FIFO 算法。具体来说，假设图 a 中所有页面都设置了 R 位。操作系统将页面依次移到链表末尾，每次都在添加到末尾时清除 R 位。最后，算法又会回到页面 A，此时的 R 位已经被清除，那么页面 A 就会被执行出链处理，因此算法能够正常结束
6. 时钟页面置换算法
即使上面提到的第二次页面置换算法也是一种比较合理的算法，但它经常要在链表中移动页面，既降低了效率，而且这种算法也不是必须的。一种比较好的方式是把所有的页面都保存在一个类似钟面的环形链表中，一个表针指向最老的页面。如下图所示
当缺页错误出现时，算法首先检查表针指向的页面，如果它的 R 位是 0 就淘汰该页面，并把新的页面插入到这个位置，然后把表针向前移动一位；如果 R 位是 1 就清除 R 位并把表针前移一个位置。重复这个过程直到找到了一个 R 位为 0 的页面位置。了解这个算法的工作方式，就明白为什么它被称为 时钟(clokc)算法了
7. 最近最少使用页面置换算法
- 最近最少使用页面置换算法的一个解释会是下面这样：在前面几条指令中频繁使用的页面和可能在后面的几条指令中被使用。反过来说，已经很久没有使用的页面有可能在未来一段时间内仍不会被使用。这个思想揭示了一个可以实现的算法：在缺页中断时，置换未使用时间最长的页面。这个策略称为 LRU(Least Recently Used) ，最近最少使用页面置换算法
- 虽然 LRU 在理论上是可以实现的，但是从长远看来代价比较高。为了完全实现 LRU，会在内存中维护一个所有页面的链表，最频繁使用的页位于表头，最近最少使用的页位于表尾。困难的是在每次内存引用时更新整个链表。在链表中找到一个页面，删除它，然后把它移动到表头是一个非常耗时的操作，即使使用硬件来实现也是一样的费时
- 然而，还有其他方法可以通过硬件实现 LRU。让我们首先考虑最简单的方式。这个方法要求硬件有一个 64 位的计数器，它在每条指令执行完成后自动加 1，每个页表必须有一个足够容纳这个计数器值的域。在每次访问内存后，将当前的值保存到被访问页面的页表项中。一旦发生缺页异常，操作系统就检查所有页表项中计数器的值，找到值最小的一个页面，这个页面就是最少使用的页面
8. 用软件模拟 LRU
尽管上面的 LRU 算法在原则上是可以实现的，但是很少有机器能够拥有那些特殊的硬件。上面是硬件的实现方式，那么现在考虑要用软件来实现 LRU 。一种可以实现的方案是 NFU(Not Frequently Used，最不常用)算法。它需要一个软件计数器来和每个页面关联，初始化的时候是 0 。在每个时钟中断时，操作系统会浏览内存中的所有页，会将每个页面的 R 位（0 或 1）加到它的计数器上。这个计数器大体上跟踪了各个页面访问的频繁程度。当缺页异常出现时，则置换计数器值最小的页面
NFU 最主要的问题是它不会忘记任何东西，想一下是不是这样？例如，在一个多次（扫描）的编译器中，在第一遍扫描中频繁使用的页面会在后续的扫描中也有较高的计数。事实上，如果第一次扫描的执行时间恰好是各次扫描中最长的，那么后续遍历的页面的统计次数总会比第一次页面的统计次数小。结果是操作系统将置换有用的页面而不是不再使用的页面
幸运的是只需要对 NFU 做一个简单的修改就可以让它模拟 LRU，这个修改有两个步骤
首先，在 R 位被添加进来之前先把计数器右移一位
第二步，R 位被添加到最左边的位而不是最右边的位
修改以后的算法称为 老化(aging) 算法，下图解释了老化算法是如何工作的
我们假设在第一个时钟周期内页面 0 - 5 的 R 位依次是 1，0，1，0，1，1，（也就是页面 0 是 1，页面 1 是 0，页面 2 是 1 这样类推）。也就是说，在 0 个时钟周期到 1 个时钟周期之间，0，2，4，5 都被引用了，从而把它们的 R 位设置为 1，剩下的设置为 0 。在相关的六个计数器被右移之后 R 位被添加到 左侧 ，就像上图中的 a。剩下的四列显示了接下来的四个时钟周期内的六个计数器变化
CPU正在以某个频率前进，该频率的周期称为时钟滴答或时钟周期。一个 100Mhz 的处理器每秒将接收100,000,000个时钟滴答
当缺页异常出现时，将置换（就是移除）计数器值最小的页面。如果一个页面在前面 4 个时钟周期内都没有被访问过，那么它的计数器应该会有四个连续的 0 ，因此它的值肯定要比前面 3 个时钟周期内都没有被访问过的页面的计数器小
这个算法与 LRU 算法有两个重要的区别：看一下上图中的 e，第三列和第五列
它们在两个时钟周期内都没有被访问过，在此之前的时钟周期内都引用了两个页面。根据 LRU 算法，如果需要置换的话，那么应该在这两个页面中选择一个。那么问题来了，我萌应该选择哪个？现在的问题是我们不知道时钟周期 1 到时钟周期 2 内它们中哪个页面是后被访问到的。因为在每个时钟周期内只记录了一位，所以无法区分在一个时钟周期内哪个页面最早被引用，哪个页面是最后被引用的。因此，我们能做的就是置换页面3，因为页面 3 在周期 0 - 1 内都没有被访问过，而页面 5 却被引用过
LRU 与老化之前的第 2 个区别是，在老化期间，计数器具有有限数量的位（这个例子中是 8 位），这就限制了以往的访问记录。如果两个页面的计数器都是 0 ，那么我们可以随便选择一个进行置换。实际上，有可能其中一个页面的访问次数实在 9 个时钟周期以前，而另外一个页面是在 1000 个时钟周期之前，但是我们却无法看到这些。在实际过程中，如果时钟周期是 20 ms，8 位一般是够用的。所以我们经常拿 20 ms 来举例
9. 工作集页面置换算法
在最单纯的分页系统中，刚启动进程时，在内存中并没有页面。此时如果 CPU 尝试匹配第一条指令，就会得到一个缺页异常，使操作系统装入含有第一条指令的页面。其他的错误比如 全局变量和 堆栈 引起的缺页异常通常会紧接着发生。一段时间以后，进程需要的大部分页面都在内存中了，此时进程开始在较少的缺页异常环境中运行。这个策略称为 请求调页(demand paging)，因为页面是根据需要被调入的，而不是预先调入的
在一个大的地址空间中系统的读所有的页面，将会造成很多缺页异常，因此会导致没有足够的内存来容纳这些页面。不过幸运的是，大部分进程不是这样工作的，它们都会以局部性方式(locality of reference) 来访问，这意味着在执行的任何阶段，程序只引用其中的一小部分
一个进程当前正在使用的页面的集合称为它的 工作集(working set)，如果整个工作集都在内存中，那么进程在运行到下一运行阶段（例如，编译器的下一遍扫面）之前，不会产生很多缺页中断。如果内存太小从而无法容纳整个工作集，那么进程的运行过程中会产生大量的缺页中断，会导致运行速度也会变得缓慢。因为通常只需要几纳秒就能执行一条指令，而通常需要十毫秒才能从磁盘上读入一个页面。如果一个程序每 10 ms 只能执行一到两条指令，那么它将需要很长时间才能运行完。如果只是执行几条指令就会产生中断，那么就称作这个程序产生了 颠簸(thrashing)
在多道程序的系统中，通常会把进程移到磁盘上（即从内存中移走所有的页面），这样可以让其他进程有机会占用 CPU 。有一个问题是，当进程想要再次把之前调回磁盘的页面调回内存怎么办？从技术的角度上来讲，并不需要做什么，此进程会一直产生缺页中断直到它的工作集 被调回内存。然后，每次装入一个进程需要 20、100 甚至 1000 次缺页中断，速度显然太慢了，并且由于 CPU 需要几毫秒时间处理一个缺页中断，因此由相当多的 CPU 时间也被浪费了
因此，不少分页系统中都会设法跟踪进程的工作集，确保这些工作集在进程运行时被调入内存。这个方法叫做 工作集模式(working set model)。它被设计用来减少缺页中断的次数的。在进程运行前首先装入工作集页面的这一个过程被称为 预先调页(prepaging)，工作集是随着时间来变化的
根据研究表明，大多数程序并不是均匀的访问地址空间的，而访问往往是集中于一小部分页面。一次内存访问可能会取出一条指令，也可能会取出数据，或者是存储数据。在任一时刻 t，都存在一个集合，它包含所哟欧最近 k 次内存访问所访问过的页面。这个集合 w(k,t) 就是工作集。因为最近 k = 1次访问肯定会访问最近 k > 1 次访问所访问过的页面，所以 w(k,t) 是 k 的单调递减函数。随着 k 的增大，w(k,t) 是不会无限变大的，因为程序不可能访问比所能容纳页面数量上限还多的页面
事实上大多数应用程序只会任意访问一小部分页面集合，但是这个集合会随着时间而缓慢变化，所以为什么一开始曲线会快速上升而 k 较大时上升缓慢。为了实现工作集模型，操作系统必须跟踪哪些页面在工作集中。一个进程从它开始执行到当前所实际使用的 CPU 时间总数通常称作 当前实际运行时间。进程的工作集可以被称为在过去的 t 秒实际运行时间中它所访问过的页面集合
下面来简单描述一下工作集的页面置换算法，基本思路就是找出一个不在工作集中的页面并淘汰它。下面是一部分机器页表
因为只有那些在内存中的页面才可以作为候选者被淘汰，所以该算法忽略了那些不在内存中的页面。每个表项至少包含两条信息：上次使用该页面的近似时间和 R（访问）位。空白的矩形表示该算法不需要其他字段，例如页框数量、保护位、修改位
算法的工作流程如下，假设硬件要设置 R 和 M 位。同样的，在每个时钟周期内，一个周期性的时钟中断会使软件清除 Referenced(引用)位。在每个缺页异常，页表会被扫描以找出一个合适的页面把它置换
随着每个页表项的处理，都需要检查 R 位。如果 R 位是 1，那么就会将当前时间写入页表项的 上次使用时间域，表示的意思就是缺页异常发生时页面正在被使用。因为页面在当前时钟周期内被访问过，那么它应该出现在工作集中而不是被删除（假设 t 是横跨了多个时钟周期）
如果 R 位是 0 ，那么在当前的时钟周期内这个页面没有被访问过，应该作为被删除的对象。为了查看是否应该将其删除，会计算其使用期限（当前虚拟时间 - 上次使用时间），来用这个时间和 t 进行对比。如果使用期限大于 t，那么这个页面就不再工作集中，而使用新的页面来替换它。然后继续扫描更新剩下的表项
然而，如果 R 位是 0 但是使用期限小于等于 t，那么此页应该在工作集中。此时就会把页面临时保存起来，但是会记生存时间最长（即上次使用时间的最小值）的页面。如果扫描完整个页表却没有找到适合被置换的页面，也就意味着所有的页面都在工作集中。在这种情况下，如果找到了一个或者多个 R = 0 的页面，就淘汰生存时间最长的页面。最坏的情况下是，在当前时钟周期内，所有的页面都被访问过了（也就是都有 R = 1），因此就随机选择一个页面淘汰，如果有的话最好选一个未被访问的页面，也就是干净的页面
10. 工作集时钟页面置换算法
当缺页异常发生后，需要扫描整个页表才能确定被淘汰的页面，因此基本工作集算法还是比较浪费时间的。一个对基本工作集算法的提升是基于时钟算法但是却使用工作集的信息，这种算法称为WSClock(工作集时钟)。由于它的实现简单并且具有高性能，因此在实践中被广泛应用。与时钟算法一样，所需的数据结构是一个以页框为元素的循环列表，就像下面这样
最初的时候，该表是空的。当装入第一个页面后，把它加载到该表中。随着更多的页面的加入，它们形成一个环形结构。每个表项包含来自基本工作集算法的上次使用时间，以及 R 位（已标明）和 M 位（未标明）
与时钟算法一样，在每个缺页异常时，首先检查指针指向的页面。如果 R 位被是设置为 1，该页面在当前时钟周期内就被使用过，那么该页面就不适合被淘汰。然后把该页面的 R 位置为 0，指针指向下一个页面，并重复该算法。该事件序列化后的状态参见图 b
现在考虑指针指向的页面 R = 0 时会发生什么，参见图 c，如果页面的使用期限大于 t 并且页面为被访问过，那么这个页面就不会在工作集中，并且在磁盘上会有一个此页面的副本。申请重新调入一个新的页面，并把新的页面放在其中，如图 d 所示。另一方面，如果页面被修改过，就不能重新申请页面，因为这个页面在磁盘上没有有效的副本。为了避免由于调度写磁盘操作引起的进程切换，指针继续向前走，算法继续对下一个页面进行操作。毕竟，有可能存在一个老的，没有被修改过的页面可以立即使用
原则上来说，所有的页面都有可能因为磁盘I/O 在某个时钟周期内被调度。为了降低磁盘阻塞，需要设置一个限制，即最大只允许写回 n 个页面。一旦达到该限制，就不允许调度新的写操作
那么就有个问题，指针会绕一圈回到原点的，如果回到原点，它的起始点会发生什么？这里有两种情况：
- 至少调度了一次写操作
- 没有调度过写操作
在第一种情况中，指针仅仅是不停的移动，寻找一个未被修改过的页面。由于已经调度了一个或者多个写操作，最终会有某个写操作完成，它的页面会被标记为未修改。置换遇到的第一个未被修改过的页面，这个页面不一定是第一个被调度写操作的页面，因为硬盘驱动程序为了优化性能可能会把写操作重排序
对于第二种情况，所有的页面都在工作集中，否则将至少调度了一个写操作。由于缺乏额外的信息，最简单的方法就是置换一个未被修改的页面来使用，扫描中需要记录未被修改的页面的位置，如果不存在未被修改的页面，就选定当前页面并把它写回磁盘
11. 页面置换算法小结
最优算法在当前页面中置换最后要访问的页面。不幸的是，没有办法来判定哪个页面是最后一个要访问的，因此实际上该算法不能使用。然而，它可以作为衡量其他算法的标准
NRU 算法根据 R 位和 M 位的状态将页面氛围四类。从编号最小的类别中随机选择一个页面。NRU 算法易于实现，但是性能不是很好。存在更好的算法
FIFO 会跟踪页面加载进入内存中的顺序，并把页面放入一个链表中。有可能删除存在时间最长但是还在使用的页面，因此这个算法也不是一个很好的选择
第二次机会算法是对 FIFO 的一个修改，它会在删除页面之前检查这个页面是否仍在使用。如果页面正在使用，就会进行保留。这个改进大大提高了性能。
时钟 算法是第二次机会算法的另外一种实现形式，时钟算法和第二次算法的性能差不多，但是会花费更少的时间来执行算法
LRU算法是一个非常优秀的算法，但是没有特殊的硬件(TLB)很难实现。如果没有硬件，就不能使用 LRU 算法
NFU算法是一种近似于 LRU 的算法，它的性能不是非常好
老化算法是一种更接近 LRU 算法的实现，并且可以更好的实现，因此是一个很好的选择
最后两种算法都使用了工作集算法。工作集算法提供了合理的性能开销，但是它的实现比较复杂。WSClock 是另外一种变体，它不仅能够提供良好的性能，而且可以高效地实现
算法 注释 最优算法 不可实现，但可以用作基准 NRU(最近未使用) 算法 和 LRU 算法很相似 FIFO(先进先出) 算法 有可能会抛弃重要的页面 第二次机会算法 比 FIFO 有较大的改善 时钟算法 实际使用 LRU(最近最少)算法 比较优秀，但是很难实现 NFU(最不经常食用)算法 和 LRU 很类似 老化算法 近似 LRU 的高效算法 工作集算法 实施起来开销很大 工作集时钟算法 比较有效的算法