操作系统四种核心的页面置换算法

文章目录

• • • 1. 最佳置换算法 (OPT / Optimal)
    • 2. 先进先出算法 (FIFO / First-In First-Out)
    • 3. 最近最久未使用算法 (LRU / Least Recently Used)
    • 4. 时钟置换算法 (CLOCK / NRU)
    • 📊 一张表总结（复习神器）

1. 最佳置换算法 (OPT / Optimal)

口诀： “向后看，谁最远，就踢谁。”

• 原理： 选择未来最长时间内不再被访问的页面进行淘汰。
• 特点：
  • 理论上的最优解：能保证获得最低的缺页率。
  • 无法实现：因为操作系统无法预知未来的页面访问序列（它是“上帝视角”）。
  • 作用：通常作为评价其他算法好坏的标准（Benchmark）。
• 模拟过程（3个块）：
• 装入 7, 0, 1 （缺页3次，内存满：[7, 0, 1]）
• 访问 2：内存满。看未来序列 0, 3, 0, 4。
  • 0 马上要用。
  • 1 很久以后才用（甚至不用了）。
  • 决策： 淘汰 1。（因为它在未来最久不会被用到）。
• 访问 0：命中（内存里有）。
• 访问 3：内存满 [7, 0, 2]。看未来 0, 4。
  • 0 马上用。
  • 7 后面都不用了。
  • 决策： 淘汰 7。
• 总结： 性能最好，但只存在于理论中。

2. 先进先出算法 (FIFO / First-In First-Out)

口诀： “排队论，谁先来，先踢谁。”

• 原理： 总是淘汰最早进入内存的页面。就像排队买票，先来的人先走。
• 特点：
  • 实现简单：只需要一个队列记录顺序。
  • 性能较差：因为它不管页面是否常用，可能把常用的初始化代码（很早就调入）给踢出去。
  • Belady异常：这是FIFO特有的坑——分配的物理块越多，缺页次数反而可能增加。
• 模拟过程（3个块）：
• 装入 7, 0, 1 （顺序：7在最底，1在最顶）。
• 访问 2：淘汰最早进来的 7。内存变为 [0, 1, 2]。
• 访问 0：命中。
• 访问 3：淘汰最早进来的 0。内存变为 [1, 2, 3]。
• 访问 0：缺页！淘汰 1。内存变为 [2, 3, 0]。
• 访问 4：缺页！淘汰 2。
• 总结： 最简单，但效率低，且有Belady异常。

3. 最近最久未使用算法 (LRU / Least Recently Used)

口诀： “向前看，谁最久没用，就踢谁。”

• 原理： 选择过去最长时间内没有被访问过的页面进行淘汰。它是OPT算法的“逆向思维”（利用局部性原理：过去不用的，未来大概率也不用）。
• 特点：
  • 性能较好：接近OPT算法，是实际系统中比较理想的算法。
  • 开销大：硬件实现困难。需要给每个页面记录“上次使用时间”或者维护一个栈/计数器，硬件成本高。
• 模拟过程（3个块）：
• 装入 7, 0, 1。
• 访问 2：看过去，7是最早以前用的（0和1刚用过）。淘汰 7。内存 [0, 1, 2]。
• 访问 0：命中！注意：0变成了“最新”的。现在的老旧程度排序：1(最老) > 2 > 0(最新)。
• 访问 3：淘汰最老的 1。内存 [0, 2, 3]。
• 访问 0：命中！0又变最新了。
• 访问 4：此时内存里是 0, 2, 3。其中 2 是最久没被碰过的。淘汰 2。
• 总结： 性能好，但硬件太贵，难以完美实现。

4. 时钟置换算法 (CLOCK / NRU)

口诀： “转圈圈，指针扫，没用过就踢，用过给机会。”

• 原理： LRU的近似实现。为了降低硬件成本，给每个页面加一个访问位（Use Bit）。
  • 页面刚调入或被访问时，把访问位设置为 1。
  • 淘汰时，像时钟指针一样扫描页面：
    • 如果访问位是 1：给它一次机会，把它置为 0，指针下移。
    • 如果访问位是 0：说明这段时间都没用它，淘汰它。
• 进阶版（考试常考）：改进型Clock算法
  • 不仅看访问位(A)，还要看修改位(M)。
  • 优先级：
  • (A=0, M=0)：最佳淘汰（没访问也没改，直接踢，不用写回磁盘）。
  • (A=0, M=1)：次佳（没访问但改了，踢的时候要写回磁盘，慢一点）。
  • (A=1, M=0)：刚用过，给机会。
  • (A=1, M=1)：刚用过且改了，最后考虑。
  • 修改位就是看使用这个页面的时候是否有修改操作。
  • 如果内存中一直存在 (A=0, M=0) 的页面，那么算法在第一轮扫描时就会立刻找到它并把它淘汰掉，根本不会进入第二轮，自然也就永远不会触发对 (A=0, M=1) 页面的淘汰。
  • 为了防止内存中积累过多脏页（A=0, M=1）导致页面置换算法陷入频繁的多轮扫描与磁盘 I/O 瓶颈，现代操作系统引入了后台回写线程机制。该机制会专门对（A=0, M=1）的页面把数据写回到磁盘后，把M位设置为0。
• 总结：

  • 性价比之王。性能接近LRU，但硬件实现简单，是现代操作系统（如Linux）最常用的算法基础。

  • 曾经用过的页面，至少需要被扫描两次才会被淘汰，第一次置为0，再转一圈的时候才淘汰。

  • 在时钟置换算法中，当扫描指针将页面的访问位置为0时，无需进行额外的“是否正在被使用”的状态判定。理论上，若某页面的活跃周期跨越了扫描周期，确实存在在二次扫描时被误淘汰的风险。但在实际工程运行中，由于硬件自动置位的频率远高于软件扫描清零的频率，这种误淘汰的概率极低。即便发生，系统也仅需通过触发一次缺页中断，将页面重新从磁盘调入内存即可恢复，其代价仅仅是增加了一次磁盘I/O开销。

📊 一张表总结（复习神器）