此算法又称为第二次机会算法；大致有两种思路：

思路1：

王道讲解的：

思路2：

清华大学陈渝讲解的：

刚开始接触时，觉得有一个是错误的，但不知道是哪个错误，其次清华大学这个也不太理解。尤其是讲到例子：当页面e进入时，为什么a(11)变成了a(00),b(11)变为了b(00).经过多次听讲终于明白了(参考自操作系统(RISC-V) - 清华大学 - 学堂在线；爆肝上传！清华大佬终于把困扰我大学四年的【计算机操作系统】讲的如此通俗易懂_哔哩哔哩_bilibili)：

它是从指针开始的位置开始扫描，

只要遇到(0,0) 则直接进行置换，并伴随的指针的后移；

只要遇到(0,1)变为(0,0)，指针后移；

只要遇到(1,0)变为(0,0)，指针后移；

只要遇到(1,1)变为(0,1),，指针后移；

指针一直循环扫描。

所以当e页面进入时，第一轮为：a(01) b(01) c(00) d(00) 第二轮 a(00) b(00),页面c为00，所以调出页面c,调入页面e(10),且指针下移，指向页面d。

 使用此种思路和王道思路发现最后殊途同归，结果一致，但本人认为还是清华的思路更为简洁，清楚。

来源：https://www.bilibili.com/video/BV1YE411D7nH

背景：在内存不足的情况下，操作系统会将内存中暂时不需要使用的信息换出到外存，页面置换算法就是用于选择到底将哪个页面换出到外存的算法。

注意：页面置换算法的好坏是可以通过缺页率来体现的，一个好的页面置换算法往往拥有较小的缺页率。

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

思想：每次选择淘汰的页面将是以后永远不再使用或在最长时间内不再使用的页面，以保证最低的缺页率。

例子：假如系统为操作系统分配了三个内存块，并且采用以下的页面号引用串（会依次访问这些页面）：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0

解释：首先进程一共有三个内存块，因此7 、0、 1依次进入内存块。当2想要进入内存块的时候，发现已满(里面是7,0,)，这时候从前往后找，0和1下一次会被使用的位置，在7下一次使用的位置之前。这说明7就是最长时间不会被使用的页面，因此将7的内存块换出到外存，2进入到内存块1。后面依次类推。在整个过程中：缺页中断发生了8次**，页面置换发生了5次（前3次都发生了缺页，但是没用进行置换）。因此可以知道：**缺页时未必发生页面置换，若还有可用的内存块时，就不会进行置换

总结：最佳置换算法可以保证最低的缺页率，但是实际上不能被实现。因为只有在进程执行过程中才能知道接下来会访问哪个页面，而操作系统并不能提前预知页面的访问顺序。

先进先出置换算法（FIFO）

思想：每次选择淘汰的页面是最早进入内存的页面（FIFO队列的最大长度取决于系统为进程分配了多少个内存块）

例子：假设系统为某进程分配了三个内存块，并以下面的页面号为引用串：3，2，1，0，3，2，4，3，2，1，0

解释：当访问1号页面的时候，这时候队列的形式是3->2->1；当要访问0号页面的时候，内存已满，则将最先进入队列的3置换到外存，这时候队列的形式为2->1>0，后面的情形可以依次类推

注意：

• FIFO算法实现简单，但是与进程实际运行的规律相违背，因为先进入内存的页面也可能会被经常访问。

• FIFO算法会出现Belady（贝拉迪）异常。

  **Belady异常**是指：当为进程分配的物理块数增大的时候，缺页的次数不增反减（在上面的例子中，如果将内存块改为4个，其他不变，那么缺页的次数将达到10次）

最近最少使用置换算法（Least Recently Used，LRU）

思想：淘汰最近最少使用的页面

实现方法：在每个页面的页表项中，用访问字段记录该页面自从上一次被访问以来经历的时间t，如果需要淘汰一个页面的话，就在页表中选择t值最大的页面。格式如下：

例子：假设系统为某进程分配了四个内存块，并以下面的页面号为引用串：1，8，1，7，8，2，7，2，1，8，3，8，2，1，3，1，7

解释：首先肯定是1 8 7 2将内存填满，在下一次访问到3的时候，这时候内存中没有，所以要进行置换操作，在访问3前面，7是最远一次访问的，因此t比较大，所以要置换7。下一次要访问7时，也是这样子进行置换的。

