页置换算法FIFO、LRU、OPT
2024-10-02 19:02:43
页置换算法FIFO、LRU、OPT
为什么需要页置换
在地址映射过程中，若在页面中发现所要访问的页面不再内存中，则产生缺页中断。当发生缺页中断时操作系统必须在内存选择一个页面将其移出内存，以便为即将调入的页面让出空间。而用来选择淘汰哪一页的规则叫做页面置换算法
实力（实例）
考虑下述页面走向：
1，2，3，4，2，1，5，6，2，1，2，3，7，6，3，2，1，2，3，6
当内存块数量分别为3时，试问FIFO、LRU、OPT这三种置换算法的缺页次数各是多少?
假设：缺页定义为所有内存块最初都是空的，所以第一次用到的页面都产生一次缺页。
当内存块数量为3时：
1、FIFO
发生缺页中断的次数为16。
在FIFO算法中，先进入内存的页面被先换出。当页6要调入时，内存的状态为4、1、5，考查页6之前调入的页面，分别为5、1、2、4，可见4为最先进入内存的，本次应换出，然后把页6调入内存。
2、LRU
发生缺页中断的次数为15。
在LRU算法中，最近最少使用的页面被先换出。当页6要调入时，内存的状态为5、2、1，考查页6之前调入的页面，分别为5、1、2，可见2为最近一段时间内使用最少的，本次应换出，然后把页6调入内存。
3、OPT
发生缺页中断的次数为11。
在OPT算法中，在最远的将来才被访问的页面被先换出。当页6要调入时，内存的状态为1、2、5，考查页6后面要调入的页面，分别为2、1、2、…，可见5为最近一段时间内使用最少的，本次应换出，然后把页6调入内存。
总结
- LRU算法：平均命中率最高算法，选择近期最少访问的页作为被替换页。 无Belady异常
- FIFO算法：是一个实现起来比较简单的页面置换算法，其基本原则是“选择最早进入主存的页面淘汰”，理由是最早进入的页面，其不再使用的可能性比最近调入的页面要大。有Belady异常
- OPT算法：根据未来实际使用情况将未来的近期里不用的页替换出去。这种算法是用来评价期它替 换算法好坏的标准。不可能实现。所选择的被淘汰页面将是以后永不使用的，或者是在最长时间内不再被访问的页面，这样可以保证获得最低的缺页率。无Belady异常
最新文章
- TB6612FNG电机驱动模块的简单使用
- c++ 调用模板函数时加template什么意思？
- 发布以NLog作为日记工具的ASP.NET站点到IIS注意事项
- OneProxy的功能与限制
- 10688 XYM-AC之路
- Linux学习笔记----（2）
- BASH 进阶（转载防丢）
- UVA - 208 Firetruck（消防车）（并查集+回溯）
- gridView 单元格绑定不同控件方法
- PHP数据库45道题整理~~~啦啦啦
- Java命令模式以及来自lambda的优化
- 去掉xcode编译warning：ld: warning: directory not found for option '-L
- 聊聊LightProbe原理实现以及对LightProbe数据的修改
- phpstudy 产生You don't have permission to access / on this server.解决
- django2+uwsgi+nginx上线部署到服务器Ubuntu16.04（最新最详细版）
- 重新设计导出API
- LeetCode OJ 102. Binary Tree Level Order Traversal
- 目录文件管理及vim
- python 字符串 列表 字典 常用方法
- Oracle_SQL(6) 单行函数