页面置换算法(计算缺页次数)
2021/4/14 22:55:20
本文主要是介绍页面置换算法(计算缺页次数),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
目录
- 最近最少使用置换算法(LRU)
- 最佳页面置换算法(OPT)
- 先进先出页面置换算法(FIFO)
最近最少使用置换算法(LRU)
选择最近最久未使用的页面予以淘汰
页面访问序列 | 7 | 0 | 1 | 2 | 0 | 3 | 0 | 4 | 2 | 3 | 0 | 3 | 2 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
页框1 | 7 | 7 | 7 | ||||||||||
页框2 | 0 | 0 | |||||||||||
页框3 | 1 | ||||||||||||
是否缺页 | √ | √ | √ |
当访问页面号为2的页面时,应该置换哪个页面?我们可以通过判断从当前访问页面向左哪个页面(页框中的页面)距离当前访问页面最远来进行置换,如图:
1距离当前页面0个间隔,0距离当前页面1个间隔,7距离当前页面2个间隔,由此可知,7距离当前访问页面最远,所以替换7,接下来其他的置换也是相同的原理,全部置换完成后如下图:
页面访问序列 | 7 | 0 | 1 | 2 | 0 | 3 | 0 | 4 | 2 | 3 | 0 | 3 | 2 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
页框1 | 7 | 7 | 7 | 2 | 2 | 2 | 2 | 4 | 4 | 4 | 0 | 0 | 0 |
页框2 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 3 | 3 | 3 | 3 | |
页框3 | 1 | 1 | 1 | 3 | 3 | 3 | 2 | 2 | 2 | 2 | 2 | ||
是否缺页 | √ | √ | √ | √ | × | √ | × | √ | √ | √ | √ | × | × |
采用最近最少使用页面置换算法(LRU),缺页次数为9
最佳页面置换算法(OPT)
将以后都不再访问或者很长时间内不再访问的页面调出
页面访问序列 | 4 | 2 | 9 | 6 | 2 | 6 | 9 | 4 | 9 | 2 |
---|---|---|---|---|---|---|---|---|---|---|
页框1 | 4 | 4 | 4 | |||||||
页框2 | 2 | 2 | ||||||||
页框3 | 9 | |||||||||
是否缺页 | √ | √ | √ |
当访问页面号为6的页面时,应该置换哪个页面?和最近最少使用页面置换算法相反,我们可以通过判断从当前访问页面向右哪个页面(页框中的页面)距离当前访问页面最远来进行置换,如图:
2距离当前页面0个间隔,9距离当前页面2个间隔,4距离当前页面3个间隔,由此可知,4距离当前访问页面最远,所以置换4,接下来其他的置换也是相同的原理,全部置换完成后如下图:
页面访问序列 | 4 | 2 | 9 | 6 | 2 | 6 | 9 | 4 | 9 | 2 |
---|---|---|---|---|---|---|---|---|---|---|
页框1 | 4 | 4 | 4 | 6 | 6 | 6 | 6 | 4 | 4 | 4 |
页框2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | |
页框3 | 9 | 9 | 9 | 9 | 9 | 9 | 9 | 9 | ||
是否缺页 | √ | √ | √ | √ | × | × | × | √ | × | × |
采用最佳页面置换算法(OPT),缺页次数为5
先进先出页面置换算法(FIFO)
每次置换最先调入内存的页面,即将内存中等待时间最长的页面进行置换
页面访问序列 | 7 | 0 | 1 | 2 | 0 | 3 | 0 | 4 | 2 | 3 | 0 | 3 | 2 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
页框1 | 7 | 7 | 7 | ||||||||||
页框2 | 0 | 0 | |||||||||||
页框3 | 1 | ||||||||||||
是否缺页 | √ | √ | √ |
当访问页面号为2的页面时,应该置换哪个页面?
方法一:
可以通过判断哪个页面(页框中的页面)最先调入内存,置换最先调入内存的页面,如图:
因为序号为7的页面最先最先调入内存,所以置换序号为7的页面
方法二:
也可以通过下面这种方式:通过判断哪个页面(页框中的页面)连续的次数最多,置换连续次数最多的页面,如图:
序号为7的页面连续的次数最多,所以置换序号为7的页面
接下来其他的置换也是相同的原理,全部置换完成后如下图:
页面访问序列 | 7 | 0 | 1 | 2 | 0 | 3 | 0 | 4 | 2 | 3 | 0 | 3 | 2 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
页框1 | 7 | 7 | 7 | 2 | 2 | 2 | 2 | 4 | 4 | 4 | 0 | 0 | 0 |
页框2 | 0 | 0 | 0 | 0 | 3 | 3 | 3 | 2 | 2 | 2 | 2 | 2 | |
页框3 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 3 | 3 | 3 | 3 | ||
是否缺页 | √ | √ | √ | √ | × | √ | √ | √ | √ | √ | √ | × | × |
采用先进先出页面置换算法(FIFO),缺页次数为10
有不对的地方还请指出呀,不胜感激 [嘻嘻]
这篇关于页面置换算法(计算缺页次数)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-04TiDB 资源管控的对撞测试以及最佳实践架构
- 2024-07-03万字长文聊聊Web3的组成架构
- 2024-07-02springboot项目无法注册到nacos-icode9专业技术文章分享
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现