页面置换算法

可能是最全的页面置换算法总结了。转自：https://www.ofweek.com/ai/2021-04/ART-201721-11000-30495592.html

最佳置换法（OPT）

最佳置换算法（OPT，Optimal） ：每次选择淘汰的页面将是以后永不使用，或者在最长时间内不再被访问的页面，这样可以保证最低的缺页率。

最佳置换算法可以保证最低的缺页率，但实际上，只有在进程执行的过程中才能知道接下来会访问到的是哪个页面。操作系统无法提前预判页面访问序列。因此，最佳置换算法是无法实现的

先进先出置换算法（FIFO）

先进先出置换算法（FIFO） ：每次选择淘汰的页面是最早进入内存的页面实现方法：把调入内存的页面根据调入的先后顺序排成一个队列，需要换出页面时选择队头页面队列的最大长度取决于系统为进程分配了多少个内存块。

Belady 异常—当为进程分配的物理块数增大时，缺页次数不减反增的异常现象。

只有 FIFO 算法会产生 Belady 异常，而 LRU 和 OPT 算法永远不会出现Belady异常。另外，FIFO算法虽然实现简单，但是该算法与进程实际运行时的规律不适应，因为先进入的页面也有可能最经常被访问。因此，算法性能差

FIFO的性能较差，因为较早调入的页往往是经常被访问的页，这些页在 FIFO 算法下被反复调入和调出，并且有Belady现象。所谓Belady现象是指：采用 FIFO 算法时，如果对—个进程未分配它所要求的全部页面，有时就会出现分配的页面数增多但缺页率反而提高的异常现象。

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

最近最久未使用置换算法（LRU，least recently used） ：每次淘汰的页面是最近最久未使用的页面实现方法：赋予每个页面对应的页表项中，用访问字段记录该页面自．上次被访问以来所经历的时间t（该算法的实现需要专门的硬件支持，虽然算法性能好，但是实现困难，开销大）。当需要淘汰一个页面时，选择现有页面中t值最大的，即最近最久未使用的页面。

LRU性能较好，但需要寄存器和栈的硬件支持。LRU是堆栈类算法，理论上可以证明，堆栈类算法不可能出现Belady异常。

在手动做题时，若需要淘汰页面，可以逆向检查此时在内存中的几个页面号。在逆向扫描过程中最后一个出现的页号就是要淘汰的页面。

时钟置换算法（CLOCK）

最佳置换算法性 OPT 能最好，但无法实现；先进先出置换算法实现简单，但算法性能差；最近最久未使用置换算法性能好，是最接近 OPT 算法性能的，但是实现起来需要专门的硬件支持，算法开销大。

所以操作系统的设计者尝试了很多算法，试图用比较小的开销接近 LRU 的性能，这类算法都是 CLOCK 算法的变体，因为算法要循环扫描缓冲区像时钟一样转动。所以叫clock算法。

时钟置换算法是一种性能和开销较均衡的算法，又称 CLOCK 算法，或最近未用算法（NRU，Not Recently Used）

简单的 CLOCK 算法实现方法：为每个页面设置一个访问位，再将内存中的页面都通过链接指针链接成一个循环队列。

当某页被访问时，其访问位置为1，当需要淘汰一个页面时，只需检查页的访问位。如果是0，就选择该页换出；如果是1，则将它置为0，暂不换出，继续检查下一个页面，若第一轮扫描中所有页面都是1，则将这些页面的访问位依次置为0后，再进行第二轮扫描（第二轮扫描中一定会有访问位为0的页面，因此简单的CLOCK算法选择一个淘汰页面最多会经过两轮扫描）

改进型的时钟置换算法

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

因此，除了考虑一个页面最近有没有被访问过之外，操作系统还应考虑页面有没有被修改过。在其他条件都相同时，应优先淘汰没有修改过的页面，避免I／O操作。这就是改进型的时钟置换算法的思想。修改位＝0，表示页面没有被修改过；修改位＝1，表示页面被修改过。

为方便讨论，用（访问位，修改位）的形式表示各页面状态。如（1， 1）表示一个页面近期被访问过，且被修改过。

改进型的Clock算法需要综合考虑某一内存页面的访问位和修改位来判断是否置换该页面。在实际编写算法过程中，同样可以用一个等长的整型数组来标识每个内存块的修改状态。访问位A和修改位M可以组成一下四种类型的页面。

算法规则：将所有可能被置换的页面排成一个循环队列

第一轮：从当前位置开始扫描到第一个（0， 0）的帧用于替换。本轮扫描不修改任何标志位。（第一优先级：最近没访问，且没修改的页面）

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

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

第四轮：若第三轮扫描失败，则重新扫描，查找第一个（0， 1）的帧用于替换。（第四优先级：最近访问过，且修改过的页面）由于第二轮已将所有帧的访问位设为0，因此经过第三轮、第四轮扫描一定会有一个帧被选中，因此改进型CLOCK置换算法选择一个淘汰页面最多会进行四轮扫描。

总结

算法规则优缺点：

• OPT优先淘汰最长时间内不会被访问的页面缺页率最小，性能最好；但无法实现
• FIFO优先淘汰最先进入内存的页面实现简单；但性能很差，可能出现Belady异常
• LRU优先淘汰最近最久没访问的页面性能很好；但需要硬件支持，算法开销大
• CLOCK （NRU）循环扫描各页面 第一轮淘汰访问位＝0的，并将扫描过的页面访问位改为1。若第一轮没选中，则进行第二轮扫描。实现简单，算法开销小；但未考虑页面是否被修改过。
• 改进型CLOCK （改进型NRU）若用（访问位，修改位）的形式表述，则 第一轮：淘汰（0，0）； 第二轮：淘汰（O，1），并将扫描过的页面访问位都置为0； 第三轮：淘汰（O， 0）； 第四轮：淘汰（0， 1）算法开销较小，性能也不错