一、前言

　　缓存算法历史已经很久了，但在楼主查询相关资料时，发现知识零碎，且原理介绍的很不详细，遂有了总结常用缓存算法文章的想法，以供广大朋友们查阅。本文是缓存系列的第一篇，知识侧重于初略的介绍，并未深入。

二、NRU(Not recently used)

　　1、算法思想

　　　　NRU算法的思想是保留最近使用过的对象。

　　2、工作原理

　　　　缓存维护两个标记位，初始值为0。一个标记位R标识对象是否被使用过，另一个M用来标识对象是否被修改过。当一个对象在缓存中找到时，R置为1(referenced);当一个对象被修改时，M置为1(modified)。一个对象拥有的标记位有4种状态：

　　　　3. referenced, modified

　　　　2. referenced, not modified

　　　　1. not referenced, modified

　　　　0. not referenced, not modified

　　　　当缓存已满，但新的对象需要加入缓存时，从等级(上面状态最左边的数字代表等级)最低的对象中随机淘汰一个。

　　　　同时，缓存还有一个周期性的时钟，它在每个时间间隔会把所有对象的R标记为清零(这样就知道该对象最近，也就是一个时间间隔，是否被使用)，但M不会清零。所以上面not referenced, modified状态看似不可能，但在经历过一个时间间隔，R位被清零时将有可能发生。

　　　　注意，该算法认为，最近被使用过的对象，比最近被修改过的对象更重要。

 三、FIFO(First-in, first-out)

 　　1、算法思想

　　　　该算法是最简单的缓存淘汰算法，其原理正如它名字一样，最近使用过的对象放到缓存队列的末尾，队列头部保存的是最早使用的对象。

四、Second-chance

　　1、算法思想

　　　　这是FIFO算法的改进版，相对于FIFO算法立刻淘汰对象，该算法会检查待淘汰对象的引用标志位。如果对象被引用过，该对象引用位清零，重新插入队列尾部，像新的对象一样；如果该对象未被引用过，则将被淘汰。

　　2、工作原理

　　　　在FIFO算法的基础上，

　　　　*为缓存中的所有对象增加一个“引用标志位”

　　　　*每次对象被使用时，设置标志位为1

　　　　*新对象加入缓存时，设置其标志位为0

　　　　*在淘汰对象时，查看它的标志位。如果为0，则淘汰该对象；如果为1，则设置其标志位为0，重新加入队列末尾。　　　　　　　　　

五、LRU(Least recently Used)

　　1、算法思想

　　LRU算法的核心思想是基于“如果数据最近被访问过，它在未来也极有可能访问过”。因此如果数据的变化趋势符合这个思想，效果会比较好。

　　2、工作原理

　　　　(1)数据结构：链表，用于保存需要缓存的数据；HashMap，用来读取缓存中的数据，保证时间复杂读为O(1)

　　　　(2)实现：

　　　　当数据读取时，有两种情况：

　　　a、数据在缓存中，则把该数据从新移到链表头部

　　　b、数据不在缓存中，则把数据插入到链表中。

　　　　如何插入：

　　　a、如果链表不满，则把数据插入链表头部

　　　b、如果链表满了，则把尾部的数据删除，同时把其插入链表头部

六、参考文献

　　Page replacement algorithm

　　The Second Chance Page Replacement Policy

　　The Not Recently Used Page Replacement Algorithm

　　Operating Systems Virtual Memory Paging

　   Page Replacement Algorithms

缓存淘汰算法系列(一)