工作集替换算法

1、(1) 局部最佳页面替换算法1976年由Prieve提出一种局部最佳页面替换算法，它与全局最佳替换算法类似，需事 先知道程序的页面引用串，再根据进程行为改变页面数量。现在介绍此算法的思想，进程在时刻t访问某页面，如果该页面不在内存中，导致一次缺页，把该页面装入一个空闲页框。 不论发生缺页与否，算法在每一步要考虑引用串，如果该页面在时间间隔(t,t+ T )内未被再次引用，那么就移出页面；否则，该页被保留在进程的驻留集中，直到再次被引用。T为一个系统常量，间隔(t,t+ T )称作滑动窗口，因为，在任意给定时刻，驻留集包含这个窗口中可见的那些页面(当前引用的页面，未来的T次内存访问引用的页面)，

2、因此，窗口实际大小 为 T +1。通过例子说明此算法，假如进程页面引用串为：p3、p3、p4、p2、p3、p5、p3、p5、pl、p4。滑动窗口 t =3,初始时页面p4己被装入。若采用局部替换，通过图 1来了解驻留集的 变化情况。时刻t0时，p4被引用，因为它在时刻 t4时再次被引用，即在时间间隔(0,0+3)之内，故p4留在驻留集。时刻t1时，p3被引用，它被装入空闲页框中，这时驻留集中包 含p3与p4。在时刻t2和t3，显然，页面p3与p4被保留。页面p4在时刻t4被移出驻留 集，因为，在时间间隔(4,4+3)之内，不再被引用。同时，p2被装入空闲页框，但p2在时刻t5就脱离滑动窗口并移

3、出驻留集，而p3依然驻留，直到时刻 t7再次被引用。发生在时刻t6的下次缺页把p5装入页框，它被保持驻留，直到时刻t8再次被引用。最后两次引用装入p1与p4页面。本例中，缺页总数为5,驻留集大小在1-2之间变化，任何时刻至多两个页框被占用，通过增加t值，缺页数目可减少，但代价是花费更多页框。时刻t012345678910引用串P4p3p3P4p2p3P5p3P5PlP4pl p2 p3P4P5VVVVVVVVVVVVVVVVVIn t OUT tp3p2p4p2p5p3p1p5p4p1图1局部最佳页面替换算法示例(2) 工作集模型和工作集置换算法P.J.De nning提出了工作集模型，用来对

4、局部最佳页面替换算法进行模拟实现，也使用 了滑动窗口概念，但并不向前查看页面引用串，而是基于程序的局部性原理向后看，该原理意味着，在任何给定时刻，一个进程不久的将来所需内存数量，可通过考查其过去最近的时间内的内存需求做出估计。进程工作集指：“在某一段时间间隔内，一个进程运行所需访问的页面集合”。用W(t，)表示在时刻t- 到时刻t之间所访问的页面集合，则它就是进程在时刻t的工作集，是系统定义的一个常量。变量称为“工作集窗口尺寸”，可以通过窗口来观察进程的行为，还把工作集中所包 含的页面数目称为“工作集尺寸”。图2例子中，页面引用串与上例相同，工作集窗口尺寸 =4。如果系统有足够空闲页框供分配，

5、并且在时刻tO时，初始工作集为（p1,p4,p5），其中，pl在时刻tO被引用，p4在时刻t-1被引用，而p5在时刻t-2被引用。图中说明了每次引用时的工作集，第1次缺页发生在时刻t1，页面p3被装入一个空闲页框。另外3个当前驻留页面 pl、p4和p5在窗口 （1-3,1）中仍然可见，并被保留。在时刻 t2，页面p5离开了当前窗口（2-3,2），它被移出工作集。在时刻 t4，缺页会把p2装入，它 占用了移出的页面 pl的位置，因为，pl离开了当前窗口 （4-3,4）。时刻t6，发生缺页并装 入了 p5,并且当前驻留页面 p2、p3和p4作为由当前窗口（6-3,6）定义的当前工作集的一部 分被保

6、留。在下面两次引用中，工作集会缩小到仅两个页面p3和p5，并因为在时刻t9和t10发生两次缺页，使工作集再次增长到4个页面。此算法总的缺页数为5次，工作集尺寸在2-4个页框间波动。时刻t012345678910引用串Plp3P3P4P2P3P5P3P5PlP4plVVVVVp2一一一一VVVV一一一p3/VVVVVVVVVP4V/VVVVV一一一VP5V/VVVVVIn t OUT tp3p5p2p1p5p4p2p1p4图2工作集替换示例工作集是程序局部性的近似表示，可以通过它来确定驻留集的大小：监视每个进程的工作集，只有属于工作集的页面才能留在内存。定期地从进程驻留集中删去那些不在工作集中的

