页面置换算法
虚拟内存技术
- 在程序执行中,当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)执行