第5章 虚拟存储器

1、第五章第五章 虚拟存储器虚拟存储器n重点重点n理解理解虚拟存储器的基本概念虚拟存储器的基本概念 n掌握掌握请求分页系统的基本原理请求分页系统的基本原理 n掌握页面置换算法掌握页面置换算法n页面抖动的工作集模型页面抖动的工作集模型n难点难点n请求分页系统的地址转换请求分页系统的地址转换n页面置换算法页面置换算法第五章第五章 虚拟存储器虚拟存储器n知识点知识点n虚拟存储器的基本概念、特征虚拟存储器的基本概念、特征n页面置换技术页面置换技术 n请求分页系统，页表机制、地址变换请求分页系统，页表机制、地址变换n页面置换算法页面置换算法n页面抖动工作集模型页面抖动工作集模型第五章虚拟存储器 5.1 虚拟

2、存储器概述虚拟存储器概述 5.2请求分页存储管理方式请求分页存储管理方式 5.3页面置换算法页面置换算法5.4“抖动抖动”与工作集与工作集5.5请求分段存储管理方式请求分段存储管理方式5.1 虚拟存储器概述虚拟存储器概述n5.1.1 常规存储管理方式的特征和局部性原常规存储管理方式的特征和局部性原理理n5.1.2 虚拟存储器的定义和特征虚拟存储器的定义和特征n5.1.3 虚拟存储器的实现方法虚拟存储器的实现方法5.1.1 常规存储管理方式的特征和局部性原理常规存储管理方式的特征和局部性原理连续分配连续分配 离散分配离散分配 (基本基本)分页分页 (基本基本)分段分段段页式段页式方便程序装入方便

3、程序装入提高内存利用率提高内存利用率n程序装入内存时可能出现的问题程序装入内存时可能出现的问题n程序太大，要求的空间超出了内存总容量程序太大，要求的空间超出了内存总容量n大量作业要求运行，但内存不能容下所有作业大量作业要求运行，但内存不能容下所有作业n常规存储器管理方式的特征常规存储器管理方式的特征n一次性一次性n要求作业全部装入内存才能运行要求作业全部装入内存才能运行n驻留性驻留性n程序装入内存后便一直驻留内存，直至运行结束程序装入内存后便一直驻留内存，直至运行结束许多不用或暂时不用的程序占用了大量内存空许多不用或暂时不用的程序占用了大量内存空间，而其他程序却无法装入！间，而其他程序却无法装

4、入！是否必要？是否必要？5.1.1 常规存储管理方式的特征和局部性原理常规存储管理方式的特征和局部性原理n局部性原理（局部性原理（1968年，年， Denning.P） n程序执行时，除了少部分的转移和过程调用指程序执行时，除了少部分的转移和过程调用指令外，在大多数情况下仍是令外，在大多数情况下仍是顺序执行顺序执行的；的；n过程调用将会使程序的执行轨迹由一部分区域过程调用将会使程序的执行轨迹由一部分区域转至另一部分区域，但经研究看出，过程调用转至另一部分区域，但经研究看出，过程调用的深度在大多数情况下都的深度在大多数情况下都不超过不超过5；n程序中存在许多程序中存在许多循环结构循环结构，这些虽

5、然只由少数，这些虽然只由少数指令构成，但是它们将多次执行；指令构成，但是它们将多次执行；n程序中还包括许多对数据结构的处理，如对数程序中还包括许多对数据结构的处理，如对数组进行操作，它们往往都组进行操作，它们往往都局限于很小的范围内局限于很小的范围内5.1.1 常规存储管理方式的特征和局部性原理常规存储管理方式的特征和局部性原理n局限性的表现局限性的表现n时间局限性时间局限性n某条指令被执行某条指令被执行= 不久以后该指令可能再次执行不久以后该指令可能再次执行n数据被访问过数据被访问过=不久以后该数据可能再次被访问不久以后该数据可能再次被访问n典型原因：因在程序中存在着大量典型原因：因在程序中

6、存在着大量循环操作循环操作n空间局限性空间局限性n存储单元被访问存储单元被访问=不久之后，其附近的存储单元也不久之后，其附近的存储单元也将被访问，即程序在一段时间内所将被访问，即程序在一段时间内所访问的地址访问的地址，可可能集中能集中在一定的范围之内在一定的范围之内n典型情况：程序的顺序执行。典型情况：程序的顺序执行。5.1.1 常规存储管理方式的特征和局部性原理常规存储管理方式的特征和局部性原理n虚拟存储器的基本工作情况虚拟存储器的基本工作情况n程序、数据、堆栈的大小可以超过内存的大小，程序、数据、堆栈的大小可以超过内存的大小，操作系统把程序当前使用的部分保留在内存，操作系统把程序当前使用的

7、部分保留在内存，而把其它部分保存在磁盘上，并在需要时在内而把其它部分保存在磁盘上，并在需要时在内存和磁盘之间动态交换。存和磁盘之间动态交换。n虚拟存储器支持多道程序设计技术虚拟存储器支持多道程序设计技术5.1.1 常规存储管理方式的特征和局部性原理常规存储管理方式的特征和局部性原理5.1.2 虚拟存储器的定义和特征虚拟存储器的定义和特征n虚拟存储器定义虚拟存储器定义n具有具有请求调入功能请求调入功能和和置换功能置换功能， 能从能从逻辑上逻辑上对对内存容量加以扩充的一种存储器系统内存容量加以扩充的一种存储器系统。其逻辑。其逻辑容量由容量由内存容量和外存容量之和内存容量和外存容量之和所决定，其运所

