文档章节

算法LRU、LFU与FIFO

kenyon_君羊
 kenyon_君羊
发布于 2015/04/10 16:44
字数 475
阅读 146
收藏 0
缓存过期管理有很多种方式,常见的有FIFO,LRU与LFU,当然还有其他算法,比如rand,opt等。这三种简单的区别如下:

FIFO:是first in first out 的缩写
LRU :是least recently used 的缩写
LFU :是least frequently used 的缩写

fifo很容易理解,是先进先出,最做进去的page将被置换
lru是最近最少使用的page将被置换
lfu是最近最不常用的page将被置换

Least Recently Used (LRU)
Discards the least recently used items first. This algorithm requires keeping track of what was used when, which is expensive if one wants to make sure the algorithm always discards the least recently used item. General implementations of this technique require keeping "age bits" for cache-lines and track the "Least Recently Used" cache-line based on age-bits. In such an implementation, every time a cache-line is used, the age of all other cache-lines changes.


Least-Frequently Used (LFU)
Counts how often an item is needed. Those that are used least often are discarded first.


It requires three data structures. One is a hash table which is used to cache the key/values so that given a key we can retrieve the cache entry at O(1). Second one is a double linked list for each frequency of access. The max frequency is capped at the cache size to avoid creating more and more frequency list entries. If we have a cache of max size 4 then we will end up with 4 different frequencies. Each frequency will have a double linked list to keep track of the cache entries belonging to that particular frequency. The third data structure would be to somehow link these frequencies lists. It can be either an array or another linked list so that on accessing a cache entry it can be easily promoted to the next frequency list in time O(1).

redis使用LRU的近似算法来进行page置换
LRU的一个例子:
1 2 3 4 1 2 5 1 2 3 4 5
1 1 1 1 1 1 1 1 1 1 1 5

2 2 2 2 2 2 2 2 2 2 2


3 3 3 3 5 5 5 5 3 3



4 4 4 4 4 4 3 4 4
fill fill fill full hit hit repl hit hit repl repl repl



参考:
1.http://en.wikipedia.org/wiki/Cache_algorithms
2.http://stackoverflow.com/questions/17759560/what-is-the-difference-between-lru-and-lfu 3.http://redis.io/topics/lru-cache
4.http://www.cs.jhu.edu/~yairamir/cs418/os6/sld014.htm

© 著作权归作者所有

共有 人打赏支持
上一篇: Redis的主从复制
下一篇: Redis的源码安装
kenyon_君羊
粉丝 499
博文 170
码字总数 121714
作品 0
杭州
其他
私信 提问
页面置换算 - FIFO、LFU、LRU

缓存算法(页面置换算法)-FIFO、LFU、LRU   在前一篇文章中通过leetcode的一道题目了解了LRU算法的具体设计思路,下面继续来探讨一下另外两种常见的Cache算法:FIFO、LFU 1.FIFO算法   ...

孟宇
2015/12/17
0
0
常用缓存淘汰算法(LFU、LRU、ARC、FIFO、MRU)

QQ用得起来越少了,现在就加入300+技术微信群,下方公众号回复"微信群"即可加入。 image 缓存算法是指令的一个明细表,用于决定缓存系统中哪些数据应该被删去。 常见类型包括LFU、LRU、ARC、...

架构之路
2017/12/17
0
0
Retrofit 风格的 RxCache及其多种缓存替换算法

RxCache 是一个支持 Java 和 Android 的 Local Cache 。 之前的文章《给 Java 和 Android 构建一个简单的响应式Local Cache》、《RxCache 整合 Android 的持久层框架 greenDAO、Room》曾详细...

fengzhizi715
2018/11/01
0
0
cache 的设计与实现

本文整理自一下两篇博客:http://my.oschina.net/ScottYang/blog/298727 http://my.oschina.net/u/866190/blog/188712 Cache简介: Cache(高速缓存), 一个在计算机中几乎随时接触的概念。C...

peiquan
2014/09/26
0
0
缓存算法(页面置换算法)-FIFO、LFU、LRU

转自:http://www.cnblogs.com/dolphin0520/ 1.FIFO算法   FIFO(First in First out),先进先出。其实在操作系统的设计理念中很多地方都利用到了先进先出的思想,比如作业调度(先来先服...

宝塔镇河妖
2015/09/04
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Httpd 整合 Tomcat 步骤

环境:Tomcat8 + Httpd2.4 工作原理:借助于Tomcat的AJP连接器实现Apache与Tomcat的通信 配置步骤: 1. 配置httpd.conf 新增: Include conf/extra/mod_jk.conf 修改:添加 index.jsp <IfM...

ZeroneLove
昨天
1
0
Docker笔记3——容器命令(未写完,明天整理接着写)

未写完,明天整理接着写 新建并启动容器 docker run docker run [OPTIONS] IMAGE [COMMEND] [ARG...] OPTIONS: --name=[容器新名字] :为容器指定一个名称 -d:后台运行容器,并返回容器ID,...

HappyBKs
昨天
1
0
2018个人年终总结

感谢领导的信任和指导,新的一年获得了很多成长和提高,改掉了很多不好的习惯。 在这一年里,我在领导的帮助下,主要完成了以下功能: 1、完成上海银行版本投资营销相关功能的开发。 2、完成车...

万山红遍
昨天
11
0
保密工作与linux系统的发展

保密工作从性质上可以分成商业方面的保密和国家安全方面的保密。由于自己从事的是IT方面的工作,工作中必然会接触涉及到计算机信息方面的相关文件。加上单位已近通过武器装备科研生产单位二级...

linux-tao
昨天
3
0
Spark共享变量

概述 Spark程序的大部分操作都是RDD操作,通过传入函数给RDD操作函数来计算。这些函数在不同的节点上并发执行,但每个内部的变量有不同的作用域,不能相互访问,所以有时会不太方便,Spark提...

仟昭
昨天
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部