页面置换算法就是从若干个候选页面中选择淘汰哪一个页面的一种策略，置换算法的优劣将直接影响系统的效率

不适当的算法可能会导致作业发生一种被称为“抖动”（shaking）的现象，即核心页面被频繁的调入调出，在内存和外存之间跳来跳去，导致系统频繁“缺页”

最佳置换算法（OPT）

其所选择的被淘汰页面，将是以后永不使用或在未来最长时间内不被访问的页面

采用最佳置换算法，可保证获得最低的缺页率

这是幻想中的一种算法，实际并不能实现，因为不能预测未来

例子

假设进程拥有3个内存块，初始状态下内存块为空，进程的页面访问走向为：70120304230321201701。

先进先出页面置换算法（FIFO）

该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰

算法实现简单，只需将主存的页面按调入顺序排列，总是淘汰最老页面

先进先出置换算法最适合“顺序访问”的程序，但是现实里程序往往有循环

例子

最近最久未使用置换算法（LRU）

选择最近最久时间没有被访问过的页面予以淘汰

实际效果最好

内存消耗较大

LRU的硬件支持

（1）寄存器

- 需要给内存里每个页面配置一个移位寄存器，很难给这样一个寄存器

（2）栈

-事实上用队列更好，但是电脑里只有栈，比寄存器容易实现但是计算量大

例子

最少使用页面置换算法（LFU）

哪个使用最少淘汰哪个

在硬件上和LRU效果一样

Clock置换算法

LRU效果较好，但计算历史数据开销很大，因此从性能的角度考虑，在实际应用中通常采用简化版的LRU算法

简单的Clock置换算法

该算法又称最近未用置换算法（NRU）或第二次机会页面置换算法

改进型Clock置换算法

在访问位A的基础上结合修改位M

1类(A=0, M=0): 表示该页最近既未被访问，又未被修改， 是最佳淘汰页

2类(A=0, M=1)： 表示该页最近未被访问， 但已被修改， 并不是很好的淘汰页

3类(A=1, M=0)： 最近已被访问，但未被修改，该页有可能再被访问

4类(A=1, M=1): 最近已被访问且被修改，该页可能再被访问

(1) 从指针所指示的当前位置开始， 扫描循环队列， 寻找A=0且M=0的第一类页面， 将所遇到的第一个页面作为所选中的淘汰页。 在第一次扫描期间不改变访问位A

(2) 如果第一步失败，即扫描一圈后未遇到第一类页面， 则开始第二轮扫描，寻找A=0且M=1的第二类页面，将所遇到的第一个这类页面作为淘汰页。在第二轮扫描期间，将所有扫描过的页面的访问位都置0

(3) 如果第二步也失败，亦即未找到第二类页面，则将指针返回到开始的位置，并将所有的访问位复0。 然后重复第一步，如果仍失败，必要时再重复第二步，此时就一定能找到被淘汰的页

请求分页系统的内存有效访问时间

情况一：被访问页在内存，且其页表项在快表中：

EAT=λ+t

情况二：被访问页在内存，且其页表项不在快表中：

EAT=2×(λ+t)(含修改快表时间λ)

情况三：被访问页不在内存中时：

EAT=ε+2×(λ+t) （含缺页中断处理时间ε）

加上快表命中率a和缺页率f这两因素后:

EAT=λ+a×t+(1-a)×[t+f×(ε+λ+t)+(1-f)×(λ+t)] =λ+t+(1-a)×(λ+f×ε+t)（含缺页中断处理时间ε）

若不考虑命中率(不引入快表)，仅考虑缺页率，即上式中λ=a=0

EAT=t+f×(ε+t)+(1-f)×t=2t+f×ε

注：λ为查快表的时间，t为一次访存所需要的时间，ε为缺页中断处理时间， a为命中率，f为缺页率

其它

#“抖动”现象

在基于虚拟存储器的多道程序环境下，并不是“多道程序度越高，系统吞吐量越大”

当CPU的利用率达到某一峰值后，若继续增加多道程度，将产生抖动

#请求分段系统

(1) 存取方式：系统根据该字段对段实施保护。 (2) 访问字段A：记录该段被访问的频繁度。 (3) 修改位M：记录该段进入内存后是否被修改过。 (4) 存在位P：记录该段是否已调入内存。 (5) 增补位：记录该段是否动态增长。 (6) 外存始址：记录该段在外存的地址。

习题（随堂）

习题（课后）