8、决定，其运行行速度速度接近于接近于内存速度，而其内存速度，而其成本成本却又接近于却又接近于外存。外存。n注意：注意：虚拟存储器的最大容量是由计算机的地虚拟存储器的最大容量是由计算机的地址结构确定的。如：若址结构确定的。如：若CPU的的有效地址长度有效地址长度为为32位，则程序可以寻址范围是位，则程序可以寻址范围是0(232-1) ，即，即虚存容量为虚存容量为 4GB。5.1.2 虚拟存储器的定义和特征虚拟存储器的定义和特征n虚拟存储器的特征虚拟存储器的特征n多次性多次性 n一个作业被分成多次调入内存运行一个作业被分成多次调入内存运行n对换性对换性n允许在作业的运行过程中进行换进、换出允许在作业

9、的运行过程中进行换进、换出n虚拟性虚拟性 n能够从逻辑上扩充内存容量，使用户所看到的内存能够从逻辑上扩充内存容量，使用户所看到的内存容量远大于实际内存容量容量远大于实际内存容量注意注意：以：以CPUCPU时间和外存空间换取昂贵内存空间，这是操时间和外存空间换取昂贵内存空间，这是操作系统中的作系统中的资源转换技术。资源转换技术。5.1.3 虚拟存储器的实现方法虚拟存储器的实现方法n虚拟存储器的实现虚拟存储器的实现n建立在建立在离散分配离散分配的存储管理方式基础上。的存储管理方式基础上。n主要实现方式主要实现方式n请求分页系统请求分页系统n请求分段系统请求分段系统5.1.3 虚拟存储器的实现方法虚

10、拟存储器的实现方法n请求分页系统：请求分页系统：在分页系统的基础上增加了在分页系统的基础上增加了请请求调页求调页功能和功能和页面置换页面置换功能功能n硬件支持硬件支持n页表机制页表机制。在纯分页的页表机制上增加若干项。在纯分页的页表机制上增加若干项而形成的，作为请求分页的数据结构；而形成的，作为请求分页的数据结构；n缺页中断机构缺页中断机构。每当用户程序要访问的页面尚。每当用户程序要访问的页面尚未调入内存时未调入内存时 便产生一缺页中断，以请求便产生一缺页中断，以请求OS将将所缺的页调入内存；所缺的页调入内存；n地址变换机构地址变换机构。在纯分页地址变换机构的基础。在纯分页地址变换机构的基础上

11、发展形成的上发展形成的n软件支持软件支持n实现实现请求调页请求调页的软件和实现的软件和实现页面置换页面置换的软件的软件5.1.3 虚拟存储器的实现方法虚拟存储器的实现方法n请求分段系统请求分段系统n系统同样需要必要的硬件支持：系统同样需要必要的硬件支持：n段表机制。段表机制。在纯分段的段表机制基础上，增加在纯分段的段表机制基础上，增加若干项而形成的；若干项而形成的；n缺段中断机构。缺段中断机构。每当用户程序所要访问的段尚每当用户程序所要访问的段尚未调入内存时，产生一缺段中断，请求未调入内存时，产生一缺段中断，请求OS将所将所缺的段调入内存；缺的段调入内存；n地址变换机构。地址变换机构。与请求调

12、页类似，实现请求调与请求调页类似，实现请求调段和置换功能也需要得到段和置换功能也需要得到OS的支持。的支持。5.2 请求分页存储管理方式请求分页存储管理方式n5.2.1 请求分页中的硬件支持请求分页中的硬件支持n5.2.2 请求式分页中的内存分配请求式分页中的内存分配n5.2.3 页面调入策略页面调入策略5.2.1 请求分页中的硬件支持请求分页中的硬件支持n系统系统需要解决的问题需要解决的问题n如何获知进程当前所需页面不在主存？如何获知进程当前所需页面不在主存？n如何把所缺页面调入主存？如何把所缺页面调入主存？n采用什么策略选择欲淘汰的页面？采用什么策略选择欲淘汰的页面？n当主存中没有空闲的页

13、框时，为了要接受一个新页，当主存中没有空闲的页框时，为了要接受一个新页，需要需要把老的一页淘汰出去。把老的一页淘汰出去。5.2.1 请求分页中的硬件支持请求分页中的硬件支持n请求页表机制请求页表机制n状态位状态位P（中断位）指示该页是在内存还是在（中断位）指示该页是在内存还是在外存外存n访问位访问位A 用于记录本页在一段时间内用于记录本页在一段时间内被访问的被访问的次数次数或记录本页在最近多长时间或记录本页在最近多长时间未被访问未被访问n修改位修改位M 表示该页在内存中是否表示该页在内存中是否被修改过被修改过n外存地址外存地址 该页在外存上的地址，通常是物理该页在外存上的地址，通常是物理块号。

14、块号。页号页号 物理块号物理块号 状态位状态位P 访问位访问位A 修改位修改位M外存地址外存地址 5.2.1 请求分页中的硬件支持请求分页中的硬件支持n缺页中断机构缺页中断机构n在请求分页系统中，每当所要访问的页面不在在请求分页系统中，每当所要访问的页面不在内存时，便产生一内存时，便产生一缺页中断。缺页中断。相应的中断处理相应的中断处理程序把控制转向缺页中断子程序，执行此子程程序把控制转向缺页中断子程序，执行此子程序，即把所缺页面装入主存，然后处理机重新序，即把所缺页面装入主存，然后处理机重新执行缺页时打断的指令。这时，就将顺利形成执行缺页时打断的指令。这时，就将顺利形成物理地址。物理地址。n

