【概述】

在进程运行过程中，若访问的页面不在内存，且调入时内存已无空闲空间，那么需要将内存中的一页程序或数据调到外存

页面置换算法就是选择换出哪些页面的算法，其好坏直接影响系统的性能，因此其应具有较低的缺页率

$缺页率 = \frac{缺页次数(页面调入次数)}{页面总使用次数}$

【最佳置换算法】

最佳置换（Optimal，OPT）算法是一种理想化的算法，其具有最好的性能，但实际上无法实现，因此常将最佳置换算法来作为标准，去评价其他置换算法的优劣

最佳置换算法所选择的被淘汰页面将是以后不再使用的页面，或者是在最长时间内不再被访问的页面

由于被淘汰的页面在较长时间内不再被选用，因此可以获得最低的缺页率，但由于无法预知进程未来的运行情况，因此无法实现

【先进先出置换算法】

先进先出（First Input First Output，FIFO）算法，总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面进行淘汰

该算法实现简单，只需要将进程调入内存的页面按先后次序组织成一个队列，再设置一个替换指针，使其总是指向队首即可

但与进程实际运行规律不适应，因为较早调入的页往往是经常被访问的页，频繁的对换会造成运行性能的降低

【最近最久未使用置换算法】

最近最久未使用（Least Recently Used，LRU）算法，根据页面调入内存后的使用情况进行决策，总是淘汰最近最久未使用的页面

该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间 $t$

访问页面时，若页面在物理块中，当前页面的 $t$ 清零，其他页面的 $t$ 递增；若页面不在物理块中，即需要淘汰一个页面时，选择现有页面中 $t$ 最大的进行淘汰，新进入的页面 $t$ 置为 $0$，其他页面的 $t$ 递增

LRU 算法是利用最近的过去作为最近的将来近似，但页面过去和未来的走向间没有必然的联系，此外，该算法需要较多的硬件支持，利用寄存器或栈来保存哪页是最近最久未使用的页面

【最少使用置换算法】

最少使用（Least Frequently Used，LFU）算法，在每页设置访问计数器，每当页面被访问时，该页面的计数器值 $+1$，缺页中断时，淘汰计数值最小的界面，并将所有计数清零

LFU 算法计数的实现类似 LRU 算法，同样可利用移位寄存器

【轮转置换算法】

概述

虽然 LRU 是一种较好的算法，但由于其要求有较多的硬件支持，使得其实现成本较高，因此在实际应用中，大多采用 LRU 的近似算法。

轮转（Clock）算法，又称最近未使用（Not Recently Used，NRU）算法，是最常用的一种 LRU 的近似算法，通过循环地检查各页面的使用情况来进行页面的置换

简单轮转置换算法

简单轮转算法在每页设置一个初始为 $0$ 的访问位，当某页被访问时，将其置为 $1$

当需要进行页替换时，检查页的标志位：

如果访问位是 $0$：就将该页换出
如果访问位是 $1$：则重新将其置 $0$，暂不换出，给予该页第二次驻留内存的机会

同时，按照 FIFO 算法检查下一个页面，当检查到队列中最后一个页面时，若其访问位仍为 $1$，则返回到队首去检查第一个页面。

改进型轮转置换算法

在将一个页面换出时，若该页已被修改过，需将该页重新写回磁盘上，若该页未被修改过，则不必将其写回磁盘

因此，对于修改过的页面，在换出时所付出的开销比未修改过的页面大，简单来说，修改过的页面置换代价大

在改进型的轮转置换算法中，为减少因修改造成的频繁 I/O 操作，每页除了考虑页面的使用情况外，还须考虑置换代价，即除访问位 $A$ 外，再增加一个修改位 $M$

由访问位 $A$ 和修改位 $M$ 可组合成下面四种类型的页面：

$A=0，M=0$ 时：该页最近既未被访问，又未被修改，是最佳淘汰页
$A=0，M=1$ 时：该页最近未被访问，但已被修改，不是很好的淘汰页
$A=1，M=0$ 时：该页最近已被访问，但未被修改，可能再被访问
$A=1，M=1$ 时：该页最近已被访问，且被修改，可能再被访问

