《页面替换策略》由会员分享，可在线阅读，更多相关《页面替换策略（19页珍藏版）》请在金锄头文库上搜索。
1、,第十三讲 页面替换策略目的与要求:了解各种页面替换策略及实用的综合策略。 重点与难点:固定驻留集算法和SWS等实用动态驻留集算法。 作业:18，19，24，31，33,5.3.3 页面替换策略,虚存的作用：解决主存空间不足让更多的进程并发运行，提高系统的吞吐率,页故障引发如下操作：Page Out / Page In(访问辅存),必须防止系统发生抖动（控制页故障频度）,页面替换策略中基本概念驻留集(工作集)：进程的合法页集合访问串：进程访问虚空间的地址踪迹。,举例：某进程依次依次访问如下地址，0100，0432，0101，0612，0102，0103，页式虚存管理以页为基本单位，只需页号即可
2、。设页面大小为100，上述访问串可简化为1，4，1，6，1，1，,页面替换策略分成两类：驻留集大小固定的替换策略驻留集大小可变的替换策略,设驻留集大小为m，s(t)为t时刻的驻留集，r(t)为t时刻访问的页号。t取0,1,t，指访存指令执行时刻。,驻留集与paging in/out的关系：进程刚满创建时，驻留集为空。即s(t)=空。若t+1时刻访问的页在s(t)中时，访问之。 即若r(t+1)s(t)，则s(t+1)= s(t)。若t+1时刻访问的页不在s(t)中时，且驻留 集大小小于m，则paging in。即若r(t+1)!s(t)，且|s(t)|m，对于栈算法有S(m，t)属于 S(n，
3、t) ，任取r (t)，若r (t) ! S(n，t), 则r (t) ! S(m，t)。因此，驻留集为n时出现的页故障一定会出现在驻留集为m时。 LRU没有Belady奇异。,(四) 实用方法（兼顾FIFO和LRU策略）为页帧在页表项中增加一位使用位，硬件每访存一次即将对应页的使用位置1，操作系统页面管理程序定时将所有使用位清0。淘汰时任选一个使用位为0(表示OS清0周期内没被使用过）的页。操作系统选择淘汰页时，尽量避免选被修改过的页。因此，首先选择使用和修改位都为0的页；若没有，再选修改位为1，使用位为0；再选使用位为1，修改位为0的页；最后按FIFO选两者均为1的页。,程序行态：指程序访
4、存布局特性和行为特性 局部性行态:一段时间内程序访存有局部性. 阶段转换行态:从一个局部集向另一个局部集过渡是突然的. 局部集大小一般不超过程序总页数的20%。,二、驻留集大小可变的替换策略,引入原因: 驻留集大小小于局部集大小时引起抖动，驻留集大小大于局部集大小又是浪费。同时局部集又有大有小。 因此，应随着程序访问虚存的局部集大小变化而改变驻留集大小。,若驻留集中的某页有个访问间隔没被访问则将其淘汰。举例：取=5，访问串为,(一) WS(working set),1 2 3 4 4 4 4 4 4 4 4 4 3 4 4 4 3,7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0
5、 1,实现：每一页面设一计数器。每访存一次，将所有计数器加1，所访存的页面计数器清0，淘汰计数器值等于的页面。,特点：开销太大，没有实用,每访问一页，将当前硬时钟值记录在页表项中，操作系统定时(以T为周期)检查驻留集页表项的时钟值，若:当前时钟值 - 页表项中时钟值 ，则淘汰之。,(二) SWS(Sampled Warking Set),定时检查计时器，淘汰计时器值大于等于的页面。这样硬件消耗仍很大。,(三) VMIN(Variable Minimal replacement),若某页距下次访问的距离大于则将其淘汰。(不能实用) 相同时，VMIN与WS的故障数相同，但VMIN的平均驻留集要小。,实用操作系统选择动态驻留集FIFO(SWS)的变种。设立两个队列：自由链表和修改链表。定时作页淘汰：淘汰时不立即末去页中数据，根据页面修改否挂入自由链/修改链，修改链过长时，回写页面后改挂到自由链中。paging in要用空页时,选自由链的第一页帧，这时页中数据被覆盖。在自由链/修改链中的页面再次被访问时，则将该页从链中摘除,使该页又能通过页表项访问到。,三、替换策略选择,
