ＬＲＵ近似算法的研究
摘 要:计算机内存管理的LRU置换算法在实际使用中需要硬件的支持,因而其应用受到一定限制。为了更加方便地推广应用这种算法,在深入分析LRU算法、特点的基础上,综合利用LRU与SC算法的各自优点,研究了在无硬件支持条件下LRU置换算法的实现技术,给出LRU的近似算法NFU算法的软件实现方法。该近似算法能较好地模拟LRU算法,其应用可提高计算机内存的工作效率。
关键词:内存管理;页面置换;LRU算法;NFU算法
中图分类号:TP31文献标识码:A
文章编号:1004-373X(2009)10-036-03
Study on Approximate Method of LRU Algorithm
LI Fang,XU Li,CHEN Liangliang
(Information Engineering School,Chang′an University,Xi′an,710064,China)
Abstract: LRU algorithm needs the hardware support when applied to manage the memory of the computer,therefore its application is limited to a certian extent.Based on analysis of characteristics of LRU algorithm and SC algorithm,the realization method of LRU without the support of hardware is researched,an approximate algorithm of LRU is given.This approximate algorithm is able to improve the work efficiency of computer memory.
Keywords:memory management;page replacement;LRU algorithm;NFU algorithm
0 引 言
为了进一步提高内存的使用效率,提高用户进程的并发执行程度,在内存管理中广泛使用可变页式存储管理方案。其基本原理是:将用户进程的逻辑空间划分为若干个大小相等的页,内存空间划分成同样大小的相等存储块。当进程请求运行时,为其分配部分内存块,在进程的执行过程中,如果所需访问的页不在内存时,将发生缺页中断,当内存没有足够的存储块时,将内存中暂时不用的页置换出去,以便调入所需访问的页。一种好的置换算法应选择将来不再使用或者在最远的将来才可能被使用的页淘汰,以保证最低的缺页率。因而置换算法的好坏将直接影响到系统的性能。
目前,常用的置换算法有先进先出算法(FIFO)、第二次机会置换算法(SC)、时钟页面置换算法(Clock)、最久未使用算法(LRU)等。其中,LRU算法被认为是一种较好的算法。
1 LRU算法
根据局部性原理,最近一段时间内被访问的页,在往后的一段时间内经常被访问。因此,LRU算法认为:过去“最近一段时间”内没有被访问的页,在“将来的”一段时间内也不会被访问到;当发生缺页时,选择离当前访问时间最久没有被访问的页淘汰。例如,假定给一进程分配3个内存块,并有如下的页引用序列:0,2,5,3,2,4,2,0,3,2,1,3,2,3,4,3。采用LRU淘汰算法时,各页在内存中的变换如图1所示。
从图1中可以看出,对于这样一个引用序列,采用LRU算法将会发生9次缺页,而如果采用FIFO,则会发生12次缺页。从理论上讲LRU是一种较好的算法,但实际的应用中最主要的问题是如何实现这种算法。
2 LRU算法的硬件实现方法
为了实现LRU淘汰算法,需要一个存放内存中所有页的链表,最近使用的页在表头,最久未使用的页在表尾。或给每一个页一个计数器t,用来记录一个页上次被访问以来所经历的时间。当必须淘汰一页时,选择t值最大的淘汰。由于存储器有较高的访问速度,在1 ms内可能对某页连续访问成千上万次,因而,这一计数器需要足够大,并且有较快的访问速度。由此可见,为了实现LRU算法,需要一些特殊的硬件支持。
下面是两种可行的方法。
(1) 计数器法。
这种方法要求系统中有一个64位的硬件计数器C,它在每次执行完指令后自动加1,而进程的每个页表项必须有一个足以容纳这个计数器的值的域。在每次访问内存后,当前的C值存放到被访问的页的页表项中。当发生缺页时,操作系统检查页表中所有计数器的值,这个页就是最久未使用的页\。显然,这种方法除了硬件技术的支持,处理机还要花费时间去读写计数器的值,而且额外增加了页表的长度,将占用更多的内存空间。
(2) 栈。
这种方法可利用一个特殊的栈来保存当前使用的各个页号。每当进程访问某页时,便将该页的页号从栈中移出,将它压入栈顶。因此,栈顶始终是最近新被访问的页号,而栈底则是最近最久未使用的页\。图1所示的引用序列,其访问过程如图2所示。
将一个页移到栈顶是一个非常费时的操作,每次访问页时栈都必须进行这样的更新。因而这种方法将会降低系统的运行速率。
3 LRU算法的软件实现方法
前面介绍的硬件实现LRU算法的系统开销是很大的,并且要有相应的硬件支持,而对于没有这种硬件的系统,这些方法没有多大价值,因而使LRU算法的实际应用受到局限。然而,抛开硬件环境,用软件的方法模拟LRU算法是十分有意义的。一种可能的方案称作是不常使用(Not Frequently Used,NFU)算法\,但此算法只给出了近似LRU算法的一种基本理论,并没有给出具体的实现方法。在此设计了一个用C++描述应用NFU算法的软件实现过程,它使得页面置换在实际应用中更加容易实现和有效。
3.1 NFU算法描述
结合LRU算法的硬件实现技术和 SC算法的基本思想,为每个内存实页设计一个软件移位计数器,以记录每页的访问次数。每页设计一个访问位(R),初值为0,当某页被访问时,其对应页的R位被置1。每次时钟中断时,将移位计数器的值右移1位,同时由系统扫描每页的R位,将每页R位(页的)的值加到对应计数器的第一位中,同时将R位清零。每次发生缺页时,选择计数器值最小者所对应的页淘汰,被淘汰的页就是最近一段时间在内最不经常使用的页。
3.2数据结构
(1) 在可变页式管理中用到的主要数据结构是页表:pt\3.3 页面置换的模拟过程
当进程在运行的过程中,要访问某页x时,系统按下述步骤进行:
(1) 判断x是否在内存,如果在,将对应页的R位置为1,完成相应的地址变换过程;否则,发生缺页中断。主要代码如下:
index=-1;
for(i=0;i
(2) 当发生缺页中断,系统将计算所有的内存实页中的计数器,选择其中值最小的页并返回对应的页号p。代码如下:
int index=0;
int min=reg
(3) 置换相应的页,完成对应数据结构的修改:
pt=\//置换出寄存器中数值最小的对应的页面
pt\//访问位R置1
reg\//对应的计数器值最大
(4) 时钟中断发生时,将寄存器移位中的值移位并加入R的值,最后完成R清零操作。主要代码如下:
for(i=0;i
if(pt\//寄存器中加入R的值
pt\//R清零
} }
通过设置时钟间隔(如20 ms)以及相应参数的设置,执行上述模拟软件,对于图1所示的调页序列,可以得到与图1所示相同的置换图。同时引用文献
4 结 语
经研究表明,LRU置换算法是一种较好的置换算法,但由于其实现需要一定的硬件支持,在使用上具有一定的局限性,而页面置换算法又具有广泛的应用性,如应用到Cache、磁盘缓冲、网页监听、对象管理等场合。因而需要一种能用软件实现的LRU算法。由此给出一个近似LRU的算法的NFU软件实现方法。实验表明,该算法可以较好地仿真LRU算法,使得LRU算法在应用中更加贴近实际,更加有效。
参考文献
[1]汤子瀛.计算机操作系统.西安:西安电子科技大学出版社,2001.
[2]Andrew S Tanenbaum.操作系统设计与实现.王鹏,译.北京:电子工业出版社,1998.
[3]阳小华.基于WWW浏览过程的最近最少使用算法.计算机应用,2000,20(5):19-20,23.
[4]朱平.磁盘缓冲管理机制研究.计算机工程与应用,2004,40(20):47-49,145.
[5]Abranham Silberschatz.Operating Aystem Concepts.北京:高等教育出版社,2002.
[6]阳慧.LRU算法的研究及实现.计算机时代,2004(2):29-30.
[7]孟宪福.基于优先级和LRU算法的持续CORBA对象管理策略研究.大连理工大学学报,2005,45(6):907-911.
[8]吴庆.HLR中的Cache机制及其SLRU替换算法.计算机工程与应用,2002,38(21):76-78.
[9]Wang Hongbo.LRU-based Algorithm for Identifying and Measuring Large Flows.Journal of Electronics and Information Technology,2007,39(10).
[10]Chrobak,Marek.LRU is Better than FIFO.Procee-dings of the Annual ACM-SIAM Symposium on Discrete Algorithms.San Francisco,1998:87-96.
