【操作系统】页面置换算法_先进先出页面置换算法例题

页面的换入、换出需要磁盘I/O，会有较大的开销，因此好的页面置换算法应该追求更少的缺页率。

最佳置换算法（OPT）

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

例：假设系统为某进程分配了三个内存块，并考虑到有一下页面号引用串（会依次访问这些页面）：
7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1

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

先进先出置换算法（FIFO）

先进先出置换算法（FIFO）：每次选择淘汰的页面是最早进入内存的页面

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

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

例：假设系统为某进程分配了四个内存块，并考虑到有以下页面号引用串：
3, 2, 1, 0, 3, 2, 4, 3, 2, 1, 0, 4

Belady 异常——当为进程分配的物理块数增大时，缺页次数不减反增的异常现象。
只有 FIFO 算法会产生 Belady 异常。另外，FIFO算法虽然实现简单，但是该算法与进程实际运行时的
规律不适应，因为先进入的页面也有可能最经常被访问。因此，算法性能差

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

最近最久未使用置换算法（LRU，least recently used）：每次淘汰的页面是最近最久未使用的页面

实现方法：赋予每个页面对应的页表项中，用访问字段记录该页面自上次被访问以来所经历的时间t。
当需要淘汰一个页面时，选择现有页面中 t 值最大的，即最近最久未使用的页面。

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

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

该算法的实现需要专门的硬件支持，虽然算法性能好，但是实现困难，开销大。

时钟置换算法（CLOCK）

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

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

简单的CLOCK 算法实现方法：为每个页面设置一个访问位（为1，表示最近访问过；为0，表示最近没有访问过），再将内存中的页面都通过链接指针接成一个循环队列。
当某页被访问时，其访问位置为1。
当需要淘汰一个页面时，只需检查页的访问位。如果是0，就选择该页换出；如果是1，则将它置为0，暂不换出；继续检查下一个页面，若第一轮扫描中所有页面都是1，则将这些页面的访问位依次置为0后；
再进行第二轮扫描（第二轮扫描中一定会有访问位为0的页面，因此简单的CLOCK 算法选择一个淘汰页面最多会经过两轮扫描）

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

首先1，3，4，2，5分配内存，并设置访问位。如下：

在6时，需要淘汰一个页面，第一遍扫描，没有访问位为0，需要将扫描过的访问位置为0。如下：

然后第二遍扫描，1号页面访问位为0，置换为6号页面，访问位置为1，指针指向下一个页面。如下：

然后3号页面，将3号页面访问位置为1；如下（注意指针）：

4号页面，将4号页面访问位置为1；如下：

7号页面，需要淘汰一个页面，将3、4页面访问位置为0，2页面访问位为0，置换为7号页面，访问位置为1，指针指向下一个页面，如下：

改进型的时钟置换算法

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

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

修改位=0，表示页面没有被修改过；修改位=1，表示页面被修改过。

**（访问位，修改位）**形式；（1，1）表示一个页面近期被访问过，且被修改过。

算法最多进行四轮扫描：
第一轮：从当前位置开始扫描到第一个（0, 0）的帧用于替换。本轮扫描不修改任何标志位
第二轮：若第一轮扫描失败，则重新扫描，查找第一个（0, 1）的帧用于替换。本轮将所有扫描过的帧访问位设为0
第三轮：若第二轮扫描失败，则重新扫描，查找第一个（0, 0）的帧用于替换。本轮扫描不修改任何标志位
第四轮：若第三轮扫描失败，则重新扫描，查找第一个（0, 1）的帧用于替换。

按照算法规则自己实现下上面的例题。

【参考文献】
https://www.bilibili.com/video/BV1YE411D7nH?t=1102&p=45