- 浏览: 271670 次
- 性别:
- 来自: 北京
文章分类
- 全部博客 (161)
- 【**计划】 (2)
- 【**Core Java**】 (30)
- 【**JAVA EE】 (6)
- JDBC (3)
- Hibernate专题系列 (0)
- 【**OS】 (14)
- 【**架构设计/设计模式】 (11)
- 【Hadoop】 (3)
- 【**分布式】 (9)
- 模板 (1)
- C (2)
- 常用工具 (1)
- Oracle (2)
- 【Tips】 (3)
- 【数据库】 (2)
- 玩转Ubuntu (0)
- 【计算机网络/网络编程】 (7)
- 【**Search Engine】 (21)
- 【**专题**】 (6)
- 【**Python】 (10)
- XML (1)
- 【**Open Source Framework】 (1)
- 【高级主题】 (1)
- 【存储】 (3)
- 【笔试面试】 (2)
- 【**数据结构与算法设计】 (20)
- 【其他】 (3)
- 【编程练习】 (2)
- 【待完成】 (12)
- 【工作】 (6)
- 【软件研发】 (4)
- 【**多线程多进程编程】 (5)
- 【Web Service】 (1)
- 【表达式解析/JavaCC系列】 (5)
- 【缓存系统:Memcached】 (1)
- 【Java IO/NIO】 (5)
- 【JVM运行机制及内存管理】 (7)
最新评论
-
107x:
...
python list排序 -
yuzhu223:
...
【Python基础】Python的lambda函数与排序 -
Tonyguxu:
分析查询结果的打分小于11.query=1065800715* ...
lucene打分机制的研究 -
Tonyguxu:
query=139320661963.013709 = (MA ...
lucene打分机制的研究 -
Tonyguxu:
query=10658007150.6772446 = (MA ...
lucene打分机制的研究
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.
发表评论
-
【Java IO】Java的序列化机制
2012-06-12 18:07 980Java序列化机制采用的序列化算法: 1.所有保存到磁盘 ... -
LRU算法介绍
2012-06-05 22:30 3707问题背景 在操作系统的内存管理里,如何节省有限的内存并为尽可 ... -
关于 Java 对象序列化【转载】
2012-06-04 16:45 1327简介: Java 对象序列化(Java Object Seri ... -
数据结构之位图bitmap
2012-05-10 23:12 0http://dongxicheng.org/structur ... -
常见数据结构与算法汇总
2012-05-10 23:01 10731、常见数据结构 线性:数组,链表,队列, ... -
数据结构之位图
2012-05-10 18:34 5611介绍 (20120511)位图就是通过将数组下标与应用中 ... -
CRC循环校验
2012-05-10 15:11 1319http://www.360doc.com/content/1 ... -
map3搜索与存储的一道面试题
2012-05-10 15:10 881假设一个mp3搜索引擎收录了2^24首歌曲,并记录了可收听这些 ... -
字符串匹配算法——Edit distance
2012-05-09 11:20 2483如何比较两个字符串之间的相似程度(或者差异)? 想要比较 ... -
JavaCC/JJTree入门
2012-05-03 18:17 1359JavaCC 介绍 JJTree JJTree为了让 ... -
【Java NIO】内存映射文件
2012-04-24 14:16 1317java.nio包包含对下列特性的支持: 1.字符集 ... -
排序算法
2012-04-21 23:06 638插入排序 shell排序 ... -
【编程珠矶】开篇 千万号码的排序问题
2012-04-21 12:52 909注:学习了《编程珠矶》第一章,将涉及的一些知识点整理如下 ... -
【Core Java】正则表达式
2012-04-05 23:40 01 -
【Core Java】类加载
2012-04-02 21:16 824主要内容包括: 1.类加载 / 类连接 / 类初始化 2. ... -
【****Core Java提纲****】
2012-04-02 18:54 768Java IO NIO Java并发编程 ... -
Java编程中“为了性能”尽量要做到的一些地方[zz]
2012-03-19 23:31 8131. 尽量在合适的场合使用单例 使用单例可以减轻 ... -
【Java并发】线程安全
2012-03-10 15:44 1022什么是线程安全? 当多个线程访问一个类时,如果不用考 ... -
【Java Socket】
2012-03-07 18:49 2712 -
各个rules里代码分析
2012-03-06 10:54 734InternalChannelRule private ...
相关推荐
在内存运行过程中,若其所要访问的页面不在内存而需要把他们调入内存,但内存已经没有空闲空间时,为了保证该进程能正常运行,系统...目前存在着许多种置换算法(如FIFO,OPT,LRU),他们都试图更接近理论上的目标。
针对民用飞机航线可更换件(Li ne replaceable units,LRU )在多级保障组织中的配置问题,提出了基于VARI-METRI C理论的多级库存模型。首先,为解决民机非固定分配到基地,不适用于METRI C理论的情况,根据航空公司的运营...
理论讲解: LRU Cache.mp4 54.面试题:岛屿的个数&朋友圈(下).mp4 53.面试题:岛屿的个数&朋友圈(上).mp4 52.理论讲解:并查集.mp4 51.面试题:编辑距离.mp4 50.面试题:零钱兑换.mp4 49.面试题:最长上升子序列...
本课程设计是学生学习完《操作系统教程》课程后,进行的一次全面的综合训练,通过课程设计,让学生更好地掌握操作系统的原理及实现方法,加深对操作系统基础理论和重要算法的理解,加强学生的动手能力
(1)理解页面置换相关理论 (2)掌握OPT、FIFO、LRU、Clock及改进型Clock置换算法 (3) 观察不同算法的页面置换情况,分析比较不同算法的特点
理论基础:熟悉常见的数据结构、起码看过一本算法入门书 开始 git clone https://github.com/shenwl/algorithm-java.git cd algorithm-java mvn install mvn clean test 算法切题 Clarification Possible solutions ...
CAP理论 锁 事务 消息队列 协调器 ID生成方式 一致性hash 限流 微服务 微服务介绍 服务发现 API网关 服务容错保护 服务配置中心 算法 数组-快速排序-第k大个数 数组-对撞指针-最大蓄水 数组-滑动窗口-最小连续子数组...
leetcode上升的温度 刷题顺序 hot100 数据结构 链表 目前 两数相加/排序链表/合并K个升序链表 掌握不熟练 ...应用的底层理论知识,如:mysql的底层引擎,索引实现 开发语言原理,如:golang的GC,底层调度
lru缓存leetcode 指数 数学 理论 讲义 概率与统计 线性代数 问题 计算机科学 leetcode/hackerrank , (有些有教程/参考资料等...) 计算机图形/游戏开发 并发 算法和数据结构 Linux 机器学习 语言 C# C/C++ 电阻 ...
读通常在Redis,若读取不到,则从MySQL读取,然后将数据同步到Redis,Redis通常设置expire或者默认LRU进行数据淘汰。这种使用方式会有如下问题:1)MySQL及Redis存在数据不一致风险,尤其是长时间运行的系统2)业务...
lru leetcode 带插图的算法 当你理解某事时,你就可以找到数学来表达这种理解。 数学不提供理解。 计算的目的是洞察力,而不是数字。 唯一真正有价值的是直觉。 作者:莱斯利·兰波特、理查德·汉明和阿尔伯特·...
规范化理论是围绕这些范式而建立的。规范化的基本思想是逐步消除数据依赖 中不合适的部分,使模式中的各关系模式达到某种程度的"分离",即采用"一事一地"的 模式设计原则,因此,所谓规范化实质上就是概念的单一化。...
lru缓存leetcode 2020 年 4 月力扣挑战赛 有些问题很有挑战性,所以我不仅在谷歌上搜索了理论,还搜索了解决这些问题的方法。 第 1 周 编号 标题 解决方案 困难 136. 简单的 202. 简单的 53. 简单的 283. 简单的 122...
lru cache leetcode Notes Summary 这个repo是关于面试准备的。 互联网公司面试准备思维导图 数据结构和算法理论基础 掌握数据结构和算法直接的好处就是能写出性能更优的代码。算法是一种解决问题的思路和方法,从...
lru leetcode 项目结构 LeetCode ├── Golang └── Java 教学资源 书 入门书——《》 基础知识——《》 理论加持——《》 思维改善——《》 网站 其他 力码 不。 标题 解决方案 困难 类别 永不 1 、 简单的 大批...
在32位系统上,您一次可以映射的内存量自然限于理论上的4GB内存,对于某些应用程序可能还不够。 局限性 系统资源(文件句柄)可能会泄漏! 这是由于库作者依赖于确定性__del__()析构函数。 内存访问在设计上是只读...
本课程设计是学习完“操作系统原理”课程后进行的一次全面的综合训练,通过课程设计,更好地掌握操作系统的原理及实现方法,加深对操作系统基础理论和重要算法的理解,加强学生的动手能力。
lru leetcode 这个 repo 实际上只是我所做事情的公开日志,但让我们挑战一下。 1000天挑战 学习或做一些关于 CS 或 SE 的新事物 每天1小时 1000 天(2.7 年) 错过一天没关系 公共日志 目标是成为最好的软件工程师/...
lru缓存leetcode 面试准备 我在实习面试准备期间收集的资源集。 我在设计时花了大量时间来选择资源,并用主题提及它们以便于阅读。 很快会添加问题! 目录 资源 用于研究/修改每个我认为简洁且足够好的主题的免费...
基于反馈控制理论,通过系统辨识设计了缓存控制器。动态调整不同类别缓存对象的缓存空间,可保证高优先级Web对象的高命中率,而不同类别的Web对象命中率之比保持不变。在服务器端实现了基于比例命中率的缓存区分服务...