LRU缓存机制

LRU(最近最少使用)缓存机制

LRU：最近最少使用缓存机制

其设计的原则依据：如果一个数据在最近一段时间没有被访问到，那么在将来它被访问的可能性也很小。也就是说，当限定的空间已存满数据时，应当把最久没有被访问到的数据淘汰。
假定系统为某进程分配了3个物理块，进程运行时的页面走向为 7 0 1 2 0 3 0 4，开始时3个物理块均为空，那么LRU算法是如下工作的：

上述操纵通过一个双向链表就可以轻松实现了。
只需要每次将不论是否出现在链表中的值都置于链表的头就可以了，如果链表满了，就将链表的元素移除链表。