操作系统-页面置换算法

置换算法的功能和目标

功能

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

设计目标

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

页面锁定(frame locking)

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

置换算法的评价方法

  • 记录进程访问内存的页面轨迹
  • 评价:模拟页面置换算法,记录缺页的次数,更少的缺页意味着更好的性能

页面置换算法分类

  • 局部页面置换算法:着眼于当前进程 最优算法,先进先出算法,最近最久未使用算法,时钟算法,最不常用算法
  • 全局页面置换算法:着眼于所有可换出的物理页面 工作集算法,缺页率算法

局部页面置换算法

最优页面置换算法 OPT

  • 置换未来最长时间不访问的页面
  • 实际系统中无法实现

FIFO算法

  • 思路: 选择在内存中滞留时间最长的页面进行置换
  • 实现:
    • 维护一个记录所有位于内存中的逻辑页面链表
    • 链表元素按驻留内存时间排序,链首最长,链尾最短
    • 出现缺页时,选择链首进行置换
  • 特征:
    • 实现简单
    • 性能较差
    • Belady现象

时钟置换算法

  • 思路:对页面的访问情况进行大致统计
  • 实现:
    • 在页表项增加访问位,
    • 各页面组织成环形链表
    • 指针指向最先调入的页面
  • 算法:
    • 访问页面时,在页表项记录页面访问情况
    • 缺页时,从指针处开始顺序查找未被访问的页面进行置换
  • 特征:是LRU和FIFO的折中

【Note】:访问位的标记是硬件自动完成的

  • 具体流程
    • 页面装入内存时,访问位初始化为0
    • 访问页面(读/写)时,访问位置1
    • 缺页时,从指针当前位置顺序检查环形链表
      • 访问位为0,则置换该页
      • 访问位为1,则访问位置0,并指针移动到下一个页面,
      • 直到找到可置换的页面

全局页面置换算法

工作集页置换算法

  • 工作集 $W(t, \Delta)$
    • t是当前的执行时刻
    • $\Delta$ 是工作集窗口,即一个定长的页面访问时间窗口
    • $W(t,\Delta)$表示在当前时刻t前的$\Delta$时间窗口中的所有访问页面所组成的集合
    • $|W(t,\Delta)|$指工作集的大小,即页面数目
  • 工作集页置换算法思路:换出不在工作集中的页面
  • 窗口大小$\tau$:当前时刻前$\tau$个内存访问的页引用是工作集,$\tau$被称为窗口大小
  • 实现方法:
    • 访存链表:维护窗口内的访存页面链表
    • 访存时,换出不在工作集的页面,更新访存链表
    • 缺页时,换出页面,更新访存链表
打赏