当前位置: 首页 > news >正文

页面置换算法

页面置换算法

在进程运行过程中,若需要访问的物理块不在内存中,就需要通过一定的方式来将页面载入内存,而此时内存很可能已无空闲空间,因此就需要一定的算法来选择内存中要被置换的页面,这种算法就被称为页面置换算法。页面置换算法的好坏,将直接影响系统的性能。

页面的换入、换出需要磁盘I/O,会有较大的开销,因此好的页面置换算法应该追求更少的缺页率。

下面介绍几种常用的页面置换算法。

  • 最佳置换算法(OPT)
  • 先入先出置换算法(FIFO)
  • 最近最久未使用置换算法(LRU)
  • 时钟置换算法(CLOCK)
  • 改进型的时钟置换算法

1.最佳置换算法(OPT)

该算法是一种理想化的算法,具有非常好的性能,但是由于目前无法预知未来,因此难以实现。

该算法选择淘汰的页面是:未来永远不会再使用的页面 or 未来最长时间不再被访问的页面。该算法保证了可以获得最低缺页率,但无法预知未来页面的使用情况,因此目前无法实现,但通常用来评价其他算法。

例:假定系统为某进程分配了三个物理块,并考虑有以下的页面号引用串:
7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1

进程运行时,先将 7,0,1 三个页面装入内存。以后,当进程要访问页面 2 时,将会产生缺页中断。此时 OS 根据最佳置换算法,将选择页面 7 予以淘汰。这是因为页面 0 将作为第 5 个被访问的页面,页面 1 是第 14 个被访问的页面,而页面 7 则要在第 18 次页面访问时才需调入。下次访问页面 0 时,因它已在内存而不必产生缺页中断。当进程访问页面 3时,又将引起页面 1 被淘汰;因为,它在现有的 1,2,0 三个页面中,将是以后最晚才被访问的。下图给出了采用最佳置换算法时的置换图。由图可看出,采用最佳置换算法发生了 6 次页面置换。

image-20230218001046465

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

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

例:假设系统为某进程分配了三个内存块,并考虑到有以下页面号引用串:3,2,1,0,3,2,4,3,2,1,0,4

当进程第一次访问页面0 时,将把第 3 页换出,因为它是最先被调入内存的;在第一次访问页面 3 时,又将把第 2 页换出, 因为它在现有的 2, 1, 0 三个页面中是最老的页。 由下图可以看出,利用 FIFO 算法时进行了 6 次页面置换,9次缺页中断。

image-20230218001501017

3.最近最久未使用算法(LRU)

最近最久未使用置换算法(LRU):每次淘汰的页面是最近最久未使用的页面实现方法:赋予每个页面对应的页表项中,用访问字段记录该页面自上次被访问以来所经历的时间t。当需要淘汰一个页面时,选择现有页面中t值最大的,即最近最久未使用的页面。该算法的实现需要专门的

image-20230218001647168

例:假设系统为某进程分配了四个内存块,并考虑到有以下页面号引用串:1,8,1,7,8,2,7,2,1,8,3,8,2,1,3,1,7,1,3,7

在手动做题时,若需要淘汰页面,可以逆向检查此时在内存中的几个页面号。在逆向扫image-20230218001828648

4.时钟置换算法(CLOCK)

时钟置换算法是一种性能和开销较均衡的算法,又称CLOCK算法,或最近未用算法(NRU)
简单的CLOCK算法实现方法:为每个页面设置一个访问位(访问位为1,表示最近访问过;访问位为0,表示最近没访问过),再将内存中的页面都通过链接指针链接成一个循环队列。当某页被访问时,其访问位置为1。当需要淘汰一个页面时,只需检查页的访问位。如果是0,就选择该页换出;如果是1,则将它置为0,暂不换出,继续检查下一个页面,若第一轮扫描中所有页面都是1,则将这些页面的访问位依次置为0后,再进行第二轮扫描(第二轮扫描中一定会有访问位为0的页面,因此简单的CLOCK算法选择一个淘汰页面最多会经过两轮扫描)。

image-20230218001647168

5.改进型的时钟置换算法

简单的时钟置换算法仅考虑到一个页面最近是否被访问过。事实上,如果被淘汰的页面没有被修改过,就不需要执行I/O操作写回外存。只有被淘汰的页面被修改过时,才需要写回外存。

因此,除了考虑一个页面最近有没有被访问过之外,操作系统还应考虑页面有没有被修改过。在其他条件都相同时,应优先淘汰没有修改过的页面,避免I/O操作。这就是改进型的时钟置换算法的思想。修改位=0,表示页面没有被修改过;修改位=1,表示页面被修改过。
为方便讨论,用(访问位,修改位)的形式表示各页面状态。如(1,1)表示一个页面近期被访问过,且被修改过。

