常用的4种页面置换算法：先进先出法、最佳置换法、最近最少使用置换法和最近未使用置换法

（一）页面置换概念

如果被访问的页不在内存，则产生缺页中断。操作系统进行中断处理，把该页从外存调入内存，这就是页面置换。如果内存中有空闲块，则可把该页装入任何空闲块中，调整页表项及存储分块表。如果当前内存空间已装满，此时必须先淘汰已在内存的一页，腾出空间，再把所需页面装入，这个淘汰页面的算法就是页面置换算法。

（1）页面置换过程

页面置换的工作流程如图所示，主要包括以下4个步骤：

第1步：找出所需页面在磁盘上的位置。

第2步：找出一个空闲内存块。如果有空闲块，就用它；如果没有空闲块，就用页面置换算法选择一个可置换的内存块，把该页写到磁盘上，并相应地修改页表和存储块表。

第3步：把所需页面读入刚刚得到的内存空闲块，修改页表和存储块表。

第4步：重新启动该用户进程。

（2）页面走向

置换算法的好坏直接影响系统的性能。若采用的置换算法不合适，可能出现这样的现象：刚被换出的页，很快又被访问，为把它调入而换出另一页，之后又访问刚被换出的页，……如此频繁地更换页面，以致系统的大部分时间花费在页面的调度和传输上。此时，系统好像很忙，但实际效率却很低。这种现象称为“抖动”。

好的页面置换算法能够适当降低页面更换频率（减少缺页率），尽量避免系统“抖动”。

为评价一个算法的优劣，可将该算法应用于一个特定的存储访问序列（也叫页面走向）上，并且计算缺页数量。

（二）先进先出法

实现思想：这是最简单的页面置换算法。这种算法总是淘汰在内存中停留时间最长的一页，即先进入内存的页，先被换出。理由是最早调入内存的页不再被使用的可能性要大于刚调入内存的页。这种算法把一个进程所有在内存中的页按进入内存的次序排队，淘汰页面总是在队首进行。如果一个页面刚被放入内存，就把它插在队尾。

优点：容易理解且方便程序设计。

缺点：一是性能不好。仅当按线性顺序访问地址空间时，这种算法才是理想的；否则，效率不高。因为那些常被访问的页，往往在内存中停留最久，结果它们因变“老”而不得不被淘汰出去。

二是 缺页率随内存块增加而增加。导致这种异常现象的页面走向实际上是很罕见的，称为Belady现象。

（三）最佳置换法

实现思想：最佳置换算法是1966年由Belady提出的一种算法。其实质是：为调入新页面而必须预先淘汰某个老页面时，所选择的老页面应在将来不被使用，或者是在最远的将来才被访问。采用这种算法，能保证有最小缺页率。

优点：这种算法使得缺页中断次数最小。

缺点：在实现上有困难，因为它需要预先知道一个进程整个运行过程中页面走向的全部情况。

（四）最近最少使用置换法

实现思想：先进先出算法FIFO和最佳置换算法OPT之间的主要差别是，FIFO算法将页面进入内存后的时间长短作为淘汰依据，而OPT算法是依据今后使用页面的时间。如果以“最近的过去”作为“不久将来”的近似，就可以把最近最长一段时间里不曾使用的页面淘汰掉。

它的实质是：当需要置换一页时，选择在最近一段时间里最久没有使用过的页面予以淘汰。这种算法称为最近最少使用算法。

LRU算法与每个页面最后使用的时间有关。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间t，当必须淘汰一个页面时，LRU算法选择现有页面中t值最大的那个页面。

优点：LRU算法经常被采用，被认为是相当好的页面置换算法。

缺点：LRU算法需要实际硬件的支持，如计算器、栈等，来记录页面的最后访问时间，同时也需要一定的软件开销。

（五）最近未使用置换法

实现思想：最近未使用算法是LRU算法的近似方法，它比较易于实现，开销也比较少。

其基本思想是：它在存储块表的每一表项中增加一个“引用位”，标示该页最近的使用情况：1表示被访问过；0表示未被访问过。当某一页被访问时，由硬件将该位置1。操作系统定期地检查这些位，如果是1，表示对应页最近被使用过，不被淘汰，但是要把它置为0；如果是0，表示对应页自上次检查之后还未使用过，我们就把这种在最近一段时间里未被访问过的页淘汰出去。

NRU算法