页面置换算法

为什么需要页面置换算法

• 请求分页存储管理与基本分页存储管理的主要区别就是在当我们访问的信息不在内存时，由操作系统负责将所需信息从外存调入内存，若内存空间不够的时候，由操作系统负责将内存中暂时用不到的信息换出外存——换哪些页面就是由我们的页面置换算法决定

最佳置换算法—OPT

• 最佳置换算法的思想：每次选择淘汰的页面将是以后永不使用的，或者是在最长时间内不再被访问的页面，这样可以保证最低的缺页率
• 虽然这种算法可以保证最低的缺页率，但是我们在进程运行的时候不能预知未来的事件，所以最佳置换算法是无法实现的

先进先出置换算法

• 思想：每次选择淘汰的页面是最早进入内存的页面
• 但是这种算法会出现一个问题：Belady异常，当位进程分配的物理块数增大的时候，缺页次数不减反增的异常现象

最近最久未使用置换算法——LRU

• 思想：每次淘汰的页面是最近最久未使用的页面
• 实现方法：我们在对于每个页面对应的页表项中，用访问字段记录该页面自上次被访问以来所经历的时间t,我们淘汰的时候，选择现有页面中t最大的，也就是最近最久未使用的页面

时钟置换算法

简单时钟置换算法

• 虽然LRU的算法性能不错，但是实现起来需要专门的硬件支持 栈和寄存器，算法开销比较大
• 时钟置换算法是一种性能和开销比较均衡的算法
• 简单时钟置换算法思想
  • 为每个页面设置一个访问位 放在页表项的访问位 0表示最近没访问过 1表示最近访问过
  • 再将内存中的页面都通过链接指针链接成一个循环队列
  • 简单的CLOCK算法可能需要两轮的循环
    • 第一轮扫描，我们如果找到0的，那么就停止循环，把这个页面换出，如果遇到1，就把1变成0
    • 第二轮扫描，我们就找到第一个为0的页面，停止循环

改造型时钟置换算法

• 我们的简单的时钟置换算法仅考虑了一个页面最近是否被访问的，而没有考虑过淘汰的页面有没有被修改过
  • 因为修改过了，我们需要执行I/O操作写回外存，只有被淘汰的页面被修改过，才需要写回外存
• 我们引入一个标志位表明是否被修改过 1表示被修改过，0表示没有被修改过
  1. 最近没访问，没修改
  2. 最近没访问，修改过
  3. 最近访问过，但没修改过
  4. 最近访问过，也被修改了
• 思路：
  • 第一轮 从当前位置开始扫描到第一个(0,0),这一轮不会修改任何标志位
  • 第二轮：第一轮扫描失败，所以不存在最近没访问，没修改的页面，则我们查找第一个（0，1）的页面，本轮扫描过的页面会把访问位设为0
  • 若第二轮扫描失败，则查找第一个（0，0），本轮不会修改任何标志位
  • 第四轮 查找第一个（0，1）的页面