`
Josh_Persistence
  • 浏览: 1649873 次
  • 性别: Icon_minigender_1
  • 来自: 上海
社区版块
存档分类
阅读更多
LRU是Least Recently Used 近期最少使用算法。
内存管理的一种页面置换算法,对于在内存中但又不用的数据块(内存块)叫做LRU,操作系统会根据哪些数据属于LRU而将其移出内存而腾出空间来加载另外的数据。
什么是LRU算法? LRU是Least Recently Used的缩写,即最少使用页面置换算法,是为虚拟页式存储管理服务的。
关于操作系统的内存管理,如何节省利用容量不大的内存为最多的进程提供资源,一直是研究的重要方向。而内存的虚拟存储管理,是现在最通用,最成功的方式—— 在内存有限的情况下,扩展一部分外存作为虚拟内存,真正的内存只存储当前运行时所用得到信息。这无疑极大地扩充了内存的功能,极大地提高了计算机的并发度。虚拟页式存储管理,则是将进程所需空间划分为多个页面,内存中只存放当前所需页面,其余页面放入外存的管理方式。
然而,有利就有弊,虚拟页式存储管理减少了进程所需的内存空间,却也带来了运行时间变长这一缺点:进程运行过程中,不可避免地要把在外存中存放的一些信息和内存中已有的进行交换,由于外存的低速,这一步骤所花费的时间不可忽略。因而,采取尽量好的算法以减少读取外存的次数,也是相当有意义的事情。
对于虚拟页式存储,内外存信息的替换是以页面为单位进行的——当需要一个放在外存的页面时,把它调入内存,同时为了保持原有空间的大小,还要把一个内种调动越少,进程执行的效率也就越高。那么,把哪个页面调出去可以达到调动尽量少的目的?我们需要一个算法。
其实,达到这样一种情形的算法是最理想的了——每次调换出的页面是所有内存页面中最迟将被使用的——这可以最大限度的推迟页面调换,这种算法,被称为理想页面置换算法。可惜的是,这种算法是无法实现的。

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

LRU在电子系统中的解释:
Line Replaceable Unit — LRU,电子系统中常采用模块化设计,这种可更换的模块单元则被叫做LRU,中文名称是“线性可更换单元”
例子
LRU(least recently used)最少使用。
假设 序列为 4 3 4 2 3 1 4 2
物理块有3个 则
首轮 4调入内存 4
次轮 3调入内存 3 4
之后 4调入内存 4 3
之后 2调入内存 2 4 3
之后 3调入内存 3 2 4
之后 1调入内存 1 3 2(因为最少使用的是4,所以丢弃4)
之后 4调入内存 4 1 3(原理同上)
最后 2调入内存 2 4 1
又如:
考虑下述页面走向:
1,2,3,4,2,1,5,6,2,1,2,3,7,6,3,2,1,2,3,6
1 1
2 21
3 321
4 432 1
2 243 2
1 124 3
5 512 4
6 651 2
2 265 1
1 126 5
2 216
3 321 6
7 732 1
6 673 2
3 367 3
2 236 7
1 123 6
2 213
3 312
6 631 2
发生缺页中断的次数为15。在LRU算法中,最少使用的页面被先换出。当页6要调入时,内存的状态为5、1、2,考查页6之前调入的页面,分别为5、1、2,可见2为一段时间内使用最少的,本次应换出,然后把页6调入内存。
 
1
1
分享到:
评论

相关推荐

    c语言实现的LRU算法

    在C语言中实现LRU算法,需要理解数据结构和算法的基础知识,以及如何在C语言中有效地管理内存。 首先,LRU算法的核心是数据结构的选择。通常使用双向链表来存储数据,因为双向链表允许我们快速地插入和删除元素,...

    Java实现LRU算法.zip

    在操作系统中,当内存不足以容纳所有活动页面时,LRU算法会选择最近最久未使用的页面进行淘汰,以腾出空间加载新的页面。 在Java中实现LRU算法,通常会使用数据结构如HashMap或LinkedHashMap来存储页面及其访问信息...

    lru算法实验报告

    LRU (Least Recently Used) 算法是一种常用的页面替换策略,用于管理计算机内存中的页面。在虚拟存储系统中,由于物理内存有限,当所有页面无法同时驻留在内存时,LRU 算法则用于决定将哪个页面换出到磁盘。它的基本...

    东南大学操作系统实验——实现LRU算法及其近似算法

    LRU算法是一种常见的虚拟内存管理策略,它根据页面的使用历史来决定替换哪个页面。当内存中的页面被新页面占用时,LRU算法会优先淘汰最近最久未使用的页面。 实验内容包括实现LRU算法的两种不同变体:计数器实现和...

    LRU算法 lru算法

    LRU算法就是在这个过程中发挥作用,选择最近最久未使用的页面优先进行替换。 LRU算法的基本思想是:当内存满时,新进来的页面会替换掉最近最少使用的页面。这里的“最近”是指最近一次被访问的时间,“最少使用”是...

    操作系统之LRU算法(java)(csdn)————程序.pdf

    操作系统之LRU算法(Java) LRU(Least Recently Used,最近最少使用)算法是一种常用的页面置换算法,用于操作系统中管理内存页面。该算法的基本思想是:当进程在 CPU 上运行时,如指令中涉及逻辑地址时,操作系统...

    LRU 算法(c语言)

    ### LRU算法(Least Recently Used)在C语言中的实现 #### 概述 LRU算法是一种常用的缓存淘汰策略,在计算机科学中广泛应用于操作系统、数据库系统以及Web浏览器等场景。其核心思想是当缓存满时,优先淘汰最近最少...

    LRU算法.zip

    当内存不足以容纳所有数据时,LRU算法会选择最近最少使用的数据进行淘汰。它的基本思想是:如果一个数据最近被访问过,那么它在未来的访问概率会比较高。LRU算法的核心在于维护一个有序的数据结构,例如链表或者哈希...

    LRU算法 C++实现

    在操作系统中,当内存不足以容纳所有活动进程的数据时,LRU算法会被用来决定哪些页面应该被换出到磁盘上,以便为新进来的页面腾出空间。它的核心思想是:最近最少使用的页面在未来最不可能被使用,因此优先淘汰。 ...

    LRU算法模拟实验

    在操作系统中,LRU算法用于决定何时将页面从内存移出,以便为新的页面腾出空间。当内存中的页面数量不足以容纳所有需要的页面时,LRU算法会选择最长时间没有被访问的页面进行替换。 实验目的是通过编程模拟LRU算法...

    LRU算法实现(C++版本)

    1.资源包含LRU算法整个项目,可直接在vs2019上运行项目,如果版本不对可选择把项目中cpp文件复制到自己的vs中运行 2.LRU 算法的设计原则是:如果一个数据在最近一段时间没有被访问到,那么在将来它被访问的可能性也...

    操作系统LRU算法实验报告

    LRU算法通过维护一个页面访问历史来跟踪每个页面的使用情况,当内存满时,它会优先淘汰那些长时间未被访问的页面。 在电子科技大学的这个实验报告中,学生需要设计并改进LRU算法的实现。实验的目标是让用户自定义页...

    LRU算法实现_实验报告

    在实际操作系统中,LRU算法可能需要更复杂的数据结构和算法来支持,例如使用哈希表来加速页面查找,或者使用位图来跟踪页面状态。然而,这个简单的C语言实现提供了一个直观的理解基础,展示了LRU算法的基本操作和...

    操作系统LRU算法小程序

    LRU算法就是在此背景下诞生的,它的核心思想是:最近最少使用的页面在未来最可能仍然是最少使用的。 LRU算法的基本操作流程如下: 1. 记录每个页面的访问时间。 2. 当内存满时,新进来的页面无法放入内存,此时需要...

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

    当物理内存不足以容纳所有活动进程时,LRU算法会选择最近最少使用的页面进行淘汰,以腾出空间给新的或需要访问的页面。 在计算机科学中,操作系统负责管理和调度系统的各种资源,包括内存。内存管理是操作系统的...

    进程调度算法(LRU算法)

    ### LRU算法 #### 1. LRU算法简介 LRU(Least Recently Used)算法是一种常用的内存管理与虚拟缓存置换算法,其基本思想是当缓存满时,优先淘汰最近最少使用的页面。这种算法能够很好地利用程序访问的局部性原理,...

    LRU算法(操作系统)

    ### LRU算法(操作系统) #### 一、LRU算法简介 LRU(Least Recently Used,最近最少使用)算法是一种常用的操作系统存储器管理中的页面置换算法。它的基本思想是:当内存空间不够时,系统会将最近最久未使用的...

    基于C语言的FIFO和LRU算法

    基于C语言的FIFO和LRU算法的实现。

    lru算法C语言实现

    ### LRU算法C语言实现详解 #### 一、引言 LRU(Least Recently Used,最近最少使用)算法是一种常用的数据缓存淘汰策略,在计算机科学领域应用广泛,尤其是在操作系统、数据库管理和Web服务器缓存管理等方面。本文...

    操作系统lru算法 实验

    LRU算法的基本思想是:最近最久未使用的页面优先被替换。 在C语言中实现LRU算法,通常需要构建一个数据结构来存储页面及其相关信息。描述中提到的“不同于网上的结构体”,可能指的是作者采用了自定义的方式来实现...

Global site tag (gtag.js) - Google Analytics