目录
最佳置换算法(Optimal)
随机置换算法(Random)
先入先出置换算法(FIFO)
最久未使用算法(LRU)
LRU的两种实现方法
LRU的近似算法:模拟aging
Clock算法
Clock算法的扩展
最佳置换算法(Optimal)
一种理想状态下的算法,是假设所有页面的访问次序是已知的。这也是最优的算法,其他算法可以跟最佳置换算法进行比较来测试这个算法是否够好。
在所有页面的访问次序是已知的前提下,我们只需要选择未来最长时间内不被访问的页面进行换出即可。
实例:假设系统为某进程分配了四个内存块,并考虑到有以下页面号引用串:1,2,3,4 ,1 ,2 ,5 ,1,2,3 ,4, 5
确定被换出的页面的方法是:准备置换时往观察将要访问的页面,在一段时间内,找到内存中的最晚被访问的页面,那么它就是要被置换出的页面。
随机置换算法(Random)
顾名思义,就是随机选择一个页面进行替换。这种算法易于实现,而且效果也不错。
先入先出置换算法(FIFO)
先入先出算法的原则是淘汰最先分配的页面。
实例:假设系统为某进程分配了四个内存块,并考虑到有以下页面号引用串:1,2,3,4 ,1 ,2 ,5 ,1,2,3 ,4, 5
确定将被置换出的页面的方法:可以发现FIFO算法是严格按照一条斜线来选择替换页面的,这是因为FIFO只用确定最早的页面访问顺序,后面即使遇到访问内存中已经存在的页面时,最早的那个进入顺序也不会发生改变。
由此,我们也可以发现置换算法的比较不好的一点,假设当系统分配的内存块大小为4时,页面访问顺序为1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,此时每次的访问都需要进行页面的置换,效率非常的低。
最久未使用算法(LRU)
原则:将最久未使用的页面置换出去。本质上是一种回望过去的一种算法。
实例:假设系统为某进程分配了四个内存块,并考虑到有以下页面号引用串:1,2,3,4 ,1 ,2 ,5 ,1,2,3 ,4, 5
确定将被置换出的页面的方法:在要进行页面置换时,回望过去,找到最久没有被访问的页面进行替换。
LRU的两种实现方法
LRU的Counter实现:即使用逻辑时钟来区分
每一个页表项关联一个时间,每次内存引用,把当前时钟(逻辑时钟)复制到对应的时钟域上
当一页需要被替换时,选择最老的替换。
缺点:必须搜索所有页的时间域
LRU的Stack实现 :以双向链表的形式
原则:
- 每当引用一个页,该页就从栈中删除并放到栈顶
- 每次替换栈底页(避免搜索所有页)
缺点:由实现方法我们可以看出LRU的Stack实现总是要对栈进行更新,系统开销是比较大的。
LRU的近似算法:模拟aging
原则:
- 为每个页框设置一个计数器 R=Rn-1Rn-2Rn-3 ..R2R1R0
- 每隔一段时间,时钟中断到达时,OS做以下处理
- 将R右移一位,若页被访问过,最高位置1
- 最小数值的页面即为最久未被访问的页面
Clock算法
一种将LRU和FIFO结合的算法。
页表项设置一个引用位(reference)
原则:
- 某页被访问,其引用位设为1
- 如果发生缺页中断,检查引用位
- 如果为1,重置为0,不置换(给第二次机会),按照FIFO顺序检查下一页
- 如果为0,置换该页
- 如果内存内的页面被访问,其引用位置为1,但是指针不移动。
实例:假设系统为某进程分配了四个内存块,并考虑到有以下页面号引用串:1,2,3,4 ,1 ,2 ,5 ,1,2,3 ,4, 5
- 放入1,2,3,4页表,引用位置为1,指针返回到开头
- 访问1,2页面,由于1,2存在于内存之中,于是指针位置不变。
- 依次往下寻找页面5,没找到就引用位置为0。引用位全部置为0后,指针到达开头。
- 将第一位替换为页面5,引用位置为1,并且指针下移。
- 指针所指向的页面引用位为0,就替换为页面1,引用位置为1,并且指针下移。
- 指针所指向的页面引用位为0,就替换为页面2,引用位置为1,并且指针下移。
- 以此类推即可
Clock算法的扩展
Clock算法的问题:没有区分页是脏的还是干净的 (dirty or clean )
脏页:该页的数据已经被修改,需要写回磁盘 ,因此替换脏页比替换干净页开销更大。
基本思想:应该尽量避免已修改的页面被替换
使用dirty位表示脏页
每一次访问页面:
- Read:设reference位为1
- Write:设dirty位为1
页面替换过程
- reference=0,dirty=0→替换
- reference=0,dirty=1→跳过
- reference =1,dirty =0>reference =0,dirty =0
- reference =1,dirty 1>reference =0,dirty =1
循环扫描,如果没有替换页,把未被引用的脏页(reference=0,dirty=1)写回磁盘,然后重复



