《操作系统 - 清华大学》6 -3:局部页面置换算法:最近最久未使用算法 (LRU, Least Recently Used)

文章目录

  • 1. 最近最久未使用算法的工作原理
  • 2. 最近最久未使用算法示例
  • 3.LRU算法实现
    • 3.1 LRU的页面链表实现
    • 3.2 LRU的活动页面栈实现
    • 3.3 链表实现 VS 堆栈实现

1. 最近最久未使用算法的工作原理

在这里插入图片描述最近最久未使用页面置换算法,简称 LRU, 算法思路:当缺页中断产生之后,要替换哪个页?选择最久未被使用的页,要置换这个页。

最久未被使用和前面的 FIFO 算法里面最长驻留时间不是一个概念。最长驻留时间是存在时间很久,但是它可能最近被访问过,但是最久未被使用页是说它可能很长时间程序都没有读或写页的内容,这叫最久未被使用,所以它和 FIFO 算法的依据是不一样的,它的页面特征是不一样。

本质上来说它是对最优置换算法的近似

它是根据过去来推测应该把哪个页给换出去,而不是根据未来。最优置换算法替换是将来最远未被使用页,将来很久都没被使用的页面,那个页面会被淘汰出去,而这个是过去很长时间都没访问的页,这两个正好在两头。
~  
LRU 算法其实是根据历史来推测未来,最优置换算法是根据未来推测未来,但是在不知道未来情况下,那根据过去的访问情况来推测将来访问情况,也是一种合理的选择。
~  
那这个合理性是基于程序的局部性原理,程序运行过程中具有一定局部性特征,时间局部性和空间局部性,在最近一段时间之内,程序访问的代码和数据,在未来一段时间也还有很大的概率还会持续访问,还会被频繁访问,这是局部性,有了局部性之后,LRU 的依据就是合理了。
~  
既然有这么一个特征,那么如果说在当前这段时间之内,某些页没有被访问,那也意味着接下来一小段时间它也很可能没被访问,这是局部性原理的反推,基于这个特征,如果程序是具有局部性特征的程序,LRU算法其实会比较好地预测未来发生情况。

2. 最近最久未使用算法示例

在这里插入图片描述

还是刚才访问序列,如果采取 LRU 算法会产生多少次访问中断,还是同样的一幅图:

  1. 前四次 1 2 3 4 访问序列是 c a d b,刚才已经说这几个页都在物理内存中,所以不会产生缺页中断
  2. 第五次时,依据 LRU 算法,把最久未被使用页面给替换出去, a 页面访问时刻是2 ,b 是 4 时刻,c 是1时刻访问,d 是 3 时刻,很显然 c 是最久未被访问页,所以当第 5 个时刻访问 e 时候,需要去替换最久没有访问页是 c。
  3. 访问 b, b 还在物理页中,所以不会产生中断。那么 6 7 8 这三个时刻访问页序列,由于 a 和 b 都还在物理内存中,所以不会产生中断
  4. 第 9 个时刻要访问 c 了,那么应该换出哪个页?a 是在第7个时刻访问,b 是在第8个时刻访问,都是离这个 c 很近,但不代表很久,d 是在第3时刻访问,而 e 是在第5时刻访问,那么很明显在这里面就是 d 页面是最久未被访问页面,所以说会把 d 给换出去,然后把 c 换进来,产生第二次缺页中断
  5. 接下要访问 d,刚把 d 换出去,这时候应该换哪页?当前最久未被访页是 e,所以说要把 e 给换出去

采取 LRU 算法之后产生了三次中断,比 FIFO 算法要少一些。

3.LRU算法实现

LRU算法找的是最久未被访问页,如果要有效实现算法,它需要记录每个页使用时间的先后顺序。主要采取某种方法记录起来,记录时间顺序的执行开销是比较大的,目前有两种可能的实现方法

3.1 LRU的页面链表实现

在这里插入图片描述
第一个是用链表来实现,如果说系统里面能够维护一个当前访问的页面链表,那么最近刚刚访问的页面作为首节点,放在链表的头,而最久未被使用页面放在链表的尾。

当运行程序访问内存的时候,需要看看这个内存对应的这个页是否在这个链表里面。如果在这链表里面,需要把这个页从某一位置替到链表头上,因为它当前正在被访问,代表最近访问页。如果没有的话,就把这个页插入链表中。

如果产生一次缺页中断,需要替换链表中的某一页,很明显,因为链表会把最近访问页靠近链表头,只有最久访问页放在链表尾,所以直接从链表尾把这个页给摘出来,就可以作为要替换出去的页,这是一种方法。

3.2 LRU的活动页面栈实现

