栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

操作系统页面置换算法总结

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

操作系统页面置换算法总结

目录

最佳置换算法(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实现 :以双向链表的形式

原则:

  1. 每当引用一个页,该页就从栈中删除并放到栈顶
  2. 每次替换栈底页(避免搜索所有页)

 缺点:由实现方法我们可以看出LRU的Stack实现总是要对栈进行更新,系统开销是比较大的。

LRU的近似算法:模拟aging 

原则:

  1. 为每个页框设置一个计数器 R=Rn-1Rn-2Rn-3 ..R2R1R0 
  2. 每隔一段时间,时钟中断到达时,OS做以下处理 
  3. 将R右移一位,若页被访问过,最高位置1 
  4. 最小数值的页面即为最久未被访问的页面 

Clock算法

一种将LRU和FIFO结合的算法。

页表项设置一个引用位(reference) 

原则:

  1. 某页被访问,其引用位设为1 
  2. 如果发生缺页中断,检查引用位 
  3. 如果为1,重置为0,不置换(给第二次机会),按照FIFO顺序检查下一页 
  4. 如果为0,置换该页 
  5. 如果内存内的页面被访问,其引用位置为1,但是指针不移动。

实例:假设系统为某进程分配了四个内存块,并考虑到有以下页面号引用串:1,2,3,4 ,1 ,2 ,5 ,1,2,3 ,4, 5

  1. 放入1,2,3,4页表,引用位置为1,指针返回到开头
  2. 访问1,2页面,由于1,2存在于内存之中,于是指针位置不变。
  3. 依次往下寻找页面5,没找到就引用位置为0。引用位全部置为0后,指针到达开头。
  4. 将第一位替换为页面5,引用位置为1,并且指针下移。
  5. 指针所指向的页面引用位为0,就替换为页面1,引用位置为1,并且指针下移。
  6. 指针所指向的页面引用位为0,就替换为页面2,引用位置为1,并且指针下移。
  7. 以此类推即可

Clock算法的扩展

Clock算法的问题:没有区分页是脏的还是干净的 (dirty or clean )
脏页:该页的数据已经被修改,需要写回磁盘 ,因此替换脏页比替换干净页开销更大。

基本思想:应该尽量避免已修改的页面被替换

使用dirty位表示脏页 
每一次访问页面:

  1. Read:设reference位为1 
  2. Write:设dirty位为1 

页面替换过程 

  1. reference=0,dirty=0→替换 
  2. reference=0,dirty=1→跳过 
  3. reference =1,dirty =0>reference =0,dirty =0
  4. reference =1,dirty 1>reference =0,dirty =1 

循环扫描,如果没有替换页,把未被引用的脏页(reference=0,dirty=1)写回磁盘,然后重复 
 

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/937293.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号