【操作系统】抖动、缺页中断率、页面置换算法

1、进程分得的主存页框数：页框数多则缺页中断率低，页框数少则缺页中断率高。
2、页面大小：页面大则缺页中断率低，页面小则缺页中断率高。
3、页面替换算法的优劣决定缺页率。
4、程序特性：程序局部性好，则缺页中断率低；否则缺页中断率高。

抖动（颠簸）

在请求分页虚拟存储管理系统中，刚被淘汰的页面立即又要访问，而调入不久即被淘汰，淘汰不久再被调入，如此反复，使得系统的页面调度非常频繁，以致大部分时间消耗在页面调度上，而不是执行计算任务，这种现象称为“抖动”（或者“颠簸”）。

页面置换算法

在这里插入图片描述

1、最佳页面淘汰算法（OPT）

调入一页而必须淘汰一个旧页时，所淘汰的页是以后不再访问的页或距现在最长时间后再访问的页。
OPT可用于衡量各种具体算法的标准。

例：
某程序在内存中分配三个页框，初始为空，页面走向为4，3，2，1，4，3，5，4，3，2，1，5。用最佳页面淘汰算法分析页面置换过程。
在这里插入图片描述
缺页中断率=7/12=58.3%

最佳置换算法可以保证最低的缺页率，但实际上，只有在进程执行的过程中才能知道接下来会访问到的是哪个页面。操作系统无法提前预判页面访问序列。因此，最佳置换算法是无法实现的。

2、先进先出页面淘汰算法（FIFO）

先进先出页面淘汰算法总是淘汰最先调入主存的那一页，或者说在主存中驻留时间最长的那一页（常驻的除外）。

例：
某程序在内存中分配三个页框，初始为空，页面走向为4，3，2，1，4，3，5，4，3，2，1，5。用先进先出页面淘汰算法分析页面置换过程。
在这里插入图片描述
缺页中断率=9/12=75%

缺页中断率=10/12=83.33%

Bel ad y 异常——当为进程分配的物理块数增大时，缺页次数不减反增的异常现象。

只有FIFO算法会产生Bel a d y 异常。另外，FIFO算法虽然实现简单，但是该算法与进程实际运行时的规律不适应，因为先进入的页面也有可能最经常被访问。因此，算法性能差。

页缓冲技术：
FIFO替换算法的一种改进，策略如下：淘汰了的页面进入两个队列——修改页面和非修改页面队列。
修改页面队列中的页不时地成批写出并加入到非修改页面队列；
非修改页面队列中的页面被再次引用时回收，或者淘汰掉以作替换。

3、最近最久未使用页面淘汰算法（LRU）

淘汰的页面是在最近一段时间里较久未被访问的那一页。

例：
某程序在内存中分配三个页框，初始为空，页面走向为4，3，2，1，4，3，5，4，3，2，1，5。用最近最久未使用页面淘汰算法分析页面置换过程。
在这里插入图片描述
缺页中断率=10/12=83.3%

1、最佳置换算法性能最好，但无法实现；
2、先进先出置换算法实现简单，但算法性能差；
3、最近最久未使用置换算法性能好，是最接近OPT算法性能的，但是实现起来需要专门的硬件支持，算法开销大。

4、时钟置换算法（CLOCK）

时钟置换算法是一种性能和开销较均衡的算法，又称CLOCK算法，或最近未用算法(NRU，No t Re ce n tly Used)

简单的时钟置换算法

简单的CLOCK算法实现方法：
① 为每个页面设置一个访问位，再将内存中的页面都通过链接指针链接成一个循环队列。
② 当某页被访问时，其访问位置为1。
③ 当需要淘汰一个页面时，只需检查页的访问位。
如果是0，就选择该页换出；
如果是1，则将它置为0，暂不换出，继续检查下一个页面；
若第一轮扫描中所有页面都是1，则将这些页面的访问位依次置为0后，再进行第二轮扫描（第二轮扫描中一定会有访问位为0的页面，因此简单的CLOCK算法选择一个淘汰页面最多会经过两轮扫描）。

访问位为1，表示最近访问过；
访问位为0，表示最近没访问过。

例：假设系统为某进程分配了五个内存块，并考虑到有以下页面号引用串：1，3，4，2，5，6，3，4，7

步骤：
① 将内存中的页面都通过链接指针链接成一个循环队列；
② 此时所有页访问位都是1，从队首开始扫描，经过第一轮扫描，访问位全部置为0；
③ 1号页访问位为0，淘汰1号页面，6号页装入1号页的内存块中，扫描下一个页面；
④ 扫描到3号页，访问3号页和4号页，命中页面访问位都置为1，扫描指针不变还在上一次置换页面的下一个页面3号页；
⑤ 继续从3号位开始扫描，访问位置为0，到2号页的访问位为0，淘汰2号页面，7号页装入2号页的内存块中，扫描下一个页面。

在这里插入图片描述
每次发生缺页中断，扫描的位置是从上一次置换页面的下一个页面开始扫描。

简单的时钟置换算法仅考虑到一个页面最近是否被访问过。事实上，如果被淘汰的页面没有被修改过，就不需要执行I/0操作写回外存。只有被淘汰的页面被修改过时，才需要写回外存。

改进的时钟置换算法

改进型的时钟置换算法的思想：
除了考虑一个页面最近有没有被访问过之外，操作系统还应考虑页面有没有被修改过。在其他条件都相同时，应优先淘汰没有修改过的页面，避免I/0操作。

修改位=0，表示页面没有被修改过；
修改位=1，表示页面被修改过。

为方便讨论，用(访问位，修改位)的形式表示各页面状态。如(1, 1)表示一个页面近期被访问过，且被修改过。

算法规则：
将所有可能被置换的页面排成一个循环队列
第一轮：从当前位置开始扫描到第一个(0,0)的帧用于替换，本轮扫描不修改任何标志位；
第二轮：若第一轮扫描失败，则重新扫描，查找第一个(0,1)的帧用于替换，本轮将所有扫描过的帧访问位设为0；
第三轮：若第二轮扫描失败，则重新扫描，查找第一个(0,0) 的帧用于替换，本轮扫描不修改任何标志位；
第四轮：若第三轮扫描失败，则重新扫描，查找第一个(0,1) 的帧用于替换。
由于第二轮已将所有帧的访问位设为0，因此经过第三轮、第四轮扫描一定会有一个帧被选中，因此改进型CLOCK置换算法选择一个淘汰页面最多会进行四轮扫描。