在内存中的每个页，必定是这四类页面之一，在进行页面置换时，可采用与简单轮转置换算法相似的操作，差别仅在于需同时检查访问位与修改位，以确定该页是四类页面中的哪一种，执行过程如下：

从指针所指位置开始，扫描循环队列，寻找 $A=0$ 且 $M=0$ 的页面，将所遇到的第一个页面作为被选中的淘汰页，在扫描期间不改变访问位 $A$
若第一次扫描失败，开始第二次扫描，寻找 $A=0$ 且 $M=1$ 的页面，将所遇到的第一个页面作为被选中的淘汰页，在扫描期间将访问位 $A$ 置为 $0$
若第二次扫描失败，由于此时所有的访问位 $A$ 都置为 $0$，因此一定存在 $A=0,M=0$ 或 $A=0,M=1$ 的情况，再次重复第一次、第二次扫描过程

【页面缓冲算法】

页面缓冲算法（Page Buffering Algorithm，PBA），在不需要硬件的支持的情况下，弥补了 FIFO 可能带来的 I/O 开销

其仍用 FIFO 算法选择被置换页，但不将其马上换入外存，而是根据页面是否被修改，放入相应链表：若页面未被修改，放入空闲页面链表，若页面已被修改，放入已修改页面链表

在需要调入新的物理页时，将新页面内容读入到空闲页面链表的第一项所指的页面，然后将第一项从空闲链表摘下

空闲页面和已修改页面，仍停留在内存中一段时间，如果这些页面被再次访问，只需较小开销，而被访问的页面可以返还作为进程的内存页

当已修改页面达到一定数目后，再将它们一起调出到外存，然后将它们归入空闲页面链表，从而减少 I/O 操作的次数

【访问内存的有效时间】

与基本分页存储管理不同，在请求分页管理方式中，内存有效访问时间不仅要考虑访问页表和访问实际物理地址数据的时间，还要考虑缺页中断处理的时间

在快表机制的请求分页管理中，存在下面三种方式的内存访问操作，其有效访问时间的计算公式也有所不同：

1.被访问页在内存，对应表项在快表中

此时不存在缺页中断情况，内存的有效访问时间 EAT 简单的分为查找快表的时间 $\lambda$ 与访问实际物理地址的时间 $t$，即：

$EAT = \lambda + t$

2.被访问页在内存中，对应表项不在快表中

此时不存在缺页中断情况，但需要两次访问内存，一次读取页表，一次读取数据，另外还需更新快表。因此，这种情况的内存有效访问时间 EAT 分为查找快表的时间 $\lambda$、查找页表的时间 $t$、修改快表的时间 $\lambda$、访问实际物理地址的时间 $t$，即：

$EAT = \lambda + t + \lambda + t = 2(\lambda + t)$

3.被访问页不在内存中

当被访问页不在内存中，需要进行缺页中断处理。因此，这种情况的内存有效访问时间 EAT 分为查找快表的时间 $\lambda$、查找页表的时间 $t$、处理缺页中断的时间 $\epsilon$ ，修改快表的时间 $\lambda$、访问实际物理地址的时间 $t$，即：

$EAT = \lambda + t + \epsilon + \lambda + t = 2(\lambda + t) + \epsilon$

上述的三种情况并没有考虑到快表的命中率与缺页率，设快表的命中率为 $a$，缺页率为 $f$，那么内存有效访问时间为：

$EAT = \lambda + at +(1-a)(t+f( \epsilon + \lambda + t)+(1-f)(\lambda+t))$

若不考虑命中率 $a$，仅考虑缺页率 $f$，即 $\lambda =0,a=0$ 时，设缺页中断处理时间为 $\phi$，那么内存有效访问时间为：

$EAT = t + f(\phi + t) + (1 - f) t$

Alex_McAvoy

请求分页存储管理方式的页面置换算法