15、缺页中断与一般中断的区别缺页中断与一般中断的区别n在指令执行期间产生和处理中断信号在指令执行期间产生和处理中断信号n一条指令在执行期间可能产生多次缺页中断。一条指令在执行期间可能产生多次缺页中断。涉及涉及6次缺页中断的指令次缺页中断的指令 例例. COPY, 能够移动能够移动256B块可能跨越页边界；块可能跨越页边界；移动部分字符后出现页错误；移动部分字符后出现页错误；如果源和目的块有重叠，如果源和目的块有重叠，源块可能已被修改。源块可能已被修改。解决方案解决方案试图存取两个块的两端；试图存取两个块的两端；使用临时寄存器保存被覆盖使用临时寄存器保存被覆盖位置的值。位置的值。5.2.1 请求分页

16、中的硬件支持请求分页中的硬件支持5.2.1 请求分页中的硬件支持请求分页中的硬件支持n地址变换机构地址变换机构n在分页系统地址变换机构的基础上，增加实现虚拟存在分页系统地址变换机构的基础上，增加实现虚拟存储器某些功能形成的，如产生和处理缺页中断，以及储器某些功能形成的，如产生和处理缺页中断，以及从内存中换出一页的功能等等。从内存中换出一页的功能等等。n地址变换过程地址变换过程n检索快表，试图从中找出所要访问的页。若找到，便检索快表，试图从中找出所要访问的页。若找到，便修改页表项中的访问位。对于写指令，还须将修改位修改页表项中的访问位。对于写指令，还须将修改位置成置成“1”；n然后利用页表项中给

17、出的物理块号和页内地址形成物然后利用页表项中给出的物理块号和页内地址形成物理地址，结束。理地址，结束。 n内存中去查找页表，再从找到的页表项中的状态位内存中去查找页表，再从找到的页表项中的状态位P，来了解该页是否已调入内存。来了解该页是否已调入内存。请请求求分分页页中中的的地地址址变变换换过过程程 缺页中断处理缺页中断处理保留保留CPU现场现场从外存中找到缺页从外存中找到缺页内存满否？内存满否？选择一页换出选择一页换出该页被修改否？该页被修改否？将该页写回外存将该页写回外存启动启动I/O硬件硬件将一页从外存换入内存将一页从外存换入内存修改页表修改页表否否是是是是否否页表项在快表中？页表项在快表

18、中？CPU检索快表检索快表访问页表访问页表否否页在内存？页在内存？修改访问位和修改位修改访问位和修改位形成物理地址形成物理地址地址变换结束地址变换结束否否页号页页号页表长度表长度?开始开始程序请求访问一页程序请求访问一页产生缺页中产生缺页中断请求调页断请求调页修改快表修改快表是是越界中断越界中断是是是是OS命令命令CPU从外存读缺页从外存读缺页5.2.2 请求分页中的内存分配请求分页中的内存分配n最小物理块数的确定最小物理块数的确定 n指保证进程正常运行所需的指保证进程正常运行所需的最小物理块数最小物理块数。当系。当系统分配的物理块数少于此值时，进程将无法运行统分配的物理块数少于此值时，进程将

19、无法运行n与计算机的硬件结构有关，取决于指令的格式、与计算机的硬件结构有关，取决于指令的格式、 功能和寻址方式功能和寻址方式n单地址指令单地址指令且采用且采用直接寻址方式直接寻址方式的机器，则所需最少的机器，则所需最少2个个物理块。其中，一块存放指令页面，另一块则存放数据物理块。其中，一块存放指令页面，另一块则存放数据页面页面n允许间接寻址允许间接寻址的机器，至少要求有的机器，至少要求有3个个物理块物理块n两个或多于两个字节指令两个或多于两个字节指令的机器，其指令本身可能跨两的机器，其指令本身可能跨两个页面，且源和目标地址所涉及的区域也可能跨两个页个页面，且源和目标地址所涉及的区域也可能跨两个

20、页面，至少需要面，至少需要6个个物理块物理块5.2.2 请求分页中的内存分配请求分页中的内存分配n最小物理块数的确定最小物理块数的确定n不同的作业要求不同。不同的作业要求不同。n如：允许间接寻址：则至少要求如：允许间接寻址：则至少要求3个物理块。个物理块。nMov A, BnLoad 1, 1000n 方式，方式，n 则所需的最少则所需的最少n 物理块数为物理块数为25.2.2 请求分页中的内存分配请求分页中的内存分配n物理块的分配策略物理块的分配策略 n在请求分页系统中，可采取两种内存分配策略，在请求分页系统中，可采取两种内存分配策略，即即固定固定和和可变可变分配策略。在进行置换时，也可分配

