操作系统第十三讲 页面替换策略

1、1,第十三讲 页面替换策略 目的与要求:了解各种页面替换策略及实用的综合策略。 重点与难点:固定驻留集算法和sws等实用动态驻留集算法。,2,5.3.3 页面替换策略,虚存的作用： 解决主存空间不足 让更多的进程并发运行，提高系统的吞吐率,由页故障引发： page out / page in,必须防止系统发生抖动（控制页故障频度）,3,页面替换策略中基本概念 驻留集(工作集)：进程的合法页集合 访问串：进程访问虚空间的地址踪迹。,举例：某进程依次依次访问如下地址，0100，0432，0101，0612，0102，0103， 页式虚存管理以页为基本单位，只需页号即可。设页面大小为100，上述访问

2、串可简化为1，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+

3、1时刻访问的页不在s(t)中时，且驻留 集大小等于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,先进先出置换算法例,假定系统为

4、某进程分配了3个物理块，页面访问序列为：1、2、3、4、1、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

5、,4,块4,缺,2,5,4,5,缺,2,1,4,4,缺,2,1,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

6、，开始时3个物理块均为空闲，采用最佳置换算法时的页面置换情况如下所示：,13,采用最佳置换算法的页面置换情况,从上表中可以看出，共发生了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,

7、(三) lru(least recently used),淘汰上次使用距当前最远的页。,举例：驻留集大小为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

8、,缺,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,走向,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为驻留集大小）。 lr

9、u策略中，当驻留集大小为m时，s（m，t）中保持着最近使用过的m个页帧；当驻留集大小为m+1时，s（m+1，t）中保持着最近使用过的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时。 l

10、ru没有belady奇异。,21,lru算法的实现,lru算法实现时需要较多的硬件支持，以记录进程中各页面自上次访问以来有多长时间未被访问。下面介绍几种实现方法。 计数器法 链表法,22,计数器法,为每个页面配置一个计数器，其初值为0。当进程访问某页时，将计数器的最高位置1，定时器每隔一定时间将计数器右移1位，则数值最小的页是最近最久未使用的页面。,23,计数器法（续）,最近最久未使用的页是？,7 0 0 0 0 0 1 1 1,24,链表法,用一个单链表保存当前进程所访问的各页面号，刚使用过的页面放表尾，则表头一定是最近最久未使用的页面。其实现思想为： 当分配给进程的物理块未用完时，则将进程

11、装入内存的页面按先后顺序构成一个链表 当进程访问的页面在内存时，将页面从链表中移出放到表尾 当进程访问的页面不在内存时，则发生缺页中断，将表头页面置换,25,链表法例,例如：设分配给某进程4个物理块，页面访问序列为：3、2、4、1、5、4、3、2，用单链表实现lru算法的过程如下：,26,(四) 实用方法（兼顾fifo和lru策略） 为页帧在页表项中增加一位使用位，硬件每访存一次即将对应页的使用位置1，操作系统页面管理程序定时将所有使用位清0。淘汰时任选一个使用位为0的页。 操作系统选择淘汰页时，尽量避免选被修改过的页。因此，首先选择使用和修改位都为0的页；若没有，再选修改位为1，使用位为0；

12、再选使用位为1，修改位为0的页；最后按fifo选两者均为1的页。,27,补充：时钟（clock）置换算法,lru算法需要较多硬件支持，实现成本较高，因此实际应用中往往采用lru的近似算法。clock算法就是用得较多的一种lru近似算法。,28,简单时钟置换算法,为每页设置一个访问位，再将内存中所有页面通过链接指针链成一个循环队列。 当某页被访问时，将其访问位置1。 当发生缺页中断时，从搜索指针开始检查访问位，若访问位为0就选择该页淘汰，否则将检查过的页面访问位为1的页面复位成0。,29,简单时钟置换算法页面链,块号 页号 访问位 指针 0 1 2 4 0 3 4 2 1 5 6 5 0 7 1

