C|内存管理|从LRU王国到NRU王国

缓存机制中，当发生页冲突时，操作系统将会调用页面置换算法进行淘汰，而我们这篇文章中重点介绍随机访问情况下效率较高的两种算法。

LRU：Least Recently Used

NRU：Not Recently Used

LRU

LRU淘汰的是最早被使用的Cache，算法可以分为两种实现：

A.时间戳

硬件记录最近一次访问时间，每次淘汰遍历求最早访问的Cache。

B.链表

Algorithm 4th：著名的前移编码策略，假设最近访问过的元素很有可能再次访问,因此可以用于缓存、数据压缩等许多场景。

这里将所有可能被淘汰的Cache用一张线性链表存储，当查询时，每次被查询到的Cache节点将会被移除出链表并且插入表头。如此一来，链表头将会是最新被访问的数据，而链表尾则会被淘汰。

这样一来，淘汰最早访问的Cache则非常方便，代价则是需要链表的结构是可修改的。

在硬件层，这两种实现都具有巨大的开销，因此难以用于实践。

NRU

考虑到LRU实现困难，Clock 页面置换算法（NRU）应运而生。

记录谁最早被使用很难，那么换一种思路，把时间分成一个个周期，如果最近一个周期都没有被使用，那就干脆当做一直没有被使用。

本质上这可以说是一种逆向思维：不一定要最早被使用的被淘汰，只要不是最近被使用的被淘汰就好了。而统计谁最近被使用则成本低廉，只需要在某个时间段清空访问状态，是否新被访问就很容易判断。

如同时钟一般，Clock将所有可能被淘汰的Cache entry用一张环形链表存储，并由页表维护reference bit，时钟的柄（clock hand）作为入口（如果是固定入口的话，会导致靠近入口的entry更容易被淘汰，因此不可取）。

被Cache的页表是物理内存，而非虚拟内存，而MMU负责管理的reference bit在虚拟内存页上。因此实际查找的不仅是一个页，更是一个页链表（一个物理页对应多个虚拟页），只要链表其中有一个ref bit为1，那么整个物理页就被视为新被访问。而置0操作代表将物理页对应的所有虚拟内存页的ref bit置0。

当进行查询时：

Hit：

将虚拟内存页的reference bit设置为1（新被访问）

Miss：

从clock hand开始查找物理页Reference bit为0 的entry 如果物理页Reference bit为1，将物理页对应的所有虚拟内存页的ref bit置0（注意，这里的前移会导致入口变化），指针前移，直到找到为0的entry为止。（清空访问状态） 如果物理页Reference bit 为0， 将数据放入该entry，并将虚拟内存页Reference bit置1。（没有新被访问，所以被淘汰），指针前移，终止。

由于链表环形，因此即使第一圈扫描没有找到Ref bit为0的entry，但由于已经清空了所有对应虚拟内存页Ref bit，因此下一圈依然能够轻易地找到没有新被访问的entry。

从性能上来讲，NRU和LRU差距不大，因此可以作为替代品。

而最主要的是，这种环形链表本身的结构是稳定的，不同于LRU里的节点的反复插入，这里变动的只是页表上存储的Ref Bit，使得其被硬件实现的可能性远远增强。

这使我想起以前上选修课的时候听过的一个例子，在计算机图形学中，反射公式本身运用大量积分计算，这是科研界的职责；而工业界则把这些复杂公式近似成计算效率高但是差距又不大的简单公式，这样才能在配置落后的PC上运行。

对于Cache来说，能找到最早访问的固然好，但是宽容一点，不是最早，但是也很早被访问的被淘汰问题也不大，只要不淘汰最近被访问的破坏locality就好了。而这种近似，是必然存在的对现实的妥协，也是工业界必不可少的生存智慧。