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