操作系统（课堂PPT）

1、.1第十三讲 页面替换策略目的与要求:了解各种页面替换策略及实用了解各种页面替换策略及实用的综合策略。的综合策略。重点与难点:固定驻留集算法和固定驻留集算法和SWSSWS等实用等实用动态驻留集算法动态驻留集算法。.25.3.3 页面替换策略虚存的作用：虚存的作用： 解决主存空间不足解决主存空间不足 让更多的进程并发运行，提高系统的吞让更多的进程并发运行，提高系统的吞吐率吐率由页故障引发：由页故障引发： Page Out / Page InPage Out / Page In必须防止系统发生抖动（控制页故障频度）必须防止系统发生抖动（控制页故障频度）.3页面替换策略中基本概念 驻留集(工作集)：

2、进程的合法页集合 访问串：进程访问虚空间的地址踪迹。 举例：某进程依次依次访问如下地址，举例：某进程依次依次访问如下地址，01000100，04320432，01010101，06120612，01020102，01030103， 页式虚存管理以页为基本单位，只需页页式虚存管理以页为基本单位，只需页号即可。设页面大小为号即可。设页面大小为100100，上述访问串，上述访问串可简化为可简化为1 1，4 4，1 1，6 6，1 1，1 1，.4页面替换策略分成两类： 驻留集大小固定的替换策略驻留集大小固定的替换策略 驻留集大小可变的替换策略驻留集大小可变的替换策略 设驻留集大小为设驻留集大小为m

3、m，s(t)s(t)为为t t时刻的驻时刻的驻留集，留集，r(t)r(t)为为t t时刻访问的页号。时刻访问的页号。t t取取0,1,t0,1,t，指访存指令执行时刻。，指访存指令执行时刻。.5驻留集与驻留集与paging in/outpaging in/out的关系：的关系： 进程刚创建时，驻留集为空。即进程刚创建时，驻留集为空。即s(t)=s(t)=空。空。 若若t+1t+1时刻访问的页在时刻访问的页在s(t)s(t)中时，访问之。中时，访问之。 即若即若r(t+1)s(t)r(t+1)s(t)，则，则s(t+1)= s(t)s(t+1)= s(t)。 若若t+1t+1时刻访问的页不在时刻

4、访问的页不在s(t)s(t)中时，且驻留中时，且驻留 集大小小于集大小小于m m，则，则paging inpaging in。即。即若若 r(t+1)!s(t)r(t+1)!s(t)，且且|s(t)|m|s(t)|mnm，对于栈算法有，对于栈算法有S(mS(m，t)t)属于属于 S(nS(n，t) t) ，任取，任取r (t)r (t)，若，若r (t) ! S(nr (t) ! S(n，t), t), 则则r (t) ! S(mr (t) ! S(m，t)t)。因此，驻留集为。因此，驻留集为n n时出现的页故障一定会出现在驻留集为时出现的页故障一定会出现在驻留集为m m时。时。LRULRU没

5、有没有BeladyBelady奇异奇异。.21LRU算法的实现算法的实现LRU算法实现时需要较多的硬件支持，算法实现时需要较多的硬件支持，以记录进程中各页面自上次访问以来有以记录进程中各页面自上次访问以来有多长时间未被访问。下面介绍几种实现多长时间未被访问。下面介绍几种实现方法。方法。 计数器法计数器法 链表法链表法.22计数器法计数器法为每个页面配置一个计数器，其初值为为每个页面配置一个计数器，其初值为0。当进程访问某页时，将计数器的最高位当进程访问某页时，将计数器的最高位置置1，定时器每隔一定时间将计数器右移，定时器每隔一定时间将计数器右移1位，则数值最小的页是最近最久未使用位，则数值最小

6、的页是最近最久未使用的页面。的页面。 .23计数器法（续） 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.24链表法链表法用一个单链表保存当前进程所访问的各用一个单链表保存当前进程所访问的各页面号，刚使用过的页面放表尾，则表

