操作系统 第5章 虚拟存储器

1、第五章虚拟存储器第五章虚拟存储器 5.1虚拟存储器概述虚拟存储器概述5.2请求分页存储管理方式请求分页存储管理方式5.3页面置换算法页面置换算法5.4“抖动抖动”与工作集与工作集 5.5请求分段存储管理方式请求分段存储管理方式5.1虚拟存储器概述虚拟存储器概述常规存储管理方式的特征和局部性原理常规存储管理方式的特征和局部性原理常规存储管理方式的特征常规存储管理方式的特征u一次性一次性n进程要一次性全部装入内存才可以运行进程要一次性全部装入内存才可以运行n引发两个问题引发两个问题1）若进程对内存的要求超出物理内存总容量，则无）若进程对内存的要求超出物理内存总容量，则无法运行法运行2）内存由于容量

2、的限制，只能装入少量进程运行，）内存由于容量的限制，只能装入少量进程运行，限制了并发度限制了并发度5.1虚拟存储器概述虚拟存储器概述u驻留性驻留性n进程在其运行期间，始终进程在其运行期间，始终“驻留驻留”在内存在内存n暂时不用的程序和数据部分也占据内存空间，造成暂时不用的程序和数据部分也占据内存空间，造成内存空间的浪费内存空间的浪费5.1虚拟存储器概述虚拟存储器概述局部性原理局部性原理u在一段时间内一个程序的执行往往呈现出高度的局部性，在一段时间内一个程序的执行往往呈现出高度的局部性，表现在时间与空间两方面表现在时间与空间两方面u时间局部性时间局部性n一条指令被执行了，则在不久的将来它可能再被

3、执一条指令被执行了，则在不久的将来它可能再被执行行u空间局部性空间局部性n若某一存储单元被使用，则在一定时间内，与该存若某一存储单元被使用，则在一定时间内，与该存储单元相邻的单元可能被使用储单元相邻的单元可能被使用5.1虚拟存储器概述虚拟存储器概述虚拟存储器的基本工作情况虚拟存储器的基本工作情况u在程序装入时，不必将其全部读入到内存，而只需将当在程序装入时，不必将其全部读入到内存，而只需将当前需要执行的部分页或段读入到内存，就可让程序开始前需要执行的部分页或段读入到内存，就可让程序开始执行执行u在程序执行过程中，如果需执行的指令或访问的数据尚在程序执行过程中，如果需执行的指令或访问的数据尚未在

4、内存（称为缺页或缺段），则由处理器通知操作系未在内存（称为缺页或缺段），则由处理器通知操作系统，将相应的页或段调入到内存，然后继续执行程序统，将相应的页或段调入到内存，然后继续执行程序5.1虚拟存储器概述虚拟存储器概述虚拟存储器的定义和特征虚拟存储器的定义和特征虚拟存储器的定义虚拟存储器的定义u虚拟存储器是指具有请求调入功能和置换功能，能从逻虚拟存储器是指具有请求调入功能和置换功能，能从逻辑上对内存容量进行扩充的一种存储系统辑上对内存容量进行扩充的一种存储系统u其逻辑容量之和由内、外存容量之和决定其逻辑容量之和由内、外存容量之和决定5.1虚拟存储器概述虚拟存储器概述虚拟存储器的特征虚拟存储器的

5、特征u多次性一次性多次性一次性n一个作业被分成多次地调入内存运行一个作业被分成多次地调入内存运行u对换性驻留性对换性驻留性n允许作业在运行过程中换进、换出允许作业在运行过程中换进、换出u虚拟性虚拟性n从逻辑上扩充内存容量，使用户可使用的内存空间从逻辑上扩充内存容量，使用户可使用的内存空间大于实际物理内存大于实际物理内存5.1虚拟存储器概述虚拟存储器概述虚拟存储器的实现方法虚拟存储器的实现方法技术难点技术难点u如何确定和记录当前哪些部分在内存中如何确定和记录当前哪些部分在内存中u执行中要执行的指令或访问的数据不在内存时，如何处执行中要执行的指令或访问的数据不在内存时，如何处理理u将所需部分从外存

