Page-Replacement Algorithms | 页面置换算法

页面置换策略

在请求分页式管理中，常见的页面置换策略包含了固定分配局部置换，可变分配局部置换，可变分配全局置换这三种方式。

• 固定分配局部置换为每一个进程分配一定数目的主存物理块，在整个运行期间不在改变；缺点是难以为进程分配准确的内存数量。若太少，会频繁出现缺页中断，影响进程性能；若太多，会使内存驻留的进程数据减少，造成内存利用率下降。
• 可变分配局部置换先分配一定数目的内存物理块，运行过程中频繁缺页中断就分配若干附加的物理块，缺页中断次数过少则缩小为该进程分配的物理块，控制缺页中断次数在一个合理的范围。
• 可变分配全局置换是为每一进程分配一定数目的物理 块，保持一个空闲块队列，发生缺页中断则从该队列中取出一块，用完该队列中的物理块采用内存中选择页面进行置换（可能是系统中任一进程的页）。

OPT 最佳置换算法

淘汰的页面是以后永远不再使用或者是将来最长时间内不再被访问的页面。

FIFO 先进先出置换算法

先淘汰最近进入内存的页面（认为刚被调入的页面在最近的将来被访问的可能很大），淘汰在内存中驻留时间最长的页面。Belady 现象：在未给作业分配足够要求的页面数时，分配的物理块数增多，缺页中断次数反而增加；没有考虑程序执行的动态特征。

LRU 最近最久未使用

FIFO 置换算法性能之所以较差，是因为它所依据的条件是各个页面调入内存的时间，而页面调入的先后并不能反映页面的使用情况。最近最久未使用 (LRU) 的页面置换算法，是根据页面调入内存后的使用情况进行决策的。由于无法预测各页面将来的使用情况，只能利用“最近的过去”作为“最近的将来”的近似，因此，LRU 置换算法是选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间 t，当须淘汰一个页面时，选择现有页面中其 t 值最大的，即最近最久未使用的页面予以淘汰。

利用 LRU 算法对上例进行页面置换的结果如下图所示。当进程第一次对页面 2 进行访问时，由于页面 7 是最近最久未被访问的，故将它置换出去。当进程第一次对页面 3 进行访问时，第 1 页成为最近最久未使用的页，将它换出。由图可以看出，前 5 个时间的图像与最佳置换算法时的相同，但这并非是必然的结果。因为，最佳置换算法是从 “ 向后看 ” 的观点出发的，即它是依据以后各页的使用情况；而 LRU 算法则是 “ 向前看 ” 的，即根据各页以前的使用情况来判断，而页面过去和未来的走向之间并无必然的联系。

在一个请求分页系统中，采用 LRU 页面置换算法，一个作业的页面走向为 1、2、3、4、2、1、5、6、2、1、2、3、7、6、3、2、1、2、3、6。当分配给该作业的物理块数为 5 时，在访问过程中所发生的缺页次数为 5 次。

CLOCK 时钟置换算法

当该页被访问时，由硬件将它的引用位信息置为 1；操作系统选择一个时间周期 T，每隔一个周期 T，将页表中所有页面的引用位信息置 0；这样，在时间周期 T 内，被访问过的页面的引用位为 1，而没有被访问过的页面的引用位仍为 0；当产生缺页中断时，可以从引用位为 0 的页面中选择一页调出，同时将所有页面的引用位信息全部重置 0。

淘汰一个页面时，如果该页面已被修改过，必须将它重新写回磁盘；但如果淘汰的是未被修改过的页面，就不需要写盘操作了，这样看来淘汰修改过的页面比淘汰未被修改过的页面开销要大 （1）最近没有被引用，没有被修改（r=0，m=0） （2）最近被引用，没有被修改（r=1，m=0） （3）最近没有被引用，但被修改（r=0，m=1） （4）最近被引用过，也被修改过（r=1，m=1）

周期 T 的确定：T 太大，可能所有的引用位都变成 1，找不出最近最少使用的页面淘汰；T 太小，引用位为 0 的页面可能很多，而无法保证所选择的页面是最近最少使用的

LFU 最近最不常用置换算法

选择被访问次数最少的页面调出，即认为在过去的一段时间里被访问次数多的页面可能经常需要访问；周期 T 的确定：为每一页设置一个计数器，页面每次被访问后其对应的计数器加 1，每隔一定的时间周期 T，将所有计数器全部清零。