1.最佳置换算法(OPT)
规则
- 优先淘汰最长时间内不会被访问的页面
- 保证缺页率最低
优点:缺页率最小,性能最好
缺点:无法实现
示例:

2.先进先出置换算法(FIFIO)
规则:优先淘汰最先进入内存的页面
优点:实现简单,把调入内存的页面根据先后次序连接成队列,设置一个指针总是指向最早的页面。
缺点:性能差,可能出现Belady异常;该算法与进程实际运行规律不适应,因为在进程中,有些页面经常被访问。
Belady异常:
页面置换算法会产生所分配的物理块数增大而页故障不减反增的异常现象;
只有FIFO算法可能出现Belady异常,LRU和OPT算法永远不会出现Belady异常。
示例:

3.最近最久未使用置换算法(LRU)
规则:优先淘汰最近最久没访问的页面
实现:
为每个页面设置一个访问字段,来记录页面上次被访问依赖所经历的时间,淘汰页面时选择现有页面中值最大的淘汰。
优点:性能很好
缺点:需要硬件支持,算法开销大
示例

手动计算时,可以逆向检查此时在内存中的几个页面号。在逆向扫描过程中最后一个出现的页面好就是要淘汰的页面
4.时钟置换算法(CLOCK)
规则:
- 为每一个页面设置一个访问位,再将内存中的页面都通过连接指针链接成一个循环队列。
- 当某个页面被访问时,其访问位置为1。
- 当需要淘汰一个页面时,只需检查页的访问位。如果是0就选择该页换出;如果是1,则将它置为0,暂不换出。
- 继续检查下一个页面,若第一轮扫描中所有页面都是1,则将这些页面依次置为0,在进行第二轮扫描(第二轮扫描一定会有访问位为0的页面)。
优点:实现简单,算法开销小
缺点:未考虑页面是否被修改

5.改进型的时钟置换算法
改进型CLOCK算法优于简单CLOCK算法的地方在于替换时首选没有变化的页。由于修改过的页在被替换之前必须写回,因而这样做会节省时间。
在使用位的基础上再增加一个修改位,得到改进型CLOCK置换算法。这样,每帧都处于以下4种情况:
- (0,0)最近未被访问,也未被修改
- (1,0)最近被访问,但未被修改
- (0,1)最近未被访问,但被修改
- (1,1)最近被访问,被修改
规则:
- 将所有可能被置换的页面排成一个循环队列,其中(访问位,修改位)
- 第一轮:从当前位置开始扫描到第一个(0,0)的帧用于替换。本轮扫描不修改任何标志位。
- 第二轮:若第一轮扫描失败,则重新扫描,查找第一个是(0,1)的帧用于替换。本轮将所有扫描过的帧访问位设为0.
- 第三轮:若第二轮扫描失败,则重新扫描,查找第一个(0,0)的帧用于替换。本轮扫描不修改任何标志位。
- 第四轮:若第三轮扫描失败,则重新扫描,查找第一个(0,1)的帧用于替换。
优点:算法开销小,性能也不错