算法规则: 将所有可能被置换的页面排成一个循环队列
第一轮:从当前位置开始扫描到第一个(0,0)的帧用于替换。本轮扫描不修改任何标志位
第二轮:若第一轮扫描失败,则重新扫描,查找第一个(0,1)的帧用于替换。本轮将所有扫描过的帧访问位设为0
第三轮:若第二轮扫描失败,则重新扫描,查找第一个(0,0)的帧用于替换。本轮扫描不修改任何标志位
第四轮:若第三轮扫描失败,则重新扫描,查找第一个(0,1)的帧用于替换。
由于第二轮已将所有帧的访问位设为0,因此经过第三轮、第四轮扫描一定会有一个帧被选中,因此改进型CLOCK置换算法选择一个淘汰页面最多会进行四轮扫描。

相关文章:

页面置换算法

页面置换算法 在进程运行过程中,若需要访问的物理块不在内存中,就需要通过一定的方式来将页面载入内存,而此时内存很可能已无空闲空间,因此就需要一定的算法来选择内存中要被置换的页面,这种算法就被称为页面置换算法…...

算法导论【在线算法】—The Ski-Rental Problem、The Lost Cow Problem、The Secretary Problem

算法导论【在线算法】The Ski-Rental Problem问题描述在线算法证明The Lost Cow Problem问题描述在线算法类似问题—寻宝藏The Secretary Problem问题描述在线算法The Best Possible kThe Ski-Rental Problem 问题描述 假设你正在上滑雪课。每节课结束后,你决定&a…...

linux 下怎样给pdf 文件加书签

linux 下怎样给pdf 文件加书签 对于没有书签的pdf文件,怎样给pdf加标签呢? 以方便阅读. 以前总是要借助windows下pdf 工具, 叫什么来者? 忘了 记得是编辑一个用tab表示目录级别的文本文件, 有一种直观的感觉,大目录下嵌套着小目录 ..., 然后导入到文件中 linux 下有没有这种…...

[软件工程导论(第六版)]第2章 可行性研究(课后习题详解)

文章目录1. 在软件开发的早期阶段为什么要进行可行性研究?应该从哪些方面研究目标系统的可行性?2. 为方便储户,某银行拟开发计算机储蓄系统。储户填写的存款单或取款单由业务员输入系统,如果是存款,系统记录存款人姓名…...

[软件工程导论(第六版)]第3章 需求分析(课后习题详解)

文章目录1. 为什么要进行需求分析?通常对软件系统有哪些需求?2. 怎样与用户有效地沟通以获取用户的真实需求?3. 银行计算机储蓄系统的工作过程大致如下:储户填写的存款单或取款单由业务员输入系统,如果是存款则系统记录…...

基于分布鲁棒联合机会约束的能源和储备调度(Matlab代码实现)

👨‍🎓个人主页:研学社的博客 💥💥💞💞欢迎来到本博客❤️❤️💥💥 🏆博主优势:🌞🌞🌞博客内容尽量做到思维缜…...

ETL和数据建模

一、什么是ETL ETL是数据抽取(Extract)、转换(Transform)、加载(Load )的简写,它是将OLTP系统中的数据经过抽取,并将不同数据源的数据进行转换、整合,得出一致性的数据&…...

ccc-pytorch-回归问题(1)

文章目录1.简单回归实战:2.手写数据识别1.简单回归实战: 用 线性回归拟合二维平面中的100个点 公式:ywxbywxbywxb 损失函数:∑(yreally−y)2\sum(y_{really}-y)^2∑(yreally​−y)2 迭代方法:梯度下降法,…...

【JAVA八股文】框架相关

框架相关1. Spring refresh 流程2. Spring bean 生命周期3. Spring bean 循环依赖解决 set 循环依赖的原理4. Spring 事务失效5. Spring MVC 执行流程6. Spring 注解7. SpringBoot 自动配置原理8. Spring 中的设计模式1. Spring refresh 流程 Spring refresh 概述 refresh 是…...

二叉树的相关列题!!

对于二叉树,很难,很难!笔者也是感觉很难!虽然能听懂课程,但是,对于大部分的练习题并不能做出来!所以感觉很尴尬!!因此,笔者经过先前的那篇博客,已…...

Java设计模式 - 原型模式

简介 原型模式(Prototype Pattern)是用于创建重复的对象,同时又能保证性能。这种类型的设计模式属于创建型模式,它提供了一种创建对象的最佳方式。 这种模式是实现了一个原型接口,该接口用于创建当前对象的克隆。当直…...

深度学习中的 “Hello World“