6、调入内存时，内存空间不够，如何处将所需部分从外存调入内存时，内存空间不够，如何处理理有两种典型的虚拟存储器实现方式有两种典型的虚拟存储器实现方式u请求分页系统请求分页系统u请求分段系统请求分段系统5.1虚拟存储器概述虚拟存储器概述以以CPU时间和外存空间换取昂贵内存空间，这时间和外存空间换取昂贵内存空间，这是操作系统中的资源转换技术是操作系统中的资源转换技术优点优点内存利用率高内存利用率高方便用户方便用户对多道程序运行有较强的支持对多道程序运行有较强的支持5.2请求分页存储管理方式请求分页存储管理方式基本思想基本思想进程开始运行之前，进程开始运行之前，不是装入全部页面，不是装入全部页面，而是装

7、入一个或零而是装入一个或零个页面，之后根据个页面，之后根据进程运行的需要，进程运行的需要，动态装入其它页面动态装入其它页面5.2请求分页存储管理方式请求分页存储管理方式技术难点技术难点如何确定和记录当前哪些部分在内存中如何确定和记录当前哪些部分在内存中执行中要执行的指令或访问的数据不在内存时，执行中要执行的指令或访问的数据不在内存时，如何处理如何处理将所需部分从外存调入内存时，内存空间不够，将所需部分从外存调入内存时，内存空间不够，如何处理如何处理页表页表缺页中断处理缺页中断处理页面置换页面置换5.2请求分页存储管理方式请求分页存储管理方式请求分页中的硬件支持请求分页中的硬件支持页表机制页表机

8、制状态位（存在位）状态位（存在位）P：表示该页是否调入内存：表示该页是否调入内存访问字段访问字段A：用于记录该页在某段时间内被访问的次数：用于记录该页在某段时间内被访问的次数修改位修改位M：表示该页在调入内存后是否被修改过：表示该页在调入内存后是否被修改过外存地址：该页在外存上的地址，通常是物理块号外存地址：该页在外存上的地址，通常是物理块号页号页号 物理块号物理块号 状态位状态位P 访问字段访问字段A 存取控制存取控制 修改位修改位M 外存地址外存地址5.2请求分页存储管理方式请求分页存储管理方式缺页中断机构缺页中断机构u在地址映射过程中，在页表中发现所要访问的页不在内在地址映射过程中，在页

9、表中发现所要访问的页不在内存，则产生缺页中断。存，则产生缺页中断。u操作系统接到此中断信号后，调出缺页中断处理程序，操作系统接到此中断信号后，调出缺页中断处理程序，根据页表中给出的外存地址，将该页根据页表中给出的外存地址，将该页Q调入内存，使进调入内存，使进程继续运行下去。程继续运行下去。u如果内存中有空闲物理块，则分配一页，将页如果内存中有空闲物理块，则分配一页，将页Q装入内装入内存，并修改页表。存，并修改页表。u若此时内存中没有空闲物理块，则发生页面置换。若此时内存中没有空闲物理块，则发生页面置换。5.2请求分页存储管理方式请求分页存储管理方式地址变换机构地址变换机构缺页中断处理保留CPU

10、现场从外存中找到缺页内存满否？选择一页换出该页被修改否？将该页写回外存OS命令CPU从外存读缺页启动I/O硬件将一页从外存换入内存修改页表否是是否页表项在快表中？CPU检索快表访问页表否页在内存？修改访问位和修改位形成物理地址地址变换结束否页号页表长度?开始程序请求访问一页产生缺页中断请求调页修改快表是越界中断是是5.2请求分页存储管理方式请求分页存储管理方式请求分页中的内存分配请求分页中的内存分配最小物理块数的确定最小物理块数的确定u指能保证进程正常运行所需的最小物理块数指能保证进程正常运行所需的最小物理块数u进程应获得的最少物理块数与计算机的硬件机构有关，进程应获得的最少物理块数与计算机的