在这里插入图片描述
第二个办法用堆栈,设置一个当前访问页的堆栈,当访问某个页时候就把这个页先压入栈顶,然后再考察栈内是否有跟这个页相同的页号,如果有,把这个页抽出来不要了,因为已经把页压到里面去了,但它需要去查找在这个栈中是否已经存在这个页号,如果存在踢出去,这个查找过程开销比较大。和刚才说的链表查找过程是一样的,都需要去查找在链表和堆栈中这个页是否存在。

如果又产生缺页中断,需要淘汰一页,那淘汰哪个?就要选择堆栈的栈底,就类似前面链表的尾部页面,因为这个页面代表它最久未被访问的页面。

刚刚那个图做例子,如果用所谓堆栈的办法来实现,就这么操作过程:
在这里插入图片描述
底下有 LRU 配置的 stack,就是分配一个堆栈,当每一次访页,就把这个页号压在里面去,同时还要看看这里面是否存在相同的页号,如果有把它剔出去。

  1. 当走到了第 5 时刻,访问 e ,产生缺页异常,产生缺页中断之后,需要把栈的尾部给替换出去,这时候就把 e 给压栈里
  2. 第 6 时刻,把 b 放栈里面去,但由于 b 已经在页帧中,会把 b 从栈中去掉,使得 b 从栈的中间位置调到栈顶。
  3. 同理,第 7 时刻访问 a,会把 a 从栈的某一位置调到栈顶

这就是 LRU 算法基于栈来实现的大致处理过程。可以看到在这里面每次访问都需要去查找这个栈,那如果说这个内存中物理页帧比较多的情况,那其实查找很费时,所以整个过程实现开销是大。

3.3 链表实现 VS 堆栈实现

那这是两种实现方式,每一次内存访问某一页的时候,可能都需要去做一次查找,看这个页是否在链表中,或者说是否在堆栈中,可以做一些相关操作。那这个过程其实开销挺大。

LRU 算法表面上看起来效果不错,但是如果要把它放到操作系统里面去,需要考虑代价,它的结果虽然不错,如果代价太大,它不是一个合适的实现方法。

操作系统设计讲究的第一要高效,第二要简洁,既要达到好的效果,还要实现得快捷。如果说为了实现好效果,要花很大的代价,那整个系统性能就受到很大影响,操作系统占时间越多,也意味着留给应用程序时间越少,所以说希望操作系统用最少时间获得最佳效果,它需要一个 balance,所以 balance 情况下 LRU 算法的实现开销很大,所以它也不是一个有效的方法。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/482412.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

数据集-目标检测系列- 海边漫步锻炼人检测数据集 person >> DataBall

数据集-目标检测系列- 海边漫步锻炼人检测数据集 person >> DataBall DataBall 助力快速掌握数据集的信息和使用方式,会员享有 百种数据集,持续增加中。 需要更多数据资源和技术解决方案,知识星球: “DataBall - X 数据球…

【赵渝强老师】PostgreSQL的段、区和块

PostgreSQL的逻辑存储结构主要是指数据库集群、数据库、表空间、段、区、块等;同时PostgreSQL的逻辑存储结构也包括数据库中的各种数据库对象,如:表、索引、视图等等。所有数据库对象都有各自的对象标识符oid(object identifiers&…

【YOLO系列复现】二、基于YOLOv6的目标检测:YOLOv6训练自己的数据集(史诗级详细教程)

官方模型:YOLOv6/README_cn.md at main meituan/YOLOv6 目录 1、模型和环境准备 1.1 模型下载 1.2 依赖环境安装 1.3 权重文件下载 1.4 环境测试 2、配置文件和数据集准备 2.1 准备数据集 2.2 配置文件准备 2.3 BUG修改 3、模型训练 3.1 模型训练 3.2 …

Flink常见面试题

1、Flink 的四大特征(基石) 2、Flink 中都有哪些 Source,哪些 Sink,哪些算子(方法) 预定义Source 基于本地集合的source(Collection-based-source) 基于文件的source(…

【C语言】扫雷游戏(一)

我们先设计一个简单的9*9棋盘并有10个雷的扫雷游戏。 1,可以用数组存放,如果有雷就用1表示,没雷就用0表示。 2,排查(2,5)这个坐标时,我们访问周围的⼀圈8个位置黄色统计周围雷的个数是1。排查(8,6)这个坐标时&#xf…

【博主推荐】C#中winfrom开发常用技术点收集

文章目录 前言1.打开文件夹并选中文件2.窗体之间传参3.异步调用:让数据处理不影响页面操作4.创建一个多文档界面(MDI) 应用程序5.在WinForms中使用数据绑定6.在WinForms中后台使用控件的事件处理7.在WinForms中窗体跳转的几种方式8.后台处理方法中,调用窗…

Matlab 绘制雷达图像完全案例和官方教程(亲测)

首先上官方教程链接 polarplothttps://ww2.mathworks.cn/help/matlab/ref/polarplot.html 上实例 % 定义角度向量和径向向量 theta linspace(0, 2*pi, 5); r1 [1, 2, 1.5, 2.5, 1]; r2 [2, 1, 2.5, 1.5, 2];% 绘制两个雷达图 polarplot(theta, r1, r-, LineWidth, 2); hold …

乌班图单机(不访问外网)部署docker和服务的方法

面向对象:Ubuntu不能访问外网的机子,部署mysql、redis、jdk8、minio 过程: 1、安装docker(照着图去这里找对应的下载下来https://download.docker.com/linux/static/stable/),将7个docker官网下载的文件下载下来后,传上去服务器随便一个文件夹或者常用的opt或者/usr/lo…

响应式编程一、Reactor核心

目录 一、前置知识1、Lambda表达式2、函数式接口 Function3、StreamAPI4、Reactive-Stream1)几个实际的问题2)Reactive-Stream是什么?3)核心接口4)处理器 Processor5)总结 二、Reactor核心1、Reactor1&…

