第6章：页面置换算法
操作系统
- 功能与目标
- 实验设置与评价方法
- 局部页面置换算法
- 最优页面置换算法（OPT，optional）
- 先进先出算法（FIFO，First-In First-Out）
- 最近最久未使用算法（LRU，Least Recently Used）
- 时钟页面置换算法（Clock）
- 二次机会法
- 最不常用算法（LFU，Least Frequently Used）
- Belady 现象
- LRU、FIFO和Clock的比较
- 全局页面置换算法
（一）功能目标
- 功能：
- 当缺页中断发生，需要调入新的页面而内存已满时，选择内存当中哪个物理页面被置顶
- 目标：
- 尽可能地减少页面的换入换出次数（即缺页中断的次数），具体来说，把未来不再使用的或短期内较少使用的页面换出，通常只能在局部性原理指导下依据过去的统计数据来进行预测
- 页面锁定（frame locking）：
- 用于描述必须常驻内存的操作系统的关键部分或时间关键（time - critical）的应用进程。实现的方法是：在页表中添加锁定标志位（lock bit）
6.1 最优页面置换算法（OPT，optional）
- 基本思路：
- 当一个缺页中断发生时，对于保存在内存中的每一个逻辑页面，计算在它的下一次访问之前，还需等待多长时间，从中选择等待时间最长的那个，作为被置换的页面
- 这只是一种理想情况，在实际系统中是无法实现的，因为操作系统无从得知每一个页面要等待多长时间以后才会再次被访问
- 可用作其他算法的性能评价的依据（在一个模拟器上运行某个程序，并记录每一次页面访问情况，在第二遍运行时即可使用最优置换算法）
6.2 先进先出算法（FIFO，First-In First-Out）
- 基本思路：
- 选择在内存中驻留时间最长的页面并淘汰之。具体来说，系统维护着一个链表，记录了所有位于内存当中的逻辑页面。从链表的排列顺序来看，链首页面的驻留时间最长，链尾页面的驻留时间最短。当发生一个缺页中断时，把链首页淘汰出局，并把新的页面添加到链表的末尾。
- 性能较差，调出的页面有可能是经常要访问的页面，并且有Belady现象，FIFO算法很少单独使用。
6.3 最近最久未使用算法（LRU，Least Recently Used）
基本思路：
- 当一个缺页中断发生时，选择最久未使用的那个页面，并淘汰之。
- 它是对最优页面置换算法的一个近似，其依据是程序的局部性原理，即在最近一小段时间（最近几条指令）内，如果某些页面被频繁地访问，那么在将来的一小段时间内，它们还可能会再一次被频繁地访问。反过来说，如果在过去某些页面长时间未被访问，那么在将来它们还可能会长时间地得不到访问。
- LRU算法需要记录各个页面使用时间的先后顺序，开销较大
两种可能的实现方法是：
- 系统维护一个页面链表，最近刚使用过的页面作为首结点，最久未使用的页面作为尾结点。每一次访问内存时，找到相应的页面，把它从链表中摘下来，再移动到链表之首，如果没有，则直接插入到链表之首。每次缺页中断发生时，淘汰链表末尾的页面。
- 设置一个活动页面栈，当访问某页时，将此页号压入栈顶，然后，考察栈内是否有与此页面相同的页号，若有则抽出。当需要淘汰一个页面时，总是选择栈底的页面，它就是最久未使用的。
6.4 时钟页面置换算法（Clock）
- LRU的近似，对FIFO的一种改进
- 基本思路：
- 需要用到页表项当中的访问位，当一个页面被装入内存时，把该位初始化为0.然后如果这个页面被访问（读/写），则把该位置为1；
- 把各个页面组织成环形链表（类似时钟表面），把指针指向最老的页面（最先进来）；
- 当发生一个缺页中断时，考察指针所指向的最老页面，若它的访问位为0，立即淘汰；若访问位为1，则把该位置为0，然后指针往下移动一格。如此下去，直到找到被淘汰的页面，然后把指针移动到它的下一格。
6.5 二次机会法
- 这里有一个巨大的代价来替换“脏页”
- 修改Clock算法，使它允许脏页总是在时钟头扫描中保留出来
- 同时使用脏位和使用位来指导置换
| used |
dirty |
used' |
dirty' |
| 0 |
0 |
replace page |
|
| 0 |
1 |
0 |
0 |
| 1 |
0 |
0 |
0 |
| 1 |
1 |
0 |
1 |
6.6 最不常用算法（LFU，Least Frequently Used）
- 基本思路：
- 当一个缺页中断发生时，选择访问次数最少的那个页面，并淘汰之。
- 实现方法：
- 对每个页面设置一个访问计数器，每当一个页面被访问时，该页面的访问计数器加1。在发生缺页中断时，淘汰计数值最小的那个页面。
LRU 和 LFU的区别：
- LRU考察的是多久未访问，时间越短越好；而LFU考察的是访问的次数或频率，访问次数越多越好。
问题：
- 一个页面在进程开始时使用得多，但以后就不使用了。实现费时费力。
解决方法：
6.7 Belady现象
Belady现象：
- 在采用FIFO算法时，有时会出现分配的物理页面数增加，缺页率反而提高的异常现象。
原因：
- FIFO算法的置换特征与进程访问内存的动态特征是矛盾的，与置换算法的目标是不一致的（即替换较少使用的页面），因为，被它置换出去的页面并不一定是进程不会访问的。
6.8 LRU、FIFO和Clock的比较
- LRU算法和FIFO本质上都是先进先出的思路，只不过LRU是针对页面的最近访问时间来进行排序，所以需要在每一次访问的时候动态地调整各个页面之间的先后顺序（有一个页面的最近访问时间变了）；而FIFO是针对页面进入内存的时间来进行排序，这个时间是固定不变的，所以各个页面之间的先后顺序是固定的。如果一个页面在进入内存后没有被访问，那么它的最近访问时间就是它进入内存的时间。换句话说，如果内存当中的所有页面都未曾访问过，那么LRU算法就退化为FIFO算法。
- LRU算法性能较好，但系统开销大；FIFO算法系统开销较小，但可能会发生Belady现象。因此，折中的办法是Clock算法，在每一次页面访问时，它不必去动态地调整该页面在链表中的顺序，而仅仅是做一个标记，然后等到发生缺页中断时，再把它移动到链表的末尾，对于内存中那些被访问过的页面，它不能像LRU算法一样，记住它们的准确位置。
6.9 工作集模型
（一）工作集
- defs:
- 一个进程当前正在使用的逻辑页面集合，可以用一个二元函数 w(t,△）来表示
- t 是当前执行时刻
- △ 称为工作集窗口（working-set window），即一个定长的页面访问的时间窗口
- w(t,△）= 在当前时刻t之前的 △ 时间窗口当中的所有页面组成的集合（随着t的变化，该集合也在不断的变化）
- |w(t,△）|指工作集的大小，即页面数目|
（二）常驻集
- defs:
- 是指在当前时刻，进程实际驻留在内存当中的页面集合
- 工作集是进程在运行过程中固有的性质，而常驻集取决于系统分配给进程的物理页面数目，以及所采用的页面置换算法
- 如果一个进程的整个工作集都在内存当中，即常驻集包含（=）工作集，那么进程将很顺利的运行，而不会造成太多的缺页中断（直到工作集发生剧烈变动，从而过渡到另一个状态）
- 当进程常驻集的大小达到某个数目后，再给它分配更多的物理页面，缺页率也不会明显下降
6.10 两个全局页面置换算法
（一）缺页率页面置换算法
- 可变分配策略：
- 常驻集大小可变。例如，每个进程在刚开始运行的时候，先根据程序的大小给它分配一定数目的物理页面，然后在运行过程中，再动态的调整常驻集的大小。
- 可采用全局页面置换的方式，当发生一个缺页中断时，被置换的页面可以是在其他进程当中，各个并发进程竞争地使用物理页面。
优缺点：
具体实现：
- 可以使用缺页率算法（PFF, Page fault frequency)来动态调整常驻集的大小
缺页率：
- 缺页率表示“缺页次数/内存访问次数”（比率）或“缺页的平均时间间隔的倒数”。
影响缺页率的因素：
- 页面置换算法
- 分配给进程的物理页面数目
- 页面本身的大小
- 程序的编写方法
缺页率算法
- 若运行的程序的缺页率过高，则通过增加工作集来分配更多的物理页面
- 若运行的程序缺页率过低，则通过减少工作集来减少它的物理页面数
- 力图使运行的每个程序的缺页率保持在一个合理的范围内
- 一个交替的工作集计算明确的适于最小化页缺失
- 当缺页率高的时候--增加工作集
- 当缺页率低的时候--减少工作集
算法：
- 保持追踪缺失发生概率
- 当缺失发生时，从上次页缺失起计算这个时间记录这个时间，t'last 是上次的页缺失时间
- 如果发生页缺失之间的时间是“大”的，之后减少工作集
- 如果 t'current - t'last > T，之后从内存中移除所有在[t'last,t'current]时间内没有被引用的页
- 如果发生页缺失之间的时间是“小”的，之后增加工作集
- 如果 t'current - t'last <= T，之后增加缺失页到工作集中
6.11 抖动问题(Trashing)
- defs:
- 如果分配给一个进程的物理页面很少，不能包含整个的工作集，那常驻集含于工作集，那么进程将会造成很多的缺页中断，需要频繁地在内存到外存之间替换页面，从而使进程的运行速度变得很慢，我们把这种状态称为“抖动”。
产生抖动的原因：
- 随着驻留内存的进程数目增加，分配给每个进程的物理页面数不断减小，缺页率不断上升。所以操作系统要选择一个适当的进程数目和进程需要的帧数，以便在并发水平和缺页率之间达到一个平衡。
抖动问题可能会被本地的页面置换算法改善
- 更好的规则为加载控制：调整MPL
- 平均页缺失时间（MTBF, mean time between page faults)
- 页缺失服务时间（PFST，page fault service time）
