操作系统第5章存储管理3虚拟存储

1、5.6 虚存的引入（一）程序一次性装入内存带来的问题2.程序一次性装入带来一些问题OS内存用户作业OS40K内存80K120K作业一130K作业二180K作业三250K（二）程序局部性原理：一条指令被执行后，那么一条指令被执行后，那么它可能很快会再次执行。如循环、子程序、它可能很快会再次执行。如循环、子程序、堆栈、计数或累计变量等。堆栈、计数或累计变量等。：若某一存储单元被访问，若某一存储单元被访问，那么与该存储单元相邻的单元可能也会很那么与该存储单元相邻的单元可能也会很快被访问。如程序代码的顺序执行，对线快被访问。如程序代码的顺序执行，对线性数据结构的访问或处理、常用变量等。性数据结构的访问

2、或处理、常用变量等。问题：能否将部分程序装入内存后就开始运行作业？为什么？（三）程序局部性原理的应用理由是：理由是：（四）虚拟存储器的定义与特性1.是指仅把作业的一部份是指仅把作业的一部份装入内存便可以运行作业的存储器系统。装入内存便可以运行作业的存储器系统。也即，指具有请求调入功能和置换功也即，指具有请求调入功能和置换功能，能从逻辑上对内存容量进行扩充的能，能从逻辑上对内存容量进行扩充的一种存储器系统。一种存储器系统。2.2.虚拟存储器的新特性虚拟存储器的新特性交换区（SWAP）：进程刚建立时，页表记录页面所在辅存位置，即程序文件所在的外存位置。但程序文件中一般包含有程序的二进制目标码及数据

3、初始值和初值为0的工作区。后两者在回写时不能写入程序文件所在辅存区，因此引入了交换区临时存储区。（就绪挂起、阻塞挂起的进程）23222625272326222527212423242526272421外存交换区外存202122换出21，换入25换出24，换入27内存页表例：内存原存放外存的21块和24块（存放数据和初始值），现需调入25和27块，因内存不足，需对换。它受两方面的限制。 一个是指令中表示的地址长度。假设地址长度为32字节，按字节寻址，则逻辑空间（虚存空间）大小为232个字节。（个字节）另一个是外存容量。用户的虚拟空间不能超过硬盘中作业的存放空间。（四）虚拟存储器的定义与特性（五）

4、实现虚拟存储的基本方法可采用页式虚存管理、段式虚存管理和段页式虚存管理。如： 。在页式管理的基础上，仅将进程的一部分页放于主存。页表项中注明该页是否在主存。程序执行时，如果访问的页不在主存，根据页表项的指示，将其从外存调入主存，如果此时无可用的内存空间，则先淘汰若干页帧。 （其他方法基本相同）一、基本原理 页式虚拟存储管理方式是在分页系统的基础上，增加了请求调页功能、页面置换功能所形成的虚拟存储器系统。状态位：表示该页是否已经调入内存。访问位：表示该页在内存间是否被访问过修改位：表示该页在内存是否被修改过。页号内存块号 二、页表项结构对页表增加了一些项目，具体如下： 三、地址变换机构与页式管理

5、基本相同，只是缺页时产生缺页中断，先将该页调入内存，再访问。见下图示。指令执行步骤与缺页中断处理过程5.8 页面置换算法页面置换算法一、目的与要求：一、目的与要求：1 1、掌握页面替换策略中的基本概念、掌握页面替换策略中的基本概念2、掌握驻留集固定的三种页面替换、掌握驻留集固定的三种页面替换策略。策略。3、掌握影响缺页中断率的主要因素、掌握影响缺页中断率的主要因素4 4、了解动态驻留集的页面替换策略。、了解动态驻留集的页面替换策略。二、重点与难点1、固定驻留集算法2、SWS等实用动态驻留集算法。三、课时：2(90分钟)四、教法：讲授法五、教具六、教学过程1、介绍有关概念及替换策略分类2、详细介

6、绍驻留集固定的页面替换策略3、简略介绍可变驻留集替换策略本节主要讲述的内容一、页面替换策略中的基本概念 二、页面替换策略的分类三、驻留集大小固定的替换策略四、页面替换算法解题举例五、影响缺页中断率的主要因素六、页面替换策略应用实例七、驻留集可变的替换策略八、替换策略选择一、页面替换一、页面替换( (策略策略) )策略中的基本概念策略中的基本概念 地址映射过程中，若在页面中地址映射过程中，若在页面中发现所要访问的页面不再内存中，则产生缺页发现所要访问的页面不再内存中，则产生缺页中断。当发生缺页中断时操作系统必须在内存中断。当发生缺页中断时操作系统必须在内存选择一个页面将其移出内存，以便为即将调入

