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

目标

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

最优页面置换算法 ( OPT , optimal )

置换在未来最长时间不访问的页面，理想情况

先进先出算法（First-In First-Out, FIFO）

基本思路：选择在内存驻留时间最长的页面进行置换

算法实现

  • 维护一个记录所有位于内存中的逻辑页面链表
  • 链表元素按驻留内存的时间排序，链首最长，链尾最短
  • 出现缺页时，选择链首页面进行置换，新页面加到链尾

算法特征

  • 实现简单
  • 性能较差，调出的页面可能是经常访问的
  • 进程分配物理页面数增加时，缺页并不一定减少( Belady 现象)
  • 很少单独使用

最近最久未使用算法(Least Recently Used, LRU)

基本思路

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

算法实现

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

算法特征

最优置换算法的一种近似

LRU算法的可能实现方法

  • 页面链表
    • 系统维护一个按最近一次访问时间排序的页面链表
    • 链表首节点是最近刚刚使用过的页面
    • 链表尾节点是最久未使用的页面
    • 访问内存时，找到相应页面，并把它移到链表之首
    • 缺页时，置换链表尾节点的页面
  • 活动页面栈
    • 访问页面时，将此页号压入栈顶，并栈内相同的页号抽出
    • 缺页时，置换栈底的页面

特征

开销比较大

时钟置换算法（Clock）

基本思路

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

时钟算法是LRU和FIFO的折中

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

基本思路

缺页时，置换访问次数最少的页面

算法实现

  • 每个页面设置一个访问计数（多位计数）
  • 访问页面时，访问计数加1
  • 缺页时，置换计数最小的页面

算法特征

  • 算法开销大
  • 开始时频繁使用，但以后不使用的页面很难置换

解决方法

计数定期右移、衰减

LRU和LFU的区别

  • LRU关注多久未访问,时间越短越好
  • LFU关注访问次数，次数越多越好

LRU、FIFO和Clock的比较

  • LRU算法和FIFO本质上都是先进先出的思路

    • LRU依据页面的最近访问时间排序
    • LRU需要动态地调整顺序
    • FIFO依据页面进入内存的时间排序

  • LRU可退化成FIFO

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

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

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

  • Clock算法是它们的折衷

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

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

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