福建省福州市鼓楼区福州二中 福建 福州 350001
摘要：随着计算机技术和网络技术的飞速发展，我们每天都要对数据进行高频率的访问。数据通常都是被存在数据库中的，如果每次访问都需要从数据库中查询，这样会对数据库造成极大的压力，缓存机制很好地解决了这个问题。缓存机制是计算机内部一项十分重要的数据运行机制，缓存方式设计的好坏直接影响到计算机存取数据的速度，页面置换算法就是缓存机制很好的体现。本文主要介绍了页面置换算法的思想，重点介绍了三种页面置换算法的实现原理及置换过程，并且对比不同页面置换算法的优缺点。我们在选择使用某种算法时，要了解该算法是否适合我们的需求和业务场景，这样才能够较好地合理地使用算法。
缓存机制被广泛的应用在互联网应用中。缓存机制实际上就是将我们认为将要被使用或者可能被使用的数据事先存放在内存中。这样，当需要获取该数据时，可以从内存中很快的读取该数据而不需要再从硬盘中读取数据，效率大大提升。本文将对缓存机制，特别是页面置换算法的原理进行分析介绍。
1.虚拟内存管理及页面置换介绍
1.1虚拟内存管理
虚拟内存管理也是一种缓存机制，主要被用在执行程序需要的内存大于实际内存这种情况。计算机将实际内存和相对较大的外部存储空间共同构成一个远大于实际内存空间的虚拟内存。虚拟内存将程序执行所需要的存储空间分成若干个页和段，当程序需要某些段或页时，虚拟内存将这些段和页放置在内存中，不需要时，则将其移除到外部的存储空间。
1.2页面置换
在虚拟内存管理中，当需要访问的页面不在内存中，便需要将它放入内存，但因为内存空间有限，不能够无限制地存放页面，所以系统必须从内存中调出其它页面放入硬盘的对换区中，以此保证系统及内存的正常运行。应当将哪一页调出，就必须按照一定的算法来确定，这样的调度算法就被称为页面置换算法【1】。
2.页面置换算法的原理
随着时代的进步，计算机产业正在高速发展。人们使用计算机更加频繁，对于计算机性能的要求也在不断提高。我们希望我们使用互联网应用时能够很快的获取我们希望看到的页面数据。互联网应用为了保证我们的数据能够不被轻易丢失，所以数据都被存放在了数据库中，也可以被认为是被存放在了磁盘中。磁盘的读写速度和内存相比是很慢的，如果我们每次获取数据都从磁盘中去查询，很难较快的获取数据。所以缓存机制是计算机性能中尤为重要的一项，缓存系统设计的好坏将影响计算机存放和读取数据的速度，而速度的快慢则直接决定了用户的体验。有了这样的需求，页面置换算法便应运而生。好的页面置换算法，能让用户访问想要的页面时更加高效，并且能够最合理地选择被淘汰与被放入的页面。目前已经问世的页面置换算法有先进先出（FIFO）置换算法、最近最久未使用（LRU）置换算法以及基于LRU算法衍生出的最近最少使用（LFU）置换算法。下面重点对这三种页面置换算法进行介绍。
2.1先进先出（FIFO，First In First Out）置换算法
FIFO算法是最早出现的置换算法，该算法的原理是：先进入，先淘汰。即在每次需要进行页面置换时，总是优先淘汰进入时间最长的那个页面【2】。设计该算法的理由在于：最早调入内存的页面，其不再被使用的可能性比刚调入内存的可能性大。它既符合数学中的概率思想，又体现出了人类的排队机制。FIFO算法是最简单的置换算法，它的基本思想便是建立一个FIFO队列，每次有页面需要进入内存便将页面由队头依次排至队尾，当需要置换页面时，则将队头的页面淘汰，将新页面放入队尾。在实际应用中，常常设计一个时间量度，用于记录每个页面进入内存的时间，该时间可以用软件记录在内存中，也可设置在寄存器中用硬件记录，当发生缺页中断时，就将进入时间最早的页面调出。
我们假设内存中最多可以存放3个页面，程序需要访问页面的顺序是2，3，3，4，3，6，4，7。
期刊文章分类查询,尽在期刊图书馆
使用FIFO算法，内存页面情况如下：
（1）2
（2）2，3
（3）2，3
（4）2，3，4
（5）2，3，4
（6）3，4，6
（7）4，6，7
FIFO算法虽然较为简单，但是它没有考虑到某些数据可能会被高频率的访问，对于这样的数据，我们应该将它尽可能的保留在我们的内存中，而不是将其与其他页面统一对待。所以FIFO算法在实际的生产中是基本不会被用到的。
2.2 LFU算法(LeastFrequentlyUsed)
相较于FIFO算法，LFU算法综合考虑了被访问的因素，可以解释为最近最不常用页面置换算法【3】。其思想是，在一段时间内，比如5分钟，10分钟内，被访问次数最少的页面会被置换出内存。如果被访问次数相同，则按照FIFO算法的规则执行。LFU算法的实现方法比FIFO算法难一些，使用一个队列已经不能满足，而是需要使用一个二维数组或是一个对象，既要保存数据内容，又要标记该内容在最近某个时间段内被访问的次数。在选取被置换页面时，需要对内存中的页面访问次数进行遍历和对比，找出被访问次数最少的页面，将其置换出内存。
我们同样使用FIFO算法列举的例子，程序需要访问页面的顺序是2，3，3，4，3，6，4，7。我们认为LFU的时间段为5分钟，并且这些访问次数都在5分钟内完成。
使用LFU算法，内存页面情况如下：
（1）2
（2）2，3
（3）2，3
（4）2，3，4
（5）2，3，4
（6）3，4，6
（7）3，4，7
可以看出，FIFO算法的第七步是将3页面置换出了内存，而LFU是将6页面置换出了内存，因为3页面在这段时间内被访问了3次，4页面被访问了2次，而6页面只被访问了1次，所以LFU将6页面置换出了内存。这更符合我们实际生产中想要达到的效果。
但是LFU算法还是存在一些问题的，比如由于时间段的长度设置问题，某些页面被高频访问的页面，在前期被频繁访问，但是在后期访问量较少。如果使用LFU算法，很可能在该页面被访问频率较低的时候被置换出了内存，这样是不太合理的。并且由于实现LFU算法需要使用二维数组或是对象，这样会增加空间资源的消耗。
2.3 LRU算法(LeastRecentlyUsed)
LRU算法也是综合考虑了访问时间和访问次数的因素，可以解释为最长时间未被使用页面置换算法，它的思想较FIFO算法和LFU算法更加合理【4】。
LRU算法理解起来也较为简单，被最新访问的页面会被排在队头，当需要进行页面置换时，会将队尾的页面置换出内存。这样被置换出的页面就是最久未被访问的页面，这样是更加符合现实生活中的需求的。
我们依然使用FIFO算法列举的例子，程序需要访问页面的顺序是2，3，3，4，3，6，4，7。
使用LRU算法，内存页面情况如下：
（1）2
（2）3，2
（3）3，2
（4）4，3，2
（5）3，4，2
（6）4，3，6
（7）4，3，7
我们会发现内存中页面的位置和FIFO和LFU算法差异还是比较大的，LRU解决了我们在LFU小节提出的一个问题，如果某个页面在前期被频繁访问，在某个时候访问次数减少，LRU算法应该是不会将其置换出内存的，因为在前期该页面被高频访问时，该页面在队列中的位置是十分靠前的，所以在低频访问期被置换的概率很小。
LRU也有一定的缺点，就是在每次访问后，都要大量移动页面的位置，对于页面数量较多的内存来说，这也是一个不可忽视的资源消耗。
3.总结与展望
以上介绍了三种常见页面置换算法的原理，实现方法以及各自的优缺点。从研究页面置换算法的过程中我得到了一些启发，当我们要解决一类问题时，可采用的算法很多，但是我们如果想要高效和合理的解决该问题，就需要对算法进行深层次的研究，探究该算法是否适用于我们当前的问题场景，从而找到合适的算法。
参考文献
[1] 殷联甫. 虚拟存储管理中的页面置换算法研究[J]. 嘉兴学院学报, 2004, 16(3):25-27.
[2] 张玲玲, 高林娥. FIFO页面置换算法的实现以及异常问题的讨论[J]. 图书情报导刊, 2010, 20(13):98-100.
[3] 王磊, 孟昭鹏, 刘亚琼. 一种基于LFU置换的BWT压缩算法的改进[J]. 网络新媒体技术, 2008, 29(3):80-83.
[4] 张恒瑞, 王红. Cache替换算法LRU和2Q的深度分析[J]. 现代计算机, 2017(4):17-19.
论文作者:黄昕宇
论文发表刊物:《科技新时代》2019年1期
论文发表时间:2019/3/20
标签：算法论文; 页面论文; 内存论文; 数据论文; 缓存论文; 出了论文; 机制论文; 《科技新时代》2019年1期论文;