`

LRU(最近最少使用页面置换算法)淘汰算法

阅读更多
LRU(最近最少使用页面置换算法)淘汰算法

    什么是LRU算法? LRU是Least Recently Used的缩写,即最近最少使用页面置换算法,是为虚拟页式存储管理服务的。

    关于操作系统的内存管理,如何节省利用容量不大的内存为最多的进程提供资源,一直是研究的重要方向。而内存的虚拟存储管理,是现在最通用,最成功的方式——在内存有限的情况下,扩展一部分外存作为虚拟内存,真正的内存只存储当前运行时所用得到信息。这无疑极大地扩充了内存的功能,极大地提高了计算机的并发度。虚拟页式存储管理,则是将进程所需空间划分为多个页面,内存中只存放当前所需页面,其余页面放入外存的管理方式。

    然而,有利就有弊,虚拟页式存储管理减少了进程所需的内存空间,却也带来了运行时间变长这一缺点:进程运行过程中,不可避免地要把在外存中存放的一些信息和内存中已有的进行交换,由于外存的低速,这一步骤所花费的时间不可忽略。因而,采取尽量好的算法以减少读取外存的次数,也是相当有意义的事情。

    对于虚拟页式存储,内外存信息的替换是以页面为单位进行的——当需要一个放在外存的页面时,把它调入内存,同时为了保持原有空间的大小,还要把一个内存中页面调出至外存。自然,这种调动越少,进程执行的效率也就越高。那么,把哪个页面调出去可以达到调动尽量少的目的?我们需要一个算法。
自然,达到这样一种情形的算法是最理想的了——每次调换出的页面是所有内存页面中最迟将被使用的——这可以最大限度的推迟页面调换,这种算法,被称为理想页面置换算法。可惜的是,这种算法是无法实现的。

    为了尽量减少与理想算法的差距,产生了各种精妙的算法,最近最少使用页面置换算法便是其中一个。LRU算法的提出,是基于这样一个事实:在前面几条指令中使用频繁的页面很可能在后面的几条指令中频繁使用。反过来说,已经很久没有使用的页面很可能在未来较长的一段时间内不会被用到。这个,就是著名的局部性原理——比内存速度还要快的cache,也是基于同样的原理运行的。因此,我们只需要在每次调换时,找到最近最少使用的那个页面调出内存。这就是LRU算法的全部内容。
如何用具体的数据结构来实现这个算法?

    首先,最容易想到,也最简单的方法:计时法。给页表中的每一页增加一个域,专门用来存放计时标志,用来记录该页面自上次被访问以来所经历的时间。页面每被访问一次,计时清0。要装入新页时,从内存的页面中选出时间最长的一页,调出,同时把各页的计时标志全部清0,重新开始计时。
计时法可以稍作改变,成为计数法:页面被访问,计数标志清0,其余所有内存页面计数器加1;要装入新页时,选出计数最大的一页调出,同时所有计数器清0。
    这两种方法确实很简单,但运行效率却不尽如人意。每个时刻,或是每调用一个页面,就需要对内存中所有页面的访问情况进行记录和更新,麻烦且开销相当大。
另一种实现的方法:链表法。
    操作系统为每个进程维护一条链表,链表的每个结点记录一张页面的地址。调用一次页面,则把该页面的结点从链中取出,放到链尾;要装入新页,则把链头的页面调出,同时生成调入页面的结点,放到链尾。
    链表法可看作简单计时/计数法的改良,维护一个链表,自然要比维护所有页面标志要简单和轻松。可是,这并没有在数量级上改变算法的时间复杂度,每调用一个页面,都要在链表中搜寻对应结点并放至链尾的工作量并不算小。

    以上是单纯使用软件实现的算法。不过,如果能有特殊的硬件帮忙,我们可以有更有效率的算法。
首先,如果硬件有一个64位的计数器,每条指令执行完后自动加1。在每个页表项里添加一个域,用于存放计数器的值。进程运行,每次访问页面的时候,都把计数器的值保存在被访问页面的页表项中。一旦发生缺页,操作系统检查页表中所有的计数器的值以找出最小的一个,那这一页就是最久未使用的页面,调出即可。
    其次,另外一个矩阵算法:在一个有n个页框的机器中,LRU硬件可以维持一个n*n的矩阵,开始时所有位都是0。访问到第k页时,硬件把k行的位全设为1,之后再把k列的位置设为0。容易证明,在任意时候,二进制值最小的行即为最久未使用的页面,当调换页面时,将其调出。
以上的两种算法,无疑都要比纯粹的软件算法方便且快捷。每次页面访问之后的操作——保存计数器值和设置k行k列的值,时间复杂度都是O(1)量级,与纯软件算法不可同日而语。
那是否软件算法就毫无用处?当然不是,硬件算法有它致命的缺陷,那就是需要硬件的支持才能运行。如果机器上恰好有所需硬件,那无疑是再好不过;反之,若机器上没有这种硬件条件,我们也只能无奈地抛弃硬件算法,转而选取相对麻烦的软件算法了。
最后,让我们来谈论一下LRU算法。首先,这是一个相当好的算法,它是理想算法很好的近似。在计算机系统中应用广泛的局部性原理给它打造了坚实的理论基础,而在实际运用中,这一算法也被证明拥有极高的性能。在大规模的程序运行中,它产生的缺页中断次数已很接近理想算法。或许我们还能找到更好的算法,但我想,得到的收益与付出的代价恐怕就不成比例了。当然,LRU算法的缺点在于实现方法的不足——效率高的硬件算法通常在大多数机器上无法运行,而软件算法明显有太多的开销。与之相对的,FIFO算法,和与LRU相似的NRU算法,性能尽管不是最好,却更容易实现。所以,找到一个优秀的算法来实现LRU,就是一个非常有意义的问题。
分享到:
评论

相关推荐

    计算机视觉开发:OpenCV入门教程及应用

    内容概要:本文档详细介绍了OpenCV的基本概念及其在计算机视觉领域的应用,重点讲解了OpenCV在C++和Python环境下的安装方法,并提供了图像读取、显示、基本操作、视频处理以及面部检测的具体代码示例。此外,还涉及了一些图像处理技术的快速演示和进一步学习的路径建议。 适合人群:对计算机视觉感兴趣的新手开发者和技术爱好者。 使用场景及目标:本教程适用于希望入门计算机视觉和图像处理的新手,通过实际操作练习提升技术水平,掌握OpenCV的基本用法,并能够应用于实际项目,如OCR应用、图像分割与目标检测等。 阅读建议:建议读者按照文档提供的步骤进行实践,逐步完成每个代码示例,结合官方文档和其他资源深入理解各个函数的作用。对于初学者来说,可以通过多动手尝试,加深对OpenCV的理解。

    围绕着一系列的经典Python练习题 .zip

    围绕着一系列的经典Python练习题。Python练习一些按照回顾排列的Python练习题。欢迎提交你的答案或添加更多有趣的题目!从开始学Python以来,接触了精彩的练习题。下面十个练习题,是我做的和练习出来的题里比较有趣的,现在按照难度由低到高排列。欢迎到GitHub上提交你的答案。猜测数字经典的猜数字游戏,几乎是学编程时都会做的。功能描述随机选择三个以内的数字作为答案。用户输入一个数字,程序会提示大了或者小了,直到用户猜中。2.FizzBu​​zz另一道经典编程题。功能描述遍历并打印0到100,如果数字能被3整除,显示Fizz如果数字能被5整除,显示Buzz如果能同时被3和5整除,就显示FizzBu​​zz。结果应该类似0,1 ,2,嘶嘶声,4,嗡嗡声,6……14,嘶嘶声,16……3. 猜测数字的AI和猜数字一样,不过这次是设计一个能猜数字的人工智能功能描述用户输入一个单位以内的数字,AI需要最少的猜测次数,并显示出猜测的次数和数字。4.整点报时老式的挂钟会在整点报时,响铃的次数和时间是一致的。我们设计了一个在电脑上运行的报时

    毕设源码-python-django基于python技术的学生管理系统的设计与开发-期末大作业+说明文档.rar

    本项目是一个基于Python技术的学生管理系统,采用Django框架进行开发,旨在为计算机相关专业的学生提供一个实践性强、功能全面的管理系统,以帮助他们完成毕业设计或进行项目实战练习。 系统实现了对学生信息、课程信息、成绩、考勤等多方面的管理功能。学生信息管理包括学生基本信息的增删改查;课程信息管理允许管理员设置课程信息,包括课程名称、授课老师、学分等;成绩管理功能使学生和教师能够录入、查看和修改成绩;考勤管理则方便教师记录学生的出勤情况。 该项目采用B/S架构,前端使用HTML、CSS、JavaScript等技术,后端使用Python语言和Django框架,数据库采用MySQL。Django框架提供了强大的后台管理功能,使得系统管理更加便捷。 通过开发这个项目,学生不仅能提升自己的编程能力,还能学习到如何构建一个实际应用的系统,对于即将步入职场的学生来说,具有很高的实用价值。

    python入门-安装Python软件包.pdf

    python入门——安装Python软件包

    消息中间件源码学习(打注释学习).zip

    消息中间件源码学习(打注释学习)

    阿里消息中间件MetaQ学习Demo.zip

    阿里消息中间件MetaQ学习Demo

    数学建模培训资料 数学建模实战题目真题答案解析解题过程&论文报告 抑制房地产泡沫问题研究 共69页.pdf

    数学建模培训资料 数学建模实战题目真题答案解析解题过程&论文报告 抑制房地产泡沫问题研究 共69页.pdf

    rbac组件(基于角色的权限控制).zip

    rbac组件(基于角色的权限控制)

    Discuz! X3.5 R20240520 增量补丁包下载 X3.5 2023-12-21 升级到 X3.5 2024-05-20 补丁包

    压缩包内,SC是简体补丁包,TC是繁体补丁包

    ssm框架Java项目源码-基于Java的在线日语培训平台的设计与实现+jsp毕设-大作业.zip

    本项目是一个基于Java的在线日语培训平台的设计与实现,采用SSM框架(Spring+SpringMVC+MyBatis)进行开发,旨在为计算机相关专业的学生提供一个实践和学习的平台,同时也为日语学习者提供一个在线学习的空间。项目中主要功能涵盖了用户管理、课程管理、学习资源上传下载、在线测试与反馈等多个方面。通过该平台,教师能够轻松管理课程内容和学生信息,学生则可以随时随地访问学习资源,参与在线课程和测试,从而提高学习效率和兴趣。 在开发此项目的过程中,我们重点关注了系统的可维护性和可扩展性,确保代码结构清晰,便于后续的功能迭代和优化。此外,通过使用SSM框架,实现了前后端的分离,提高了开发效率和系统的响应速度。该项目不仅能够满足毕设的需求,还能作为Java学习者提升编程能力和实践经验的实用工具。

    机器xuex(大模型):语言模型在生成问题答案时的真实性数据集

    TruthfulQA是一个专门设计的基准测试数据集,用于衡量。这个数据集包含了817个问题,覆盖了38个不同的类别,如健康、法律、金融和政治等。这些问题被精心设计,以至于某些人可能会因为错误的信念或误解而给出错误的答案。因此,要在这个数据集上表现良好,语言模型必须避免生成从模仿人类文本中学到的错误答案。 TruthfulQA的数据集结构包括两种配置:generation和multiple_choice。在generation配置中,每个问题都包含了类型、类别、问题、最佳答案、正确答案列表、错误答案列表和来源。而在multiple_choice配置中,每个问题都提供了四个选项,模型需要从中选择正确的答案。 这个数据集的目的是为了测试语言模型在真实性方面的弱点,而不是测试模型在有用任务上的表现。研究发现,最大的模型通常是最不真实的,这与其他NLP任务不同,在其他任务中,模型的性能随着模型大小的增加而提高。TruthfulQA的数据集提供了一个重要的工具,用于评估和改进语言模型在生成真实和可靠信息方面的能力。

    多彩吉安红色旅游网站-JAVA-基于springBoot多彩吉安红色旅游网站的设计与实现

    多彩吉安红色旅游网站-JAVA-基于springBoot多彩吉安红色旅游网站的设计与实现

    基于servlet+jsp+mysql实现的影视管理系统课程设计

    【作品名称】:基于servlet+jsp+mysql实现的影视管理系统【课程设计】 【适用人群】:适用于希望学习不同技术领域的小白或进阶学习者。可作为毕设项目、课程设计、大作业、工程实训或初期项目立项。 【项目介绍】: 基于servlet+jsp+mysql实现的影视管理系统【课程设计】 基于servlet+jsp+mysql实现的影视管理系统【课程设计】 Java Web课程设计,基于servlet+jsp+ajax+mysql做的影视管理系统 运行环境: Tomcat 9.0 JDK 1.8 MySQL 8.0 后台管理账号密码均为:root,项目依赖:lib 目录 【资源声明】:本资源作为“参考资料”而不是“定制需求”,代码只能作为参考,不能完全复制照搬。需要有一定的基础看懂代码,自行调试代码并解决报错,能自行添加功能修改代码。

    渗透测试人员的 Python 工具.zip

    渗透测试人员的 Python 工具渗透测试人员的 Python 工具如果你参与漏洞研究、逆向工程或渗透测试,我建议尝试 Python编程语言。它有一套丰富的有用库和程序。本页列出了其中一些。列出的大多数工具都是用 Python 编写的,其他工具只是现有 C 库的 Python 绑定,即它们使这些库可轻松地在 Python 程序中使用。一些更激进的工具(渗透测试框架、蓝牙粉碎器、Web 应用程序漏洞扫描器、战争拨号器等)被排除在外,因为这些工具在德国的法律地位仍然不太明确——即使在最高法院作出裁决之后也是如此。这个列表显然是为了帮助白帽黑客,目前我更愿意谨慎行事。网络Scapy发送、嗅探、剖析和伪造网络数据包。可交互使用或作为库使用pypcap、 Pcapy和 pylibpcaplibpcap 的几种不同的 Python 绑定libdnet低级网络例程,包括接口查找和以太网帧传输dpkt快速、简单的数据包创建/解析,包含基本 TCP/IP 协议的定义Impacket制作和解码网络数据包。包括对 NMB 和 SMB 等高级协议的支持pynidslibnids

    quark(夸克)正版下载

    quark(夸克)正版下载

    ssm框架Java项目源码-企业员工岗前培训管理系统+vue毕设-大作业.zip

    ssm框架Java项目源码-企业员工岗前培训管理系统+vue毕设-大作业.zip是一个专为计算机相关专业学生和Java学习者设计的项目资源。该项目以企业员工岗前培训管理为背景,采用经典的SSM(Spring+SpringMVC+MyBatis)框架进行后端开发,确保系统的稳定性和可扩展性。同时,前端采用Vue.js框架,实现了前后端分离,提升了用户体验和开发效率。 该项目的主要功能包括员工信息管理、培训课程管理、培训进度跟踪、考试成绩记录与统计等。通过这些功能,系统能够帮助企业高效地管理员工的岗前培训过程,确保培训质量,提升员工技能水平。 此外,该项目不仅适合作为计算机专业学生的毕业设计题目,也适合Java学习者进行项目实战练习,通过实际操作,加深对SSM框架和Vue.js的理解,提升编程能力和解决问题的能力。

    汇聚【Python应用】【Python实训】【Python技术分享】等等.zip

    你是 Pythonista汇聚【从零单排】【实战项目】【数据科学】【自然语言处理】【计算机】【面试题系列】【大航海】【Python应用】【错题集】【技术沙龙】【内推渠道】 】等等【人人都是Pythonista】由公众号【Python专栏】推出,请认准唯一标识请仔细阅读本文档,尤其是使用说明。目录说明计算机视觉计算机视觉DataScience数据科学作业所有的作业都提交在这个目录下,每个人创建属于自己的独立目录HR内推渠道Interview_Questions: 面试题集KnowledgeShare干货分享LearnFromZero从零单排NLP自然语言处理、自然语言处理OnePiece大航海PracticeProject实战项目PythonExercisePython练习、应用资源资源目录TechSalon技术沙龙WeeklyReport每周新鲜事、分享好项目、好资源使用说明命名规范文件夹命名规范必须为英文全部小写单词之间用下划线分割,例如nagios_check_tomcat第一个单词代表项目涉及应用,若有多个采用简写,最多2

    基于java的学生社团管理系统设计与实现.docx

    基于java的学生社团管理系统设计与实现.docx

    学习微服务框架SpringCloud的一些示例代码.zip

    学习微服务框架SpringCloud的一些示例代码

    基于java的数字家庭网站设计与实现.docx

    基于java的数字家庭网站设计与实现.docx

Global site tag (gtag.js) - Google Analytics