简谈计算机操作系统中几种页面置换算法比较

论文导读：
【摘要】在计算机操作系统的进程运转过程中，若被访问的页面不在内存时，就产生缺页中断。所以，计算机操作系统中页面置换算法的好坏会直接影响系统的性能。本文对几种典型的置换算法通过实例计算中断次数来进行了比较。
【关键词】计算机操作系统 置换算法 缺页
2095-3089（2014）11-0220-02
在操作系统的进程运转过程中，若被访问的页面不在内存时，就产生缺页中断。这时，操作系统进行中断处理，把该页从外存调入内存。那么新调进的页到底放在什么地方呢？如果内存中有空闲块，则可把该页装入任何空闲块中。那么，内存中没有空闲空间时，怎么办？那么必须先淘汰已在内存的一页，腾出空间，再把所需页面装入。但是这要有一定的策略，这也是“算法”。我们叫做页面置换算法。置换算法的好坏直接影响系统的性能。若采用的算法不适当，会产生“抖动”现象。即：刚被换出的页，很快又被访问，又需将它调入而将另一页换出；而刚被换出的另一页不久又被访问，还需把它调入。以致系统的大部分时间花费在页面的调度和传输上。这时，实际上系统的效率很低，只是在“白忙活”。

一、操作系统中常用的几种置换算法

(一)先进先出法（FIFO）

它是最简单的页面置换算法。这种算法总是淘汰在内存中停留时间最长的一页，即先进入内存的页，先被换出。这种算法把一个进程所有在内存中的页按进入内存的次序排序，淘汰页面总是在队首进行。刚被调入内存的那一页插在队尾。
举个例子：
比如有下述页面走向：1，2，3，4，2，1，5，6，2，1，2，3，7，6，3，2，1，2，
3，6。当内存块数量分别为3时，我们算一算使有此策略时产生的缺页次情况。（注意，所有内存块最初都是空的，凡第一次用到的页面都产生一次缺页。）
解：当内存块数量分别为3时，FIFO算法的执行过程如下图所示。
打叉的表示发生了缺页，共缺页16次。
随便一个内存块时，比如说当内存块数量为5时，同样策略计算出共缺页10次。算法的执行过程如下。

(二)最佳置换法（OPT）

最佳置换算法（OPT）在为调入新页面而必须预先淘汰某个老页面时，所选择的老页面应在将来不被使用，或者是在最远的将来才被访问。采用这种算法，能保证有最小缺页率。
举例说明一下：
还是使用上述页面走向：1，2，3，4，2，1，5，6，2，1，2，3，7，6，3，2，
1，2，3，6。当内存块数量分别为3时，看一看最佳置换法（OPT）的缺页次数是多少？（注意，所有内存块最初都是空的，凡第一次用到的页面都产生一次缺页。）
解：当内存块数量分别为3时，OPT算法的执行过程如下图所示。
打叉的表示发生了缺页，共缺页11次。
再看看比如当内存块数量为5时，同样策略算出共缺页7次。OPT算法的执行过程如下。

(三)最近最少使用置换法（LRU）

最近最少使用置换法（LRU）是选择在最近一段时间里最久没有使用过的页面予以淘汰。借鉴FIFO算法和OPT算法，以“最近的过去”作为“不久将来”的近似。
还是拿同样页面走向来举例说明一下：1，2，3，4，2，1，5，6，2，
1，2，3，7，6，3，2，1，2，3，6。当内存块数量分别为3时，看一看最近最少使用置换法（LRU）的缺页次数。（注意，所有内存块最初都是空的，凡第一次用到的页面都产生一次缺页。）
解：当内存块数量分别为3时，LRU算法的执行过程如下图所示。
打叉的表示发生了缺页，共缺页15次。
再当内存块数量为5，可算出共产生缺页8次。LRU算法的执行过程如下。

二、几种算法的比较

(一)先进先出法（FIFO）

先进先出置换算法简单易于实现、容易理解和进行程序设计，但是性能不好，拿上述例子来看：存在Belady现象。这种算法仅当按线性顺序访问地址空间时才是理想的；否则，效率不高。因为那些常被访问的页，往往在内存中也停留得最久，结果它们因变“老”而不得不被淘汰出去。

(二)最佳置换法（OPT）

同样的页面走向来看，当内存块为3时，产生了11次。比使用先进先出法（FIFO）时，缺页率减少了25%。减少了缺页率固然是好的算法，但是实际中由于OPT算法需要预先知道一个进程在整个运转过程中页面走向的全部情况，因此只是一种理想状态，实际是行不通的。不过这个算法可用来衡量（如通过模拟实验分析或理论分析）其他算法的优劣。

(三)最近最少使用置换法（LRU）

最佳置换算法在实际中行不通，于是我们找到了与它接近的算法——就是最近最少使用置换法。FIFO算法与OPT算法之间的主要差别是：FIFO算法将页面进入内存后的时间长短作为淘汰依据，而OPT算法是依据今后使用页面的时间。那么LRU就是将以“最近的过去”作为“不久的将来”的近似，把最近最长一段时间里不曾被使用的页面进行淘汰。所以，LRU算法是经常采用的页面置换算法。但是，实现LRU算法需要实际硬件的支持。这需要一定的开销。所以，如果我们想减少开销的话，也可以设计一个最近未使用算法。它是LRU的近似算法。它比较易于实现，开销也比较小。
总之，一个好的置换算法会影响到系统的性能。所以选择一个好的算法是很重要的。
参考文献：
[1]孟庆昌主编：操作系统 广播电视大学出版社，2008.
[2]吴企渊：计算机操作系统 清华大学出版社，2006.
[3]侯炳辉：信息管理系统 广播电视大学出版社 2001. 全文地址：www.7ctime.com/jsjwlyylw/lw43441.html上一论文：阐释提升《计算机网络》课堂教学效能对策的实践