## 算法LRU、LFU与FIFO 原

kenyon_君羊

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

### kenyon_君羊

2015/12/17
0
0

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 的设计与实现

peiquan
2014/09/26
0
0

2015/09/04
0
0

Httpd 整合 Tomcat 步骤

ZeroneLove

1
0
Docker笔记3——容器命令（未写完，明天整理接着写）

HappyBKs

1
0
2018个人年终总结

11
0

linux-tao

3
0
Spark共享变量

2
0