地址映射过程中，若在页面中发现所要访问的页面不在内存中，则产生缺页中断。当发生缺页中断时，如果操作系统内存中没有空闲页面，则操作系统必须在内存选择一个页面将其移出内存，以便为即将调入的页面让出空间。而用来选择淘汰哪一页的规则叫做页面置换算法。

1. 最佳置换算法(OPT)

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

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

2. FIFO

先进先出置换算法(FIFO):每次选择淘汰的页面是最早进入内存的页面

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

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

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

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

3. LRU

最近最久未使用置换算法(LRU, least recently used):每次淘汰的页面是最近最久未使用的页面

实现方法:赋予每个页面对应的页表项中,用访问字段记录该页面自上次被访问以来所经历的时间t。该算法的实现需要专门的硬件支持,虽然算法性能好但是实现困难,开销大

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

4. CLOCK

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

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

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

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

5. 改进型的时钟置换算法

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

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

修改位=0,表示页面没有被修改过;

修改位=1,表示页面被修改过,用(访问位,修改位)的形式表示各页面状态。

如(1,1)表示一个页面近期被访问过,且被修改过。

算法规则:

将所有可能被置换的页面排成一个循环队列

  1. 第一轮: 从当前位置开始扫描到第一个（0,0）的帧用于替换。本轮扫描不修改任何标志位

    第一优先级: 最近没访问且没修改的页面

  2. 第二轮: 若第一轮扫描失败，则重新扫描，查找第一个（0,1）的帧用于替换。本轮将所有扫描过的帧访问位设为0

    第二优先级: 最近没访问，但修改过的页面

  3. 第三轮: 若第二轮扫描失败，则重新扫描，查找第一个（0,0）的帧用于替换。本轮扫描不修改任何标志位

    第三优先级: 最近访问过，但没修改的页面

  4. 第四轮: 若第三轮扫描失败，则重新扫描，查找第一个（0,1）的帧用于，替换。

    第四优先级：最近访问过且修改过的页面

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