页面置换算法与工作集
1. 页面置换算法
- 最佳（Optimal）置换算法：一种理论上的算法，选择最长时间不在被访问的页面换出，保证最低的缺页率。
- 先进先出（FIFO）页面置换算法
1.1. 最近久未使用（LRU）和最少使用（LFU）置换算法
LRU（Least Recently Used）置换算法
LRU 是 FIFO 算法的优化，需要记录某进程在内存中各页的使用情况，可用寄存器或栈实现。
- 位移寄存器：每个内存页面配置一个 n 位的寄存器，当进程访问物理块时，将寄存器的最高位置“1”，定时信号每个一定时间（例如100ms）将寄存器右移一位，寄存器数值最小的进程便是最近最久未使用的页面。
- 栈：利用一个栈保存当前使用的各个页面的页面号，当进程访问某页时，将该页的页面号从栈中取出压入栈顶，栈底便是最近最久未使用页面的页面号。
LFU（Least Frequently Used）置换算法
LFU 采用位移寄存器，如 LRU 一样，每个内存页面配置一个 n 位的寄存器，当进程访问物理块时，将寄存器的最高位置“1”，定时信号每个一定时间（例如100ms）将寄存器右移一位，寄存器“1”最少的进程便是最近最少使用的页面。
1.2. Clock 置换算法
LRU 的近似算法，但无需太多硬件支持。
简单 Clock 置换算法
在每页设置一位访问位，再将内存中的所有页面都通过链接指针链接成一个循环队列。当某页被访问时，其访问位被置“1”；置换算法在选择一页淘汰时，循环检查循环队列，若访问位是“0”，则换出；否则，置为“0”。
改进型 Clock 置换算法
考虑到已被修改过的页面置换代价更大（需要将修改后的页面写回磁盘），若用 A 表示页面是否被访问过（有为“1”），用 M 表示页面是否被修改（有为“1”），则优先淘汰 (0,0)，其次是(0,1)。步骤为：
- 循环队列查找(0,0)，失败则进入2
- 循环队列查找(0,1)，并将所有扫描过的页面 A 置为“0”，失败则进入3
- 重复1，必定能找到(0,0)
1.3. 页面缓冲算法（Page Buffering Algorithm，PBA）
影响页面置换的因素有除了页面置换算法和将已修改页面写回磁盘的频率，还有将磁盘内容读入内存的频率。
PBA 设置一空闲页表链（即空闲物理块链表，用于分配给频繁置换页面的进程，以降低缺页率）和一修改页表链（由已修改的页面组成）。当页面要被换出时，可将其挂在对应表链的末尾，进程需要访问已被换出的页面时只需从链表上去下，显著降低置换频率。
1.4. 访问内存的有效时间
在请求分页管理方式中，内存有效访问时间不仅要考虑访问页表和访问物理地址数据的时间，还要考虑缺页中断的处理时间。
三种方式的内存访问操作的有效访问时间（查找快表时间为p，访问实际物理内存时间为t，缺页中断处理时间为 q）：
- 被访问页在内存中，且其对应的页表项在快表中：EAT=p+t
- 被访问页在内存中，且其对应的页表项不在快表中：EAT=p（查找快表）+t（查找页表）+p（更新快表）+t访问实际物理内存=2(p+t)
- 被访问页不在内存中：EAT=p+t+q+p+t=q+2(p+t)
2. 进程抖动与工作集
2.1. 进程抖动定义
进程抖动指刚被换出的页面很快又要被访问，需要重新选一页置换刚被调出的页面，一致页面频繁置换。
随着进程数目的增加，处理器利用率先增加，且增速不断变慢，再由于频繁缺页，使得系统中排队等待页面调进调出的进程数目增加，从而处理机利用率减小，并趋于零。
2.2. 工作集定义
由进程运行的局部性原理可知，在进程运行期间，对页面的访问是不均匀的，不同时间段会集中访问一些不同的页面（活跃页面）。若能预测进程在不同时间段的活跃页面，则可大幅降低缺页率。
工作集指在某段时间间隔 ∆ 里，进程实际所要访问页面的集合。当进程的物理块小于其工作集大小时，缺页率会急剧上升；当进程的物理块大于其工作集大小时，进程的缺页率下降幅度不大。
假设将进程在过去某段时间的行为与在将来某段时间的行为相似，把进程在时间 t 的工作集记为 w(t, ∆)，其中变量 ∆ 称为工作集的窗口尺寸。
2.3. 进程抖动的预防方法
采取局部置换策略
局部置换只允许系统对分配给进程的物理块进行缺页置换，把抖动限制在进程内，但发生抖动的进程会长期处在磁盘 I/O 的等待队列中，延长其他进程对磁盘的访问时间。
把工作集算法融入到处理机调度中
在调度程序从外存调入作业之前，必须先检查每个进程在内存的驻留页面是否足够多，以此选择调入新作业或者为缺页率高的进程增加物理块。
利用 L=S 准则调节缺页率
L 是缺页的平均时间间隔，S 是置换一个页面的平均时间，当 L=S 时，磁盘和处理机都达到最大利用率。
选择暂停的进程
当多道程序过多时，为防止发生抖动，系统必须减少多道程序的数目，可按优先级、进程大小、剩余执行时间选择暂停进程。
3. ChangeLog
2018.09.16 初稿