操作系统优秀课件.pptx

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