11、硬件机构有关，取决于指令的格式、功能和寻址方式取决于指令的格式、功能和寻址方式5.2请求分页存储管理方式请求分页存储管理方式内存分配策略内存分配策略u分配策略分配策略n固定分配策略固定分配策略n可变分配策略可变分配策略u页面置换策略页面置换策略n全局置换全局置换n局部置换局部置换5.2请求分页存储管理方式请求分页存储管理方式u三种组合三种组合n固定分配局部置换固定分配局部置换思路：分配固定数目的内存空间，在整个运行期间思路：分配固定数目的内存空间，在整个运行期间都不改变都不改变策略：如果缺页，则先从该进程在内存的页面中选策略：如果缺页，则先从该进程在内存的页面中选中一页，进行换出操作，然后再调

12、入一页。中一页，进行换出操作，然后再调入一页。特点：为每个进程分配多少页是合适的值难以确定。特点：为每个进程分配多少页是合适的值难以确定。此外，在对换时会浪费比较多的时间。此外，在对换时会浪费比较多的时间。5.2请求分页存储管理方式请求分页存储管理方式n可变分配全局置换可变分配全局置换思路：每个进程预先分配一定数目的物理块，同时思路：每个进程预先分配一定数目的物理块，同时OS也保持一个空闲物理块队列。也保持一个空闲物理块队列。策略：当缺页时，首先将对策略：当缺页时，首先将对OS所占有的空闲块进行所占有的空闲块进行分配，从而增加了各进程的物理块数。当分配，从而增加了各进程的物理块数。当OS的空闲

13、的空闲块全部用完，将引起换出操作。块全部用完，将引起换出操作。n可变分配局部置换可变分配局部置换思路：系统根据缺页率动态调整各进程占有的物理思路：系统根据缺页率动态调整各进程占有的物理块数目，使其保持在一个比较低的缺页率状态下。块数目，使其保持在一个比较低的缺页率状态下。特点：使大部分进程可以达到比较近似的性能。特点：使大部分进程可以达到比较近似的性能。5.2请求分页存储管理方式请求分页存储管理方式物理块分配算法物理块分配算法 在采用固定分配策略时，可使用下列方法在采用固定分配策略时，可使用下列方法u平均分配算法：平均分配算法：将系统中所有可供分配的物理块平均分将系统中所有可供分配的物理块平均

14、分配给各个进程配给各个进程u按比例分配算法：按比例分配算法：根据进程的大小按比例分配物理块的根据进程的大小按比例分配物理块的算法算法u考虑优先权的分配算法：考虑优先权的分配算法：为重要的、紧迫的作业分配较为重要的、紧迫的作业分配较多的内存空间。通常采取的方法是把内存中可供分配的多的内存空间。通常采取的方法是把内存中可供分配的所有物理块分成两部分：一部分按比例地分配给各进程；所有物理块分成两部分：一部分按比例地分配给各进程；另一部分则根据各进程的优先权，适当地增加其相应份另一部分则根据各进程的优先权，适当地增加其相应份额后，分配给各进程额后，分配给各进程5.2请求分页存储管理方式请求分页存储管理

15、方式页面调入策略页面调入策略何时调入页面何时调入页面u预调页策略预调页策略n将预计在不久之后会被访问的页面预先调入内存将预计在不久之后会被访问的页面预先调入内存n目前预调页的成功率仅约目前预调页的成功率仅约50%n主要用于进程的首次调入主要用于进程的首次调入u请求调页策略请求调页策略n进程运行中发现要访问的页面不在内存，便立即提进程运行中发现要访问的页面不在内存，便立即提出请求，由出请求，由OS将其所需页面调入内存。将其所需页面调入内存。n目前的虚拟存储器中大多采用此策略目前的虚拟存储器中大多采用此策略5.2请求分页存储管理方式请求分页存储管理方式从何处调入页面从何处调入页面u外存有两个部分：

