六：操作系统虚拟内存之页替换算法
深入理解操作系统：页替换算法 (Page Replacement Algorithms)
在前两篇文章中，我们探讨了虚拟内存的概念以及按需调页 (Demand Paging) 如何通过缺页中断 (Page Fault) 将所需的页面从磁盘加载到物理内存。按需调页提高了物理内存的利用率，使得我们可以在有限的 RAM 中运行更大的程序或更多程序。
然而，物理内存终究是有限的。当一个进程发生缺页中断，需要将一个新页面从磁盘调入，但物理内存中所有的物理帧 (Physical Frame) 都已经被占用时，操作系统就必须做出一个艰难的决定：牺牲 (Victimizing) 物理内存中的某个现有页面，将其移除（必要时写回磁盘），以便为新页面腾出空间。这个选择由页替换算法 (Page Replacement Algorithm) 来决定。
本文将详细讲解何时需要页替换，并深入介绍几种重要的页替换算法及其工作原理。
1. 何时需要页替换？
页替换发生的根本原因是：在处理一个缺页中断时，操作系统无法在物理内存中找到一个空闲的物理帧来加载目标页面。
回忆缺页中断的处理流程：
- 程序访问虚拟地址，MMU 检测到页面不在内存（存在位为 0）。
- 触发缺页中断，控制权转给操作系统。
- 操作系统验证地址和权限。
- 操作系统确定目标页面在磁盘上的位置。
- 操作系统查找空闲物理帧。
如果第 5 步发现没有空闲物理帧可用，系统就进入了需要进行页替换的状态。操作系统必须选择物理内存中的一个已占用物理帧，将其内容对应的页面移除。移除后，该物理帧就变成了空闲帧，可以用来加载导致缺页的那个新页面。
选择哪个页面进行替换至关重要，因为它直接影响到未来发生缺页中断的频率和系统的性能。目标是尽量选择一个将来最不可能很快被访问的页面，以最小化缺页次数。
2. 评价页替换算法的标准
页替换算法的优劣通常通过模拟在特定页面引用串 (Page Reference String) 下的性能来衡量。页面引用串是程序执行过程中访问的页面号序列。
例如，引用串可以是： 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1。
我们将使用一个固定数量的物理帧来模拟不同的算法，并计算在处理完整个引用串后发生的缺页次数 (Number of Page Faults)。缺页次数越少，算法的性能越好（对应的命中率越高）。
接下来，我们将使用上面的引用串 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1 和假设物理内存中有 3 个物理帧来演示各种算法。
3. 页替换算法
3.1 最优算法 (Optimal - OPT)
-
概念： 置换在未来最长一段时间内不再被访问的页面。
-
工作原理： 当需要替换页面时，OPT 算法会检查当前物理内存中所有页面在未来引用串中下一次出现的时机。它选择下一次访问距离当前最远的那个页面进行替换。
-
优点： 理论上可以达到最低的缺页率，是性能最好的算法。
-
缺点： 无法实现。因为操作系统无法预知程序将来的页面访问序列。OPT 算法主要用作评价其他算法性能的基准。
-
示例 (使用引用串: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1，帧数=3):
引用串 内存帧 1 内存帧 2 内存帧 3 缺页? 替换哪个? (看未来) 7 7 是 - 0 7 0 是 - 1 7 0 1 是 - 2 2 0 1 是 7 (未来最远) 0 2 0 1 否 - 3 2 3 1 是 0 (未来最远) 0 0 3 1 是 2 (未来最远) 4 0 3 4 是 1 (未来最远) 2 0 2 4 是 3 (未来最远) 3 0 2 3 是 4 (未来最远) 0 0 2 3 否 - 3 0 2 3 否 - 2 0 2 3 否 - 1 1 2 3 是 0 (未来最远) 2 1 2 3 否 - 0 1 2 0 是 3 (未来最远) 1 1 2 0 否 - 7 1 2 7 是 0 (未来最远) 0 0 2 7 是 1 (未来最远) 1 0 1 7 是 2 (未来最远) 总缺页次数：12
(注意：由于需要查看未来，上面的“替换哪个?”是根据整个引用串预测的理想情况)
3.2 先进先出 (First-In, First-Out - FIFO)
-
概念： 置换在物理内存中驻留时间最长的页面。
-
工作原理： FIFO 算法维护一个队列，记录当前在物理内存中的页面。新加载的页面加入队列尾部。需要替换时，移除队列头部的页面。
-
优点： 实现简单。
-
缺点： 没有考虑页面的使用频率或近期性。一个经常被使用的页面如果很早就被加载进来，可能会因为它“老”而被频繁置换出去，导致高缺页率。可能存在 Belady’s Anomaly（增加物理帧数量反而导致缺页次数增加）的问题。
-
示例 (使用引用串: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1，帧数=3):
引用串 内存帧 1 内存帧 2 内存帧 3 缺页? 替换哪个? (最老) 7 7 是 - 0 7 0 是 - 1 7 0 1 是 - 2 2 0 1 是 7 0 2 0 1 否 - 3 2 3 1 是 0 0 2 3 0 是 1 4 4 3 0 是 2 2 4 2 0 是 3 3 4 2 3 是 0 0 0 2 3 是 4 3 0 2 3 否 - 2 0 2 3 否 - 1 0 1 3 是 2 2 0 1 2 是 3 0 0 1 2 否 - 1 0 1 2 否 - 7 7 1 2 是 0 0 7 0 2 是 1 1 7 0 1 是 2 总缺页次数：15
3.3 最近最少使用 (Least Recently Used - LRU)
-
概念： 置换在过去最长一段时间内没有被使用的页面。
-
工作原理： LRU 算法基于局部性原理（时间局部性），认为最近被使用的页面在将来很有可能再次被使用，而很久没有被使用的页面在将来被使用的可能性较低。它需要维护一个所有在内存页面使用时间的顺序列表，或者为每个页面维护一个时间戳，每次访问页面时更新其时间戳。需要替换时，选择时间戳最小（即最久未被访问）的页面。
-
优点： 通常比 FIFO 性能更好，并且不容易出现 Belady’s Anomaly。
-
缺点： 精确实现 LRU 算法成本很高。每次页面访问都需要更新状态（链表操作或时间戳更新），这需要特殊的硬件支持或软件模拟，开销较大。
-
示例 (使用引用串: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1，帧数=3):
引用串 内存帧 1 内存帧 2 内存帧 3 缺页? 替换哪个? (LRU) 历史记录顺序 (最近到最远) 7 7 是 - 7 0 7 0 是 - 0, 7 1 7 0 1 是 - 1, 0, 7 2 2 0 1 是 7 2, 1, 0 0 2 0 1 否 - 0, 1, 2 3 0 3 1 是 2 3, 1, 0 0 0 3 1 否 - 0, 1, 3 4 0 4 1 是 3 4, 1, 0 2 0 4 2 是 1 2, 4, 0 3 0 4 3 是 4 3, 0, 2 0 0 4 3 否 - 0, 3, 4 3 0 4 3 否 - 3, 0, 4 2 0 2 3 是 4 2, 3, 0 1 1 2 3 是 0 1, 3, 2 2 1 2 3 否 - 2, 3, 1 0 0 2 3 是 1 0, 3, 2 1 0 1 3 是 2 1, 3, 0 7 1 7 3 是 0 7, 3, 1 0 1 7 0 是 3 0, 7, 1 1 1 7 0 否 - 1, 0, 7 总缺页次数：12
(注：与 OPT 算法的缺页次数一样，这对于这个特定的引用串来说是巧合，LRU 通常能接近 OPT 但不一定总是相等)
3.4 LRU 的近似实现 (Approximation)
由于精确 LRU 实现的复杂性和开销，操作系统通常采用一些算法来近似 LRU 的行为。它们利用硬件提供的引用位 (Reference Bit)。每个页表条目通常有一个引用位，当该页面被访问（读或写）时，硬件会自动将该位设置为 1。操作系统会定期（例如，通过时钟中断）将这些引用位清零。
3.4.1 时钟算法 (Clock Algorithm) 或 第二次机会算法 (Second Chance Algorithm)
-
概念： 结合了 FIFO 和 LRU 近似的算法。它维护一个物理帧的循环列表（像时钟的表盘），以及一个指向某个物理帧的指针（像时钟的指针）。
-
工作原理：
- 当需要替换页面时，检查指针当前指向的页面。
- 检查该页面的引用位。
- 如果引用位是 1：说明最近被访问过，给它“第二次机会”。将引用位清零，并向前移动指针到下一个页面，然后重复步骤 2。
- 如果引用位是 0：说明最近没有被访问过。选择这个页面进行替换，然后将新页面加载到这个物理帧中，并更新页表。指针移动到下一个页面。
- 如果指针转了一圈回到起点，所有页面的引用位都是 1，说明所有页面最近都被访问过。在这种情况下，所有引用位都被清零，算法会再进行一轮扫描，这次肯定会找到一个引用位为 0 的页面进行替换（因为所有位都已被清零）。
-
优点： 实现简单，开销远小于精确 LRU，性能通常优于 FIFO 且接近 LRU。
-
缺点： 不如精确 LRU 准确，无法区分最近一次访问的具体时间，只能区分“最近被访问过”和“最近没有被访问过”。
-
示例 (概念演示，使用引用位):
假设有 3 个物理帧，初始为空，指针指向帧 0。引用串：
7, 0, 1, 2- 引用 7: 缺页。加载 7 到帧 0。帧: [7], [], [], 指针->帧 1。引用位: [1], [0], [0].
- 引用 0: 缺页。加载 0 到帧 1. 帧: [7], [0], [], 指针->帧 2. 引用位: [1], [1], [0].
- 引用 1: 缺页。加载 1 到帧 2. 帧: [7], [0], [1], 指针->帧 0. 引用位: [1], [1], [1].
- 引用 2: 缺页。没有空闲帧。需要替换。指针在帧 0 (包含 7)。
- 检查帧 0 (7): 引用位是 1。给第二次机会。引用位设为 0。帧: [7], [0], [1]. 引用位: [0], [1], [1]. 指针->帧 1 (包含 0).
- 检查帧 1 (0): 引用位是 1。给第二次机会。引用位设为 0。帧: [7], [0], [1]. 引用位: [0], [0], [1]. 指针->帧 2 (包含 1).
- 检查帧 2 (1): 引用位是 1。给第二次机会。引用位设为 0。帧: [7], [0], [1]. 引用位: [0], [0], [0]. 指针->帧 0 (包含 7).
- 检查帧 0 (7): 引用位是 0。替换 7。加载 2 到帧 0。帧: [2], [0], [1]. 引用位: [1], [0], [0]. 指针->帧 1 (包含 0). 缺页发生。
整个过程指针会循环扫描，只有引用位为 0 的页面才会被选中替换。如果一个页面在被指针扫描到之前又被访问了，它的引用位会再次变为 1，从而获得新的第二次机会。
3.5 其他算法
还有一些其他页替换算法，各有优缺点：
-
最近最不常用 (Least Frequently Used - LFU):
- 概念： 置换访问次数最少的页面。
- 工作原理： 为每个页面维护一个计数器，每次访问页面时，计数器加 1。需要替换时，选择计数器值最小的页面。
- 优点： 能够反映页面的长期使用频率。
- 缺点： 实现复杂（需要维护和更新计数器）。无法很好地适应程序行为的变化（如果一个页面在早期大量使用，但现在不再需要，它的计数器可能仍然很高，阻止它被替换）。计数器需要定期衰减才能反映近期的使用频率。
-
MVA (Multivariate Analysis) 或 Working Set Model 相关算法：
- 一些更复杂的算法试图根据进程的“工作集”（最近活跃使用的页面集合）来做出替换决策，或者考虑页面的类型（代码、数据）和脏位状态（优先替换干净页面，因为不需要写回磁盘）。
4. 实际系统中的选择
在实际的操作系统中，通常不会使用纯粹的 FIFO 或精确的 LRU。
- FIFO 太简单且性能不稳定。
- 精确 LRU 实现成本太高。
因此，许多操作系统采用LRU 的近似算法，如时钟算法或其变种。这些算法在性能和实现开销之间取得了较好的平衡。此外，实际系统还会考虑其他因素，例如：
- 脏位 (Dirty Bit): 未被修改过的页面（干净页面）可以直接丢弃，而被修改过的页面（脏页面）必须写回磁盘。优先替换干净页面可以减少 I/O 开销。
- 页面类型： 代码页面通常是只读的，永远不需要写回磁盘；数据页面则可能需要。
- 进程优先级： 高优先级进程的页面可能不太容易被置换。
总结
页替换是虚拟内存管理中的一个关键环节，它发生在物理内存不足以容纳新页面时。页替换算法的目标是选择一个“最佳”的页面从物理内存中移除，以最小化未来的缺页次数。
- OPT 是理论最优但不可实现的算法。
- FIFO 简单但性能较差，不考虑页面使用模式。
- LRU 基于局部性原理，性能通常较好，但精确实现开销大。
- 时钟算法（第二次机会算法） 是 LRU 的一种有效近似，利用引用位在性能和实现复杂度之间取得了平衡，是许多实际操作系统采用的方法。
- LFU 基于使用频率，但实现复杂且难以适应程序行为变化。
现代操作系统通常使用 LRU 的近似算法，并结合脏位等信息，来高效地管理物理内存中的页面。理解这些算法对于深入掌握操作系统的内存管理至关重要。