7、页面号，刚使用过的页面放表尾，则表头一定是最近最久未使用的页面。其实头一定是最近最久未使用的页面。其实现思想为：现思想为： 当分配给进程的物理块未用完时，则将进程当分配给进程的物理块未用完时，则将进程装入内存的页面按先后顺序构成一个链表装入内存的页面按先后顺序构成一个链表 当进程访问的页面在内存时，将页面从链表当进程访问的页面在内存时，将页面从链表中移出放到表尾中移出放到表尾 当进程访问的页面不在内存时，则发生缺页当进程访问的页面不在内存时，则发生缺页中断，将表头页面置换中断，将表头页面置换.25链表法例链表法例例如：设分配给某进程例如：设分配给某进程4个物理块，页面访问序列为：个物理块，页面

8、访问序列为：3、2、4、1、5、4、3、2，用单链表实现，用单链表实现LRU算法算法的过程如下：的过程如下： 3head 2 4 1 2head 4 1 5 2head 1 5 4 1head 5 4 3 5head 4 3 2 .26(四) 实用方法（兼顾FIFO和LRU策略） 为页帧在页表项中增加一位使用位，硬为页帧在页表项中增加一位使用位，硬件每访存一次即将对应页的使用位置件每访存一次即将对应页的使用位置1 1，操，操作系统页面管理程序作系统页面管理程序定时定时将所有使用位清将所有使用位清0 0。淘汰时任选一个使用位为淘汰时任选一个使用位为0 0的页。的页。 操作系统选择淘汰页时，尽量避

9、免选被操作系统选择淘汰页时，尽量避免选被修改过的页。因此，首先选择使用和修改修改过的页。因此，首先选择使用和修改位都为位都为0 0的页；若没有，再选修改位为的页；若没有，再选修改位为1 1，使用位为使用位为0 0；再选使用位为；再选使用位为1 1，修改位为，修改位为0 0的的页；最后按页；最后按FIFOFIFO选两者均为选两者均为1 1的页。的页。.27补充：时钟（补充：时钟（clock）置换算法）置换算法LRU算法需要较多硬件支持，实现成本算法需要较多硬件支持，实现成本较高，因此实际应用中往往采用较高，因此实际应用中往往采用LRU的的近似算法。近似算法。clock算法就是用得较多的一算法就是

10、用得较多的一种种LRU近似算法。近似算法。.28简单时钟置换算法简单时钟置换算法为每页设置一个访问位，再将内存中所为每页设置一个访问位，再将内存中所有页面通过链接指针链成一个循环队列。有页面通过链接指针链成一个循环队列。当某页被访问时，将其访问位置当某页被访问时，将其访问位置1。当发生缺页中断时，从搜索指针开始检当发生缺页中断时，从搜索指针开始检查访问位，若访问位为查访问位，若访问位为0就选择该页淘就选择该页淘汰，否则将检查过的页面访问位为汰，否则将检查过的页面访问位为1的的页面复位成页面复位成0。.29简单时钟置换算法页面链简单时钟置换算法页面链 块号块号 页号页号 访问位访问位 指针指针

11、0 1 2 4 0 3 4 2 1 5 6 5 0 7 1 1替换指针替换指针.30简单时钟置换算法流程简单时钟置换算法流程入口入口查询指针前进一步指向下一个表目查询指针前进一步指向下一个表目返回返回页面访问位页面访问位=0？N选择该页面淘汰选择该页面淘汰Y置页面访问位为置页面访问位为0.31改进的时钟算法改进的时钟算法将一个修改过的页面换出需要写磁盘，将一个修改过的页面换出需要写磁盘，其开销大于未修改页面。为此在改进型其开销大于未修改页面。为此在改进型时钟算法中应考虑页面修改情况。设时钟算法中应考虑页面修改情况。设R为访问位，为访问位，U为修改位，将页面分为以为修改位，将页面分为以下下4种类

12、型：种类型： 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的页面，将满足条件的第一个页面