21、策略。在进行置换时，也可采取两种策略，即采取两种策略，即全局置换全局置换和和局部置换局部置换。于是。于是可组合出以下三种适用的策略可组合出以下三种适用的策略n固定分配局部置换固定分配局部置换(Fixed Allocation, Local Replacement) n可变分配全局置换可变分配全局置换(Variable Allocation, Global Replacement) n可变分配局部置换可变分配局部置换(Variable Allocation, Local Replacemen问题：分配块数难确定，太少，问题：分配块数难确定，太少，缺页频繁，吞吐量降低；太多，缺页频繁，吞吐量降低；

22、太多，内存驻留进程数减少，内存驻留进程数减少，CPU或或其它资源可能空闲其它资源可能空闲先分配给各进程一定数先分配给各进程一定数的物理块，系统有一空的物理块，系统有一空闲物理块队列，缺页时闲物理块队列，缺页时从空闲队列取，若空闲从空闲队列取，若空闲队列空时，再选页调出队列空时，再选页调出先分配给各进程一定先分配给各进程一定数的物理块，缺页时数的物理块，缺页时从该进程在内存的页从该进程在内存的页选一换出，若其频繁选一换出，若其频繁缺页，系统再分配若缺页，系统再分配若干附加物理块干附加物理块5.2.2 请求分页中的内存分配请求分页中的内存分配n物理块分配算法物理块分配算法n平均分配算法平均分配算法

23、n将系统中所有可供分配的物理块，平均分配将系统中所有可供分配的物理块，平均分配给各个进程给各个进程n 例：当系统中有例：当系统中有100个物理块，有个物理块，有5个进程在个进程在运行时，每个进程可分得运行时，每个进程可分得20个物理块。个物理块。n不公平的，因为它未考虑到各进程本身的大不公平的，因为它未考虑到各进程本身的大小。如有一个进程其大小为小。如有一个进程其大小为200页，只分配页，只分配给它给它20个块，这样，它必然会有很高的缺页个块，这样，它必然会有很高的缺页率；而另一个进程只有率；而另一个进程只有10页，却有页，却有10个物理个物理块闲置未用块闲置未用5.2.2 请求分页中的内存分

24、配请求分页中的内存分配n物理块分配算法物理块分配算法n按比例分配算法按比例分配算法n根据进程的大小按比例分配物理块的算法。如果系根据进程的大小按比例分配物理块的算法。如果系统中共有统中共有n个进程，每个进程的页面数为个进程，每个进程的页面数为Si，则系统，则系统中各进程页面数的总和为：中各进程页面数的总和为： n又假定系统中可用的物理块总数为又假定系统中可用的物理块总数为m，则每个进程，则每个进程所能分到的物理块数为所能分到的物理块数为bi，将有：，将有：n b应该取整，它必须大于最小物理块数应该取整，它必须大于最小物理块数niiSS1mSSbii5.2.2 请求分页中的内存分配请求分页中的内

25、存分配n物理块分配算法物理块分配算法n考虑优先权的分配算法考虑优先权的分配算法n在实际应用中，为了使在实际应用中，为了使重要的、紧迫重要的、紧迫的用户的用户程序能尽快地完成，为它分配较多的内存空程序能尽快地完成，为它分配较多的内存空间。间。n通常方法是把内存中可供分配的所有物理块通常方法是把内存中可供分配的所有物理块分成分成两部分两部分：一部分：一部分按比例按比例地分配给各进程；地分配给各进程；另一部分则根据各进程的另一部分则根据各进程的优先权优先权，适当地增适当地增加加其相应份额后，分配给各进程。其相应份额后，分配给各进程。n在重要的系统，如在重要的系统，如实时控制系统实时控制系统，则可能是

26、，则可能是完全按优先权完全按优先权为各进程分配其物理块的。为各进程分配其物理块的。5.2.3 页面调入策略页面调入策略n调入页面的时机调入页面的时机n预调页策略预调页策略n采用一种以预测为基础的预调页策略，将那采用一种以预测为基础的预调页策略，将那些预计在不久之后便会被访问的页面预先调些预计在不久之后便会被访问的页面预先调入内存，成功率入内存，成功率50%n请求调页策略请求调页策略n当进程在运行中需要访问某部分程序和数据当进程在运行中需要访问某部分程序和数据时，若发现其所在的页面不在内存，便提出时，若发现其所在的页面不在内存，便提出请求，由请求，由OS将其所需页面调入内存将其所需页面调入内存n

27、目前的虚拟存储中大多采用此种策略目前的虚拟存储中大多采用此种策略5.2.3 页面调入策略页面调入策略n从何处调入页面从何处调入页面n外存分为两部分外存分为两部分n通常，对换区采用连续分配方式，文件采用离通常，对换区采用连续分配方式，文件采用离散分配方式。系统应从何处将缺页调入内存，散分配方式。系统应从何处将缺页调入内存，分成三种情况分成三种情况n系统拥有足够的对换区空间系统拥有足够的对换区空间n系统缺少足够的对换区空间系统缺少足够的对换区空间nUNIX方式方式5.2.3 页面调入策略页面调入策略n所需的页面全部从对换区调入，以提高调页速度。为所需的页面全部从对换区调入，以提高调页速度。为此，在

28、进程运行前，此，在进程运行前， 将与该进程有关的文件，从文件将与该进程有关的文件，从文件区拷贝到对换区。区拷贝到对换区。n凡是不会被修改的文件，都直接从文件区调入；而当凡是不会被修改的文件，都直接从文件区调入；而当换出这些页面时，由于它们未被修改而不必再将它们换出这些页面时，由于它们未被修改而不必再将它们换出，以后再调入时，仍从文件区直接调入。换出，以后再调入时，仍从文件区直接调入。n对于那些可能被修改的部分，在将它们换出时，调到对于那些可能被修改的部分，在将它们换出时，调到对换区，以后需要时，再从对换区调入。对换区，以后需要时，再从对换区调入。5.2.3 页面调入策略页面调入策略n由于与进程

29、有关的文件都放在文件区，故凡是由于与进程有关的文件都放在文件区，故凡是未运行过的页面，都应从文件区调入。而对于未运行过的页面，都应从文件区调入。而对于曾经运行过但又被换出的页面，由于是被放在曾经运行过但又被换出的页面，由于是被放在对换区，因此在下次调入时，应从对换区调入。对换区，因此在下次调入时，应从对换区调入。n由于由于UNIX系统允许页面共享，因此，某进程系统允许页面共享，因此，某进程所请求的页面有可能已被其它进程调入内存，所请求的页面有可能已被其它进程调入内存，此时也就无须再从对换区调入。此时也就无须再从对换区调入。5.2.3 页面调入策略页面调入策略n页面调入过程页面调入过程n每当程序

30、所要访问的页面未在内存时，便向每当程序所要访问的页面未在内存时，便向CPU发出一发出一缺页中断缺页中断。 n查找所需页在磁盘上的位置；查找所需页在磁盘上的位置；n查找一空闲帧；查找一空闲帧；ni) 如果有空闲帧，那么就使用它；如果有空闲帧，那么就使用它；nii) 如果没有空闲帧，那么就使用页置换算法以如果没有空闲帧，那么就使用页置换算法以选择一个选择一个“牺牲牺牲”帧（帧（victim frame）；）；niii) 将将“牺牲牺牲”帧的内容写到磁盘上，改变页表帧的内容写到磁盘上，改变页表和帧表。和帧表。n将所需页读入（新）空闲帧，改变页表和帧表；将所需页读入（新）空闲帧，改变页表和帧表；n重启