16、文件区和对换区。对换区外存有两个部分：文件区和对换区。对换区I/O操作速操作速度比文件区相对快一些，因此一般应当尽量使用对换区度比文件区相对快一些，因此一般应当尽量使用对换区来调入页面来调入页面u对于不同情况，采用不同的策略对于不同情况，采用不同的策略n系统有足够的对换区空间系统有足够的对换区空间n系统缺少足够的对换区空间系统缺少足够的对换区空间nUNIX方式方式5.2请求分页存储管理方式请求分页存储管理方式页面调入过程页面调入过程1、进程需要的页面不在内存，引起缺页中断、进程需要的页面不在内存，引起缺页中断2、中断处理程序保留现场环境，转入缺页中断处理程序、中断处理程序保留现场环境，转入缺页

17、中断处理程序3、中断处理程序查找页表，得到对应的外存物理块号。、中断处理程序查找页表，得到对应的外存物理块号。如果内存有空闲，则启动磁盘操作，将所缺的页面读入，如果内存有空闲，则启动磁盘操作，将所缺的页面读入，并修改页表。否则，到并修改页表。否则，到4。4、执行置换算法，选出要换出的页面，如果该页修改过，、执行置换算法，选出要换出的页面，如果该页修改过，应将其写入磁盘，然后将所缺页调入内存，修改相应表应将其写入磁盘，然后将所缺页调入内存，修改相应表项，将其存在位置为项，将其存在位置为1，并放入快表，并放入快表 。5、利用修改后的页表，形成物理地址，访问内存数据。、利用修改后的页表，形成物理地址

18、，访问内存数据。5.2请求分页存储管理方式请求分页存储管理方式缺页率缺页率u （A：总的访页次数）：总的访页次数） （F：访问页面失败的次数）：访问页面失败的次数）u影响缺页率的因素影响缺页率的因素n页面大小页面大小n进程所得物理块的数目进程所得物理块的数目n页面置换算法页面置换算法n程序固有特性程序固有特性 AFf 5.2请求分页存储管理方式请求分页存储管理方式u影响缺页率的因素（续）影响缺页率的因素（续）n进程所得物理块的数目进程所得物理块的数目5.2请求分页存储管理方式请求分页存储管理方式u影响缺页率的因素（续）影响缺页率的因素（续）n程序固有特性程序固有特性例：内存分配一块，初始时第一

19、页在内存；页面例：内存分配一块，初始时第一页在内存；页面大小为大小为128个整数；矩阵个整数；矩阵A128X128按行存放按行存放程序编制方法程序编制方法2： For j:=1 to 128 For i:=1 to 128 Ai,j:=0;程序编制方法程序编制方法1： For i:=1 to 128 For j:=1 to 128 Ai,j:=0;5.2请求分页存储管理方式请求分页存储管理方式优点优点作业的地址空间不再受主存大小的限制作业的地址空间不再受主存大小的限制主存利用率大大提高主存利用率大大提高能实现多道作业同时运行能实现多道作业同时运行方便用户方便用户缺点缺点缺页中断处理增加系统开销

20、缺页中断处理增加系统开销页面的调入调出增加页面的调入调出增加I/O系统的负担系统的负担页表等占用空间且需要管理，存在内碎片页表等占用空间且需要管理，存在内碎片5.3页面置换算法页面置换算法进程在较少的内存物理块中运行，发生缺页中进程在较少的内存物理块中运行，发生缺页中断时，可能会遇到内存中无空闲物理块可提供，断时，可能会遇到内存中无空闲物理块可提供，此时应：此时应：选择一个已经在内存中的页面淘汰选择一个已经在内存中的页面淘汰将新装入页放入刚淘汰页面所在的物理块将新装入页放入刚淘汰页面所在的物理块选择哪个已经在内存中的页面淘汰选择哪个已经在内存中的页面淘汰?内存中被修改过的页面应优先保留不被淘汰