13、作的页面，将满足条件的第一个页面作为淘汰页，并将所有经历过页面的访问位置为淘汰页，并将所有经历过页面的访问位置0。若第若第2步失败，则将指针返回到开始位置，然步失败，则将指针返回到开始位置，然后重复第后重复第1步，若仍失败则必须重复第步，若仍失败则必须重复第2步。此步。此时一定能找到淘汰页面。时一定能找到淘汰页面。特点：减少了磁盘特点：减少了磁盘I/O次数，但算法本身开销次数，但算法本身开销增加。增加。.33程序行态：指程序访存布局特性和行为特性指程序访存布局特性和行为特性局部性行态局部性行态: :一段时间内程序访存有局部性一段时间内程序访存有局部性. .阶段转换行态阶段转换行态: :从一个局

14、部集向另一个局部从一个局部集向另一个局部集过渡是突然的集过渡是突然的. .局部集大小一般不超过程序总页数的局部集大小一般不超过程序总页数的20%20%。二、驻留集大小可变的替换策略引入原因: 驻留集大小小于局部集大小时引驻留集大小小于局部集大小时引起抖动，驻留集大小大于局部集大小又是起抖动，驻留集大小大于局部集大小又是浪费。同时局部集又有大有小浪费。同时局部集又有大有小。因此，应随着程序访问虚存的局部集大小因此，应随着程序访问虚存的局部集大小变化而改变驻留集大小。变化而改变驻留集大小。.34 若驻留集中的某页有若驻留集中的某页有个访问间隔没个访问间隔没被访问则将其淘汰。被访问则将其淘汰。 举例

15、：取举例：取=5=5，访问串为，访问串为(一) WS(working set)1 2 3 4 4 4 4 4 4 4 4 4 3 4 4 4 37070170127012701230123042304230423042304230237 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1021302130213210.35实现： 每一页面设一计数器。每访存一次，每一页面设一计数器。每访存一次，将进程所有页面计数器加将进程所有页面计数器加1 1，所访存的页面，所访存的页面计数器清计数器清0 0，淘汰计数器值等于，淘汰计数器值等于的页面。的页面。特点： 开销太大，没有实用开销太大，没有

16、实用.36每访问一页，将当前硬时钟值记录在页表每访问一页，将当前硬时钟值记录在页表项中，操作系统定时项中，操作系统定时( (以以T T为周期为周期) )检查驻检查驻留集页表项的时钟值，若留集页表项的时钟值，若: :当前时钟值当前时钟值 - - 页表项中时钟值页表项中时钟值 ，则淘汰之。，则淘汰之。(二) SWS(Sampled Warking Set)定时定时检查计数器，淘汰计数器值大于等检查计数器，淘汰计数器值大于等于于的页面。这样硬件消耗仍很大。的页面。这样硬件消耗仍很大。.37(三) VMIN(Variable Minimal replacement)若某页距下次访问的距离大于若某页距下

17、次访问的距离大于则将其淘则将其淘汰。汰。( (不能实用不能实用) )相同时，相同时，VMINVMIN与与WSWS的故障数相同，但的故障数相同，但VMINVMIN的平均驻留集要小。的平均驻留集要小。.38实用操作系统选择动态驻留集实用操作系统选择动态驻留集FIFO(SWS)FIFO(SWS)的的变种。变种。 系统设立两个队列：自由链表和修改链表。系统设立两个队列：自由链表和修改链表。 定时作页预淘汰定时作页预淘汰：淘汰时不立即末去页中数：淘汰时不立即末去页中数据，根据页面修改否挂入自由链据，根据页面修改否挂入自由链/ /修改链，修修改链，修改链过长时，回写页面后改挂到自由链中。改链过长时，回写页

18、面后改挂到自由链中。 paging inpaging in要用空页时要用空页时, ,选自由链的第一页帧，选自由链的第一页帧，这时页中数据被覆盖（真正被淘汰）这时页中数据被覆盖（真正被淘汰）, ,改变该改变该页帧原页面页表项相关信息。页帧原页面页表项相关信息。 在自由链在自由链/ /修改链中的页面再次被访问时，则修改链中的页面再次被访问时，则将该页从链中摘除将该页从链中摘除, ,该页又能通过页表项访问该页又能通过页表项访问到（从预淘汰回到被使用状态）。到（从预淘汰回到被使用状态）。三、替换策略选择.39预调请调与预调的区别：请调与预调的区别： 存储管理：用时分配调入与预分配调入存储管理：用时分配

