- 1、本文档共9页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
缓存淘汰算法之的LRU
缓存淘汰算法之 LRU
缓存淘汰算法之LRU
1. LRU
1.1. 原理
LRU (Least recently used ,最近最少使用 )算法根 数 的历史访问记录来进行淘汰数 ,其核心思想是 “如果数 最近被访问过 ,那么将来被访
问的几率也更高”。
1.2. 实现
最常见的实现是使用一个链表保存缓存数 ,详细算法实现如下 :
1. 新数 插入到链表头部 ;
2. 每当缓存命中 (即缓存数 被访问 ),则将数 移到链表头部 ;
3. 当链表满的时候 ,将链表尾部的数 丢弃。
1.3. 分析
【命中率】
当存在热点数 时 ,LRU的效率很好 ,但偶发性的、周期性的批量操作会导致LRU命中率急剧下降 ,缓存污染情况比较严重。
【复杂度】
实现简单。
【代价】
命中时需要遍历链表 ,找到命中的数 块索引 ,然后需要将数 移到头部。
2. LRU-K
2.1. 原理
LRU-K中的K代表最近使用的次数 ,因此LRU可以认为是LRU-1。LRU-K的主要目的是为了解决LRU算法 “缓存污染”的问题 ,其核心思想是将 “最
近使用过1次”的判断标准扩展为 “最近使用过K次”。
2.2. 实现
相比LRU ,LRU-K需要多维护一个队列 ,用于记录所有缓存数 被访问的历史。只有当数 的访问次数达到K次的时候 ,才将数 放入缓存。当需要
淘汰数 时 ,LRU-K会淘汰第K次访问时间距当前时间最大的数 。详细实现如下 :
1. 数 第一次被访问 ,加入到访问历史列表 ;
2. 如果数 在访问历史列表里后没有达到K次访问 ,则按照一定规则 (FIFO ,LRU )淘汰 ;
3. 当访问历史队列中的数 访问次数达到K次后 ,将数 索引从历史队列删除 ,将数 移到缓存队列中 ,并缓存此数 ,缓存队列重新按照时间排
序 ;
4. 缓存数 队列中被再次访问后 ,重新排序 ;
5. 需要淘汰数 时 ,淘汰缓存队列中排在末尾的数 ,即 :淘汰 “倒数第K次访问离现在最久”的数 。
LRU-K具有LRU的优点 ,同时能够避免LRU的缺点 ,实际应用中LRU-2是综合各种因素后最优的选择 ,LRU-3或者更大的K值命中率会高 ,但适应性
差 ,需要大量的数 访问才能将历史访问记录清除掉。
2.3. 分析
【命中率】
LRU-K降低了 “缓存污染”带来的问题 ,命中率比LRU要高。
【复杂度】
LRU-K队列是一个优先级队列 ,算法复杂度和代价比较高。
【代价】
由于LRU-K还需要记录那些被访问过、但还没有放入缓存的对象 ,因此内存消耗会比LRU要多 ;当数 量很大的时候 ,内存消耗会比较可观。
LRU-K需要基于时间进行排序 (可以需要淘汰时再排序 ,也可以即时排序 ),CPU消耗比LRU要高。
3. Two queues (2 )
3.1. 原理
Two queues (以下使用2Q代替 )算法类似于LRU-2 ,不同点在于2Q将LRU-2算法中的访问历史队列 (注意这不是缓存数 的 )改为一个FIFO缓存
队列 ,即 :2Q算法有两个缓存队列 ,一个是FIFO队列 ,一个是LRU队列。
3.2. 实现
当数 第一次访问时 ,2Q算法将数 缓存在FIFO队列里面 ,当数 第二次被访问时 ,则将数 从FIFO队列移到LRU队列里面 ,两个队列各自按照自
己的方法淘汰数 。详细实现如下 :
1. 新访问的数 插入到FIFO队列 ;
2. 如果数 在FIFO队列中一直没有被再次访问 ,则最终按照FIFO规则淘汰 ;
3. 如果数 在FIFO队列中被再次访问 ,则将数 移到LRU队列头部 ;
4. 如果数 在LRU队列再次被访问 ,则将数 移到LRU队列头部 ;
5. LRU队列淘汰末尾的数 。
注 :上图中FIFO队列比LRU队列短 ,但并不代表这是算法要求 ,实际应用中两者比例没有硬性规定。
3.3. 分析
【命中率】
2Q算法的命中率要高于LRU。
【复杂度】
需要两个队列
您可能关注的文档
- 第的三章土地资源与地质环境(03-2).ppt
- 第的二章 教育社会学的研究过程.ppt
- 第的二章会计数字书写技能.ppt
- 第的二章信息熵.ppt
- 第的二章 面向对象的程序设计.ppt
- 第的二章-进程管理.ppt
- 第的八章 工业计算机安装与调试-说明计算规则.doc
- 第的二节__细菌.ppt
- 第的二章 基坑工程.ppt
- 第的八章 函数.ppt
- 第十一章 电流和电路专题特训二 实物图与电路图的互画 教学设计 2024-2025学年鲁科版物理九年级上册.docx
- 人教版七年级上册信息技术6.3加工音频素材 教学设计.docx
- 5.1自然地理环境的整体性 说课教案 (1).docx
- 4.1 夯实法治基础 教学设计-2023-2024学年统编版九年级道德与法治上册.docx
- 3.1 光的色彩 颜色 电子教案 2023-2024学年苏科版为了八年级上学期.docx
- 小学体育与健康 四年级下册健康教育 教案.docx
- 2024-2025学年初中数学九年级下册北京课改版(2024)教学设计合集.docx
- 2024-2025学年初中科学七年级下册浙教版(2024)教学设计合集.docx
- 2024-2025学年小学信息技术(信息科技)六年级下册浙摄影版(2013)教学设计合集.docx
- 2024-2025学年小学美术二年级下册人美版(常锐伦、欧京海)教学设计合集.docx
文档评论(0)