页面置换算法

虚拟内存技术

  • 在程序执行中,当cpu所需的信息不在内存中时,操作系统负责将所需要的信息从外存调入内存。
  • 如果调入内存的空间不够,由操作系统将内存中暂时用不到的信息换出到外存中。

问题::哪些页面需要从内存中换出来,哪些有需要被调入呢?

页面置换算法

常见的有如下几种,

最佳(Optimal, OPT)页面置换算法

最佳页面置换算法选择被淘汰页面将是以后永不使用的,或者在最长时间内不被访问的页面,这样可以保证最低的缺页率。

但,关键在于,如何预知未来,因此这是个理想情况的算法,不可能实现。

先进先出(FIFO)页面置换算法

顾名思义,先进先出算法优先淘汰最先调入的页面,也是在内存中驻留最久的页面。使用队列实现。

最近最久未使用(Least Recently Used, LRU)页面置换算法

选择最近最长时间未被访问过的页面淘汰,它认为过去一段时间未访问过页面,在最近的将来也不会访问。

使用寄存器实现

  • 为每一个页面分配一个移位寄存器
  • 某个页面被访问时,将对应寄存器置为1
  • 此后,定时器定时将寄存器右移1位,随着时间推移,页面的寄存器值会越来越小
  • 需要页面置换时,将寄存器值最小的置换出去

使用栈实现

每当某个页面被访问时,将该页面号从栈中移除,并置于栈顶。因此栈顶总是最新访问的,栈底是最久未被访问的。当需要置换时,将栈底页面置换出去。

最少使用(Least Recently Used,LFU)页面置换算法

LFU的思想就是未每一个页面设置一个计数器,需要置换时,选择计数最小的那个页面。

时钟(Clock)页面置换算法

简单的Clock算法

首先,内存中的页面具有几个属性,

  • 状态位,是否调入内存
  • 访问位,是否被访问过,如果是,则值为1
  • 修改为,是否被更新过

简单的Clock算法将页面链成一个循环队列,需要置换时,

  • 遍历这个队列,如果遇到访问位为0的就置换出去
  • 如果没有找到,则指针会循环一周将所有使用位都置为0,并停在初始页,将其置换出去。

改进的Clock算法

改进的clock算法除了访问位外,还使用修改位,每一种页面都具有以下四种状态,

访问位 修改位 description
0 0 最佳替换页面
0 1 第二考虑的页面
1 0 该页面可能再次被访问
1 1 该页面很有可能被再次访问

改进的算法步骤如下,

  • 1)从指针位置开始扫描循环队列,在这次扫描中不做任何修改,遇到00类页面,直接置换
  • 2)如果1)失败,则重新扫描,遇到第一个01类页面则置换,这次扫描中,对每个跳过的页面,将其访问位置于0
  • 3)如果2)失败,指针将回到初始位置,并且所有页面的访问位都被置于0了。重复回到步骤1)执行