文章目录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)。优先级(A0, M0)最佳淘汰没访问也没改直接踢不用写回磁盘。(A0, M1)次佳没访问但改了踢的时候要写回磁盘慢一点。(A1, M0)刚用过给机会。(A1, M1)刚用过且改了最后考虑。修改位就是看使用这个页面的时候是否有修改操作。如果内存中一直存在(A0, M0)的页面那么算法在第一轮扫描时就会立刻找到它并把它淘汰掉根本不会进入第二轮自然也就永远不会触发对(A0, M1)页面的淘汰。为了防止内存中积累过多脏页A0, M1导致页面置换算法陷入频繁的多轮扫描与磁盘 I/O 瓶颈现代操作系统引入了后台回写线程机制。该机制会专门对A0, M1的页面把数据写回到磁盘后把M位设置为0。总结性价比之王。性能接近LRU但硬件实现简单是现代操作系统如Linux最常用的算法基础。曾经用过的页面至少需要被扫描两次才会被淘汰第一次置为0再转一圈的时候才淘汰。在时钟置换算法中当扫描指针将页面的访问位置为0时无需进行额外的“是否正在被使用”的状态判定。理论上若某页面的活跃周期跨越了扫描周期确实存在在二次扫描时被误淘汰的风险。但在实际工程运行中由于硬件自动置位的频率远高于软件扫描清零的频率这种误淘汰的概率极低。即便发生系统也仅需通过触发一次缺页中断将页面重新从磁盘调入内存即可恢复其代价仅仅是增加了一次磁盘I/O开销。 一张表总结复习神器算法依据性能实现代价备注OPT未来⭐⭐⭐⭐⭐ (理论最优)无法实现用于做对比标准FIFO进入时间⭐⭐低有Belady异常LRU过去⭐⭐⭐⭐高 (需硬件支持)实际应用多但有开销CLOCK访问位/修改位⭐⭐⭐中LRU的近似最常用