[使用矩阵实现LRU的页面置换算法] 置换矩阵算法

　　摘 要：操作系统的内存管理一直是计算机领域研究的一个重要方向。文中分析了几种常用内存管理中的页面置换算法及其存在的问题，提出了LUR页面置换算法的操作系统内存管理中比较接近理想算法的一种页面置换算法，并阐述了使用矩阵方法实现该页面置换算法的原理。
　　关键词：页面置换；LRU；矩阵；内存管理
　　中图分类号：TP316 文献标识码：A 文章编号：2095-1302(2012)08-0053-02
　　Realization of LRU page-replacement algorithm using matrix
　　DU Ya-li
　　(College of Information Engineering, Longdong University, Qingyang 745000, China)
　　Abstract: Memory management of operating system is a very important research direction in computer science field. In the paper, several widely-used page-replacement algorithms are introduced and their advantages/disadvantages are analyzed. The research indictaes that LRU page-replacement algorithm is very close to the ideal one in memory management of operating system. Based on this, the principle of matrix method, which is used to realize the LRU algorithms, is introduced and discussed in detail.
　　Keywords: page replacement; LRU; matrix; memory management
　　0 引 言
　　操作系统的内存管理一直是计算机领域研究的一个重要方向，而内存的虚存管理是存储管理的核心。其原因在于内存的价格昂贵，用大量的内存存储所有被访问的程序与数据段是不可能的；而外存尽管访问速度较慢，但价格便宜，适合于存放大量的信息。因此，在内存有限的情况下，扩展一部分外存作为虚拟内存，真正的内存只存储当前运行时所用得到的信息，这无疑可以大大扩充内存的功能，并大大提高计算机的并发度。虚拟页式存储管理，就是将进程所需空间划分为多个页面，内存中只存放当前所需页面，其余页面放入外存的管理的一种假内存扩充方式。在程序执行时，如果发现要访问的页面不在内存，则系统将产生缺页中断。缺页中断服务程序将负责把位于磁盘上的数据加载到物理内存。
　　虚拟页式存储管理虽然在某些程度上可以减少进程所需的内存空间，但同时也会带来运行时间变长的问题。进程在运行的过程中，不可避免地要把在外存中存放的一些信息和内存中已有的数据进行交换，由于内外存运行速度的差异，这一步骤所花费的时间一般不可忽略，因而必须采取尽量好的算法来减少读取外存的次数。
　　对于虚拟页式存储，内外存信息的替换是以页面为单位进行的。当需要一个放在外存的页面时，系统便把它调入内存，同时又要把内存中的一个页面调出至外存。当然，这种调动越少，进程执行的效率也就越高。那么，把哪个页面调出去就可以达到调动尽量少的目的？操作系统中提出了很多种页面置换算法，LRU(Least Recently Used)最近最少使用页面置换算法就是比较接近理想算法的一种解决方案。
　　1 LRU算法的提出
　　1.1 传统的页面置换算法
　　为了尽量减少与理想算法的差距，现在已经出现了各种精妙的算法，如随机淘汰算法、轮转法(RR)和先进先出算法(FIFO)等，但这几种算法都有着各自的缺点。随机淘汰算法的思想是无法确定哪些页面被访问的概率较低时，随机地选择某个用户的页面并将其换出的一种方法。这种算法的随机性太大，无法达到减少页面调动的目的。轮转法是循回换出内存可用区内一个可以被换出的页，无论该页是刚被换进或已换进内存很长时间。FIFO认为先调入内存的页不再被访问的可能性要比其它页大，因而选择最先调入内存的页并将其换出。但是实验证明，FIFO算法和RR算法的内存利用率都不高，因为这两种算法都是基于CPU按线性顺序访问地址空间这一假设。事实上， CPU不一定是按线性顺序访问地址空间的。FIFO算法的另一个重要的缺点是它会产生Belady现象，即对于一个进程，如果给它分配的页面数增多，缺页次数反而会增加这一奇怪现象。
　　1．2 LRU页面置换算法
　　LRU算法是基于这样一个事实：在前面几条指令中使用频繁的页面也很可能在后面的几条指令中频繁使用。反过来说，已经很久没有使用过的页面很可能在未来较长的一段时间内也不会被用到。这就是著名的局部性原理 。比内存速度还要快的cache，也是基于同样的原理运行的。因此，从程序运行的原理来看，LRU算法是比较接近理想的置换算法。
　　2 LRU算法的实现
　　用矩阵的方法来实现LRU算法的思想是使用矩阵来记录页面使用的频率和时间。设矩阵是n×n维的，n是相关程序当前驻内存的页面数。矩阵的初值为0，每次访问一个页面，例如第i个虚拟页被访问时，可对矩阵进行如下操作：
　　一是将第i行的值全部置1；二是将第i列的值全部置0。
　　在每次需要更换页面时，选择矩阵里对应行值最小的页面。行值是指把此行所有的01代码连起来作为二进制的取值。
　　假如某程序有3个虚拟页面0、1、2，该页面的访问次序是0、1、2、2、1、0、2、1。随着页面的访问，矩阵的状态变换如图1中的(a)～(i)所示。
　　在经过一系列的页面访问之后，行值最小的是第1行，也就是说，虚页面0是最近最少被访问过的页面。如果此时需要替换某个页面，则第0个虚拟页面将被淘汰。
　　当一个页面被访问时，该页面所对应的行值将被置1，这样就保证了该页面对应的行值为最大之一，随后将该页面的对应列值置0，以保证该页面对应的行值为唯一最大。每次访问都将某一列置0，长时间没有被访问的页面，所对应的行元素里面被置0的列个数就越多，即它对应的行值就越小。因此，用矩阵的方法可以实现接近理想算法的页面置换。
　　3 结 语
　　使用矩阵法相比其它页面淘汰算法有其突出的优点，因为可以使用矩阵的理论来迅速判断哪个矩阵行值最小。即：当需要替换掉某一页时，哪个页面将能被最先淘汰掉。使用矩阵来实现LRU的成本也比其它的算法要低，因为矩阵的行列数并不需要虚拟页面数，而是内存的实际页面数，而实际页面数则要小得多。另外，它的缺点是矩阵太大，总的存储位是页面数的平方。
　　参 考 文 献
　　[1]张尧学.计算机操作系统教程[M] .北京：清华大学出版社，2006.
　　[2]徐甲同，方敏.操作系统教程[M ].西安：西安电子科技大学出版社，2005.
　　[3]张剑.虚拟存储管理技术中的淘汰算法[J].安徽教育学院学报，2001.19.(6)：30-34.
　　[4]邹恒明.操作系统之哲学原理[M] .北京：机械工业出版社.2009.
　　[5]张震波，杨鹤标，马振华.基于LRU算法的web系统缓存机制[J].计算机工程，2006.(19)：68-70.
　　作者简介： 杜雅丽 女，1976年出生，甘肃宁县人，讲师。主要从事计算机软件教学与研究。