操作系统5-3ppt课件

.,1,第十三讲页面替换策略目的与要求:了解各种页面替换策略及实用的综合策略。重点与难点:固定驻留集算法和SWS等实用动态驻留集算法。,.,2,5.3.3页面替换策略,虚存的作用：解决主存空间不足让更多的进程并发运行，提高系统的吞吐率,由页故障引发：PageOut/PageIn,必须防止系统发生抖动（控制页故障频度）,.,3,页面替换策略中基本概念驻留集(工作集)：进程的合法页集合访问串：进程访问虚空间的地址踪迹。,举例：某进程依次依次访问如下地址，0100，0432，0101，0612，0102，0103，页式虚存管理以页为基本单位，只需页号即可。设页面大小为100，上述访问串可简化为1，4，1，6，1，1，,.,4,页面替换策略分成两类：驻留集大小固定的替换策略驻留集大小可变的替换策略,设驻留集大小为m，s(t)为t时刻的驻留集，r(t)为t时刻访问的页号。t取0,1,t，指访存指令执行时刻。,.,5,驻留集与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(m，t)属于S(n，t)，任取r(t)，若r(t)!S(n，t),则r(t)!S(m，t)。因此，驻留集为n时出现的页故障一定会出现在驻留集为m时。LRU没有Belady奇异。,.,21,LRU算法的实现,LRU算法实现时需要较多的硬件支持，以记录进程中各页面自上次访问以来有多长时间未被访问。下面介绍几种实现方法。计数器法链表法,.,22,计数器法,为每个页面配置一个计数器，其初值为0。当进程访问某页时，将计数器的最高位置1，定时器每隔一定时间将计数器右移1位，则数值最小的页是最近最久未使用的页面。,.,23,计数器法（续）,最近最久未使用的页是？,700000111,.,24,链表法,用一个单链表保存当前进程所访问的各页面号，刚使用过的页面放表尾，则表头一定是最近最久未使用的页面。其实现思想为：当分配给进程的物理块未用完时，则将进程装入内存的页面按先后顺序构成一个链表当进程访问的页面在内存时，将页面从链表中移出放到表尾当进程访问的页面不在内存时，则发生缺页中断，将表头页面置换,.,25,链表法例,例如：设分配给某进程4个物理块，页面访问序列为：3、2、4、1、5、4、3、2，用单链表实现LRU算法的过程如下：,.,26,(四)实用方法（兼顾FIFO和LRU策略）为页帧在页表项中增加一位使用位，硬件每访存一次即将对应页的使用位置1，操作系统页面管理程序定时将所有使用位清0。淘汰时任选一个使用位为0的页。操作系统选择淘汰页时，尽量避免选被修改过的页。因此，首先选择使用和修改位都为0的页；若没有，再选修改位为1，使用位为0；再选使用位为1，修改位为0的页；最后按FIFO选两者均为1的页。,.,27,补充：时钟（clock）置换算法,LRU算法需要较多硬件支持，实现成本较高，因此实际应用中往往采用LRU的近似算法。clock算法就是用得较多的一种LRU近似算法。,.,28,简单时钟置换算法,为每页设置一个访问位，再将内存中所有页面通过链接指针链成一个循环队列。当某页被访问时，将其访问位置1。当发生缺页中断时，从搜索指针开始检查访问位，若访问位为0就选择该页淘汰，否则将检查过的页面访问位为1的页面复位成0。,.,29,简单时钟置换算法页面链,块号页号访问位指针0124034215650711,替换指针,.,30,简单时钟置换算法流程,入口,查询指针前进一步指向下一个表目,返回,页面访问位=0？,N,选择该页面淘汰,Y,置页面访问位为0,.,31,改进的时钟算法,将一个修改过的页面换出需要写磁盘，其开销大于未修改页面。为此在改进型时钟算法中应考虑页面修改情况。设R为访问位，U为修改位，将页面分为以下4种类型：1类(R=0,U=0)：未被访问又未被修改2类(R=0,U=1)：未被访问但已被修改3类(R=1,U=0)：已被访问但未被修改4类(R=1,U=1)：已被访问且已被修改,.,32,改进型时钟算法描述,从指针当前位置开始扫描循环队列，寻找R=0,U=0的页面，将满足条件的第一个页面作为淘汰页。若第1步失败，则开始第2轮扫描，寻找R=0,U=1的页面，将满足条件的第一个页面作为淘汰页，并将所有经历过页面的访问位置0。若第2步失败，则将指针返回到开始位置，然后重复第1步，若仍失败则必须重复第2步。此时一定能找到淘汰页面。特点：减少了磁盘I/O次数，但算法本身开销增加。,.,33,程序行态：指程序访存布局特性和行为特性局部性行态:一段时间内程序访存有局部性.阶段转换行态:从一个局部集向另一个局部集过渡是突然的.局部集大小一般不超过程序总页数的20%。,二、驻留集大小可变的替换策略,引入原因:驻留集大小小于局部集大小时引起抖动，驻留集大小大于局部集大小又是浪费。同时局部集又有大有小。因此，应随着程序访问虚存的局部集大小变化而改变驻留集大小。,.,34,若驻留集中的某页有个访问间隔没被访问则将其淘汰。举例：取=5，访问串为,(一)WS(workingset),12344444444434443,70120304230321201,.,35,实现：每一页面设一计数器。每访存一次，将进程所有页面计数器加1，所访存的页面计数器清0，淘汰计数器值等于的页面。,特点：开销太大，没有实用,.,36,每访问一页，将当前硬时钟值记录在页表项中，操作系统定时(以T为周期)检查驻留集页表项的时钟值，若:当前时钟值-页表项中时钟值，则淘汰之。,(二)SWS(SampledWarkingSet),定时检查计数器，淘汰计数器值大于等于的页面。这样硬件消耗仍很大。,.,37,(三)VMIN(VariableMinimalreplacement),若某页距下次访问的距离大于则将其淘汰。(不能实用)相同时，VMIN与WS的故障数相同，但VMIN的平均驻留集要小。,.,38,实用操作系统选择动态驻留集FIFO(SWS)的变种。系统设立两个队列：自由链表和修改链表。定时作页预淘汰：淘汰时不立即末去页中数据，根据页面修改否挂入自由链/修改链，修改链过长时，回写页面后改挂到自由链中。pagingin要用空页时,选自由链的第一页帧，这时页中数据被覆盖（真正被淘汰）,改变该页帧原页面页表项相关信息。在自由链/修改链中的页面再次被访问时，则将该页从链中摘除,该页又能通过页表项访问到（从预淘汰回到被使用状态）。,三、替换策略选择,.,39,预调请调与预调的区别：存储管理：用时分配调入与预分配调入替换策略：要时页淘汰与预淘汰;,固定驻留集大小时，一般驻留集未满时，采用预调；待驻留集满即改为请调。,.,40,补充：请求分段存储管理,请求分段存储管理是另一种实现虚拟存储器的方法。分段有如下优点：有利于动态增长允许按段进行编译有利于共享有利于保护,.,41,请求分段的思想,请求分段存储管理系统基于分段存储管理，是在分段存储管理系统的基础上，增加了请求调段、分段置换功能所形成的一种虚拟存储系统。在请求分段存储管理中，作业运行之前，只要求将当前需要的若干个分段装入主存，便可启动作业运行。在作业运行过程中，若所要访问的分段不在主存，则通过调段功能将其调入，同时还可以通过置换功能将暂时不用的分段换出到外存上，以便腾出内存空间。,.,42,1.请求分段的支持机构,请求分段的支持机构有：段表缺段中断机构地址变换机构请求调段和分段置换软件,.,43,段表结构,请求分段系统中使用的主要数据结构仍然是段表。由于每次只将作业的一部分调入内存，还有一部分内容存放在磁盘上，故需扩充段表表项，扩充后的段表项如下所示：,.,44,段表项中各字段的说明,段号、段长和段基址：其定义同分段存储管理。存取方式：标识该分段的存取方式：读、写、执行。访问字段：记录该段在一段时间内被访问的次数。修改位：表示该段调入内存后是否被修改过。存在位：表示该段是否在主存中。增补位：指出该段在运行过程中，是否作过动态增长。外存地址：指出该段在外存上的地址。,.,45,缺段中断处理,在请求分段系统中，每当所访问的段不在内存时，便产生一个缺段中断信号，请求OS将所缺分段调入内存。缺段中断与缺页中断类似，也是在指令执行期间产生和处理。,.,46,缺段中断处理流程,缺段中断处理,阻塞请求进程,唤醒请求进程,内存中有合适的空闲区吗？,N,拼接以形成合适的空闲区,从外存读入缺段,Y,修改段表及内存空闲区链,N,Y,空闲区容量总和能否满足,淘汰实段以形成合适的空闲区,返回,.,47,缺段中断涉及的几个问题,内存管理：请求分段的内存管理与与分区管理类似，采用连续内存管理方式。段的置换：调入缺段时，若有足够的空闲分区则直接调入，否则查看空闲区之和能否满足要求，若能则进行拼接，否则进行置换。置换时可能要淘汰多段。,.,48,动态地址变换,请求分段系统的地址变换是在分段系统地址变换的基础上形成的。在地址变换过程中，若段在内存则判断其存取权限是否合