Docker for Everyone Plus——No Enough Privilege

直接告诉我们flag在/flag中,访问第一小题: sudo -l查看允许提权执行的命令: 发现有image load命令 题目指明了有rz命令,可以用ZMODEM接收文件,看到一些write up说可以用XShell、MobaXterm、Tabby Terminal等软件连接上…

深度学习基础2

1.损失函数 1.1 线性回归损失函数 1.1.1 MAE损失 MAE(Mean Absolute Error,平均绝对误差)通常也被称为 L1-Loss,通过对预测值和真实值之间的绝对差取平均值来衡量他们之间的差异。。 公式: 其中: n 是样…

【Android】组件化嘻嘻嘻gradle耶耶耶

文章目录 Gradle基础总结:gradle-wrapper项目根目录下的 build.gradlesetting.gradle模块中的 build.gradlelocal.properties 和 gradle.properties 组件化:项目下新建一个Gradle文件定义一个ext扩展区域config.gradle全局基础配置(使用在项目…

基础Web安全|SQL注入

基础Web安全 URI Uniform Resource Identifier,统一资源标识符,用来唯一的标识一个资源。 URL Uniform Resource Locator,统一资源定位器,一种具体的URI,可以标识一个资源,并且指明了如何定位这个资源…

【插入排序】:直接插入排序、二分插入排序、shell排序

【插入排序】:直接插入排序、二分插入排序、shell排序 1. 直接插入排序1.1 详细过程1.2 代码实现 2. 二分插入排序2.1 详细过程2.2 代码实现 3. shell排序3.1 详细过程3.2 代码实现 1. 直接插入排序 1.1 详细过程 1.2 代码实现 public static void swap(int[]arr,…

一万台服务器用saltstack还是ansible?

一万台服务器用saltstack还是ansible? 选择使用 SaltStack 还是 Ansible 来管理一万台服务器,取决于几个关键因素,如性能、扩展性、易用性、配置管理需求和团队的熟悉度。以下是两者的对比分析,帮助你做出决策: SaltStack&…

通讯专题4.1——CAN通信之计算机网络与现场总线

从通讯专题4开始,来学习CAN总线的内容。 为了更好的学习CAN,先从计算机网络与现场总线开始了解。 1 计算机网络体系的结构 在我们生活当中,有许多的网络,如交通网(铁路、公路等)、通信网(电信、…

使用OSPF配置不同进程的中小型网络

要求: 给每个设备的接口配置好相应的地址 对进程1的各区域使用认证,认证为明文发送,明文保存 对骨干区域使用接口认证,非骨干区域使用区域认证 其他ospf进程均使用区域0 FW1上配置接口信任域和非信任域和服务器&#xff0c…

软考高项经验分享:我的备考之路与实战心得

软考,尤其是信息系统项目管理师(高项)考试,对于众多追求职业提升与专业认可的人士来说,是一场充满挑战与机遇的征程。我在当年参加软考高项的经历,可谓是一波三折,其中既有成功的喜悦&#xff0…

Transformers在计算机视觉领域中的应用【第1篇:ViT——Transformer杀入CV界之开山之作】

目录 1 模型结构2 模型的前向过程3 思考4 结论 论文: AN IMAGE IS WORTH 16X16 WORDS: TRANSFORMERS FOR IMAGE RECOGNITION AT SCALE 代码:https://github.com/google-research/vision_transformer Huggingface:https://github.com/huggingf…

Unity3D模型场景等测量长度和角度功能demo开发

最近项目用到多段连续测量物体长度和角度功能,自己研究了下。 1.其中向量角度计算: 需要传入三个坐标来进行计算。三个坐标确定两条向量线段的方向,从而来计算夹角。 public Vector3 SetAngle(Vector3 p1, Vector3 p2,Vector3 p3) { …