LRU算法之我见

---

一、LRU算法是什么？

LRU算法又称最近最少使用算法，它是是大部分操作系统为最大化页面命中率而广泛采用的一种页面置换算法。是一种缓存淘汰策略，根据使用频率来淘汰无用信息，使有用信息进行长时间的保留。

二、使用原理

LRU算法须有两类硬件之一的支持：寄存器或栈。
具体流程（个人理解）：
假如我们有这么一个寄存器或栈，头是很久没有访问过的数据，尾是经常访问的数据。我们进行一次访问2的操作，LRU算法会使刚刚访问的元素（也就是2）放到尾部，而后面的元素依次前移。

如果是添加，则会将首元素（也就是1）删除，其余元素依次前移，新元素添加到尾部。

三、代码实现

此处是我做CSAPP的CacheLab中的伪代码

   /*没有空位，使用LRU算法进行替换*/eviction_count++;int evictIndex = 0;int maxTime = 0;for (int i = 0; i < E; i++) {if (cacheSet[i].time > maxTime) {maxTime = cacheSet[i].time;evictIndex = i;}}cacheSet[evictIndex].tag = tagIndex;cacheSet[evictIndex].time = 0;

---

总结

这就是我大概的理解，有点像我平时摞书，最近常看的书放到最顶上，不长看的书就慢慢放到底下了。