13、 1,替换指针,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的页面，将满足条件的第一个页

14、面作为淘汰页。 若第1步失败，则开始第2轮扫描，寻找r=0,u=1的页面，将满足条件的第一个页面作为淘汰页，并将所有经历过页面的访问位置0。 若第2步失败，则将指针返回到开始位置，然后重复第1步，若仍失败则必须重复第2步。此时一定能找到淘汰页面。 特点：减少了磁盘i/o次数，但算法本身开销增加。,33,程序行态：指程序访存布局特性和行为特性 局部性行态:一段时间内程序访存有局部性. 阶段转换行态:从一个局部集向另一个局部集过渡是突然的. 局部集大小一般不超过程序总页数的20%。,二、驻留集大小可变的替换策略,引入原因: 驻留集大小小于局部集大小时引起抖动，驻留集大小大于局部集大小又是浪费。同时

15、局部集又有大有小。 因此，应随着程序访问虚存的局部集大小变化而改变驻留集大小。,34,若驻留集中的某页有个访问间隔没被访问则将其淘汰。 举例：取=5，访问串为,(一) ws(working set),1 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为周期)检查驻留集页表项的时钟值，若:当前时钟值

16、 - 页表项中时钟值 ，则淘汰之。,(二) sws(sampled warking set),定时检查计数器，淘汰计数器值大于等于的页面。这样硬件消耗仍很大。,37,(三) vmin(variable minimal replacement),若某页距下次访问的距离大于则将其淘汰。(不能实用) 相同时，vmin与ws的故障数相同，但vmin的平均驻留集要小。,38,实用操作系统选择动态驻留集fifo(sws)的变种。 系统设立两个队列：自由链表和修改链表。 定时作页预淘汰：淘汰时不立即末去页中数据，根据页面修改否挂入自由链/修改链，修改链过长时，回写页面后改挂到自由链中。 paging in要

17、用空页时,选自由链的第一页帧，这时页中数据被覆盖（真正被淘汰）,改变该页帧原页面页表项相关信息。 在自由链/修改链中的页面再次被访问时，则将该页从链中摘除,该页又能通过页表项访问到（从预淘汰回到被使用状态）。,三、替换策略选择,39,预调 请调与预调的区别： 存储管理：用时分配调入与预分配调入 替换策略：要时页淘汰与预淘汰;,固定驻留集大小时，一般驻留集未满时，采用预调；待驻留集满即改为请调。,40,补充： 请求分段存储管理,请求分段存储管理是另一种实现虚拟存储器的方法。 分段有如下优点： 有利于动态增长 允许按段进行编译 有利于共享 有利于保护,41,请求分段的思想,请求分段存储管理系统基于

18、分段存储管理，是在分段存储管理系统的基础上，增加了请求调段、分段置换功能所形成的一种虚拟存储系统。 在请求分段存储管理中，作业运行之前，只要求将当前需要的若干个分段装入主存，便可启动作业运行。在作业运行过程中，若所要访问的分段不在主存，则通过调段功能将其调入，同时还可以通过置换功能将暂时不用的分段换出到外存上，以便腾出内存空间。,42,1.请求分段的支持机构,请求分段的支持机构有： 段表 缺段中断机构 地址变换机构 请求调段和分段置换软件,43,段表结构,请求分段系统中使用的主要数据结构仍然是段表。 由于每次只将作业的一部分调入内存，还有一部分内容存放在磁盘上，故需扩充段表表项，扩充后的段表项如下所示：,44,段表项中各字段的说明,段号、段长和段基址：其定义同分段存储管理。 存取方式：标识该分段的存取方式：读、写、执行。 访问字段：记录该段在一段时间内被访问的次数。 修改位：表示该段调入内存后是否被修改过。 存在位：表示该段是否在主存中。 增补位：指出该段在运行过程中，