## 页面置换算法
页面的换入换出, 需要启动磁盘的IO 会有较大的开销 , 因此好的页面置换算法应该 ==追求更少的缺页率==
<img src="https://xingqiu-tuchuang-1256524210.cos.ap-shanghai.myqcloud.com/1082/image-20221222172809672.png" style="zoom:80%;" />
### 1.最佳置换算法 =>无法实现
最佳置换算法(OPT,Optimal): **每次选择淘汰的页面将是以后永不使用,或者在最长时间内不再被访问的页面**,这样可以保证最低的缺页率。
<u>最佳置换算法可以保证最低的缺页率</u>,但实际上,只有在进程执行的过程中才能知道接下来会访问到的是哪个页面。
<u>操作系统无法提前预判页面访问序列</u>。因此,**最佳置换算法是无法实现的**。
> 只有当 内存块全部占满并且出现了缺页中断 才会发生 页面置换
![](https://xingqiu-tuchuang-1256524210.cos.ap-shanghai.myqcloud.com/1082/image-20210809161659809.png)
### 2.先进先出置换算法-FIFO
先进先出置换算法(FIFO): **每次选择淘汰的页面是最早进入内存的页面**
实现方法:把调入内存的页面根据调入的先后顺序排成一个队列,需要换出页面时选择队头页面即可。队列的最大长度取决于系统为进程分配了多少个内存块。
![](https://xingqiu-tuchuang-1256524210.cos.ap-shanghai.myqcloud.com/1082/image-20210809161847953.png)
那么当我们增加了内存块的个数 :
![](https://xingqiu-tuchuang-1256524210.cos.ap-shanghai.myqcloud.com/1082/image-20221224141054903.png)
可以发现虽然我们增加了内存块的个数, 缺页中断的 发生次数反而增加了 , 这就是 Belady 异常
**Belady**异常:**当为进程分配的物理块数增大时,缺页次数不减反增的异常现象。**
**只有FIFO算法会产生Belady异常**。另外,FIFO算法虽然实现简单,但是该算法与进程实际运行时的规律不适应,因为先进入的页面也有可能最经常被访问。因此,**算法性能差。**
### 3.最近最久未使用算法-LRU
最近最久未使用置换算法(LRU,least recently used): **每次淘汰的页面是最近最久未使用的页面。**
实现方法:赋予每个页面对应的页表项中,<u>用访问字段记录该页面自上次被访问以来所经历的时间t</u>。
当需要淘汰一个页面时,选择现有页面中t值最大的,即最近最久未使用的页面。
![](https://xingqiu-tuchuang-1256524210.cos.ap-shanghai.myqcloud.com/1082/image-20210809162117351.png)
### 4.时钟置换算法-NRU
最佳置换算法性能最好,但**无法实现**;先进先出置换算法实现简单,**但算法性能差**;最近最久未使用置换算法性能好,是最接近OPT算法性能的,但是实现起来需要专门的硬件支持,**算法开销大**。
**<u>时钟置换算法**是一种性能和开销较均衡的算法,又称CLOCK算法,或最近未用算法(NRU,NotRecently Used)</u>
简单的CLOCK 算法实现方法:
为每个页面设置一个**访问位**,再将内存中的页面都通过链接指针链接成一个**循环队列**。
当某页被访问时,其访问位置为1。当需要淘汰一个页面时,只需检查页的访问位。
- 如果是0,就选择该页换出;
- 如果是1,则将它置为0,暂不换出,继续检查下一个页面,
若第一轮扫描中所有页面都是1,则将这些页面的访问位依次置为0后,再进行第二轮扫描(<u>第二轮扫描中一定会有访问位为0的页面</u>,**因此简单的CLOCK算法选择一个淘汰页面最多会经过两轮扫描)**
![](https://xingqiu-tuchuang-1256524210.cos.ap-shanghai.myqcloud.com/1082/image-20210809162337421.png)
### 5.改进型的时钟置换算法
<u>简单的时钟置换算法仅考虑到一个页面最近是否被访问过。</u>
事实上,==如果被淘汰的页面没有被修改过,就不需要执行I/o操作写回外存。只有被淘汰的页面被修改过时,才需要写回外存。==
因此,<u>除了考虑一个页面最近有没有被访问过之外,操作系统还应**考虑页面有没有被修改过**。</u>
在其他条件都相同时,应优先淘汰没有修改过的页面,避免I/o操作。这就是改进型的时钟置换算法的思想。修改位=0,表示页面没有被修改过;修改位=1,表示页面被修改过。
为方便讨论,用==(访问位,修改位)==的形式表示各页面状态。
- 如(1,1)表示一个页面近期被访问过,且被修改过。
**算法规则**: 将所有可能被置换的页面排成一个**循环队列**
第一轮:从当前位置开始扫描到第一个(0,0)的帧用于替换。<u>本轮扫描不修改任何标志位</u>
第二轮:若第一轮扫描失败,则重新扫描,查找第一个(0,1)的帧用于替换。本轮将所有扫描过的帧访问位设为0
第三轮:若第二轮扫描失败,则重新扫描,查找第一个(0,0)的帧用于替换。本轮扫描不修改任何标志位
第四轮:若第三轮扫描失败,则重新扫描,查找第一个(0,1)的帧用于替换。
由于第二轮已将所有帧的访问位设为0,因此经过第三轮、第四轮扫描一定会有一个帧被选中,因此**改进型CLOCK置换算法选择一个淘汰页面最多会进行四轮扫描**
![图示](https://xingqiu-tuchuang-1256524210.cos.ap-shanghai.myqcloud.com/1082/image-20210809162555604.png)
> 第一优先级:最近没访问,且没修改的页面
> 第二优先级:最近没访问,但修改过的页面
> 第三优先级:最近访问过,但没修改的页面
> 第四优先级:最近访问过,且修改过的页面
没有合适的资源?快使用搜索试试~ 我知道了~
温馨提示
【资源说明】 1、该资源内项目代码都是经过测试运行成功,功能ok的情况下才上传的,请放心下载使用! 2、本项目适合计算机相关专业(如计科、人工智能、通信工程、自动化、电子信息等)的在校学生、老师或者企业员工下载使用,也适合小白学习进阶,当然也可作为毕设项目、课程设计、作业、项目初期立项演示等。 3、如果基础还行,也可在此代码基础上进行修改,以实现其他功能。 基于多种语言实现操作系统算法_进程调度_页面置换_动态分区匹配_磁盘调度实现源码.zip 基于多种语言实现操作系统算法_进程调度_页面置换_动态分区匹配_磁盘调度实现源码.zip基于多种语言实现操作系统算法_进程调度_页面置换_动态分区匹配_磁盘调度实现源码.zip
资源推荐
资源详情
资源评论
收起资源包目录
基于多种语言实现操作系统算法_进程调度_页面置换_动态分区匹配_磁盘调度实现源码.zip (123个子文件)
MLFQ.cpp 8KB
RR.cpp 6KB
FCFS.cpp 6KB
SLF.cpp 5KB
PS.cpp 5KB
SRTF.cpp 5KB
SCAN.cpp 4KB
QF.cpp 4KB
BF.cpp 3KB
WF.cpp 3KB
SSTF.cpp 3KB
C-SCAN.cpp 3KB
FIFO.cpp 3KB
FF.cpp 2KB
LRU.cpp 2KB
FCFS.cpp 2KB
LFU.cpp 2KB
ClockSimple.cpp 2KB
ClockUpdate.cpp 2KB
LIFO.cpp 1KB
LRUExample.cpp 1KB
ClockSimpleExample.cpp 1KB
ClockUpdateExample.cpp 1KB
MLFQexample.cpp 1KB
LFUExample.cpp 1KB
SLFexample.cpp 578B
SRTFexample.cpp 304B
RRexample.cpp 229B
PSexample.cpp 227B
FIFOExample.cpp 193B
FCFSexample.cpp 189B
FCFS.go 2KB
main.go 1KB
lru.go 1KB
Process.go 1KB
main.go 495B
PCB.h 2KB
Mem.h 420B
CacheNode.h 409B
BFExample.java 7KB
QF.java 7KB
RandomTestUtil.java 6KB
WFExample.java 6KB
NRU.java 5KB
LFU.java 5KB
NF.java 5KB
HRRN.java 5KB
LRU.java 5KB
BF.java 5KB
MLFQ.java 5KB
NFExample.java 5KB
FF.java 5KB
FFExample.java 4KB
TestUtil.java 4KB
WF.java 4KB
Priority.java 4KB
QFExample.java 4KB
SCAN.java 3KB
FIFO.java 3KB
SJF.java 3KB
FCFS.java 3KB
AlgorithmUtil.java 3KB
Process.java 3KB
HRRNSample.java 3KB
LRUCache.java 3KB
MLFQSample.java 3KB
Process.java 3KB
FIFOExample.java 3KB
PrioritySample.java 3KB
LFUExample.java 3KB
LRUExample.java 2KB
NRUExample.java 2KB
SJFSample.java 2KB
SSTF.java 2KB
CSCAN.java 2KB
Example.java 1KB
DoubleLinkedList.java 1KB
DoubleList.java 1KB
FramePartitionNode.java 1KB
FCFSSample.java 1KB
FCFS.java 1KB
Frame.java 884B
Element.java 585B
LRUSample.java 560B
Node.java 550B
Constant.java 519B
TimeUtil.java 370B
DMConstant.java 305B
README.md 6KB
README.md 5KB
README.md 4KB
说明.md 4KB
README.md 3KB
README.md 3KB
go.mod 23B
go.mod 23B
PS.py 4KB
MLFQ.py 4KB
FirstFit.py 2KB
Sample.py 2KB
共 123 条
- 1
- 2
资源评论
Make程序设计
- 粉丝: 5636
- 资源: 3568
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- MyBatis 动态 SQL:灵活而强大的查询构建器.pdf
- com.accordion.prettyo.apk
- 毕业设计:基于SSM的mysql-ssm软件bug管理系统(源码 + 数据库 + 说明文档)
- MTSQL8.0.35windows(64bit)-mysql-installer-community-8.0.35.0
- 人工智能引领音乐创作新时代之Suno AI
- Public-bicycle-usage-forecast-master.zip
- 通道处理过程模拟:从理论到实践.pdf
- 数据库第七次作业E-R图第一题
- 大厂面试真题Java语法基础面试专题及答案
- IMG20240428211124.jpg
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功