操作系统_页面替换策略

页面替换策略目的与要求：了解各种页面替换策略及实用的综合策略。重点与难点：固定驻留集算法和SWS等实用动态驻留集算法。Ch11页面替换策略虚存的作用：•解决主存空间不足；•让更多的进程并发运行，提高系统的吞吐率。页故障引发：•PageOut/PageIn；•访问辅存。必须防止系统发生抖动。页面替换策略中的基本概念驻留集(工作集)：进程的合法页集合；访问串：进程访问虚空间的地址踪迹。举例：某进程依次访问如下地址，0100，0432，0101，0612，0102，0103，……页式虚存管理以页为基本单位，只需页号即可。设页面大小为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)，且|s(t)|m，则s(t+1)=s(t)+{r(t+1)}。•若t+1时刻访问的页不在s(t)中时，且驻留集大小等于m，则先pagingouty页，再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奇异：指替换策略不满足随着驻留集的增大，页故障数一定减少的规律。(二)OPT(Optimalreplacement)举例：驻留集大小为3，访问串为7,0,1,2,0,3,0,4,2,3,0,3,2..770701201201203203243243243203203203OOOOOOO淘汰下次访问距当前最远的那些页中序号最小的页。OPT方法特点：•最优的固定驻留集大小替换策略。•不可实现。OPT策略对任意一个访问串的控制均有最小的时空积（进程所占空间与时间的乘积）。由于需要预先得知整个访问串的序，故不能用于实践,仅作为一种标准，用以测量其他可行策略的性能。(三)LRU(LeastRecentlyUsed)淘汰上次使用距当前最远的页。举例：驻留集大小为3，访问串为7,0,1,2,0,3,0,4,2,3,0,3,2..770701201201203203403402432032032032OOOOOOOOOLRU策略是一种栈算法。满足：S（m,t）属于S（m+1,t）的替换算法被称为栈算法。LRU策略中，当驻留集大小为时,S(m,t)中保持着最近使用过的m个页帧；当驻留集大小为m+1时，S(m+1,t)中保持着最近使用过的m+1个页帧。故S(m,t)属于S(m+1,t)的LRU策略是栈算法。LRU策略的特点：要硬件配合，实现费用高，但效果适中。实现方法1：给每个页帧设一个计数器，每访问一页，对应页帧计数清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的页。操作系统选择淘汰页时，尽量避免选被修改过的页。因此，首先选择使用和修改位都为0的页；若没有，再选修改位为1，使用位为0的页；再选使用位为1，修改位为0的页；最后按FIFO选两者均为1的页。程序行态：指程序访存布局特性和行为特性。•局部性行态:一段时间内程序访存有局部性.•阶段转换行态:从一个局部集向另一个局部集过渡是突然的.•局部集一般不超过程序总页数的20%。二、驻留集可变的替换策略引入原因：若驻留集小于局部集时引起抖动，而驻留集大于局部集又是浪费。同时局部集又有大有小。因此，应随着程序访问虚存的局部集大小变化而改变驻留集。若驻留集中的某页有△个访问间隔没被访问，则将其淘汰。举例：取△=5，访问串为(一)WS(workingset)1234444444443444370701701270127012301230423042304230423042302370120304230321201021302130213210实现：每一页面设一计数器。每访存一次，将所有计数器加1，所访存的页面计数器清0，淘汰计数器值等于△的页面。特点：开销太大，不实用。每访问一页，将当前硬时钟值记录在页表项中，操作系统定时(以T为周期)检查驻留集页表项的时钟值，若:当前时钟值-页表项中时钟值＞△，则淘汰之。(二)SWS(SampledWarkingSet)定时检查计数器，淘汰计数器值大于等于△的页面。这样硬件消耗仍很大。费用小，但效果不好。D为两次页故障距离，1/D为当前页故障率，f为阈值。1/D＜f，则淘汰驻留集中使用位为0的页。1/D≥f，增加驻留集大小，加入故障页，所有驻留集中页的使用位清0。(三)VMIN(VariableMinimalreplacement)若某页距下次访问的距离大于△，则将其淘汰(不能实用)；与△相同时，VMIN与WS的故障数相同，但VMIN的平均驻留集要小。(四)PFF(PageFaultFrequency)实用OS选择动态驻留集FIFO(SWS)的变种。•设立两个队列：自由链表和修改链表。•定时作页淘汰：淘汰时不立即删除页中数据，要根据页面是否修改挂入自由链/修改链，修改链过长时，回写页面后改挂到自由链中。•pagingin要用空页时,选自由链的第一页帧，这时页中数据被覆盖,改变该页帧原页面页表项状态等信息。•在自由链/修改链中的页面再次被访问时，则将该页从链中摘除,该页又能通过页表项访问到。三、替换策略选择预调请调与预调的区别：•存储管理：用时分配调入与预分配调入；•替换策略：要时页淘汰与预淘汰。固定驻留集大小时，一般驻留集未满时，采用预调；待驻留集满即改为请调。