31、用户进程。重启用户进程。请求分页中的地址变换过程请求分页中的地址变换过程缺页中断处理缺页中断处理保留保留CPU现场现场从外存中找到缺页从外存中找到缺页内存满否？内存满否？选择一页换出选择一页换出该页被修改否？该页被修改否？将该页写回外存将该页写回外存启动启动I/O硬件硬件将一页从外存换入内存将一页从外存换入内存修改页表修改页表否否是是是是否否页表项在快表中？页表项在快表中？CPU检索快表检索快表访问页表访问页表否否页在内存？页在内存？修改访问位和修改位修改访问位和修改位形成物理地址形成物理地址地址变换结束地址变换结束否否页号页页号页表长度表长度?开始开始程序请求访问一页程序请求访问一页产生缺页

32、中产生缺页中断请求调页断请求调页修改快表修改快表是是越界中断越界中断是是是是OS命令命令CPU从外存读缺页从外存读缺页页置换例子页置换例子n访问页访问页f页置换例子（页置换例子（cont.）5.2.3 页面调入策略页面调入策略页面调入页面调入页面在内存页面在内存页面未在内存页面未在内存内存能容纳新页内存能容纳新页内存已满内存已满该页未被修改过该页未被修改过该页已被修改该页已被修改5.2.3 页面调入策略页面调入策略n缺页率缺页率n进程在运行过程中，访问页面失败的次数进程在运行过程中，访问页面失败的次数F F，与对页面访问次数与对页面访问次数A A的比值的比值f,f,即即n影响缺页次数的因素影响

33、缺页次数的因素n 分配给进程的分配给进程的物理页面数物理页面数n 页面本身的页面本身的大小大小n 程序的程序的编制方法编制方法n 页面页面淘汰算法淘汰算法5.3 页面置换算法页面置换算法n5.3.1 先进先出置换算法和最佳置换算法先进先出置换算法和最佳置换算法n5.3.2 最近最久未使用和最少使用置换算法最近最久未使用和最少使用置换算法n5.3.3 CLOCK置换算法置换算法n5.3.4 页面缓存算法页面缓存算法n5.3.5 访问内存的有效时间访问内存的有效时间5.3 页面置换算法页面置换算法n评价标准评价标准n最低的缺页率。最低的缺页率。n评价方法评价方法n通过运行一个特殊的页面引用串检验算

34、法，计通过运行一个特殊的页面引用串检验算法，计算其页错误率；算其页错误率；n基本条件：事先知道可用帧的数量；基本条件：事先知道可用帧的数量；n测试用例：可用帧的数量为测试用例：可用帧的数量为3，页面引用串如，页面引用串如下：下：7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 15.3.1 先进先出置换算法和最佳置换算法先进先出置换算法和最佳置换算法n先进先出先进先出(FIFO)页面置换算法页面置换算法 n选择在内存中选择在内存中驻留时间最长驻留时间最长的页并淘汰之。的页并淘汰之。n优点优点：实现简单，只需把一个进程已调入内存：实

35、现简单，只需把一个进程已调入内存的页面，按先后次序链接成一个队列，并设置的页面，按先后次序链接成一个队列，并设置一个指针，称为替换指针，使它总是指向最老一个指针，称为替换指针，使它总是指向最老的页面。的页面。n缺点缺点：与进程实际运行的规律不相适应，因为：与进程实际运行的规律不相适应，因为在进程中，有些页面经常被访问，比如，含有在进程中，有些页面经常被访问，比如，含有全局变量、常用函数、例程等的页面，不能保全局变量、常用函数、例程等的页面，不能保证这些页面不被淘汰。证这些页面不被淘汰。引用次序引用次序7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 177070120

36、1231230430420423页帧（页框）页帧（页框） 3次次 12次次 缺页缺页 0230130127127027015.3.1 先进先出置换算法和最佳置换算法先进先出置换算法和最佳置换算法n先进先出先进先出(FIFO)页面置换算法页面置换算法1234125349 page faults213 4215 1324 51235.3.1 先进先出置换算法和最佳置换算法先进先出置换算法和最佳置换算法n先进先出先进先出(FIFO)页面置换算法页面置换算法n引用页：引用页：1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5。n3个帧（每个进程最多只有个帧（每个进程最多只有3个页面同

37、时在内存）个页面同时在内存）n先进先出先进先出(FIFO)页面置换算法页面置换算法n引用页：引用页：1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5。n4个帧个帧nBelady异常：帧越多，页错误越多。异常：帧越多，页错误越多。10 page faults1235124543213 4215 1324 512345.3.1 先进先出置换算法和最佳置换算法先进先出置换算法和最佳置换算法5.3.1 先进先出置换算法和最佳置换算法先进先出置换算法和最佳置换算法n最佳最佳(Optimal)置换算法置换算法n最佳置换算法是由最佳置换算法是由Belady于于1966年提出的一种年提出的