Here’s an interesting fact—Each month, there are 186.000 Google searches for the keyword “deep learning.” 大家好✨,这里是bio🦖。每月有超18万的人使用谷歌搜索深度学习这一关键词,是什么让人们对深度学习如此感兴趣?接下来请跟随我来揭开深度学习的神秘面纱。…...

购买WMS系统前,有搞清楚与ERP仓库模块的区别吗

经常有朋友在后台询问我们关于WMS系统的问题,他们自己也有ERP系统,但是总觉得好像还差了点什么,不知道是什么。今天,我想通过本文,来向您简要地阐述ERP与WMS系统在仓储管理上的不同之处。 ERP仓库是以财务为导向的&…...

一文吃透 Spring 中的IOC和DI

✅作者简介:2022年博客新星 第八。热爱国学的Java后端开发者,修心和技术同步精进。 🍎个人主页:Java Fans的博客 🍊个人信条:不迁怒,不贰过。小知识,大智慧。 💞当前专栏…...

分布式任务处理:XXL-JOB分布式任务调度框架

文章目录1.业务场景与任务调度2.任务调度的基本实现2.1 多线程方式实现2.2 Timer方式实现2.3 ScheduledExecutor方式实现2.4 第三方Quartz方式实现3.分布式任务调度4.XXL-JOB介绍5.搭建XXL-JOB —— 调度中心5.1 下载与查看XXL-JOB5.2 创建数据库表5.3 修改默认的配置信息5.4 启…...

【源码解析】Ribbon和Feign实现不同服务不同的配置

Ribbon服务实现不同服务,不同配置是通过RibbonClient和RibbonClients两个注解来实现的。RibbonClient注册的某个Client配置类。RibbonClients注册的全局默认配置类。 Feign实现不同服务,不同配置,是根据FeignClient来获取自定义的配置。 示…...

【webpack5】一些常见优化配置及原理介绍(二)

