1、局部置换算法的问题

局部置换算法给每个程序分配固定的页帧数，但是一个程序在不同的运行阶段所需要的页帧数量可能大不相同，因此局部置换算法总是不会分配刚好的页帧数程序，总是会造成一定的页帧冗余或者页帧不足的情况。

2、工作集模型

之前介绍的各种页面置换算法，都是基于程序的局部性原理，若局部性原理不成立，那么各种页面置换算法就没有什么分别，也没有什么意义。例如：假设进程对逻辑页面的访问顺序是1,2,3,4,5,…，即单调递增，那么在物理页面数有限的情况下，不管采用何种置换算法，每次的页面访问都必然导致缺页中断。

如果局部性原理是成立的，那么需要用到工作集模型来证明它存在并对它进行定量地分析。

2.1 工作集

工作集值得是一个进程当前正在使用的逻辑页面的集合，可以用一个二元函数 W ( t , Δ ) W(t, \Delta ) W(t,Δ)来表示：其中

t：指当前的执行时刻；

Δ：称为工作集窗口，寄一个定长的页面访问的时间窗口；

W(t,Δ)：表示在当前时刻  t之前的 Δ 时间窗口中的所有页面所组成的集合（随着 t的变化，该集合也在不断变化）

∣W(t,Δ)∣：指工作集的大小，即页面的个数

工作集大小的变化：进程开始执行后，随着访问新页面逐步建立较稳定的工作集。当内存访问的局部性区域的位置大致稳定之后，工作集的大小也大致稳定；局部性区域的位置改变时，工作集快速扩张和收缩过渡到下一个稳定值。

上图是工作集的一个示意图。

2.2 常驻集

常驻集指在当前时刻，进程实际驻留在内存当中的页面集合。

工作集市进程在运行过程中固有的属性，而常驻集取决于系统分配给进程的物理页面数目，以及所采用的的页面置换算法；

如果一个进程的整个工作集都在内存当中，即常驻集  ⊆工作集，那么进程将很顺利地运行，而不会造成太多的缺页中断（直到工作集发生剧烈变动，从而过渡到另一个状态）；

当进程常驻集的大小达到某个数目之后，在给他分配更多的物理页面，缺页率也不会明显下降。

3、两个全局置换算法

3.1 工作集页置换算法

追踪前 τ \tau τ个访问的页面的引用，建立工作集， τ \tau τ称作工作集的时间窗口大小，example：τ=4 references。在程序执行的过程中，不是等到缺页之后才开始进行置换，而是一旦某个页面不属于工作集了，则直接将这个页面从工作集之中丢掉。

上图是工作集页置换算法的一个示意图。

3.2 缺页率页面置换算法

可变分配策略： 常驻集大小可变。例如：每个进程在刚开始运行的时候，先根据程序大小给它分配一定数目的物理页面，然后再进程运行的过程中，再动态调整常驻集的大小。

可以采用全局页面置换算法的方式，当发生一个缺页中断时，被置换的页面可以是在其他进程当值的，各个并发进程竞争地使用物理页面。

优缺点：性能较好，但增加了系统开销。

具体实现：可以采用缺页率算法(PFF, Page Fault Frequency)来动态调整常驻集的大小。

· **缺页率：**表示“缺页次数 / 内存访问次数”(比率)，或者“缺页平均时间间隔的倒数”。影响缺页率的因素包括以下几个方面：页面置换算法；分配给进程的物理页面数目；页面本身的大小；程序的编写方法。

在程序开始运行时，若运行的程序缺页率过高，则通过增加工作集来分配更多的物理页面；若运行的程序的缺页率过低，则通过减少工作集来减少他的物理页面数量。力图使运行的每一个程序的缺页率在一个合理的范围之内。

缺页率算法直观的想法就是：当缺页率高的时候，增加工作集；当缺页率低的时候，减少工作集。缺页率算法的算法流程如下所示：

保持追踪缺失发生概率

当缺页发生时，从上次页缺失起计算这个时间，记录上次缺页的时间为 t l a s t t_{last} tlast，记录本次缺页的时间为 tcurrent；

若发生页缺之间的时间是“大”的，之后减少工作集，

e.g. i f   t c u r r e n t − t l a s t > T if \ t_{current}-t_{last}>T if tcurrent−tlast>T，之后从内存中移除所有在 [ t l a s t ,   t c u r r e n t ] [t_{last}, \ t_{current}] [tlast, tcurrent]时间内没有被引用的页。

若发生页缺失的时间是“小”的，之后增加工作集，

e.g. if tcurrent−tlast<T，之后增加缺失页到工作集之中。

上图是缺页率页置换算法的一个示意图。