第六章 局部页面置换算法
页面置换算法概述
根据页面置换算法可借用的外界条件，将页面置换算法分为局部页面置换算法：置换页面的选择范围仅限于当前进程占用的内存页面，全局页面置换算法：置换页面的选择范围是所有可换出的内存页面(并不是所有的内存页面都可以换出内存，比如内核关键代码所在内存页面；因此对这些页面，会将其页表项的锁定位置1，从而操作系统在换出内存页面时就不会考虑这些页面)。
局部页面置换算法
下面介绍三种理论上的局部页面置换算法。
最优算法：将未来最长时间不访问的页面换出内存；缺页次数最少，但是无法实现。用来评价其他置换算法的效率。
先进先出算法：将在内存中驻留时间最长的页面进行置换。易于实现，但是效率很低；甚至会出现Belady现象。
最近最久未使用算法：将内存中最长时间未被引用的页面进行置换。
实际实现的算法在上述置换算法的基础上做一些折中，使得既易于实现，效率又不是太差。
时钟置换算法
- 各页面组成环形链表，指针指向最先调入的页面；
- 若要访问的页面在内存中，则将页面对应页表项的A位置1；
- 若要访问的页面不在内存中，从指针处开始顺序查找，对于访问过的页面，将页面对应页表项的A位置0；直到找到A位为0的页面(可以想一下此时A位为0与页面未被访问过的区别)，这就是可以置换的页面；
如下是一个使用时钟置换算法进行内存分配的例子：
改进的时钟置换算法
由于置换修改过的内存页面需要将该页面的数据写到外存，然后再从外存中读取要换入的页面；这样缺页中断的处理时间几乎是置换未被修改的内存页面的两倍(指令执行的时间可以忽略不计，主要是读取数据的时间)；因此，为了提高缺页中断处理的效率，操作系统应该避免在缺页时置换修改过的内存页面，而是在另外合适的时机将修改过的内存页面的数据写入外存对应位置。
因此有了改进的时钟置换算法，相比于经典的时钟置换算法，操作系统在内存页面分配，访问，置换时还要再对页表项的D位进行维护；
最不常用置换算法
发生缺页时，置换访问次数最少的内存页面；
Belady现象
在给进程分配的内存页面数目增加之后，使用某个(局部)页面置换算法反而使得发生缺页的次数增加，这一现象称为Belady现象。而先进先出算法就具有Belady现象，下面举例说明。
| FIFO | 1 | 2 | 3 | 4 | 1 | 2 | 5 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 尾部 | 1 | 2 | 3 | 4 | 1 | 2 | 5 | 5 | 5 | 3 | 4 | 4 |
| 1 | 2 | 3 | 4 | 1 | 2 | 2 | 2 | 5 | 3 | 3 | ||
| 头部 | 1 | 2 | 3 | 4 | 1 | 1 | 1 | 2 | 5 | 5 | ||
| 缺页状态 | √ | √ | √ | √ | √ | √ | √ | √ | √ |
此时缺页9次；如果分配4个内存页面：
| FIFO | 1 | 2 | 3 | 4 | 1 | 2 | 5 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 尾部 | 1 | 2 | 3 | 4 | 4 | 4 | 5 | 1 | 2 | 3 | 4 | 5 |
| 1 | 2 | 3 | 3 | 3 | 4 | 5 | 1 | 2 | 3 | 4 | ||
| 1 | 2 | 2 | 2 | 3 | 4 | 5 | 1 | 2 | 3 | |||
| 头部 | 1 | 1 | 1 | 2 | 3 | 4 | 5 | 1 | 2 | |||
| 缺页状态 | √ | √ | √ | √ | √ | √ | √ | √ | √ | √ |
此时缺页10次，分配的内存页面增加，而缺页的次数增加。
最优算法无Belady现象。