资源描述：
《5.3页面替换策略》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第十三讲页面替换策略目的与要求:了解各种页面替换策略及实用的综合策略。重点与难点:固定驻留集算法和SWS等实用动态驻留集算法。作业:18，19，24，31，335.3.3页面替换策略虚存的作用：解决主存空间不足让更多的进程并发运行，提高系统的吞吐率页故障引发如下操作：PageOut/PageIn(访问辅存)必须防止系统发生抖动（控制页故障频度）页面替换策略中基本概念驻留集(工作集)：进程的合法页集合访问串：进程访问虚空间的地址踪迹。举例：某进程依次依次访问如下地址，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，指访存指令执行时刻。驻留集与pagingin/out的关系：进程刚满创建时，驻留集为空。即s(t)=空。若t+1时刻访问的页在s(t)中时，访问之。即若r(t+1)∈s(t)，则s(t+1)=s(t)。若t+1时刻访问的页不在s(t)中时，且驻留集大小小于m，则pagingin。即若r(t+1)!∈s(t)，且
3、s(t)
4、5、)+{r(t+1)}。若t+1时刻访问的页不在s(t)中时，且驻留集大小等于m，则先pagingout页y，再paginginr(t+1)页。即s(t+1)=s(t)-{y}+{r(t+1)}。一、驻留集大小固定的替换策略(一)FIFO替换算法(替换最早进入的页)举例：驻留集大小为3，访问串为7,0,1,2,0,3,0,4,2,3,0,3,2..770701201201231230430420423023023023OOOOOOOOOOFIFO方法的特点：实现方便。不需要额外硬件。效果不好，有Belady奇异。Belady奇异：指替换策略不满足随着驻留集的增大，页故障数
6、一定减少的规律。(二)OPT(Optimalreplacement)举例：驻留集大小为3，访问串为7,0,1,2,0,3,0,4,2,3,0,3,2..770701201201203203243243243203203203OOOOOOO淘汰下次访问距当前最远的那些页中序号最小的页。OPT方法特点：最优的固定驻留集大小替换策略。不可实现。OPT策略对任意一个访问串的控制均有最小的时空积。（进程所占空间与时间的乘积）由于需要预先得知整个访问串的序，故不能用于实践。仅作为一种标准，用以测量其他可行策略的性能。(三)LRU(LeastRecentlyUsed)淘汰上次使用距当
7、前最远的页。举例：驻留集大小为3，访问串为7,0,1,2,0,3,0,4,2,3,0,3,2..770701201201203203403402432032032032OOOOOOOOOLRU策略是一种栈算法。满足：S（m，t）属于S（m+1，t）的替换算法被称为栈算法。(m/m+1为驻留集大小）。LRU策略中，当驻留集大小为m时，S（m，t）中保持着最近使用过的m个页帧；当驻留集大小为m+1时，S（m+1，t）中保持着最近使用过的m+1个页帧。故S（m，t）属于S（m+1，t），LRU策略是栈算法。LRU策略的特点：要硬件配合，实现费用高，但效果适中。实现方法1：给每
8、个页帧设一个计数器，每访问一页，对应页帧计数清0，其余页帧计数加1，淘汰计数最大的页帧。实现方法2：类似栈的结构来管理和实现LRU栈算法没有Belady奇异。设n>m，对于栈算法有S(m，t)属于S(n，t)，任取r(t)，若r(t)!∈S(n，t),则r(t)!∈S(m，t)。因此，驻留集为n时出现的页故障一定会出现在驻留集为m时。LRU没有Belady奇异。(四)实用方法（兼顾FIFO和LRU策略）为页帧在页表项中增加一位使用位，硬件每访存一次即将对应页的使用位置1，操作系统页面管理程序定时将所有使用位清0。淘汰时任选一个使用位为0的页。操作系统选择淘汰页时，尽量避
9、免选被修改过的页。因此，首先选择使用和修改位都为0的页；若没有，再选修改位为1，使用位为0；再选使用位为1，修改位为0的页；最后按FIFO选两者均为1的页。程序行态：指程序访存布局特性和行为特性局部性行态:一段时间内程序访存有局部性.阶段转换行态:从一个局部集向另一个局部集过渡是突然的.局部集大小一般不超过程序总页数的20%。二、驻留集大小可变的替换策略引入原因:驻留集大小小于局部集大小时引起抖动，驻留集大小大于局部集大小又是浪费。同时局部集又有大有小。因此，应随着程序访问虚存的局部集大小变化而改变驻留集大小。若驻留集中的某页有△个访问间
