通过代码实例了解页面置换算法原理
作者:七月在野,八月在宇 发布时间:2024-01-24 21:26:23
页面置换算法:本质是为了让有限内存能满足无线进程。
先说明一下处理缺页错误的过程:
分页硬件在通过页表转换地址时会注意到无效位被设置,从而陷入操作系统,这种陷阱是因为操作系统未能将所需要的页面调入内存引起的。
处理缺页错误:
1、检查这个进程的内部表,确定该引用是否为有效的内存访问(可以理解为这个内存能被当前进程使用),如果无效那么直接终止进程;如果有效但是尚未调入页面,就将该页面调入内存。
2、然后从空闲帧链表上找到一个空闲帧。
3、调度磁盘将进程所需要的内存读入页帧中,
4、磁盘读取完成,修改页表,使空闲帧对应到该页号上。并且修改页表有效-无效位 为有效。
注意页表中的一些标志位:
修改位:如果有效为位1,表明被修改,那么替换页面时需要将内存写入磁盘中;如果为0,表明未被修改,那么使用页面替换算法直接释放
保护位:可以标记为只读,写。
有效-无效位:i:表示逻辑页号不对应物理页帧,为V表示有对应的物理页帧
页面替换算法:
FIFO:算法
操作系统总时替换出在内存中停留时间最久的页面,可以用一个指针来指向这个位置(开销很小,可以使用一个队列来实现,每次缺页时移出末尾的页面,再队列头添加新的页面,未发生缺页错误就不需要对队列进行操作)
LRU算法:操作系统总时替换在内存中最久没有使用的页面:我么可以使用链表来实现这个算法,表头表示的是最近被使用的页面,表尾表示最久没被使用的页面,每一次不管是否发生缺页,都需要对这个链表进行从新增删改查,来保证每一次的链表都是我们需要的(开销太大)
近似LRU算法:我们在页表中添加一个引用位clock,当clock为1时,不能移出,当clock为0时,表明可以移除
procedure t: {
指针p:指向当前的页面
p = 0;//指向初始位置
boolean :标志位clock
进程包含的所有页面组成的循环链表:linklist//当进程在运行时,链表存在,进程结束时,链表也消失
while(进程运行){
if(p.clock == 1){
p.clock = 0;
p++;//指针指向下一个
}
if(p.clock == 0){
删除p指向的页面并且在p处添加新的页面;
p.clock = 1;
p++;
}
}
}
近似LRU增强算法:将修改位和引用位合起来作为是否替换条件:当(修改位,引用位) = (0,0)时表明可以替换
procedure t: {
指针p:指向当前的页面
p = 0;//指向初始位置
boolean :标志位clock
boolean : 修改位m
进程包含的所有页面组成的循环链表:linklist//当进程在运行时,链表存在,进程结束时,链表也消失
while(进程运行){
if(p.(clock,m) == (0,0)){
删除p指向的页面并且在p处添加新的页面;
p.(clock,m) = (1,0);
p++;
}
if(p.(clock,m) == (0,1)){
p.(clock,m) = (0,0);
p++;
}
if(p.(clock,m) == (1,0)){
p.(clock,m) = (0,0);
p++;
}
if(p.(clock,m) == (1,1)){
p.(clock,m) = (0,1);
p++;
}
if(修改页面){
p.(clock,m) = (1,1);
p++
}
if(读页面){
p.(clock,m) = (1,0);
p++;
}
}
}
页面缓冲算法:操作做系统保留一个空闲帧池。
当发生缺页错误时,所需要的页面就读取空闲帧,并且将替换的牺牲帧放入缓冲池,在调页空闲时期将缓冲池中的牺牲帧中的内容写入(如果页表上的修改位为1)磁盘中(减少了操作系统的调页时直接访问磁盘的过程,提高了调页效率).
第二种方法:将牺牲帧中的内容写入磁盘,但是不释放帧中的内容,因为进程有可能调用之前的页,这样就将缓冲池中的帧直接写入内存,减少了(从磁盘读取数据的操作)。
以上均为局部页面置换算法,都是在单个进程内部进行的页面替换操作,但是操作系统在运行过程中不同的进程可以并行并发执行,这样对页面的替换就不会仅仅局限于单个进程中
下面我们学习全局置换算法:我们规定一个工作集和一个常驻集。工作集表明当前程序需要访问的Δ个页面,常驻集表明操作系统正在使用的页面。
工作集:WS(Δ,t) = {}工作集不断移动,操作系统替换出不在工作集中的页面
动态工作集页面替换算法:如下图,我们规定一个阈值windows size = 2,我们使用两次缺页中断的差值(表明两次中断之间有多少次没有中断)和阈值比较,如果比阈值大,那么将不再当前工作集的页面换出,并且重置工作集的大小,如果比阈值小,那么将缺的页换入工作集并且重置工作集的大小。
来源:https://www.cnblogs.com/guosai1500581464/p/13112045.html
猜你喜欢
- 在项目的根目录下建立一个.gitignore的文件(和.git文件同级).gitignore文件用记事本打开,输入如下内容:## Ignor
- 前言大家应该都有所了解,下面就简单介绍下Numpy,NumPy(Numerical Python)是一个用于科学计算第三方的Python包。
- 装饰器本质是一个接受参数为函数的函数。作用:为一个已经实现的方法添加额外的通用功能,比如日志记录、运行计时等。举例1.不带参数的装饰器,不用
- 在昨天关于substring的blog中有如下一段代码:也许你已经发现,在Python 3中其实有办法只用一行完成函数:>>&g
- 本文实例讲述了MySQL Union合并查询数据及表别名、字段别名用法。分享给大家供大家参考,具体如下:union关键字SELECT s_i
- 废话不多说了,直接给大家贴代码了。import urllibimport urllib2import cookielibdef getImg
- mysql 8.0.20 安装配置方法图文教程整理下,供大家参考。一、准备工作1、检查是否已经安装mysql当前计算机没有安装mysql。2
- 问题背景: 日常对Sql Server 2005关系数据库进行操作时,有时对数据库(如:Sharepoint网站配置数据库名Sharepoi
- 最近用layer ui上传文件遇到了一个问题,我想在上传文件之前把data-id传入后台,layer文档找了一下也没有找到类似的说明,经过一
- 目录1. python内置方法(read、readline、readlines)2. 内置模块(csv)3. 使用numpy库(loadtx
- 身份证号码的编排规则前1、2位数字表示:所在省份的代码;第3、4位数字表示:所在城市的代码;第5、6位数字表示:所在区县的代码;第7~14位
- 最好用的mysql密码忘记的解决方法 ,经过测试,如果不能成功一般是你的mysql运行的不正常解决办法: 在windows下:&n
- 使用 Beanstalkd 作为消息队列服务,然后结合 Python 的装饰器语法实现一个简单的异步任务处理工具.最终效果定义任务:from
- 本文主要介绍了django admin search_fields placeholder 管理后台添加搜索框提示文字,分享给大家,具体如下
- 首先看这下面的例子(鼠标移上去):<TABLE><TBODY><TR&g
- Object 类型的对象虽然有 toString 方法,但结果却是 [Object Object] 让人没法理解的字符。比如简单的对象:{n
- Python字符串介绍字符串是一系列字符。在 Python 中,引号内的任何内容都是字符串。您可以使用单引号或双引号。例如:message
- 在Python2.x中表示八进制的方式有两种:以'0'开头和以'0o'(字母o)开头: Pyth
- function getBytesLength(str){ var re=/[\x00-\xf
- 之前在懒懒分会上分享的一点关于border画小图的内容, 完整的ppt在这里.原理css盒模型一个盒子包括: margin+border+p