LRU算法的实现

什么是LRU算法? LRU是Least Recently Used的缩写，即最近最少使用页面置换算法，是为虚拟页式存储管理服务的。

关于操作系统的内存管理，如何节省利用容量不大的内存为最多的进程提供资源，一直是研究的重要方向。而内存的虚拟存储管理，是现在最通用，最成功的方式——在内存有限的情况下，扩展一部分外存作为虚拟内存，真正的内存只存储当前运行时所用得到信息。这无疑极大地扩充了内存的功能，极大地提高了计算机的并发度。虚拟页式存储管理，则是将进程所需空间划分为多个页面，内存中只存放当前所需页面，其余页面放入外存的管理方式。

然而，有利就有弊，虚拟页式存储管理减少了进程所需的内存空间，却也带来了运行时间变长这一缺点：进程运行过程中，不可避免地要把在外存中存放的一些信息和内存中已有的进行交换，由于外存的低速，这一步骤所花费的时间不可忽略。因而，采取尽量好的算法以减少读取外存的次数，也是相当有意义的事情。

对于虚拟页式存储，内外存信息的替换是以页面为单位进行的——当需要一个放在外存的页面时，把它调入内存，同时为了保持原有空间的大小，还要把一个内存中页面调出至外存。自然，这种调动越少，进程执行的效率也就越高。那么，把哪个页面调出去可以达到调动尽量少的目的？我们需要一个算法。

自然，达到这样一种情形的算法是最理想的了——每次调换出的页面是所有内存页面中最迟将被使用的——这可以最大限度的推迟页面调换，这种算法，被称为理想页面置换算法。可惜的是，这种算法是无法实现的。

为了尽量减少与理想算法的差距，产生了各种精妙的算法，最近最少使用页面置换算法便是其中一个。LRU算法的提出，是基于这样一个事实：在前面几条指令中使用频繁的页面很可能在后面的几条指令中频繁使用。反过来说，已经很久没有使用的页面很可能在未来较长的一段时间内不会被用到。这个，就是著名的局部性原理——比内存速度还要快的cache，也是基于同样的原理运行的。因此，我们只需要在每次调换时，找到最近最少使用的那个页面调出内存。这就是LRU算法的全部内容。

如何用具体的数据结构来实现这个算法？

首先，最容易想到，也最简单的方法：计时法。给页表中的每一页增加一个域，专门用来存放计时标志，用来记录该页面自上次被访问以来所经历的时间。页面每被访问一次，计时清0。要装入新页时，从内存的页面中选出时间最长的一页，调出，同时把各页的计时标志全部清0，重新开始计时。

计时法可以稍作改变，成为计数法：页面被访问，计数标志清0，其余所有内存页面计数器加1；要装入新页时，选出计数最大的一页调出，同时所有计数器清0。

这两种方法确实很简单，但运行效率却不尽如人意。每个时刻，或是每调用一个页面，就需要对内存中所有页面的访问情况进行记录和更新，麻烦且开销相当大。

另一种实现的方法：链表法。

操作系统为每个进程维护一条链表，链表的每个结点记录一张页面的地址。调用一次页面，则把该页面的结点从链中取出，放到链尾；要装入新页，则把链头的页面调出，同时生成调入页面的结点，放到链尾。

链表法可看作简单计时/计数法的改良，维护一个链表，自然要比维护所有页面标志要简单和轻松。可是，这并没有在数量级上改变算法的时间复杂度，每调用一个页面，都要在链表中搜寻对应结点并放至链尾的工作量并不算小。

以上是单纯使用软件实现的算法。不过，如果能有特殊的硬件帮忙，我们可以有更有效率的算法。

首先，如果硬件有一个64位的计数器，每条指令执行完后自动加1。在每个页表项里添加一个域，用于存放计数器的值。进程运行，每次访问页面的时候，都把计数器的值保存在被访问页面的页表项中。一旦发生缺页，操作系统检查页表中所有的计数器的值以找出最小的一个，那这一页就是最久未使用的页面，调出即可。

其次，另外一个矩阵算法：在一个有n个页框的机器中，LRU硬件可以维持一个n*n的矩阵，开始时所有位都是0。访问到第k页时，硬件把k行的位全设为1，之后再把k列的位置设为0。容易证明，在任意时候，二进制值最小的行即为最久未使用的页面，当调换页面时，将其调出。

以上的两种算法，无疑都要比纯粹的软件算法方便且快捷。每次页面访问之后的操作——保存计数器值和设置k行k列的值，时间复杂度都是O(1)量级，与纯软件算法不可同日而语。

那是否软件算法就毫无用处？当然不是，硬件算法有它致命的缺陷，那就是需要硬件的支持才能运行。如果机器上恰好有所需硬件，那无疑是再好不过；反之，若机器上没有这种硬件条件，我们也只能无奈地抛弃硬件算法，转而选取相对麻烦的软件算法了。

最后，让我们来谈论一下LRU算法。首先，这是一个相当好的算法，它是理想算法很好的近似。在计算机系统中应用广泛的局部性原理给它打造了坚实的理论基础，而在实际运用中，这一算法也被证明拥有极高的性能。在大规模的程序运行中，它产生的缺页中断次数已很接近理想算法。或许我们还能找到更好的算法，但我想，得到的收益与付出的代价恐怕就不成比例了。当然，LRU算法的缺点在于实现方法的不足——效率高的硬件算法通常在大多数机器上无法运行，而软件算法明显有太多的开销。与之相对的，FIFO算法，和与LRU相似的NRU算法，性能尽管不是最好，却更容易实现。所以，找到一个优秀的算法来实现LRU，就是一个非常有意义的问题