21、内存中被修改过的页面应优先保留不被淘汰最好不要选择使用频率高的页面淘汰，否则将导最好不要选择使用频率高的页面淘汰，否则将导致使用频繁的页被多次调入调出致使用频繁的页被多次调入调出5.3页面置换算法页面置换算法最佳（最佳（Optimal）置换算法）置换算法1966年年 Belady选择选择“未来不再使用的未来不再使用的”或或“在最远的将来被使在最远的将来被使用的用的”页面来置换。页面来置换。理论上最优，但是无法实现（由于一般程序的行理论上最优，但是无法实现（由于一般程序的行为难以预料）为难以预料）可以作为评估其它页面置换算法的标准可以作为评估其它页面置换算法的标准5.3页面置换算法页面置换算法例

22、，假定系统为某进程分配了三个物理块，并考例，假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串虑有以下的页面号引用串u7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1引用率70770170122010320304243230321201201770101页框(物理块）243缺页中断次数缺页中断次数=9 缺页率缺页率=9/20=45%页面置换次数页面置换次数=65.3页面置换算法页面置换算法先进先出（先进先出（FIFO）页面置换算法）页面置换算法系统将所有页面排入一个系统将所有页面排入一个FIFO队列队列u按各页进入内

23、存的时间顺序按各页进入内存的时间顺序排在排在FIFO队列队首的页面先被淘汰队列队首的页面先被淘汰缺点缺点u先进入主存的页可能将被高频率反复使用而导致内外存先进入主存的页可能将被高频率反复使用而导致内外存置换次数增加置换次数增加u存在存在Belady异常：有时分配给进程的物理块增加时，缺异常：有时分配给进程的物理块增加时，缺页中断次数也增加页中断次数也增加5.3页面置换算法页面置换算法同例同例引用率70770170122010323104430230321013201770201页框230420423023012712701缺页中断次数缺页中断次数=15 缺页率缺页率=15/20=75%页面置换

24、次数页面置换次数=125.3页面置换算法页面置换算法再例再例页面访问序列页面访问序列 0 1 2 3 0 1 4 0 1 2 3 4 0 1 2 3 0 1 4 4 4 2 3 3 0 1 2 3 0 1 1 1 4 2 2 0 1 2 3 0 0 0 1 4 4 + + + + + + + + + 缺页次数缺页次数=9； 缺页率缺页率 f=9/12=75% 页面访问序列页面访问序列 0 1 2 3 0 1 4 0 1 2 3 4 0 1 2 3 3 3 4 0 1 2 3 4 0 1 2 2 2 3 4 0 1 2 3 0 1 1 1 2 3 4 0 1 2 0 0 0 1 2 3 4 0

25、1 + + + + + + + + + + 缺页次数缺页次数=10； 缺页率缺页率 f=10/12=83% 5.3页面置换算法页面置换算法最近最久未使用（最近最久未使用（LRU）置换算法）置换算法选择最近最久未使用的页面予以淘汰选择最近最久未使用的页面予以淘汰该算法赋予每个页面一个访问字段，用来记录一该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间个页面自上次被访问以来所经历的时间t，当须淘，当须淘汰一个页面时，选择现有页面中其汰一个页面时，选择现有页面中其t值最大的，即值最大的，即最近最久未使用的页面予以淘汰最近最久未使用的页面予以淘汰理论上可行，但实现代价很高理

26、论上可行，但实现代价很高5.3页面置换算法页面置换算法同例同例引用率70770170122010320304403230321132201770101页框402432032102缺页中断次数缺页中断次数=12 缺页率缺页率=12/20=60%页面置换次数页面置换次数=95.3页面置换算法页面置换算法硬件支持硬件支持u寄存器寄存器n每个页面设立移位寄存器，被访问时左边最高位置每个页面设立移位寄存器，被访问时左边最高位置1，定期右移并且最高位补定期右移并且最高位补0，于是寄存器数值最小的是，于是寄存器数值最小的是最久未使用页面。最久未使用页面。R 实 页 R7 R6 R5 R4 R3 R2 R1

27、R0 1 0 1 0 1 0 0 1 0 2 1 0 1 0 1 1 0 0 3 0 0 0 0 0 1 0 0 4 0 1 1 0 1 0 1 1 5 1 1 0 1 0 1 1 0 6 0 0 1 0 1 0 1 1 7 0 0 0 0 0 1 1 1 8 0 1 1 0 1 1 0 1 5.3页面置换算法页面置换算法u栈栈n把被访问的页面移到栈顶，于是栈底的是最久未使把被访问的页面移到栈顶，于是栈底的是最久未使用页面用页面n例，假定现有一进程所访问的页面的页面号序列为：例，假定现有一进程所访问的页面的页面号序列为：4，7，0，7，1，0，1，2，1，2，64474707407047170

28、4101740107412107421207412107426210765.3页面置换算法页面置换算法最少使用（最少使用（LFU）置换算法）置换算法为在内存中的每个页面设置一个移位寄存器，用为在内存中的每个页面设置一个移位寄存器，用来记录该页面被访问的频率来记录该页面被访问的频率每次访问某页时，便将该移位寄存器的最高位置每次访问某页时，便将该移位寄存器的最高位置1，再每隔一定时间右移一次再每隔一定时间右移一次在最近一段时间使用最少的页面将是在最近一段时间使用最少的页面将是Ri最小的页最小的页5.3页面置换算法页面置换算法Clock置换算法置换算法简单的简单的Clock置换算法置换算法u也称最近

29、未使用算法也称最近未使用算法NRU，是，是LRU和和FIFO的折衷的折衷u内存中所有页面通过链接指针形成一个循环队列内存中所有页面通过链接指针形成一个循环队列n每页有一个访问位，某页被访问则其访问位置每页有一个访问位，某页被访问则其访问位置1n在选择一页淘汰时，只需检查页的访问位。如果是在选择一页淘汰时，只需检查页的访问位。如果是0，就选择该页换出；若为就选择该页换出；若为1，则重新将它置，则重新将它置0，暂不换，暂不换出，而给该页第二次驻留内存的机会，再按照出，而给该页第二次驻留内存的机会，再按照FIFO算法检查下一个页面。算法检查下一个页面。n当检查到队列中的最后一个页面时，若其访问位仍当

30、检查到队列中的最后一个页面时，若其访问位仍为为1，则再返回到队首去检查第一个页面。，则再返回到队首去检查第一个页面。5.3页面置换算法页面置换算法简单简单Clock置换算法的流程和示例置换算法的流程和示例 入口查寻指针前进一步，指向下一个表目页面访问位0?选择该页面淘汰是返回置页面访问位“0”否块号页号访问位指针0124034215650711替换指针5.3页面置换算法页面置换算法改进型改进型Clock置换算法置换算法u选择页面时，尽量选择既未使用又没有修改的页面选择页面时，尽量选择既未使用又没有修改的页面u页面（访问位页面（访问位A，修改位，修改位M）有四种不同情形）有四种不同情形n1类（类

31、（A=0,M=0）既未访问又没有修改，最佳淘汰页）既未访问又没有修改，最佳淘汰页n2类（类（A=0,M=1）未访问但有修改）未访问但有修改n3类（类（A=1,M=0）被访问但没有修改）被访问但没有修改n4类（类（A=1,M=1）既被访问又有修改）既被访问又有修改5.3页面置换算法页面置换算法u算法：算法：（1）指针从当前位置开始，开始第一轮扫描循环队列，）指针从当前位置开始，开始第一轮扫描循环队列，寻找未使用且没有修改过的页面（第寻找未使用且没有修改过的页面（第1类页面），找到类页面），找到则可换出。则可换出。（2）如果找不到，则开始第二轮扫描，寻找未使用但修）如果找不到，则开始第二轮扫描，寻

32、找未使用但修改过的页面（第改过的页面（第2类页面），并且每经过一个页面时，类页面），并且每经过一个页面时，将其访问位将其访问位A设置为设置为0。如果找到一个第。如果找到一个第2类页面，则可类页面，则可换出。换出。（3） 如果仍旧未找到合适的换出页面，则此时指针回到如果仍旧未找到合适的换出页面，则此时指针回到初始位置，且所有页面其访问位初始位置，且所有页面其访问位A为为0。 再转回（再转回（1）继）继续工作。续工作。5.3页面置换算法页面置换算法页面缓冲算法（页面缓冲算法（PBA）是对是对FIFO算法的发展，通过被置换页面的缓冲，算法的发展，通过被置换页面的缓冲，有机会找回刚被置换的页面有机会找

33、回刚被置换的页面被置换页面的选择和处理：由操作系统中专门的被置换页面的选择和处理：由操作系统中专门的页面置换进程，用页面置换进程，用FIFO算法选择被置换页，把被算法选择被置换页，把被置换的页面放入两个链表（空闲页面链表和已修置换的页面放入两个链表（空闲页面链表和已修改页面链表）之一改页面链表）之一u如果页面未被修改，就将其归入到空闲页面链表的末尾如果页面未被修改，就将其归入到空闲页面链表的末尾u否则将其归入到已修改页面链表否则将其归入到已修改页面链表5.3页面置换算法页面置换算法访问内存的有效时间访问内存的有效时间t访问一次内存的时间；访问一次内存的时间； 查找快表的时间；查找快表的时间；a

34、快表的命中率；快表的命中率； f缺页率；缺页率； 缺页中断处理时间缺页中断处理时间被访问页在内存，且其对应的页表项在快表中被访问页在内存，且其对应的页表项在快表中 EAT= + t被访问页在内存，且其对应的不页表项在快表中被访问页在内存，且其对应的不页表项在快表中 EAT= 2( + t)被访问页不在内存被访问页不在内存 EAT= + 2 ( + t)加入快表命中率和缺页率等因素加入快表命中率和缺页率等因素 EAT= +at +(1-a)t +f( + +t) +(1-f)( +t)5.4“抖动抖动”与工作集与工作集 多道程序度与多道程序度与“抖动抖动”多道程序度与处理机的利用率多道程序度与处

35、理机的利用率5.4“抖动抖动”与工作集与工作集产生产生“抖动抖动”的原因的原因u在虚存中，页面在内存与外存之间频繁调度，以至于调在虚存中，页面在内存与外存之间频繁调度，以至于调度页面所需时间比进程实际运行的时间还多，此时系统度页面所需时间比进程实际运行的时间还多，此时系统效率急剧下降，甚至导致系统崩溃，这种现象称为效率急剧下降，甚至导致系统崩溃，这种现象称为“颠颠簸簸”或或“抖动抖动”u产生原因产生原因n分配给进程的物理页面数太少分配给进程的物理页面数太少n页面置换算法不合理页面置换算法不合理5.4“抖动抖动”与工作集与工作集工作集工作集工作集的基本概念工作集的基本概念u1968年由年由Den

36、ning提出并推广提出并推广u基本思想：根据程序的局部性原理，一般情况下，进程基本思想：根据程序的局部性原理，一般情况下，进程在一段时间内总是集中访问一些页面，这些页面称为活在一段时间内总是集中访问一些页面，这些页面称为活跃页面，如果分配给一个进程的物理块数太少，使该进跃页面，如果分配给一个进程的物理块数太少，使该进程所需的活跃页面不能全部装入内存，则进程在运行过程所需的活跃页面不能全部装入内存，则进程在运行过程中将频繁发生缺页中断程中将频繁发生缺页中断u如果能为进程提供与活跃页面数相等的物理块数，则可如果能为进程提供与活跃页面数相等的物理块数，则可减少缺页中断次数减少缺页中断次数5.4“抖动

37、抖动”与工作集与工作集工作集的定义工作集的定义u指在某段时间间隔里，进程实际所要访问的页面集合指在某段时间间隔里，进程实际所要访问的页面集合u内容取决于三个因素内容取决于三个因素n访页序列特性访页序列特性n时间时间tn窗口尺寸窗口尺寸()5.4“抖动抖动”与工作集与工作集“抖动抖动”的预防方法的预防方法采取局部置换策略采取局部置换策略把工作集算法融入到处理机调度中把工作集算法融入到处理机调度中利用利用“L=S”准则调节缺页率准则调节缺页率选择暂停的进程选择暂停的进程5.5请求分段存储管理方式请求分段存储管理方式请求分页系统建立的虚拟存储器，是以页面为请求分页系统建立的虚拟存储器，是以页面为单位

38、进行换入、换出操作的。单位进行换入、换出操作的。在请求分段系统中实现的虚拟存储器，以分段在请求分段系统中实现的虚拟存储器，以分段为单位进行换入和换出。为单位进行换入和换出。程序在运行之前，只需要装入必要的若干个分程序在运行之前，只需要装入必要的若干个分段即可运行。当访问的分段不在内存时，可由段即可运行。当访问的分段不在内存时，可由OS将所缺少的段调入内存。将所缺少的段调入内存。5.5请求分段存储管理方式请求分段存储管理方式请求分段中的硬件支持请求分段中的硬件支持段表机制段表机制存取方式：标记本段存取属性，如读存取方式：标记本段存取属性，如读R，写，写W，执行，执行X访问字段访问字段A：记录本段

39、使用的频繁程度：记录本段使用的频繁程度修改位：是否在调入内存后做过修改修改位：是否在调入内存后做过修改存在位：本段是否装入内存存在位：本段是否装入内存增补位增补位 ：该段是否动态增长过，在请求页式中没有该位：该段是否动态增长过，在请求页式中没有该位外存地址：外存地址：段号段号 段长段长段的段的基址基址 存取存取方式方式 访问字访问字段段A 修改位修改位M 存在存在位位p 增补位增补位 外存起址外存起址5.5请求分段存储管理方式请求分段存储管理方式缺段中断机构缺段中断机构u要有专门的缺段中断处理程序要有专门的缺段中断处理程序u特点特点n指令和操作数必定不会跨越在段边界上指令和操作数必定不会跨越在

40、段边界上n由于段的长度是不固定的，处理比缺页系统复杂由于段的长度是不固定的，处理比缺页系统复杂n调入一个段可能要淘汰几个内存中的段调入一个段可能要淘汰几个内存中的段u中断处理过程请参看中断处理过程请参看P174 图图5-125.5请求分段存储管理方式请求分段存储管理方式地址变换地址变换u请求分段系统的地址变换机构，是在分段系统的地址变请求分段系统的地址变换机构，是在分段系统的地址变换机构基础上形成的换机构基础上形成的u由于分段可能不在内存，因此会引起缺段中断。先将需由于分段可能不在内存，因此会引起缺段中断。先将需要的段调入内存，修改段表，然后再利用段表进行地址要的段调入内存，修改段表，然后再利

41、用段表进行地址变换变换u地址变换过程请参看地址变换过程请参看P174 图图5-135.5请求分段存储管理方式请求分段存储管理方式分段保护与共享分段保护与共享在多道程序系统中，尤其在分时系统中，数据共在多道程序系统中，尤其在分时系统中，数据共享是很重要的，在分段系统中，各共享进程应能享是很重要的，在分段系统中，各共享进程应能访问被共享的段，所以共享的方法是使这些共享访问被共享的段，所以共享的方法是使这些共享用户的逻辑空间中的段指向相同的段号，在共享用户的逻辑空间中的段指向相同的段号，在共享中必须小心处理的一个问题是共享段的保护问题。中必须小心处理的一个问题是共享段的保护问题。5.5请求分段存储管理方式请求分段存储管理方式共享段表共享段表u为了实现共享，可为了实现共享，可在系统中配置一张在系统中配置一张段表，所有的共享段表，所有的共享段都在共享段表中段都在共享段表中占有一表项。表项占有一表项。表项中记录了共享段的中记录了共享段的段号、段长、内存段号、段长、内存始址、存在位等信始址、存在位等信息，并记录有共享息，并记录有共享此分段的每个进程此分段的每个进程的情况。的情况。作业作业1的段表的段表作业作业2的段表的段表共享段共享段5.5请求分段存储管理方式请求分段存储管理方式u共享进程计数共享进程计数n记录了多少个进程在共享该分