置换算法的功能和目标

• 功能

  • 当出现缺页异常，需调入新页面而内存已满时，置换算法选择被置换的物理页面

• 设计目标

  • 尽可能减少页面的调入调出次数
  • 把未来不再访问或者短期内不访问的页面调出

• 页面锁定（frame locking）

  • 描述必须常驻内存的逻辑页面
  • 操作系统的关键部分
  • 要求响应速度的代码和数据
  • 页表中的锁定标志位（lock bit）

页面置换算法分类

• 局部页面置换算法

  页面总数是不会变化的

  • 置换页面的选择范围仅限于当前进程占用的物理页面内
  • 最优算法、先进先出算法、最近最久未使用算法
  • 时钟算法、最不常用算法（这两个是LRU的近似）

• 全局页面置换算法

  • 置换页面的选择范围是所有可换出的物理页面
  • 工作集算法、缺页率算法

最优、先进先出、最近最久未使用算法

最优页面置换算法（OPT，optimal）

• 基本思路

  在缺页的时候观察内存当中存在的各个逻辑页在未来什么时间会被访问

  • 置换在未来最长时间不访问的页面

• 算法实现

  • 缺页时，计算内存中每个逻辑页面的下一次访问时间
  • 选择未来最长时间不访问的页面

• 算法特征

  • 缺页最少，是理想情况
  • 实际系统无法实现
  • 无法预知每个页面在下一次访问前的等待时间
  • 作为置换算法的性能评价依据
    • 在模拟器上运行某个程序，并记录每一次的页面访问情况
    • 第二遍运行时使用最优算法

先进先出算法（First-In First-out,FIFO)

• 思路
  • 选择在内存驻留时间最长的页面进行置换
• 实现
  • 维护一个记录所有位于内存中的逻辑页面链表
  • 链表元素按驻留内存的时间排序，链首最长，链尾最短
  • 出现缺页时，选择链首页面进行置换，新页面加到链尾
• 特征
  • 实现简单
  • 性能较差，调出的页面可能是经常访问的
  • 进程分配物理页面数增加时，缺页并不一定减少（Belady现象）
  • 很少单独使用

最近最久未使用（Least Recently Used，LRU）

• 思路

  • 选择最长时间没有被引用的页面进行置换
  • 如某些页面长时间未被访问，则它们在将来还可能会长时间不会访问

• 实现

  • 缺页时，计算内存中每个逻辑页面的上一次访问时间
  • 选择上一次使用到当前时间最长的页面

• 特征

  • 最优置换算法的近似

LRU算法的可能实现办法

• 页面链表

  • 系统维护一个按最近一次访问时间排序的页面链表
    • 链表首节点是最近刚刚使用过的页面
    • 链表尾节点是最久未使用的页面
  • 访问内存时，找到相应页面，并把它移到链表之首
  • 缺页时，置换链表尾节点的页面

• 活动页面栈

  • 访问页面时，将此页号压入栈顶
  • 如果是栈内相同的页号抽出放到栈顶
  • 缺页时，置换栈底的页面

• 特征

  • 开销大

时钟置换算法和最不常用算法

时钟置换算法（Clock）

• 思路

  • 仅对页面的访问情况进行大致统计

• 数据结构

  • 在页表项中增加访问位，描述页面在过去一段时间的内访问情况
  • 各页面组织成环形链表
  • 指针指向最先调入的页面

• 算法

  • 访问页面时，在页表项记录页面访问的情况
  • 缺页时，从指针处开始顺序查找未被访问的页面进行量

• 特征

  • 在LRU和FIFO中的折中

改进的clock算法

• 思路
  • 减少修改页的缺页处理开销
• 算法
  • 在页面中增加修改位，并在访问时进行修改
  • 缺页时，修改页面标志位，以跳过有修改的页面

最不常用算法（Least Frequently Used LFU）

• 思路
  • 缺页时，置换访问次数最少的页面
• 实现
  • 每个页面设置一个访问计数
  • 访问页面时，访问计数加1
  • 缺页时，置换计数最小的页面
• 实现
  • 算法开销大
  • 开始时频繁使用，但以后不使用的页面很难置换
    • 解决方法：计数定期右移
• LRU和LFU的区别
  • LRU关注多久未访问，时间越短越好
  • LFU关注访问次数，次数越多越好

Belady现象和局部置换算法比较

Belady现象

• 现象
  • 采用FIFO等算法时，可能出现分配的物理页面数增加，缺页次数反而升高的异常现象
• 原因
  • FIFO算法的置换特征与进程访问内存的动态特征矛盾
  • 被它置换出去的页面并不一定是进程近期不会访问的

LRU、FIFO和Clock的比较

• LRU和FIFO本质上都是先出现出的思路

  • LRU根据页面的最近访问时间排序
  • LRU需要动态的调整顺序（开销大）
  • FIFO根据页面进入内存的时间排序
  • FIFO的页面进入时间是固定不变的

• LRU可退化成FIFO

  • 如页面进入内存后没有被访问，最近访问时间与进入内存的时间相同

  • 例如：给进程分配3个物理页面，逻辑页面的访问顺序为1、2、3、4、5、6、1、2、3

    播视频（信息只放一遍）

• LRU算法性能较好，但系统开销较大

• FIFO算法系统开销较小，会发生Belady现象

• Clock算法是它们的折中

  • 页面访问时，不动态调整页面在链表中的顺序，仅作标记
  • 缺页时，再把它移动到链表末尾

• 对于未被访问的页面，clock和LRU算法的表现一样好

• 对于被访问过的页面，clock算法不能记录准确访问顺序，而LRU算法可以