总结：LRU的实现需要硬件支持，其性能最接近最佳页面置换算法，但是该算法实现困难，开销大

时钟置换算法（CLOCK）

简介：是一种性能和开销相对均衡的算法。也被称为最近未使用算法（Not Recenty Use，NRE）。

思想：简单的CLOCK算法为页面设置一个访问位，再将内存中的页面通过链接指针链接成一个循环队列。当某页被访问的时候，其访问位置设置为1。当淘汰一个页面的时候，只需要检查页的访问位，如果是0，就选择将该页换出（之前没被访问过）；如果是1，则将其置换为0，暂时不换出（上次访问过，可能还会继续访问）。然后接着检查下一个页面，如果第一轮扫描结束后，所以的页面的访问位都是1，则会将这些页面全部置0，再进行第二次扫描（第二轮扫描中肯定有为0的页面）。因此，简单的CLOCK算法选择淘汰一个页面最多经过两轮扫描。

例子：假设系统为某进程分配了五个内存块，并以下面的页面号为引用串：1，3，4，2，5，6，3，4，7

首先五个内存块中分别放入了页面1，3，4，2，5，这时候循环队列如下，访问位都设置为1了：

想要放入6的时候，这时候内存满了，因此需要淘汰，经过一轮的遍历后，会将这五个页面的标志位修改位0，再从队头1的位置放入6,此时循环队列如下：

下一次访问3，则将3号页置为1，再下一次访问4再将4号页置为1，此时循环队列为：

最后访问7，只是7不在内存中，则遍历队列，先将3号页置为0，再将4号页置为0，遍历到2号页的时候，发现2号页的访问位为0，则将2号页换出，此时循环队列如下：

改进型的时钟置换算法

​ 简单的时钟置换算法仅考虑了一个页面是否被访问过。事实上，如果淘汰的页面是一些没有被修改过的页面，那么就不用执行I/O操作。只有被淘汰的页面被修改过时，才需要写回外存。

思想：除了考虑一个页面最近是否被访问之外，操作系统还应考虑页面是否被修改过。在其它条件相同下，优先淘汰没有被修改过的页面，避免I/O操作。其中，修改位为0表示没有被修改过，修改位为1表示被修改过。

算法规则： 假设用（访问位，修改位）的形式记录各个页面的状态。如（1,1）表示一个页面最近被访问过并修改过。

首先还是将可能被置换的页面排成一个循环队列。

第一轮：从当前位置开始扫描到第一个（0，0）的帧用于替换本轮扫描不修改任何标志位【第一优先级：找一个既没有被标记也没有被修改过的页面】

第二轮：若第一轮扫描失败，则重新扫描，查找第一个（0， 1）的帧用于替换本轮将所有扫描的帧访问位设置为0【第二优先级：找一个没有被标记但是被修改过的页面】

第三轮：若第二轮扫描失败，则重新扫描，查找第一个（1，0）的帧用于替换。本轮扫描不修改任何标志位【第三优先级：找一个最近被访问过但是未被修改过的页面】

第四轮：若第三轮扫描失败，则重新扫描，查找第一个（1，1）的帧用于替换【第四优先级：找一个最近被访问过同样也被修改过的页面】

注：由于第二轮扫描的时候将访问位设置为0了，因此经过第三轮、第四轮扫描一定有一个帧被选中。因此改进的CLOCK置换算法选择一个淘汰页面最多会进行四次扫描

页面置换算法

知识总览

最佳置换算法（OPT）

每次选择淘汰的页面将是以后永不使用，或者在最长时间内不再被访问的页面， 这样可以保证最低的缺页率。
跟开了上帝视角似的
是最优的情况（实际不可能达到，是无法实现的）

先进先出置换算法（FIFO）

淘汰最先进入内存的页面。
有Belady异常：当为进程分配的物理块增大时，可能出现缺页次数增多的反常现象。（也只有它会有这种异常）
算法性能差。

最近最久未使用置换算法（LRU）

每次淘汰的页面是最近最久未使用的页面。
需要专门的硬件支持，算法性能好，但实现困难，开销大。
它是最接近最佳置换算法的算法！

时钟置换算法（CLOCK）

一种开销和性能较均衡的算法，也成为最近未用算法。
换出最近没有被访问的（访问位为0）。若都被访问过，则转到谁谁访问位置为0再转。
也就是说，当且仅当某个位置访问位为0且被转到，就被置换出去。

改进型的时钟置换算法

考虑了修改页面的情况。

总结