38、一种理论上理论上的算法。的算法。n其其所选择的被淘汰页面，将是所选择的被淘汰页面，将是以后永不使用以后永不使用的，的，或许是在或许是在最长最长(未来未来)时间时间内内不再被访问不再被访问的页面。的页面。n优点优点：采用最佳置换算法，通常可保证获得最：采用最佳置换算法，通常可保证获得最低的缺页率。低的缺页率。n缺点缺点：无法预知一个进程在内存的若干个页面：无法预知一个进程在内存的若干个页面中，哪一个页面是未来最长时间内不再被访问中，哪一个页面是未来最长时间内不再被访问的。的。引用次序引用次序7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 177070120120324

39、3203201701页帧（页框）页帧（页框） 3次次 6次次 缺页缺页 5.3.1 先进先出置换算法和最佳置换算法先进先出置换算法和最佳置换算法n最佳最佳(Optimal)置换算法置换算法5.3.2 最近最久未使用和最少使用置换算法最近最久未使用和最少使用置换算法nLRU(Least Recently Used)置换算法的描述置换算法的描述n利用利用“最近的过去最近的过去”作为作为“最近的将来最近的将来”的近的近似，即，选择最近最久未使用的页面予以淘汰。似，即，选择最近最久未使用的页面予以淘汰。n选择选择最后一次访问时间距离当前时间最长最后一次访问时间距离当前时间最长的一的一页并淘汰之。即淘汰

40、没有使用的时间最长的页。页并淘汰之。即淘汰没有使用的时间最长的页。实现代价很高（时间戳或硬件方法）实现代价很高（时间戳或硬件方法）引用次序引用次序7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1770701201203403402432页帧（页框）页帧（页框） 3次次 9次次 缺页缺页 0321321021075.3.2 最近最久未使用和最少使用置换算法最近最久未使用和最少使用置换算法nLRU(Least Recently Used)置换算法置换算法5.3.2 最近最久未使用和最少使用置换算法最近最久未使用和最少使用置换算法nLRU置换算法的硬件支持置换算法的硬件

41、支持n优点：对于各种类型的程序都能适用；优点：对于各种类型的程序都能适用；n缺点：要求系统具有较多的支持硬件，实现难度大；缺点：要求系统具有较多的支持硬件，实现难度大；n主要问题主要问题n 一个进程在内存中的各个页面各有多久时间未被进一个进程在内存中的各个页面各有多久时间未被进程访问；程访问；n 如何快速地知道哪一页最近最久未使用的页面。如何快速地知道哪一页最近最久未使用的页面。n硬件支持硬件支持n移位寄存器移位寄存器n栈栈5.3.2 最近最久未使用和最少使用置换算法最近最久未使用和最少使用置换算法nLRU置换算法的硬件支持置换算法的硬件支持n寄存器寄存器n为了记录某进程在内存中各页的使用情况

42、，为了记录某进程在内存中各页的使用情况，须为每个在内存中的页面配置一个移位寄存须为每个在内存中的页面配置一个移位寄存器，可表示为器，可表示为 n访问访问时将时将Rn-1位置成位置成1，定时信号，定时信号每隔一时间每隔一时间间隔右移一位间隔右移一位，则具有，则具有最小数值最小数值的寄存器所的寄存器所对应的页面，对应的页面，就是最近最久未使用就是最近最久未使用的页面的页面R=Rn-1Rn-2Rn-3 R2R1R0 实页实页R7R6R5R4R3R2R1R0101010010210101100实页实页R7R6R5R4R3R2R1R010010100102010101100t0t1实页实页R7R6R5R

43、4R3R2R1R010001010012001010110t2实页实页R7R6R5R4R3R2R1R0110010100200101011访问访问1实页实页R7R6R5R4R3R2R1R010100101002000101011t35.3.2 最近最久未使用和最少使用置换算法最近最久未使用和最少使用置换算法5.3.2 最近最久未使用和最少使用置换算法最近最久未使用和最少使用置换算法n栈栈n访问某页时，将该页面的页号从栈中移出或直访问某页时，将该页面的页号从栈中移出或直至栈空，再依次入栈，最后访问页入栈顶。至栈空，再依次入栈，最后访问页入栈顶。47407470417040174107421074

44、120742107462107470710121265.3.2 最近最久未使用和最少使用置换算法最近最久未使用和最少使用置换算法n最少使用最少使用(LFU: Least Frequently Used)置换算法置换算法n为内存中的每个页面设置一个为内存中的每个页面设置一个移位寄存器移位寄存器，用来记，用来记录该页面录该页面被访问的频率被访问的频率n该算法选择在最近使用最少的页面作为淘汰页该算法选择在最近使用最少的页面作为淘汰页n与最近最少用算法与最近最少用算法LRU的区别的区别n只考虑一段时间内使用的次数，而不管其使用的只考虑一段时间内使用的次数，而不管其使用的时间时间iR这种算法并不能真正反

45、映出页面的使用情况，因在每一时间这种算法并不能真正反映出页面的使用情况，因在每一时间间隔内只是用寄存器的一位来记录页的使用情况，因此访问间隔内只是用寄存器的一位来记录页的使用情况，因此访问1次和次和10000次是等效的。次是等效的。5.3.3 Clock置换算法置换算法n简单的简单的Clock置换算法置换算法（近似的近似的LRU） n为每页设置一位为每页设置一位访问位访问位，再将内存中的所有页，再将内存中的所有页面都通过链接指针链成一个循环队列。面都通过链接指针链成一个循环队列。n当某页被访问时，其访问位被置当某页被访问时，其访问位被置1。n置换算法在选择一页淘汰时，只需检查其访问置换算法在选

