`
Tonyguxu
  • 浏览: 277804 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论
阅读更多

1.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,就是一个非常有意义的问题。——OS里存储管理/虚拟页式存储里确认页面调出的置换算法

 

阅读材料

1.http://blog.csdn.net/Ackarlix/article/details/1759793

2.

分享到:
评论

相关推荐

    LRU算法C语言版本

    文档"1408424057-郑光飞-LRU.doc"可能是关于LRU算法的详细讲解或实验报告,作者郑光飞可能提供了更深入的理论解释和实现细节,包括算法的性能分析、复杂度讨论以及可能的优化方法。 "reademe.txt"通常是项目说明...

    LRU.rar_LRU

    1. 理论上,LRU能提供较好的性能,因为它基于实际使用模式,倾向于保留最近活跃的数据。 2. 实现相对简单,尤其是在现代编程语言中,可以利用内置的数据结构高效地实现。 缺点: 1. 需要额外的空间存储访问信息,...

    操作系统 LRU算法 实验报告 及 程序代码

    1. **算法原理**:详细解释LRU算法的工作机制和背后的理论依据。 2. **实现细节**:介绍代码实现中的关键部分,如数据结构的选择和操作流程。 3. **实验环境**:描述实验所用的操作系统、编译器等软硬件环境。 4. **...

    lru.zip_FIFO LRU

    这个策略与日常生活中的排队理论相似,先进来的先出去。FIFO实现起来简单,但并不总是最优,因为它可能将频繁访问但后来才进来的页面过早地淘汰。 在实际应用中,LRU通常比FIFO表现更好,因为它能更好地预测未来...

    仿真LRU算法

    ### LRU算法仿真:深入解析与C语言实现 在计算机科学领域,LRU...这种仿真不仅有助于学习者掌握LRU算法的核心概念,还能促进对内存管理和缓存机制的理解,对于软件开发、系统设计和优化具有重要的理论和实践价值。

    模拟LRU算法

    - **优点**:LRU算法理论上有较好的性能,尤其是在工作集(近期经常访问的页面集合)大小与内存大小相近时。 - **缺点**:实现相对复杂,需要额外的数据结构支持。对于某些访问模式,LRU可能会表现得不如其他算法...

    页面置换算法(FIFO,LRU)

    在操作系统中,页面置换算法是解决虚拟内存管理问题的关键技术之一。当物理内存不足时,系统需要将一些页面从内存中移出,为...通过实验,我们可以更好地理解这两种算法的特性,为实际操作系统的内存管理提供理论支持。

    操作系统实验 请求分页存储管理(包括FIFO,LRU等等)

    在这个实验中,我们关注的是如何实现不同的页面替换算法,如FIFO(先进先出)、LRU(最近最少使用)以及最优页替换算法。这些算法的目的是为了在物理内存资源有限的情况下,有效地管理和调度虚拟内存中的页面,以...

    fifo_lru_opt.rar_FIFO LRU_OPT_OPT_ LRU_ FIFO_fifo_lru_opt_visual

    **OPT(最优页面置换算法)**是理论上的理想情况,它能够预知未来所有的页面访问序列,从而总是选择将来最长时间内不会被访问的页面进行替换。在现实中,由于无法预知未来,所以无法实现真正的OPT算法,但它的存在为...

    操作系统的页面置换算法(FIFO和LRU)

    操作系统中的页面置换算法是内存管理的关键技术之一,用于处理虚拟内存中的...通过编写这样的模拟程序,可以帮助我们深入理解这些算法的工作原理,以及它们在不同工作负载下的表现,为实际操作系统设计提供理论基础。

    操作系统LRU

    操作系统LRU,全称Least Recently Used,是一种常用的页面替换算法,用于解决计算机内存与外存之间的数据交换问题。...这是一项既理论又实践的任务,对于学习操作系统和提高编程技能都是非常有价值的。

    页面置换算法FIFO,LRU,NRU,OPT

    本项目封装了四种常见的页面置换算法:FIFO(先进先出),LRU(最近最少使用),NRU(非最近使用)和OPT(最优页面置换)。下面将对这些算法进行详细介绍。 1. FIFO(先进先出)算法: FIFO是最简单的页面置换算法...

    操作系统_FIFO_LRU_OPT

    根据给定文件的信息,我们可以看出该文件主要涉及的是操作系统中的三种页面置换算法:FIFO(先进先出)、LRU(最近最少使用)以及 OPT(最佳置换算法)。这三种算法是虚拟内存管理中用来决定何时替换内存中哪些页面...

    页面置换算法 OPT FIFO LRU

    根据提供的信息,我们可以详细探讨页面置换算法中的三种主要方法:最优置换算法(OPT)、先进先出(FIFO)以及最近最少使用(LRU)算法。这些算法在计算机内存管理中至关重要,尤其是在虚拟内存系统中,用于决定何时将哪些...

    aaa.rar_FIFO LRU OPT_OPT FIFO LRU_OPT_ LRU_ FIFO_java fifo lru_l

    本文将详细讨论三种常见的缓存淘汰策略:FIFO(First In First Out)、LRU(Least Recently Used)以及OPT(Optimal)。这些策略的Java实现是编程实践中的常见需求,下面我们将逐一探讨它们的原理和实现。 1. FIFO...

    操作系统页面置换FIFO,LRU,OPT,CLOCK

    OPT(也称为最小未来引用页替换)是理论上的最优页面置换算法,它能够预知未来,总是选择未来最长时间内不会被访问的页面进行替换。由于实际操作中无法预测未来,所以OPT无法在现实中实现,但它为其他算法提供了性能...

    JAVA实现FIFO、LRU、OPT页面置换算法,有界面

    然而,实际操作中,由于无法预知未来,所以OPT通常只作为理论上的最优解,实际应用中一般采用近似算法,如LRU。 4. JAVA实现带界面的页面置换算法: 在这个项目中,开发者使用Java编程语言实现了上述三种页面置换...

    虚拟存储中页面调度算法的模拟实现fifo ,lru opt

    3. OPT(最佳页面替换)算法是一种理论上的最优策略,它具有前瞻性的能力,能够预测未来页面访问序列,从而选择未来最长时间内不会被访问的页面进行替换。虽然在实际操作中无法完美实现,因为未来的访问信息往往是...

    操作系统页面置换LRU,FIFO,OPT算法实现代码

    至于OPT,虽然理论上无法精确实现,但可以通过一些启发式算法,如Clock算法,来近似实现。 在实际操作系统中,除了上述基础算法外,还有许多其他策略,如LFU(最近最不常用)、Second Chance等。这些算法各有优缺点...

    页面置换算法(fifo,lru,opt) C语言编写

    OPT,也称为理想页面置换算法,是理论上的最优算法,它总是能预知未来,选择未来最长时间内不会被访问的页面进行替换。在实际应用中难以实现,因为需要预测未来的访问模式。但在理解和评估其他算法的性能时,它是...

Global site tag (gtag.js) - Google Analytics