这里写目录标题介绍sourcemap定位报错热模块替换(或热替换,HMR)oneOf精准解析指定或排除编译开启缓存多进程打包移除未引用代码配置babel,减小代码体积代码分割(Code Split)介绍预获取/预加载(prefetch/pre…...

力扣sql简单篇练习(十九)

力扣sql简单篇练习(十九) 1 查询结果的质量和占比 1.1 题目内容 1.1.1 基本题目信息 1.1.2 示例输入输出 1.2 示例sql语句 # 用count是不会统计为null的数据的 SELECT query_name,ROUND(AVG(rating/position),2) quality,ROUND(count(IF(rating<3,rating,null))/count(r…...

线段树c++

前言 在谈论到种种算法知识与数据结构的时候,线段树无疑总是与“简单”和“平常”联系起来的。而这些特征意味着,线段树作为一种常用的数据结构,有常用性,基础性和易用性等诸多特点。因此,今天我来讲一讲关于线段树的话题。 定义 首先,线段树是一棵“树”,而且是一棵…...

HTML+CSS+JavaScript学习笔记~ 从入门到精通!

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录前言一、HTML1. 什么是HTML&#xff1f;一个完整的页面&#xff1a;<!DOCTYPE> 声明中文编码2.HTML基础①标签头部元素标题段落注释水平线文本格式化②属性3.H…...

LeetCode 430. 扁平化多级双向链表

原题链接 难度&#xff1a;middle\color{orange}{middle}middle 题目描述 你会得到一个双链表&#xff0c;其中包含的节点有一个下一个指针、一个前一个指针和一个额外的 子指针 。这个子指针可能指向一个单独的双向链表&#xff0c;也包含这些特殊的节点。这些子列表可以有一…...

2.5|iot|第1章嵌入式系统概论|操作系统概述|嵌入式操作系统

目录 第1章&#xff1a; 嵌入式系统概论 1.嵌入式系统发展史 2.嵌入式系统定义* 3.嵌入式系统特点* 4.嵌入式处理器的特点 5.嵌入式处理分类 6.嵌入式系统的应用领域及嵌入式系统的发展趋势 第8章&#xff1a;Linux内核配置 1.内核概述 2.内核代码结构 第1章&#xf…...

一文教会你使用ChatGPT画图

引言 当今,ChatGPT在各行各业都有着广泛的应用,其自然语言处理技术也日益成熟。ChatGPT是一种被广泛使用的技术,除了能够生成文本,ChatGPT还可以用于绘图,这为绘图技术的学习和应用带来了新的可能性。本文将介绍如何利用ChatGPT轻松绘制各种形状,为对绘图技术感兴趣的读…...

Java资料分享

随着Java开发的薪资越来越高&#xff0c;越来越多人开始学习 Java 。在众多编程语言中&#xff0c;Java学习难度还是偏高的&#xff0c;逻辑性也比较强&#xff0c;但是为什么还有那么多人要学Java呢&#xff1f;Java语言是目前流行的互联网等企业的开发语言&#xff0c;是市面…...

yum/vim工具的使用

yum 我们生活在互联网发达的时代&#xff0c;手机电脑也成为了我们生活的必须品&#xff0c;在你的脑海中是否有着这样的记忆碎片&#xff0c;在一个明媚的早上你下定决心准备发奋学习&#xff0c;“卸载”了你手机上的所有娱乐软件&#xff0c;一心向学&#xff01;可是到了下…...

内网渗透(三十九)之横向移动篇-pass the ticket 票据传递攻击(PTT)横向攻击

系列文章第一章节之基础知识篇 内网渗透(一)之基础知识-内网渗透介绍和概述 内网渗透(二)之基础知识-工作组介绍 内网渗透(三)之基础知识-域环境的介绍和优点 内网渗透(四)之基础知识-搭建域环境 内网渗透(五)之基础知识-Active Directory活动目录介绍和使用 内网渗透(六)之基…...

Unity性能优化之纹理格式终极篇

知识早班车&#xff1a;1、当n大于1时&#xff0c;2的n次幂一定能被4整除&#xff1b;证明&#xff1a;2^n 2^2*2^(n-1) 4*2^(n-1)2、4的倍数不一定都是2的次幂&#xff1b;证明&#xff1a;4*3 12&#xff1b;12不是2的次幂3、Pixel&#xff08;像素&#xff09;是组成图片…...

【Spark分布式内存计算框架——Spark SQL】9. Dataset(下)RDD、DF与DS转换与面试题

5.3 RDD、DF与DS转换 实际项目开发中&#xff0c;常常需要对RDD、DataFrame及Dataset之间相互转换&#xff0c;其中要点就是Schema约束结构信息。 1&#xff09;、RDD转换DataFrame或者Dataset 转换DataFrame时&#xff0c;定义Schema信息&#xff0c;两种方式转换为Dataset时…...

Windows 环境下,cmake工程导入OpenCV库

目录 1、下载 OpenCV 库 2、配置环境变量 3、CmakeLists.txt 配置 1、下载 OpenCV 库 OpenCV官方下载地址&#xff1a;download | OpenCV 4.6.0 下载完毕后解压&#xff0c;便可以得到下面的文件 2、配置环境变量 我们需要添加两个环境变量&#xff0c;一个是 OpenCVConfi…...

微服务架构设计模式-(16)重构

绞杀者应用程序 由微服务组成的应用程序&#xff0c;将新功能作为服务&#xff0c;并逐步从单体应用中提取服务来实现。好处 尽早并频繁的体现价值 快速开发交付&#xff0c;使用 与之相对的是“一步到位”重构&#xff0c;这时间长&#xff0c;且期间有新的功能加入&#xff…...

wordpress+HTML5游戏/重庆 seo

1.先从微软网站下载补丁. 下载地址1为&#xff1a;http://download.microsoft.com/download/8/0/7/8071514d-9370-45c3-8af1-4ff09a70e59d/VS80sp1-KB926604-X86-CHS.exe&#xff08;中文版&#xff09;大约为430M。2.作好打VS2005 SP1补丁之前的设置. 第一步&#xff1a;…...

个人网站建设的流程/游戏推广员骗局

Linux 网络设备驱动程序的体系结构 图片说明如下&#xff1a;网络协议接口层 网络协议接口层向网络层协议提供统一的数据包收发接口&#xff0c;不论上层协议是ARP还是IP,都通过 dev_queue_xmit() 函数发送数据&#xff0c; 并通过 netif_rx() 函数接受数据&#xff0c;这一层的…...

手机app制作网站用什么软件/微信营销方法

一:首先nuget安装 IdentityModel二:客户端验证模式代码 1.注册客户端获取token访问api static async Task Main(string[] args) {//如果要授权var client = new HttpClient();...

建筑网站设计/sem优化师是什么意思

面包板是创客硬件布置电路非常常用的器件&#xff0c;它可以看做是一个很大的电路板&#xff0c;只不过这个电路板不需要焊接&#xff0c;只需要将元器件插在面包板上就可以了&#xff0c;非常方便&#xff0c;也降低了硬件设计的难度&#xff1b;至于为什么叫面包板&#xff0…...

iis wordpress index.php/上海aso苹果关键词优化

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…...

wdcp 快速迁移网站/营销平台建设

在用五笔加加Plus打字时&#xff0c;打了一会儿切换个输入法&#xff0c;再换回来时就只能输入字母了。转载于:https://www.cnblogs.com/wuchang/archive/2004/08/20/35092.html...