7、选择一个页面将其移出内存，以便为即将调入的页面让出空间。而用来选择淘汰哪一页的规的页面让出空间。而用来选择淘汰哪一页的规则叫做页面置换算法则叫做页面置换算法( (策略策略) )。一、页面替换一、页面替换( (策略策略) )策略中的基本概念策略中的基本概念 进程的合法页集合；也即系进程的合法页集合；也即系统分给一个进程的内存可用块数。统分给一个进程的内存可用块数。：进程的存储访问序列或进程的存储访问序列或进程访问虚空间的地址踪迹。页式虚存管理以进程访问虚空间的地址踪迹。页式虚存管理以页为基本单位，只需页号即可。页面走向可合页为基本单位，只需页号即可。页面走向可合理简化。理简化。页面走向可合理简化

8、原则：页面走向可合理简化原则： （1 1）对于给定的页面大小，仅考虑其）对于给定的页面大小，仅考虑其页号，不关心完整的地址。页号，不关心完整的地址。 （2 2）如果当前对页面）如果当前对页面P P进行了访问，那进行了访问，那么，马上又对该页访问就不会缺页。这样么，马上又对该页访问就不会缺页。这样连续出现的页号就简化为一个页号。连续出现的页号就简化为一个页号。举例：某进程依次访问如下地址：0100，0432，0101，0612，0102，0103，0104，0101，0611，0102，0103，0104，0101，0610，0102，0103，0104，0101，0609，0102，0105。

9、若页面大小为100，上述访问串可简化为：1，4，1，6，1，6，1，6，1，6，1二、页面替换策略分成两类： 驻留集大小固定的替换策略； 驻留集大小可变的替换策略。三、驻留集大小固定的替换策略(一)先进先出置换算法(FIFO)(二)最佳置换算法(OPT)(三)最近最少使用算法(LRU)(四)时钟置换算法(CLOCK)(一) FIFO替换算法优先淘汰最早进入内存的页面，亦即在内存中驻留时间最久的页面7012030423032是012030423032是 是7712030423032是 是77700是2030423032是 是77700是1是017030423032是 是77700是1是0202否

10、 是1100423032是 是77700是1是0202否 是11 123 3是0423032是 是77700是1是0202否 是11 1233是230 0是023032是 是77700是1是0202否 是11 1233是2300是304 4是03032是 是77700是1是0202否 是11 1233是2300是304 4是0 04 42 2是0032是 是77700是1是0202否 是11 1233是2300是304 4是0 04422是423 3是032是 是77700是1是0202否 是11 1233是2300是304 4是0 04422是423 3是 否 否（1 1）FIFOFIFO方

11、法的特点：方法的特点： 实现方便。不需要额外硬件。实现方便。不需要额外硬件。 效果不好，有效果不好，有BeladyBelady奇异。奇异。（2 2）FIFOFIFO存在存在BeladyBelady奇异：奇异：指替换策指替换策略不满足随着驻留集的增大，页故障略不满足随着驻留集的增大，页故障数（缺页中断次数）一定减少的规律。数（缺页中断次数）一定减少的规律。 这一规律由这一规律由BeladyBelady于于19691969年发现，年发现，故称为故称为BeladyBelady异常异常 (二) OPT替换算法当要调入一页而必须淘汰旧页时，应该淘汰以后不再访问的页，或距现在最长时间后要访问的页面。 19

12、66年，年，Belady提出最佳提出最佳(优优)页面替换算页面替换算法法(OPTimal replacement，OPT)。是操作。是操作系统存储管理中的一种全局页面替换策略系统存储管理中的一种全局页面替换策略 。7012030423032是7012030423032是 是7712030423032是 是70是70712030423032是 是70是70701是71030423032是 是70是70701是701 102 2否 是71030423032是 是70是70701是701 102 2否 是2 20 03否 是71030423032是 是70是70701是701 102 2否 是2 2