46、择一页淘汰时，只需检查其访问位。位。页号页号 物理块号物理块号 状态位状态位P 访问字段访问字段A 修改位修改位M外存地址外存地址 5.3.3 Clock置换算法置换算法n简单的简单的Clock置换算法置换算法n状态位状态位(存在位存在位)P。n修改位修改位M。表示该页在调入内存后是否被修改过。由。表示该页在调入内存后是否被修改过。由于内存中的每一页都在外存上保留一份副本，因此，于内存中的每一页都在外存上保留一份副本，因此，若未被修改，在置换该页时就不须将该写回到外存上；若未被修改，在置换该页时就不须将该写回到外存上；若已被修改，则必须将该页重写到外存上，以保证外若已被修改，则必须将该页重写到

47、外存上，以保证外存中所保留的始终是最新副本。存中所保留的始终是最新副本。n外存地址。外存地址。5.3.3 Clock置换算法置换算法n简单的简单的CLOCK置换算法置换算法n置换算法在选择一页淘汰时，只需检查页的置换算法在选择一页淘汰时，只需检查页的访访问位，是问位，是0换出，是换出，是1重新置重新置0且暂不换出，再且暂不换出，再按按FIFO检查下一个页面。检查到最后一个页检查下一个页面。检查到最后一个页面，若其访问位仍为面，若其访问位仍为1，则，则再返到队首再返到队首检查。检查。n由于该算法是循环地检查各页面的访问情况，由于该算法是循环地检查各页面的访问情况，故称为故称为CLOCK算法算法，

48、置换的是未使用过的页，置换的是未使用过的页，又称为又称为最近未用算法最近未用算法NRU（Not Recently Used）5.3.3 Clock置换算法置换算法n简单的简单的CLOCK置换算法置换算法入口入口查寻指针前进一步，指查寻指针前进一步，指向下一个表目向下一个表目页面访问位页面访问位0?选择该页面淘汰选择该页面淘汰是是返回返回置页面访置页面访问位问位“0”否否块号块号页号页号访问位访问位指针指针0124034215650711替换替换指针指针注意：是循环注意：是循环队列！队列！5.3.3 Clock置换算法置换算法5.3.3 Clock置换算法置换算法n改进型改进型Clock置换算法

49、置换算法n在将一个页面换出时，如果该页已被修改过，在将一个页面换出时，如果该页已被修改过，便须将它重新写到磁盘上；但如果该页未被修便须将它重新写到磁盘上；但如果该页未被修改过，则不必将它拷回磁盘。改过，则不必将它拷回磁盘。n同时满足两条件的页面作为首选淘汰的页。同时满足两条件的页面作为首选淘汰的页。页号页号 物理块号物理块号 状态位状态位P 访问字段访问字段A 修改位修改位M外存地址外存地址 5.3.3 Clock置换算法置换算法n改进型改进型Clock置换算法置换算法n状态位状态位(存在位存在位)P。n外存地址。外存地址。5.3.3 Clock置换算法置换算法n改进型改进型Clock置换算法

50、置换算法n考虑考虑使用情况使用情况和和置换代价，置换代价，换出的最好是未使用且未换出的最好是未使用且未被修改过的页面被修改过的页面n由由访问位访问位A和和修改位修改位M组合：组合：n1类类(A=0, M=0)：最近既未被访问，又未被修改，是最近既未被访问，又未被修改，是最佳淘汰页；最佳淘汰页；n2类类(A=0, M=1)：最近未被访问，但已被修改，并不最近未被访问，但已被修改，并不是很好的淘汰页；是很好的淘汰页；n3类类(A=1, M=0)：最近已被访问，但未被修改，最近已被访问，但未被修改， 该该页有可能再被访问；页有可能再被访问；n4类类(A=1, M=1)：最近已被访问且被修改，该页可能

51、：最近已被访问且被修改，该页可能再被访问。再被访问。5.3.3 Clock置换算法置换算法n改进型改进型Clock置换算法置换算法n执行过程执行过程n从指针所指示的当前位置开始，从指针所指示的当前位置开始， 扫描循环队列，扫描循环队列， 寻寻找找A=0且且M=0的页面，的页面， 将所遇到的第一个页面作为将所遇到的第一个页面作为所选中的淘汰页。所选中的淘汰页。 在在本次扫描期间不改变访问位本次扫描期间不改变访问位An如果第一步失败，即查找一周后未遇到第一类页面，如果第一步失败，即查找一周后未遇到第一类页面， 则开始第二轮扫描，则开始第二轮扫描，寻找寻找A=0且且M=1的页面，将所的页面，将所遇到

52、的第一个这类页面作为淘汰页。在第二轮扫描遇到的第一个这类页面作为淘汰页。在第二轮扫描期间，期间，将所有扫描过的页面的访问位将所有扫描过的页面的访问位A都置都置0n如果第二步也失败，亦即未找到第二类页面，则将如果第二步也失败，亦即未找到第二类页面，则将指针返回到开始指针返回到开始的位置，并将的位置，并将所有的访问位所有的访问位A复复0。 然后然后回到第一步。回到第一步。5.3.3 Clock置换算法置换算法n改进型改进型Clock置换算法置换算法-示例示例页号页号块号块号AM05001301210103111141411最佳淘汰页最佳淘汰页次佳淘汰页次佳淘汰页0005.3.4 页面缓冲算法页面缓

53、冲算法(PBA： Page Buffering Algorithm)n影响页面换进换出效率的若干因素影响页面换进换出效率的若干因素n页面置换算法页面置换算法n写回磁盘的效率写回磁盘的效率n读入内存的频率读入内存的频率5.3.4 页面缓冲算法页面缓冲算法(PBA： Page Buffering Algorithm)n页面缓存算法页面缓存算法PBAn采用了采用了可变分配可变分配和和局部置换局部置换方式，置换算法采用方式，置换算法采用FIFOn将一个被淘汰的页放入将一个被淘汰的页放入两个链表中的一个，即如两个链表中的一个，即如果页面果页面未被修改未被修改，就将它直接，就将它直接放进空闲链表放进空闲链

