页面置换算法

  在进程运行过程中,若其所要访问的页面不在内存而需把它们调入内存,但内存中已无空闲空间时,为了保证该进程能正常运行,

系统必须从内存中调出一页程序或数据到磁盘的对换区中。但应将哪个页面调出,需根据一定的算法来实现。

  常见的页面置换算法有:

1. 最佳置换算法(Optimal)

从内存中移除永远都不再需要的页面或者说是未来最长时间内不再被访问的页面,如果这样的页面存在,则选择最长时间不需要访问的页面。采用最佳置换算法,可以保证较低的页面更新频率。从理论上讲,由于无法预知哪一个页面是未来最长时间内不再被访问的,因而该算法无法实现,但是可用来衡量其他算法。

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

该算法总是淘汰最早进入内存的页面,即选择在内存中停留时间最久的页面予以淘汰。

  这个算法的实现简单,只需要将进程已调入内存中的页面,按照先后顺序连接成一个队列,设置一个替换指针,总是指向最老的页面

  但是该算法与进程实际的规律并不相适应,因为在进程中,有些页面经常被访问,比如:含有全局变量、常用函数、例程等的页面,FIFO不能保证这些页面不会被淘汰。

3.最近最久未使用页面置换算法(LRU)

在之前的FIFO算法中,依据的是各个页面调入内存的时间,这并不能反映页面的真实使用情况。

  而LRU(Latest Recently Used)是根据页面调入内存之后的使用情况

  由于无法预测页面未来的情况,所以只能利用“最近的过去”来作为预测未来的方法,LRU选择的是最近最久未使用的页面予以淘汰。

  该算法赋予每个页面一个访问字段,用来记录一个页面从上次被访问以来所经历的时间t,当需要淘汰一个页面的时候,选择现有页面中t的值最大的页面进行淘汰

  LRU是一种优秀的页面置换算法,但是需要硬件的支持,为了了解一个进程在内存中各个页面各有多少时间未被进程访问,以及如何快速地知道哪一个页面是最近最久未使用的页面,需要 寄存器+栈 来支持。

  (1)寄存器

  为了记录某进程在内存中各页的使用情况,需要为每个在内存中的页面设置一个移位寄存器,可表示为:R=R(n-1)R(n-2)...R2R1R0,当进程访问某物理块时,要将相应寄存器的R(n-1)位置成1。此时,定时信号将每隔一定时间(例如100ms)将寄存器右移一位。如果我们把n位寄存器的数看做是一个整数,那么具有最小数值的寄存器所对应的页面,就是最近最久未使用的页面。当发生缺页时,首先将它置换出去。

  (2)栈

  可以利用一种特殊的栈来保存当前使用的各个页面的页面号,每当进程访问某页面的时候,便将该页面的页面号从栈中移除,将它压入栈顶。因此,栈顶始终是最新被访问页面的编号,栈底则是最近最久未访问页面的页面号,当需要置换页面的时候,将栈底对应的页面置换出来。

4.Clock置换算法

  当采用简单Clock算法时,只需为每页设置一位访问位,再将内存中的所有页面都通过链接指针链接成一个循环队列

  当某页被访问时,其访问位被置为1。置换算法在选择一页淘汰时,只需检查页的访问位,如果是0,就选择将该页换出;若为1,则重新将它置0,暂不换出,而给该页第二次驻留内存的机会,再按照FIFO算法检查下一个页面。当检查到队列中的最后一个页面时,若其访问位仍为1,则再返回到队首去检查第一个页面。由于该算法是循环地检查各页面的使用情况,故称为Clock算法。因该算法只有一位访问位,只能用它表示该页是否已经使用过,而置换时是将未使用过的页面换出去,又称为最近未用算法NRU(Not recently used)。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏FreeBuf

破译优利德旗舰万用表UT181A通讯协议

UT181A是优利德门下旗舰级手持数字万用表,主打数据记录(Data Logging)功能,支持USB联机通讯。基本评测可以看我以前发的文章。前文说到,其官方或...

4178
来自专栏信安之路

ROP Emporium 挑战 WP

ROP Emporium 挑战是用来学习 ROP 技术的一系列挑战,本文就对于其中涉及的所有挑战记录一下 wirte up。

1090
来自专栏大数据文摘

维基百科中的数据科学:手把手教你用Python读懂全球最大百科全书

几年前谁能想到,匿名贡献者们的义务工作竟创造出前所未有的巨大在线知识库?维基百科不仅是你写大学论文时最好的信息渠道,也是一个极其丰富的数据源。

1613
来自专栏开发 & 算法杂谈

动态数据竞争验证方法(一)

动态数据竞争检测算法可以在不知道程序中是否存在数据竞争前提下执行,而动态数据竞争验证方法则是在知道程序中可能存在的数据竞争前提下,对这部分可疑的数据竞争进行验证...

2354
来自专栏java达人

如何编写一个简易网络爬虫

感谢小臣投稿 本文将简述网络爬虫及其工作流程,结合个人实践,简单介绍如何使用HttpClient、HtmlParser第三方jar工具包,编写一个简易的网络爬虫...

2297
来自专栏腾讯Bugly的专栏

Redex 初探与 Interdex:Andorid 冷启动优化

导语 早在去年10月份,facebook就发布了介绍redex的文章,这个据说可以直接对apk做处理,既提高启动性能,又可减少安装包的利器让安卓开发者们都心动不...

6066
来自专栏hotqin888的专栏

HydroCMS规范、图集查询系统设计

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/hotqin888/article/det...

1622
来自专栏铭毅天下

Elasticsearch常见的5个错误及解决策略

网罗Elasticsearch最佳实践,实际应用场景中常见错误要预知和避免,以最大化提升集群性能。

1792
来自专栏月色的自留地

AngularJS2+调用原有的js脚本(AngularJS脚本跟本地原有脚本之间的关系)

1826
来自专栏DevOps时代的专栏

你可能会忽略的 Git 提交规范

一直是 ESLint 的忠实用户,深知规范的重要性。然而,在新项目交接中,我被 Git Commit 规范逼疯了。才意识到自己的疏忽,于是便有了一探究竟的想法。

1042

扫码关注云+社区

领取腾讯云代金券