7、页面。仅当一个进程的工作集在内存时，进程才能执行。Windows2000/XP的页面替换机制结合了工作集模型和clock算法的优点，采用局部替换算法，一个进程缺页时，不会逐出其他进程的页面。系统为每个进程维护一个当前工作集，系统指定了一个工作集最小尺寸（20-50个页框）和最大尺寸（45-345个页框）。缺页时，把引用到的页面添加到进程工作集中，直至达到最大值，此时，若还发生缺页，必须要从工作集 中移出一个页面。淘汰页面选择使用模拟LRU和clock策略的变种，每个页框有一个访问位u及一个计数器count。该页被引用时，u位被硬件置1,当在工作集中寻找淘汰页面时，工作集管理程序扫描工作集中页面

8、的访问位，并执行操作：如果u=1，那么，把u和count清0;否则，count加1。扫描结束时，移出 count值最大的页面。凡从工作集中逐出的页框， 被放入两个内存队列之一：一个是保存暂时移出的并已被修改过的页面；另一个保存暂时移出的并为只读的页面。如果其中页面被再次引用，可迅速从队列中找到，而不会产生缺页， 仅当实际的空闲页框队列为空时，它们才被用来满足缺页需求。(3) 模拟工作集替换算法工作集策略在概念上很有吸引力， 但实现中监督驻留页面变化的开销很大， 估算合适的 窗口 的大小也是个难题，为此，已经设计出各种工作集近似算法，下面介绍两种。进程在运行前要把它的工作集预先装入主存， 为每个

9、页设置引用位及年龄寄存器， 寄存 器初始化为0,每隔时间T,系统扫描内存中所有页面，先将寄存器右移一位，再把引用位 R位的值加到对应寄存器的最左边位，这样，没有引用的页面，其年龄寄存器的值逐步减小，当达到下限或 0 值时,由于页面已经落在窗口之外,就可把它从工作集中移去。例如，年龄寄存器共有四位，时间间隔T定为1000次存储器引用(即1000个指令周期)， 页面P在时刻t时寄存器为“ 1000”，在时刻t+1000时寄存器为“ 0100”，在时刻t+2000 时寄存器为“0010”，在时刻 t+3000 时寄存器为“0001”，在时刻 t+4000 时寄存器为“0000”， 此时，页面p被移出

10、工作集。这就有效地模拟了窗口大小为1000 X 4的一个工作集。它又被称为 “老化 (Aging) 算法”，年龄寄存器各位的累加值， 反映了页面最近使用的情 况，访问次数越多，累加值越大。而较早访问的页面，随着寄存器的右移，由于老化使得其 作用越来越小。另一种方法是为每个页面设置引用位及关联的时间戳， 通过超时中断， 至少每隔若干条 指令就周期性地检查引用位及时间戳。 当发现使用位为 1 时，就把它置 0并把这次改变的时 间作为时间戳记录下来。 每当发现使用位为 0时， 通过系统当前时间减去时间戳时间， 计算 出从它常次使用以来未被再次访问的时间量，记作 t_off 。 t_off 值会随着每

11、次超时中断的 处理而不断增加，除非页面在此期间被再次引用，导致其使用位为1。把 t_off 与系统时间参数 t_max 相比，若 t_off>t_max ，就把页面从工作集中移出，释放相应页框。(4) 缺页频率替换算法工作集算法中保证最少缺页次数是通过调整工作集大小来间接实现的，一个直接的改善系统性能的方法是使用缺页频率替换算法 (Page Fault Frequency) 。它根据连续的缺页之间 的时间间隔来对缺页频率进行测量， 每次缺页时， 利用测量时间调整进程工作集尺寸。 其规 则是：如果本次缺页与前次缺页之间的时间超过了临界值t ,那么，所有在这个时间间隔内没有引用的页面都被移出

12、工作集。 这就保证了进程工作集不会不必要地扩大， 与工作集模型 相比，实现效率高，只在发生缺页时才调整页面，而不是每次引用时需要调整。图 3 的例子再次使用上选引用串，并设临界值 t =2，在时刻 t0 时，驻留的集合包含 页面p1、p4和p5。在时刻t1发生第1次缺页，假设前一次缺页刚刚发生，故本次无页面 被移出。 下次缺页发生在时刻 t4 ，因为本次缺页时刻 (4)- 上次缺页时刻 (1)> t 成立，所以， 在时间间隔(1,4)内未被引用的页面 p1和p5应当移出。继而缺页发生在时刻t6，但由于本次缺页时刻(6)-上次缺页时刻(4)并不t ,所以，这次无页面被移出。但在时刻t9发生下次缺页时，因移出条件又为真了， 故页面p2和p4被移出。在时刻t10发生最