54、表中；中；否则，便放入否则，便放入已修改页面的链表已修改页面的链表中中 空闲链表空闲链表已修改链表已修改链表5.3.5 访问内存的有效时间访问内存的有效时间n页面在内存中，也在快表中页面在内存中，也在快表中nEAT=+n页面在内存中，不在快表中页面在内存中，不在快表中nEAT=+ +=2(+)n页面不在内存中页面不在内存中nEAT=+ += +2(+)n考虑缺页率考虑缺页率f，命中率，命中率nEAT=+ +(1- )+f(+ +)+(1-f)（+）5.4 “抖动抖动”与工作集与工作集n5.4.1 多道程序度与多道程序度与“抖动抖动”n5.4.2 工作集工作集n5.4.3 “抖动抖动”的预防方法

55、的预防方法5.4.1 多道程序度与多道程序度与“抖动抖动”n多道程序度与处理机的利用率多道程序度与处理机的利用率5.4.1 多道程序度与多道程序度与“抖动抖动”n抖动，又称为颠簸抖动，又称为颠簸n在虚存中，页面在内存与外存之间在虚存中，页面在内存与外存之间频繁调度频繁调度，以至于调度页面所需时间比进程实际运行的时以至于调度页面所需时间比进程实际运行的时间还多，此时系统效率急剧下降，甚至导致系间还多，此时系统效率急剧下降，甚至导致系统崩溃。这种现象称为颠簸或抖动。统崩溃。这种现象称为颠簸或抖动。n原因原因n页面淘汰算法不合理页面淘汰算法不合理n分配给进程的物理页面数太少分配给进程的物理页面数太少

56、5.4.2 工作集工作集n工作集的基本概念工作集的基本概念n1968年由年由Denning提出，并定义了局部模型。提出，并定义了局部模型。它表明进程执行时，从一个局部移到另一个局它表明进程执行时，从一个局部移到另一个局部。局部就是一个经常使用的页的集合。部。局部就是一个经常使用的页的集合。5.4.2 工作集工作集n缺页率与物理内存块数的关系缺页率与物理内存块数的关系5.4.2 工作集工作集n工作集的定义工作集的定义n工作集窗口（工作集窗口（Working set window）：最近）：最近个个页面引用页面引用n最近最近个引用的页集合称为工作集合个引用的页集合称为工作集合（Working se

57、t）nWSSi (进程进程Pi的工作集的工作集) = 最近所引用的所有页最近所引用的所有页面的总数（不同时刻值不同）面的总数（不同时刻值不同）n如果如果太小，则不能包含整个局部；太小，则不能包含整个局部；n如果如果太大，则可能包含多个局部；太大，则可能包含多个局部；n如果如果=，则包含了整个程序。，则包含了整个程序。5.4.2 工作集工作集n工作集的定义工作集的定义nD WSSi 表示总的帧需求量表示总的帧需求量nm=可分配的页帧可分配的页帧n如果如果 D 大于大于m，那么有的进程就得不到足够帧，那么有的进程就得不到足够帧，从而会出现颠簸从而会出现颠簸n策略：可以悬挂某些进程，以消除颠簸现象策

58、略：可以悬挂某些进程，以消除颠簸现象5.4.3 “抖动抖动”的预防方法的预防方法n采用局部置换策略采用局部置换策略n把抖动影响局限在单个进程内把抖动影响局限在单个进程内n把工作集算法融入到处理机调度中把工作集算法融入到处理机调度中n调度前检查每个进程在内存中驻留页面是否足够多，调度前检查每个进程在内存中驻留页面是否足够多，如果够则调入新的作业，否则为缺页率高的进程增加如果够则调入新的作业，否则为缺页率高的进程增加物理块。物理块。n利用利用“L=S”准则调节缺页率准则调节缺页率nL是缺页之间的平均时间，是缺页之间的平均时间，S处理一次缺页的时间。处理一次缺页的时间。n选择暂停的进程选择暂停的进程

59、n降低多道程序度降低多道程序度5.5 请求分段存储管理方式请求分段存储管理方式n5.5.1 请求分段中的硬件支持请求分段中的硬件支持n5.5.2 分段的共享与保护分段的共享与保护5.5.1 请求分段中的硬件支持请求分段中的硬件支持n段表机制段表机制n存取方式存取方式 用于标识本分段存取属性是只执行、只读还用于标识本分段存取属性是只执行、只读还是允许读是允许读/写写n存在位存在位P 用于指示该段是否已调入内存用于指示该段是否已调入内存n访问字段访问字段A 用于记录本页在一段时间内被访问的次数，用于记录本页在一段时间内被访问的次数，或记录本页在最近多长时间未被访问或记录本页在最近多长时间未被访问n

60、修改位修改位M 表示该段在调入内存后是否被修改过表示该段在调入内存后是否被修改过n外存地址外存地址 本段在外存上的地址，盘块块号本段在外存上的地址，盘块块号n增补位增补位 本段在运行过程中是否做过动态增长本段在运行过程中是否做过动态增长段名段名 段长段长 段的段的基址基址 存取存取方式方式 访问字访问字段段A 修改修改位位M 存在存在位位P 增补增补位位 外存外存始址始址 5.5.1 请求分段中的硬件支持请求分段中的硬件支持n缺段中断机构缺段中断机构n每当发现运行进程所要访问的段尚未调入内存每当发现运行进程所要访问的段尚未调入内存时，便由缺段中断机构产生一缺段中断信号，时，便由缺段中断机构产生