页面置换算法 LRU

备注：神策面试时问cache时 我竟然说成是红黑树，这个算法就是对缓存的来说的，只是加了个应用场景而已。

1、原理

LRU（Least recently used，最近最少使用）算法根据数据的历史访问记录来进行淘汰数据，其核心思想是“如果数据最近被访问过，那么将来被访问的几率也更高”。

2、实现

1337859321_3597.png

基于双链表 的LRU实现。
它的原理： 将Cache的所有位置都用双连表连接起来，当一个位置被命中之后，就将通过调整链表的指向，将该位置调整到链表头的位置，新加入的Cache直接加到链表头中。
这样，在多次进行Cache操作后，最近被命中的，就会被向链表头方向移动，而没有命中的，而想链表后面移动，链表尾则表示最近最少使用的Cache。当需要替换内容时候，链表的最后位置就是最少被命中的位置，我们只需要淘汰链表最后的部分即可。

3、其他页面置换算法

FIFO 当前进来的进队列 之前进来的出队列
LFU（Least Frequently Used） 保存每个节点被访问的次数 然后不断访问后排序
参考：http://www.cnblogs.com/s-b-b/p/6047954.html