19、调入与预分配调入 替换策略：要时页淘汰与预淘汰替换策略：要时页淘汰与预淘汰; ;固定驻留集大小时，一般驻留集未满时，固定驻留集大小时，一般驻留集未满时，采用预调；待驻留集满即改为请调。采用预调；待驻留集满即改为请调。.40补充：补充： 请求分段存储管理请求分段存储管理请求分段存储管理是另一种实现虚拟存请求分段存储管理是另一种实现虚拟存储器的方法。储器的方法。分段有如下优点：分段有如下优点： 有利于动态增长有利于动态增长 允许按段进行编译允许按段进行编译 有利于共享有利于共享 有利于保护有利于保护.41请求分段的思想请求分段的思想请求分段存储管理系统基于分段存储管理，是请求分段存储管理系统基于分

20、段存储管理，是在分段存储管理系统的基础上，增加了请求调在分段存储管理系统的基础上，增加了请求调段、分段置换功能所形成的一种虚拟存储系统。段、分段置换功能所形成的一种虚拟存储系统。在请求分段存储管理中，作业运行之前，在请求分段存储管理中，作业运行之前，只要只要求将当前需要的若干个分段装入主存，便可启求将当前需要的若干个分段装入主存，便可启动作业运行动作业运行。在作业运行过程中，若所要访问。在作业运行过程中，若所要访问的分段不在主存，则通过的分段不在主存，则通过调段功能调段功能将其调入，将其调入，同时还可以通过置换功能将暂时不用的分段换同时还可以通过置换功能将暂时不用的分段换出到外存上，以便腾出内

21、存空间。出到外存上，以便腾出内存空间。.421.请求分段的支持机构请求分段的支持机构请求分段的支持机构有：请求分段的支持机构有： 段表段表 缺段中断机构缺段中断机构 地址变换机构地址变换机构 请求调段和分段置换软件请求调段和分段置换软件.43段表结构段表结构请求分段系统中使用的主要数据结构仍然是段请求分段系统中使用的主要数据结构仍然是段表。表。由于每次只将作业的一部分调入内存，还有一由于每次只将作业的一部分调入内存，还有一部分内容存放在磁盘上，故需扩充段表表项，部分内容存放在磁盘上，故需扩充段表表项，扩充后的段表项如下所示：扩充后的段表项如下所示：.44段表项中各字段的说明段表项中各字段的说明

22、段号、段长和段基址：其定义同分段存储管理。段号、段长和段基址：其定义同分段存储管理。存取方式：标识该分段的存取方式：读、写、执行。存取方式：标识该分段的存取方式：读、写、执行。访问字段：记录该段在一段时间内被访问的次数。访问字段：记录该段在一段时间内被访问的次数。修改位：表示该段调入内存后是否被修改过。修改位：表示该段调入内存后是否被修改过。存在位：表示该段是否在主存中。存在位：表示该段是否在主存中。增补位：指出该段在运行过程中，是否作过动态增增补位：指出该段在运行过程中，是否作过动态增长。长。外存地址：指出该段在外存上的地址。外存地址：指出该段在外存上的地址。段号段号段长段长段基段基址址存存

23、 取取 方方 式式访问访问字段字段修改修改位位存在存在位位增补增补位位外存外存地址地址.45缺段中断处理缺段中断处理在请求分段系统中，每当所访问的段不在请求分段系统中，每当所访问的段不在内存时，便产生一个缺段中断信号，在内存时，便产生一个缺段中断信号，请求请求OS将所缺分段调入内存。将所缺分段调入内存。缺段中断与缺页中断类似，也是在指令缺段中断与缺页中断类似，也是在指令执行期间产生和处理。执行期间产生和处理。.46缺段中断处理流程缺段中断处理流程缺段中断处理缺段中断处理阻塞请求进程阻塞请求进程唤醒请求进程唤醒请求进程内存中有合适的空闲区吗？内存中有合适的空闲区吗？N拼接以形成合适的空闲区拼接以形成合适的空闲区从外存读入缺段从外存读入缺段Y修改段表及内