目标

  • 当缺页中断发生，需要调入新的页面而内存已满，则需要对物理页面进行换入换出操作；
  • 尽可能地减少页面换进换出的次数
  • 页面锁定：在页面中添加锁定位

最优页面置换算法

  • 置换页面是在将来最长时间不会访问的页面

先进先出算法

  • first-in first-out，FIFO
  • 性能较差，调出的页面可能是经常要访问的页面，并且有belady现象，FIFO算法很少单独使用

最近最久未使用算法

  • 最近最久未使用算法（Least Recently Used，LRU）
  • 是对最优页面置换算法的一个近视，其依据是程序的局部性原理
  • 可能的实现方式：1. 链表 2. 堆栈

时钟页面置换算法

  • 环形链表
  • 初始化为0，used bit =1 表示最近被使用了，若为0则被置换出去

二次机会置换算法

  • 修改clock算法，允许脏页总是在一次时钟头扫描中保留下来
  • dirty bit = 1时，则需要回写到外存

最不常用算法

  • Least Frequently Used，LFU
  • 换出访问次数最少的页面
  • 实现方法：增加一个访问的计数器

几种算法的比较

  • Belady现象：在采用fifo算法时，有时会出现分配的物理页面数增加，缺页率反而提高的异常现象
  • Belady现象的原因：与算法的目标不一致，替换出去的页面，并不是不会访问的页面