第七章 全局页面置换算法
工作集置换算法
工作集：一个进程当前正在使用的逻辑页面集合，可表示为二元函数W(t,delta)；t为当前执行时刻，delta为一个页面访问时间窗口，称为工作集窗口；W(t,delta)是时刻t前delta时间窗口内所有访问的页面所组成的集合，|W(t,delta)|就是时刻t前delta时间窗口内访问的页面的数目。
常驻集：当前时刻，进程实际驻留在内存中的页面集合。
缺页率与(工作集, 常驻集)的关系：
- 常驻集包含工作集时，缺页率较小；
- 工作集发生剧烈变动时，缺页率较高；
- 进程常驻集大小到达一定数目后，缺页率不会明显下降；
工作集置换算法：每次访问内存后，换出不在工作集中的页面；
缺页率置换算法
缺页率：缺页时间间隔的倒数。
缺页率置换算法：通过(在发生缺页中断时)调节常驻集大小，使进程的缺页率保持在一个合理的范围内。具体来说，在发生缺页时计算相邻两次缺页的时间间隔delta；对于预先设定的T，若delta>T，操作系统将未被引用的内存页面换出内存，记这些页面的数目为nr，则操作系统收回进程的(nr-1)个未被引用的内存页面，并将缺失页写入剩下的那个未被引用的内存页面；若delta<=T，操作系统为进程申请一个内存页面来写入缺失页(相当于将缺失页增加到工作集中)。
抖动与负载控制
抖动：并发进程数目太多，使得分配给每个进程的内存页面太少而不能包含工作集；造成了大量缺页，从而操作系统需要频繁地进行置换，降低了CPU的工作效率，进程的运行速度变慢。
操作系统通过调节并发进程数(MPL)来进行负载控制。
CPU利用率与并发进程数的关系大致如下图：
而图中的Nmax不好确定，因此只能对Nmax作一个估计，使平均缺页间隔时间/缺页异常处理时间=1的并发进程数，这样可以近似地估计Nmax，从而使系统处于均衡的繁忙状态。