5.3页面替换策略

《5.3页面替换策略》由会员分享，可在线阅读，更多相关《5.3页面替换策略（19页珍藏版）》请在装配图网上搜索。

1、第十三讲 页面替换策略目的与要求:了解各种页面替换策略及实用了解各种页面替换策略及实用的综合策略。的综合策略。重点与难点:固定驻留集算法和固定驻留集算法和SWSSWS等实用等实用动态驻留集算法动态驻留集算法。作业:18，19，24，31，335.3.3 页面替换策略虚存的作用：虚存的作用：解决主存空间不足解决主存空间不足 让更多的进程并发运行，提高系统的让更多的进程并发运行，提高系统的吞吐率吞吐率页页故障引发如下操作故障引发如下操作：Page Out/Page In(Page Out/Page In(访问辅存访问辅存)必须防止系统发生抖动（控制页故障频度）必须防止系统发生抖动（控制页故障频度）

2、页面替换策略中基本概念 驻留集(工作集)：进程的合法页集合 访问串：进程访问虚空间的地址踪迹。举例：某进程依次依次访问如下地址，举例：某进程依次依次访问如下地址，01000100，04320432，01010101，06120612，01020102，01030103，页式虚存管理以页为基本单位，只需页号页式虚存管理以页为基本单位，只需页号即可。设页面大小为即可。设页面大小为100100，上述访问串可简，上述访问串可简化为化为1 1，4 4，1 1，6 6，1 1，1 1，页面替换策略分成两类：驻留集大小固定的替换策略驻留集大小固定的替换策略 驻留集大小可变的替换策略驻留集大小可变的替换策略

3、设驻留集大小为设驻留集大小为m m，s(t)s(t)为为t t时刻的驻时刻的驻留集，留集，r(t)r(t)为为t t时刻访问的页号。时刻访问的页号。t t取取0,1,0,1,t t，指访存指令执行时刻。指访存指令执行时刻。驻留集与驻留集与paging in/outpaging in/out的关系：的关系：进程刚满创建时，驻留集为空。即进程刚满创建时，驻留集为空。即s(t)=s(t)=空。空。若若t+1t+1时刻访问的页在时刻访问的页在s(t)s(t)中时，访问之。中时，访问之。即若即若r(t+1)s(t)r(t+1)s(t)，则则s(t+1)=s(t)s(t+1)=s(t)。若若t+1t+1时

4、刻访问的页不在时刻访问的页不在s(t)s(t)中时，且驻留中时，且驻留 集大小小于集大小小于m m，则则paging inpaging in。即即若若 r(t+1)!s(t)r(t+1)!s(t)，且且|s(t)|ms(t)|mnm，对于栈算法有对于栈算法有S(mS(m，t)t)属于属于 S(nS(n，t)t)，任取任取r(t)r(t)，若若r(t)!S(nr(t)!S(n，t),t),则则r r(t)!S(m(t)!S(m，t)t)。因此，驻留集为因此，驻留集为n n时时出现出现的页故障一定会出现在驻留集为的页故障一定会出现在驻留集为m m时。时。LRULRU没有没有BeladyBelady

5、奇异奇异。(四)实用方法（兼顾FIFO和LRU策略）为页帧在页表项中增加一位使用位，硬为页帧在页表项中增加一位使用位，硬件每访存一次即将对应页的使用位置件每访存一次即将对应页的使用位置1 1，操，操作系统页面管理程序定时将所有使用位清作系统页面管理程序定时将所有使用位清0 0。淘汰时任选一个使用位为淘汰时任选一个使用位为0 0的页。的页。操作系统选择淘汰页时，尽量避免选被操作系统选择淘汰页时，尽量避免选被修改过的页。因此，首先选择使用和修改位修改过的页。因此，首先选择使用和修改位都为都为0 0的页；若没有，再选修改位为的页；若没有，再选修改位为1 1，使用，使用位为位为0 0；再选使用位为；再

6、选使用位为1 1，修改位为，修改位为0 0的页；的页；最后按最后按FIFOFIFO选两者均为选两者均为1 1的页。的页。程序行态：指程序访存布局特性和行为特性指程序访存布局特性和行为特性局部性行态局部性行态:一段时间内程序访存有局部性一段时间内程序访存有局部性.阶段转换行态阶段转换行态:从一个局部集向另一个局部从一个局部集向另一个局部集过渡是突然的集过渡是突然的.局部集大小一般不超过程序总页数的局部集大小一般不超过程序总页数的20%20%。二、驻留集大小可变的替换策略引入原因:驻留集大小小于局部集大小时引驻留集大小小于局部集大小时引起抖动，驻留集大小大于局部集大小又是浪起抖动，驻留集大小大于局

7、部集大小又是浪费。同时局部集又有大有小。费。同时局部集又有大有小。因此，应随着程序访问虚存的局部集大小变因此，应随着程序访问虚存的局部集大小变化而改变驻留集大小。化而改变驻留集大小。若驻留集中的某页有若驻留集中的某页有个个访问间隔访问间隔没没被访问则将其淘汰。被访问则将其淘汰。举例：取举例：取=5=5，访问串为，访问串为(一)WS(working set)1 2 3 4 4 4 4 4 4 4 4 4 3 4 4 4 37070170127012701230123042304230423042304230237 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 10213021302

8、13210实现：每一页面设一计数器。每访存一次，每一页面设一计数器。每访存一次，将所有计数器加将所有计数器加1 1，所访存的页面计数器，所访存的页面计数器清清0 0，淘汰计数器值等于，淘汰计数器值等于的页面。的页面。特点：开销太大，没有实用开销太大，没有实用每访问一页，将当前硬时钟值记录在页表每访问一页，将当前硬时钟值记录在页表项中，操作系统定时项中，操作系统定时(以以T T为周期为周期)检查驻检查驻留集页表项的时钟值，若留集页表项的时钟值，若:当前时钟值当前时钟值-页表项中时钟值页表项中时钟值 ，则淘汰之。，则淘汰之。(二)SWS(Sampled Warking Set)定时检查计数器，淘汰

9、计数器值大于等定时检查计数器，淘汰计数器值大于等于于的页面。这样硬件消耗仍很大。的页面。这样硬件消耗仍很大。(三)VMIN(Variable Minimal replacement)若某页距下次访问的距离大于若某页距下次访问的距离大于则将其淘则将其淘汰。汰。(不能实用不能实用)相同时，相同时，VMINVMIN与与WSWS的故障数相同，但的故障数相同，但VMINVMIN的平均驻留集要小。的平均驻留集要小。实用操作系统选择动态驻留集实用操作系统选择动态驻留集FIFO(SWS)FIFO(SWS)的的变种。变种。设立两个队列：自由链表和修改链表。设立两个队列：自由链表和修改链表。定时作页淘汰：淘汰时不立即末去页中数据，定时作页淘汰：淘汰时不立即末去页中数据，根据页面修改否挂入自由链根据页面修改否挂入自由链/修改链，修改链修改链，修改链过长时，回写页面后改挂到自由链中。过长时，回写页面后改挂到自由链中。paging inpaging in要用空页时要用空页时,选自由链的第一页帧，选自由链的第一页帧，这时页中数据被覆盖。这时页中数据被覆盖。在自由链在自由链/修改链中的页面再次被访问时，修改链中的页面再次被访问时，则将该页从链中摘除则将该页从链中摘除,使该页又能通过页表项使该页又能通过页表项访问到。访问到。三、替换策略选择