LRU 算法的实现
-----Yuconan 整理
什么是 LRU 算法? LRU 是 Least Recently Used 的缩写,即最近最少使用页面置换算法,
是为虚拟页式存储管理服务的。
关于操作系统的内存管理,如何节省利用容量不大的内存为最多的进程提供资源,一直是
研究的重要方向。而内存的虚拟存储管理,是现在最通用,最成功的方式——在内存有限的情
况下,扩展一部分外存作为虚拟内存,真正的内存只存储当前运行时所用得到信息。这无疑极
大地扩充了内存的功能,极大地提高了计算机的并发度。虚拟页式存储管理,则是将进程所需
空间划分为多个页面,内存中只存放当前所需页面,其余页面放入外存的管理方式。
然而,有利就有弊,虚拟页式存储管理减少了进程所需的内存空间,却也带来了运行时间
变长这一缺点:进程运行过程中,不可避免地要把在外存中存放的一些信息和内存中已有的进
行交换,由于外存的低速,这一步骤所花费的时间不可忽略。因而,采取尽量好的算法以减少
读取外存的次数,也是相当有意义的事情。
对于虚拟页式存储,内外存信息的替换是以页面为单位进行的——当需要一个放在外存的
页面时,把它调入内存,同时为了保持原有空间的大小,还要把一个内存中页面调出至外存。
自然,这种调动越少,进程执行的效率也就越高。那么,把哪个页面调出去可以达到调动尽量
少的目的?我们需要一个算法。
自然,达到这样一种情形的算法是最理想的了——每次调换出的页面是所有内存页面中最
迟将被使用的——这可以最大限度的推迟页面调换,这种算法,被称为理想页面置换算法。可
惜的是,这种算法是无法实现的。
为了尽量减少与理想算法的差距,产生了各种精妙的算法,最近最少使用页面置换算法便
是其中一个。LRU 算法的提出,是基于这样一个事实:在前面几条指令中使用频繁的页面很可
能在后面的几条指令中频繁使用。反过来说,已经很久没有使用的页面很可能在未来较长的一
段时间内不会被用到。这个,就是著名的局部性原理——比内存速度还要快的 cache,也是基
于同样的原理运行的。因此,我们只需要在每次调换时,找到最近最少使用的那个页面调出内
存。这就是 LRU 算法的全部内容。
如何用具体的数据结构来实现这个算法?
首先,最容易想到,也最简单的方法:计时法。给页表中的每一页增加一个域,专门用来
存放计时标志,用来记录该页面自上次被访问以来所经历的时间。页面每被访问一次,计时清
0。要装入新页时,从内存的页面中选出时间最长的一页,调出,同时把各页的计时标志全部
清 0,重新开始计时。
计时法可以稍作改变,成为计数法:页面被访问,计数标志清 0,其余所有内存页面计数
器加 1;要装入新页时,选出计数最大的一页调出,同时所有计数器清 0。
这两种方法确实很简单,但运行效率却不尽如人意。每个时刻,或是每调用一个页面,就
需要对内存中所有页面的访问情况进行记录和更新,麻烦且开销相当大。
另一种实现的方法:链表法。
操作系统为每个进程维护一条链表,链表的每个结点记录一张页面的地址。调用一次页面,
则把该页面的结点从链中取出,放到链尾;要装入新页,则把链头的页面调出,同时生成调入
页面的结点,放到链尾。
链表法可看作简单计时/计数法的改良,维护一个链表,自然要比维护所有页面标志要简单
和轻松。可是,这并没有在数量级上改变算法的时间复杂度,每调用一个页面,都要在链表中
搜寻对应结点并放至链尾的工作量并不算小。