13、0 03否 是2 23 3否 否 是47103042332是 是70是70701是701 102 2否 是2 20 03否 是2 23 3否 否 是4否 否(三) LRU替换算法：淘汰上次使用距当前最远的页或最近很少使用的页。7012030423032是7012030423032是 是7712030423032是 是70是70712030423032是 是70是70701是71030423032是 是70是70701是701 102 2否 是71030423032是 是70是70701是701 102 2否 是2 20 03否 是71030423032是 是70是70701是701 102 2

14、否 是2 20 03否 是40 03 3是71030423032是 是70是70701是701 102 2否 是2 20 03否 是40 03 3是20 04 4是71030423032是 是70是70701是701 102 2否 是2 20 03否 是40 03 3是20 04 4是32 24 4是7103042332是 是70是70701是701 102 2否 是2 20 03否 是40 03 3是20 04 4是32 24 4是否 否 LRU算法，内存块为算法，内存块为3时，缺页中断次数为时，缺页中断次数为8次。次。LRU算法，内存块为算法，内存块为4时，缺页中断次数为时，缺页中断次数为

15、7次。次。实现方法1用计数器实现LRU举例：若驻留集大小为3，访问串为 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 20/71/70/02/71/00/10/22/01/11/20/02/12/21/00/33/20/01/30/41/02/31/42/00/22/40/31/20/01/32/21/00/33/22/01/30/2实现方法2用栈实现LRU 可用一个特殊的栈来保存当前使用的各个页面的页面号。每当进程访问某页面时便将该面页从栈中移出，然后将它压入栈顶。因此，栈顶始终是最新的页号，而栈底则是最近最久未使用的页号。例如:举例：驻留集大小为3，访问串为 7,

16、 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2707107210021302032403240324032302230淘汰的页：7 1 2 3 0 4缺页次数：9次栈顶栈底(四四)时钟置换算法时钟置换算法(CLOCK) CLOCKCLOCK算法是算法是LRULRU算法的近似算法。算法的近似算法。CLOCKCLOCK算法给每个页面设置一个访问位，算法给每个页面设置一个访问位，标识该页最近有没有被访问过，再将内存标识该页最近有没有被访问过，再将内存中的所有页面通过一个指针链接成一个循中的所有页面通过一个指针链接成一个循环队列。其算法流程图如下图所示。环队列。其算法流程图如下

17、图所示。开始该页命中？P指针不动，将命中页的页面访问位置为1P指针所指页面访问位=0？淘汰该页，换入新页，该页页面访问位置为1P指针下移一个页面置该页页面访问位为0P指针下移一个页面YESNOYESNOCLOCK算法的流程图读取要访问的页号读取要访问的页号CLOCK算法举例：驻留集大小为3，访问串为 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2淘汰页序: O O O 7 1 2 0 3 41/70/-0/-1/71/01/71/01/10/70/00/11/20/00/11/21/00/11/21/01/30/20/00/31/40/00/31/41/20/31/

18、41/21/30/40/21/01/30/21/01/31/21/00/40/20/31/20/00/11/20/01/30/-0/-0/-初始注意: 若循环链表存在当前访问页(命中)时，直接将其访问位改为1指针不移动（命中后指针不移动）；否则，若当前P指针指向页面的访问位为0，则淘汰该页，调入新页将其访问位改为1，指针移到下一个物理块；若当前P指针指向页面的访问位为1则将其访问位改为0,并移动指针到下一个物理块。 CLOCK算法的优点是:比LRU算法少了很多硬件的支持，实现比较简单，但和FIFO算法相比，仍需要较多的硬件支持。缺页次数为缺页次数为9次；缺页中断率次；缺页中断率f= 9/1275%. 缺页次数为缺页次数为7次，缺页中断率：次，缺页中断率： f=7/12=58.3%。缺页次数为缺页次数为6次，缺页中断率：次，缺页中断率： f=6/12=50%。缺页次数为缺页次数为10次，缺页中断率：次，缺页中断率： f=10/12=83.3%。对于如下的页面访问序列：对于如下的页面访问序列：7 7，1 1， 2 2， 0 0，3 3，0 0，4 4， 2 2， 3 3， 0 0， 3 3， 2 2， 7 7， 0 0 。当内存块数。当内存块数量为量为4 4时，试问：使用栈结构实现时，试问：使用栈结构实现LRULRU置换算法产置换算法产生的缺页中断是多