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,就是一个非常有意义的问题。
分享到:
相关推荐
本主题聚焦于通过链表实现的存储管理,特别是涉及了三种重要的页面置换算法:先出(FIFO)页面置换算法、最近最少使用(LRU)页面置换算法和最佳(OPT)置换算法。 首先,内存分配与回收是存储管理的基础。当一个新...
最近最久未使用(LRU) 选择最后一次访问时间距离当前时间最长的一页并淘汰之 LRU软件实现 设置一个页号栈, 当一个页面被访问时,就立即将它的页号压入页号栈,并检查页号栈中是否有与刚压入栈顶的相同的页号,若...
这里我们将讨论两种常见的页面置换算法:FIFO(先进先出)和NUR(最近未使用)。 FIFO算法基于简单的队列原理,它将新进来的页面添加到内存的末尾,并且最先被调入内存的页面也最先被换出。在给定的代码中,`Fifo`...
本课程设计项目专注于两种常见的页面置换算法:FIFO(先进先出)和LRU(最近最少使用)。这两种算法都是为了在主存空间不足时决定哪些页面应该被换出到磁盘,以便腾出空间加载新的页面。 **FIFO页面置换算法**: ...
LRU(Least Recently Used)页面置换算法是一种在操作系统中用于管理内存资源的策略,尤其是在虚拟内存系统中。它的核心思想是:最近最久未使用的页面优先被替换出去。当内存空间不足,需要替换页面时,LRU算法会...
LRU(Least Recently Used,最近最少使用)页面置换算法是一种常用的内存管理策略,它用于解决在有限的物理内存中管理大量虚拟内存页的问题。当内存不足时,LRU算法会淘汰那些最近最少使用的页面,以腾出空间供新...
在这个C语言实现的项目中,我们主要关注三种常见的页面置换算法:FIFO(先进先出)、LRU(最近最少使用)和OPT(最佳页面置换)。下面将详细解释这三种算法的工作原理以及它们在C语言编程中的实现。 1. FIFO(先进...
本资源包含的是一个针对三种常见页面置换算法的模拟程序:FIFO(先进先出)、LRU(最近最少使用)和LFU(最不经常使用)。通过这个程序,用户可以直观地理解这些算法的工作原理和性能差异。 **FIFO(先进先出)页面...
根据给定的文件标题、描述、标签以及部分内容,本文将详细介绍页面置换算法中的三种常见算法:先进先出(FIFO)、最近最少使用(LRU)和最佳置换算法(OPT),并探讨它们在操作系统内存管理中的应用。 ### 页面置换...
LRU(Least Recently Used)页面置换算法是一种在操作系统中用于管理内存资源的策略,它遵循一个简单的原则:当内存满时,最近最久未使用的页面将被替换出去。这个算法假设最近频繁使用的数据将来也更可能被频繁访问...
(2)最近最少访问页面算法(LRU) 2.要有体现算法比较的程序输出,比如:缺页率和页面置换次数等。 3.采用固定分配局部置换,且可以在程序中实现块数重新分配。 具有抖动判断和Belady异常判断机制 根据设计要求实现对...
该算法的工作原理是,将那些最近最少被访问的页面淘汰。LRU 算法的优点是可以减少页面置换次数,但缺点是需要维护一个访问时间表。 知识点五:实验源码解析 实验源码中提供了一个菜单项选择界面,用户可以选择使用...
本项目实现了两种常见的页面置换算法——FIFO(先进先出)和LRU(最近最少使用),并使用C++编程语言进行实现。 **FIFO(先进先出)页面置换算法**: FIFO是最简单的页面置换算法,它的原理是将最早进入内存的页面...
LRU算法的基本思想是:最近最少使用的页面最有可能在未来一段时间内继续不被使用,因此在需要替换页面时,应该优先选择这种页面。 LRU算法的操作基于一个假设,即如果一个页面最近被频繁访问,那么它在将来也更可能...
本项目将深入探讨两种重要的页面置换算法:FIFO(先进先出)和LRU(最近最久未使用)。通过使用C语言在Linux环境下进行模拟,我们可以更好地理解这些算法的工作原理。 **FIFO(先进先出)页面置换算法**: FIFO是最...
在操作系统中,当物理内存不足以容纳所有活动页面时,LRU算法会选择最近最少使用的页面进行淘汰,以腾出空间加载新的页面。这个C语言程序旨在模拟LRU算法的工作过程,帮助用户理解其运作机制。 首先,我们来深入...
本项目着重于模拟两种常见的页面置换算法:FIFO(先进先出)和LRU(最近最少使用)。下面将详细介绍这两种算法及其工作原理。 **FIFO(先进先出)页面置换算法** FIFO算法基于一个简单的思想:最早进入内存的页面...
本篇文章将详细讲解三种常见的页面置换算法:LRU(最近最少使用)、OPT(最佳页面置换)和FIFO(先进先出)。 1. LRU(最近最少使用)算法: LRU算法的基本思想是:如果一个页面最近被访问过,那么它在不久的将来...
本实验旨在通过实际编程实现请求分页存储管理中的三种页面置换算法:最优置换算法(Optimal)、先进先出置换算法(FIFO)以及最近最少使用置换算法(LRU),帮助学生深入理解和掌握虚拟存储管理的核心概念和技术。...
本项目封装了四种常见的页面置换算法:FIFO(先进先出),LRU(最近最少使用),NRU(非最近使用)和OPT(最优页面置换)。下面将对这些算法进行详细介绍。 1. FIFO(先进先出)算法: FIFO是最简单的页面置换算法...