(精品)第8章 虚拟存储管理.ppt

第第8章章 虚拟存储管理技术虚拟存储管理技术引言引言81 虚拟存储器的基本概念虚拟存储器的基本概念82 请求分页式存储管理方式请求分页式存储管理方式83 请求分段式存储管理方式请求分段式存储管理方式84 Linux存储管理存储管理85 Windows存储管理存储管理引言引言 上一章介绍了实存储管理技术，各种实存储管理技上一章介绍了实存储管理技术，各种实存储管理技术有一个共同的特点，即它们都要求把进程全部装入内术有一个共同的特点，即它们都要求把进程全部装入内存才能运行。在运行过程中，往往可能出现两种情况：存才能运行。在运行过程中，往往可能出现两种情况：u要求运行的进程所需的内存空间之和大于系统的内存空要求运行的进程所需的内存空间之和大于系统的内存空间间，只能有部分进程能够装入内存运行，而其它进程只，只能有部分进程能够装入内存运行，而其它进程只有留在外存中等待；有留在外存中等待；u逻辑地址空间大于存储空间的进程无法在系统中运行。逻辑地址空间大于存储空间的进程无法在系统中运行。为了解决以上问题，可有两种解决方案：一是从物为了解决以上问题，可有两种解决方案：一是从物理上增加内存容量。但这受到机器寻址能力的限制，不理上增加内存容量。但这受到机器寻址能力的限制，不能无限扩充，而且无疑会增加系统成本；二是从逻辑上能无限扩充，而且无疑会增加系统成本；二是从逻辑上扩充内存容量，这就是本章所要讨论的扩充内存容量，这就是本章所要讨论的“虚拟存储虚拟存储”管管理技术理技术。81 虚拟存储器的基本概念虚拟存储器的基本概念 虚拟存储管理要研究的问题是：虚拟存储管理要研究的问题是：1.1.作业信息不全部装入主存，能否保证作业的正确运行作业信息不全部装入主存，能否保证作业的正确运行？回答是肯定的回答是肯定的,1968,1968年年P.DenningP.Denning研究了程序执行时研究了程序执行时的局部性原理。的局部性原理。2.2.以以CPUCPU时间和外存空间换取昂贵内存空间，如何进行时间和外存空间换取昂贵内存空间，如何进行动态调度？动态调度？81 虚拟存储器的基本概念虚拟存储器的基本概念程序的局部性原理：程序的局部性原理：指程序在执行过程中的一个较短时间内，所执行指程序在执行过程中的一个较短时间内，所执行的指令地址或操作数地址分别局限于一定的存储区域的指令地址或操作数地址分别局限于一定的存储区域中。具体地表现为中。具体地表现为时间局部性时间局部性和和空间局部性空间局部性。811 局部性原理局部性原理 n程序执行呈现局部性规律的原因：程序执行呈现局部性规律的原因：程序执行时，大多数情况下是顺序执行的。程序执行时，大多数情况下是顺序执行的。很少出现连续的过程调用，相反，程序中过程调用很少出现连续的过程调用，相反，程序中过程调用的深度限制在小范围内，一段时间内，指令引用被的深度限制在小范围内，一段时间内，指令引用被局限在很少几个过程中局限在很少几个过程中。程序中有许多循环语句，这些语句会重复多次执行。程序中有许多循环语句，这些语句会重复多次执行。程序中对数据结构的操作，往往局限在很小的范围程序中对数据结构的操作，往往局限在很小的范围内。内。811 局部性原理局部性原理 n局部性原理的表现形式：局部性原理的表现形式：u时间局限性：时间局限性：如果某条指令被执行，则在不久的如果某条指令被执行，则在不久的将来，该指令可能被再次执行；如果某个数据结将来，该指令可能被再次执行；如果某个数据结构被访问，则在不久的将来，该数据结构可能再构被访问，则在不久的将来，该数据结构可能再次被访问。产生时间局限性的主要原因是次被访问。产生时间局限性的主要原因是程序中程序中存在着大量的循环操作存在着大量的循环操作。u空间局限性：空间局限性：一旦程序访问了某个存储单元，则一旦程序访问了某个存储单元，则在不久的将来，其附近的存储单元也可能被访问，在不久的将来，其附近的存储单元也可能被访问，即程序在一段时间内所访问的地址，可能集中在即程序在一段时间内所访问的地址，可能集中在一定的范围内。产生空间局限性的主要原因是一定的范围内。产生空间局限性的主要原因是程程序的顺序执行序的顺序执行。n实现虚拟存储器的理论基础：实现虚拟存储器的理论基础：局部性原理。局部性原理。812 虚拟存储器虚拟存储器 n实现方法：实现方法：一个进程在运行之时，没有必要全部装一个进程在运行之时，没有必要全部装入内存，而只把当前运行所需要的页（段）装入内入内存，而只把当前运行所需要的页（段）装入内存便可启动运行，而其余部分则存放在磁盘上。程存便可启动运行，而其余部分则存放在磁盘上。程序在运行时，如果所需要的页（段）已经调入内存，序在运行时，如果所需要的页（段）已经调入内存，便可以继续执行下去。如果所需要的页（段）不在便可以继续执行下去。如果所需要的页（段）不在内存，此时程序内存，此时程序应利用操作系统所提供的请求调页应利用操作系统所提供的请求调页（段）功能，将该页（段）调入内存，以使程序能（段）功能，将该页（段）调入内存，以使程序能够运行下去够运行下去。如果此时分配给该程序的内存已全部。如果此时分配给该程序的内存已全部占用，不能装入新的页（段），则需要占用，不能装入新的页（段），则需要利用系统的利用系统的置换功能，把内存中暂时不用的页（段）调出至磁置换功能，把内存中暂时不用的页（段）调出至磁盘上盘上，腾出足够的内存空间，再将所要装入的页，腾出足够的内存空间，再将所要装入的页（段）调入内存，使程序能够继续运行下去。（段）调入内存，使程序能够继续运行下去。812 虚拟存储器虚拟存储器 n虚拟存储器的定义：虚拟存储器的定义：是指仅把进程的一部分是指仅把进程的一部分装入内存便可运行的存储器系统，它具有请装入内存便可运行的存储器系统，它具有请求调入功能和置换功能，能从逻辑上对内存求调入功能和置换功能，能从逻辑上对内存容量进行扩充的一种存储器系统。容量进行扩充的一种存储器系统。n虚拟存储器的逻辑容量：虚拟存储器的逻辑容量：虚拟存储器的逻辑虚拟存储器的逻辑容量由系统的寻址能力和外存容量之和所决容量由系统的寻址能力和外存容量之和所决定。定。812 虚拟存储器虚拟存储器虚拟存储管理主要采用以下技术实现：虚拟存储管理主要采用以下技术实现：请求分页虚拟存储管理请求分页虚拟存储管理 请求分段虚拟存储管理请求分段虚拟存储管理 请求段页式虚拟存储管理请求段页式虚拟存储管理82 请求分页式存储管理方式请求分页式存储管理方式 请请求求分分页页式式存存储储管管理理是是在在分分页页式式存存储储管管理理的的基基础础上上，增增加加了了请请求求调调页页功功能能、页页面面置置换换功功能能而而形形成成的的页页式式虚虚拟拟存存储储系系统统。它它是是目目前前常常用用的的一一种种虚虚拟拟存储器的方式。存储器的方式。82 请求分页式存储管理方式请求分页式存储管理方式基基本本原原理理：在在请请求求分分页页式式存存储储管管理理系系统统中中，进进程程运运行行之之前前将将一一部部分分页页面面装装入入内内存存，另另外外一一部部分分页页面面则则装装入入外外存存。在在进进程程运运行行过过程程中中，如如果果所所访访问问的的页页面面不不在在内内存存中中，则则发发生生缺缺页页中中断断，进进入入操操作作系系统统，由由操操作作系系统统进行页面的动态调度。进行页面的动态调度。系统需要解决下面三个问题：系统需要解决下面三个问题：系统如何获知进程当前所需页面不在主存。系统如何获知进程当前所需页面不在主存。当发现缺页时，如何把所缺页面调入主存。当发现缺页时，如何把所缺页面调入主存。当主存中没有空闲的页框时，为了要接受一个新页，需要当主存中没有空闲的页框时，为了要接受一个新页，需要把把老的一页淘汰出去，老的一页淘汰出去，根据什么策略选择欲淘汰的页面根据什么策略选择欲淘汰的页面。82 1 请求分页式存储管理的基本概念请求分页式存储管理的基本概念 n其方法如下：其方法如下：u找到被访问页面在外存中的地址；找到被访问页面在外存中的地址；u在内存中找一个空闲块，如果没有，则按照在内存中找一个空闲块，如果没有，则按照淘汰淘汰算法算法选择一个内存块，将此块内容写回外存，修选择一个内存块，将此块内容写回外存，修改改页表页表；u读入所需的页面，修改读入所需的页面，修改页表页表；u重新启动进程，执行被中断的指令。重新启动进程，执行被中断的指令。82 1 请求分页式存储管理的基本概念请求分页式存储管理的基本概念 n页表机制：页表机制：纯分页的页表只有两项：页号和物理块。纯分页的页表只有两项：页号和物理块。而请求分页存储管理增加了调入功能和置换功能，而请求分页存储管理增加了调入功能和置换功能，故需在页表中增加若干项，供程序在换进换出时参故需在页表中增加若干项，供程序在换进换出时参考。下面所示是一请求分页系统中的页表：考。下面所示是一请求分页系统中的页表：页号页号物理块号物理块号 状态位状态位P 访问字段访问字段A 修改位修改位M 外存地址外存地址状态位状态位P：记录该页是否在内存。记录该页是否在内存。P=0该页在内存；该页在内存；P=1该页不在内存该页不在内存。访问字段访问字段A：记录该页多长时间没有被访问。记录该页多长时间没有被访问。修改位修改位M：记录该页在内存期间是否被修改过。记录该页在内存期间是否被修改过。M=1该页调入内存后被修改过该页调入内存后被修改过；M=0该页调入内存后未被修改过。该页调入内存后未被修改过。外存地址：外存地址：该页在外存上的地址该页在外存上的地址82 1 请求分页式存储管理的基本概念请求分页式存储管理的基本概念 n请求分页存储管理示意图：请求分页存储管理示意图：物理地址空间物理地址空间页面映射表页面映射表存储空间存储空间页号页号 块号块号 状态状态作业作业10110430001作业作业20123作业作业3012341061032901101110321270041234567891011121382 1 请求分页式存储管理的基本概念请求分页式存储管理的基本概念 n地址变换机构：地址变换机构：请求分页系统中的地址变换机构，是请求分页系统中的地址变换机构，是在分页系统的地址变换机构的基础上，为实现虚拟在分页系统的地址变换机构的基础上，为实现虚拟存储器而存储器而增加了产生和处理缺页中断、页面置换等增加了产生和处理缺页中断、页面置换等功能功能而形成的。下图给出了请求分页系统的地址变而形成的。下图给出了请求分页系统的地址变换过程。换过程。82 1 请求分页式存储管理的基本概念请求分页式存储管理的基本概念 否否否是是产生缺页中断否是否是程序请求访问一页页号页表长度？越界中断CPU检索快表页表项是否在快表中？访问页表页是否在内存中？修改快表修改访问位和修改位保留CPU现场缺页中断处理从外存中找到该页内存满否？选择一页换出该页修改否？将该页写回外存CPU从外存读缺页启动I/O硬件形成物理地址地址变换结束将一页从外存换入内存修改页表是查快表查快表有登记有登记无登记无登记查页表查页表登记入快表登记入快表发缺页中断发缺页中断在主存在主存在辅存在辅存形成绝对地址形成绝对地址继续执行指令继续执行指令重新执行重新执行被中断指令被中断指令恢复现场恢复现场调整页表和调整页表和主存分配表主存分配表装入所需页面装入所需页面主存有空闲块主存有空闲块保护现场保护现场有有选择调出页面选择调出页面该页是否修改该页是否修改未修改未修改已修改已修改把该页写回把该页写回辅存相应位置辅存相应位置操作系统操作系统硬件硬件逻辑地址逻辑地址无无82 2 页面分配策略页面分配策略 n内存页面分配策略：内存页面分配策略：u平均分配平均分配：将内存中的所有可供分配的物理块，将内存中的所有可供分配的物理块，平均分配给各个进程。这是最简单的分配方式，平均分配给各个进程。这是最简单的分配方式，它看起来很公平，但实际上很不公平，因为它没它看起来很公平，但实际上很不公平，因为它没有考虑进程的大小等因素。有考虑进程的大小等因素。u按进程大小比例分配按进程大小比例分配：系统按进程的大小按比例系统按进程的大小按比例分配物理块。若分配物理块。若m为可用物理块总和，为可用物理块总和，S为各进程为各进程页面总和，页面总和，si为第为第i个进程的页面数，则为第个进程的页面数，则为第i个进个进程分配的页面数为：程分配的页面数为：u按进程优先级比例分配按进程优先级比例分配：为照顾重要的、紧迫的为照顾重要的、紧迫的进程，使其能够尽快的完成，可以为其分配较多进程，使其能够尽快的完成，可以为其分配较多的内存物理块。的内存物理块。82 2 页面分配策略页面分配策略 n外存块的分配策略：外存块的分配策略：u静态分配静态分配：一个进程在运行前，一个进程在运行前，将其所有页面全将其所有页面全部装入外存部装入外存。当某一外存页面被调入内存时，。当某一外存页面被调入内存时，所所占用外存页面并不释放占用外存页面并不释放。这样，当该页面以后被。这样，当该页面以后被淘汰时，如果它在内存中未被修改过，则不必写淘汰时，如果它在内存中未被修改过，则不必写回外存，因为外存中有一个和它完全相同的副本，回外存，因为外存中有一个和它完全相同的副本，这可以减少因页面调度而引起的系统开销，代价这可以减少因页面调度而引起的系统开销，代价是牺牲一定的外存空间。是牺牲一定的外存空间。u动态分配动态分配：一个进程在运行前，一个进程在运行前，仅将未装入内存仅将未装入内存的那部分页面装入外存的那部分页面装入外存。当某一外存页面被调入。当某一外存页面被调入内存，释放所占用的外存空间。这样，当该页面内存，释放所占用的外存空间。这样，当该页面以后被淘汰时，不管它在内存中是否被修改过，以后被淘汰时，不管它在内存中是否被修改过，都必须重新为其申请外存物理块，将该页重新写都必须重新为其申请外存物理块，将该页重新写回外存。这种方法的优点是节省外存空间，但会回外存。这种方法的优点是节省外存空间，但会增加由页面调度而引起的系统开销。增加由页面调度而引起的系统开销。82 3 页面调入时机页面调入时机 n请求调页策略：请求调页策略：发生缺页时，调入内存。根发生缺页时，调入内存。根据局部性原理据局部性原理,一段时间后一段时间后,缺页中断会下降到缺页中断会下降到很低水平很低水平,程序进入相对平稳阶段。程序进入相对平稳阶段。缺缺点点：处处理理缺缺页页中中断断和和调调页页的的系系统统开开销销较较大大，每次仅调一页每次仅调一页,增加了磁盘增加了磁盘I/O次数。次数。n预调页策略：预调页策略：预计要访问的页，提前调入内预计要访问的页，提前调入内存。每次调入若干页面存。每次调入若干页面,而不是仅调一页。一而不是仅调一页。一次调入多页能减少磁盘次调入多页能减少磁盘I/O启动次数。启动次数。缺点：缺点：如果调入的一批页面中多数未被使用如果调入的一批页面中多数未被使用,则效率就很低了，可见预调页要建立在则效率就很低了，可见预调页要建立在预测预测的基础上的基础上82 4 页面置换算法页面置换算法目标：把目标：把未来不再使用未来不再使用的或的或短时间内不再使用短时间内不再使用的页调的页调出。出。最佳置换算法最佳置换算法OPT先进先出置换算法先进先出置换算法FIFO最近最久未使用置换算法最近最久未使用置换算法LRU时钟置换算法时钟置换算法82 4 页面置换算法页面置换算法 n最佳置换算法（最佳置换算法（OPT，Optimal）：）：最佳置换算法置换最佳置换算法置换那些以后那些以后永不再使用的永不再使用的或者或者在最长的时间以后才会在最长的时间以后才会用到的用到的页面。显然，这种算法的缺页率最低。然而，页面。显然，这种算法的缺页率最低。然而，该算法只是一种理论上的算法，因为很难估计哪一该算法只是一种理论上的算法，因为很难估计哪一个页面是以后永远不再使用或在最长时间以后才会个页面是以后永远不再使用或在最长时间以后才会用到的页面，所以，这种算法是不能实现的。尽管用到的页面，所以，这种算法是不能实现的。尽管如此，该算法仍然是有意义的，可以把它作为如此，该算法仍然是有意义的，可以把它作为衡量衡量其它算法优劣的一个标准其它算法优劣的一个标准。82 4 页面置换算法页面置换算法 【例8-1】假定系统为某进程分配了3个物理块，页面访问序列为：5、0、1、2、0、3、0、4、2、3、0、3、2、1、2、0、1、5、0、1。采用最佳置换算法，计算缺页中断次数和缺页中断率。解：页面置换过程如下表所示：页面访问序列页面访问序列50120304230321201501501113333333322225555000004440000000000522222222221111111+-+-+-+-+-+-缺页中断次数=9缺页中断率=9/20=45%82 4 页面置换算法页面置换算法 n先进先出置换算法（先进先出置换算法（FIFO，First-In First-Out）：先先进先出置换算法总是置换最先进入内存的页面。该进先出置换算法总是置换最先进入内存的页面。该算法实现简单，只须把一个进程已调入内存的页面，算法实现简单，只须把一个进程已调入内存的页面，按照进入内存的先后顺序排成一个队列，按照进入内存的先后顺序排成一个队列，当一个页当一个页面由外存调入内存时排入队尾，需要淘汰时取队首面由外存调入内存时排入队尾，需要淘汰时取队首的页面的页面。82 4 页面置换算法页面置换算法 【例例8-2】假定系统为某进程分配了假定系统为某进程分配了3个物理块，个物理块，页面访问序列为：页面访问序列为：5、0、1、2、0、3、0、4、2、3、0、3、2、1、2、0、1、5、0、1。采用先进先出置换算法，。采用先进先出置换算法，计算缺页中断次数和缺页中断率。计算缺页中断次数和缺页中断率。解：页面置换过程如下表所示：解：页面置换过程如下表所示：页面访问序列页面访问序列50120304230321201501501223042300012225015011230423330111250500123042223000125+-+-+-+缺页中断次数缺页中断次数=15缺页中断率缺页中断率=15/20=75%82 4 页面置换算法页面置换算法 Belady异常现象：异常现象：一般而言，分配给进程的物理一般而言，分配给进程的物理块越多，运行时的缺页次数应该越少。但是块越多，运行时的缺页次数应该越少。但是Belady在在1969年发现了一个反例，使用年发现了一个反例，使用FIFO算法时，四个算法时，四个物理块时的缺页次数比三个物理块时的多，这种反物理块时的缺页次数比三个物理块时的多，这种反常的现象称为常的现象称为Belady异常。如下面两表所示，一个异常。如下面两表所示，一个进程有进程有5个页面，页面访问序列如下：个页面，页面访问序列如下：Belady异常现象（异常现象（3个物理块的个物理块的FIFO现象）现象）82 4 页面置换算法页面置换算法 Belady异常现象（异常现象（4个物理块的个物理块的FIFO现象）现象）由表中可见，由表中可见，3个物理块时缺页次数是个物理块时缺页次数是9次，缺页中断次，缺页中断率为率为9/12=75%；而；而4个物理块时的缺页次数是个物理块时的缺页次数是10次，次，缺页中断率为缺页中断率为10/1283.3%。82 4 页面置换算法页面置换算法 n最近最久未使用置换算法（最近最久未使用置换算法（LRU，Least Recently Used）：）：该算法的基本思想是：如果某一页面被访该算法的基本思想是：如果某一页面被访问了，那么它很可能马上又被访问；反之，如果某问了，那么它很可能马上又被访问；反之，如果某一页面很久没有被访问，那么最近也不会再次被访一页面很久没有被访问，那么最近也不会再次被访问。因此，问。因此，该算法为每一个页面设置一个访问字段该算法为每一个页面设置一个访问字段，用来用来记录一个页面自上次被访问以来所经历的时间记录一个页面自上次被访问以来所经历的时间t，当须淘汰一个页面时，选择现有页面中，当须淘汰一个页面时，选择现有页面中t值最大的，值最大的，即最近最久未使用的页面予以淘汰。即最近最久未使用的页面予以淘汰。uLRU的实现：的实现：p记时法：记时法：系统为每一页面增设一个系统为每一页面增设一个记时器记时器。每。每当一个页面被访问时，当时的绝对时钟内容被当一个页面被访问时，当时的绝对时钟内容被拷贝到对应的记时器中，这样系统记录了内存拷贝到对应的记时器中，这样系统记录了内存所有页面所有页面最后一次被访问的时间最后一次被访问的时间。淘汰页面时，。淘汰页面时，选取记时器中值最小的页面淘汰。选取记时器中值最小的页面淘汰。82 4 页面置换算法页面置换算法 p堆栈法：堆栈法：用一个栈保留页号。每当访问一个页用一个栈保留页号。每当访问一个页面时，就把它从栈中取出放在栈顶上。这样一面时，就把它从栈中取出放在栈顶上。这样一来，栈顶总是放最新被访问页面的页面号，而来，栈顶总是放最新被访问页面的页面号，而栈底放着最近最久未使用的页面号。由于要从栈底放着最近最久未使用的页面号。由于要从栈的中间移走一项，所以要用具有头尾指针的栈的中间移走一项，所以要用具有头尾指针的双向链连起来。双向链连起来。注意：不是通常意义上的栈注意：不是通常意义上的栈 82 4 页面置换算法页面置换算法 uLRU的缺点：的缺点：虽然虽然LRU在理论上是可以实现的，在理论上是可以实现的，但代价太高。为了实现但代价太高。为了实现LRU，需要在内存维持一，需要在内存维持一个包含所有页的链表，最近使用的页面在表头，个包含所有页的链表，最近使用的页面在表头，最近未使用的页面在表尾。而每次访问页面时都最近未使用的页面在表尾。而每次访问页面时都需要对链表进行更新。在链表中找到所需的页，需要对链表进行更新。在链表中找到所需的页，将它移动到表头是一个非常费时的操作，即使使将它移动到表头是一个非常费时的操作，即使使用硬件实现也是一样。用硬件实现也是一样。82 4 页面置换算法页面置换算法 【例例8-3】假定系统为某进程分配了假定系统为某进程分配了3个物理块，个物理块，页面访问序列为：页面访问序列为：5、0、1、2、0、3、0、4、2、3、0、3、2、1、2、0、1、5、0、1。采用。采用最近最久未使用置最近最久未使用置换算法换算法，计算缺页中断次数和缺页中断率。，计算缺页中断次数和缺页中断率。解：页面置换过程如下表所示：解：页面置换过程如下表所示：页面访问序列页面访问序列50120304230321201501501203042303212015015012030423032120150501223042203312015+-+-+-+-+-+-缺页中断次数缺页中断次数=12缺页中断率缺页中断率=12/20=60%82 4 页面置换算法页面置换算法 nClock置换算法（最近未使用算法置换算法（最近未使用算法(NRU)）：）：最近最久未使用置最近最久未使用置换算法是一种比较合理的算法，但它经常要在链表中移动页面，换算法是一种比较合理的算法，但它经常要在链表中移动页面，大大降低了系统效率。为了克服这个缺陷，把所有的页面保存大大降低了系统效率。为了克服这个缺陷，把所有的页面保存在一个类似时钟表面的环形链表中，用一个表针指向可能淘汰在一个类似时钟表面的环形链表中，用一个表针指向可能淘汰的页面，如下图所示的页面，如下图所示 ABCDEFGHIJK设置一个设置一个访问位访问位:0 表示最近未使用表示最近未使用 1表示最近使用过表示最近使用过82 4 页面置换算法页面置换算法 当发生缺页时，该算法首先当发生缺页时，该算法首先检查表针指向的页面，如果其检查表针指向的页面，如果其访问位是访问位是0 0，则淘汰该页，并把，则淘汰该页，并把新的页面插入到这个位置，然新的页面插入到这个位置，然后把表针前移一个位置；如果后把表针前移一个位置；如果访问位是访问位是1 1则把其置则把其置0 0，暂不换，暂不换出，并把表针前移一个位置，出，并把表针前移一个位置，重复这个过程直到找到一个访重复这个过程直到找到一个访问位为问位为0 0的页为止。了解了这个的页为止。了解了这个算法的工作方式，我们就知道算法的工作方式，我们就知道这种算法为什么被称为这种算法为什么被称为ClockClock算算法了。但法了。但因该算法只有一位访因该算法只有一位访问位，只能用它表示该页是否问位，只能用它表示该页是否使用过，而置换时将未使用过使用过，而置换时将未使用过的页面换出去，故又把该算法的页面换出去，故又把该算法称为最近未使用算法（称为最近未使用算法（NRUNRU）。）。ABCDEFGHIJK82 4 页面置换算法页面置换算法CLOCKCLOCK算法执行过程算法执行过程算法执行过程算法执行过程82 4 页面置换算法页面置换算法 n改进改进CLOCK置换算法置换算法 事实上，时钟算法不但希望淘汰最近未访问的页，事实上，时钟算法不但希望淘汰最近未访问的页，而且还希望被挑选的页在内存驻留期间，其页面内而且还希望被挑选的页在内存驻留期间，其页面内的的数据未被修改过数据未被修改过。淘汰该页时，由于该页未被修。淘汰该页时，由于该页未被修改过，因此不必写盘，从而减少了磁盘的改过，因此不必写盘，从而减少了磁盘的I/O操作次操作次数。为此，要为每页增设两个硬件位：访问位和修数。为此，要为每页增设两个硬件位：访问位和修改位：改位：82 4 页面置换算法页面置换算法 访问位访问位A=0：该页尚未被访问过：该页尚未被访问过 =1：该页已经被访问过：该页已经被访问过修改位修改位M=0：该页尚未被修改过：该页尚未被修改过 =1：该页已经被修改过：该页已经被修改过访问位和修改位的组合有以下四种：访问位和修改位的组合有以下四种：u1类（类（A=0，M=0）：表示该页最近既未被访问，）：表示该页最近既未被访问，又未被修改，是最佳淘汰页；又未被修改，是最佳淘汰页；u2类（类（A=0，M=1）：表示该页最近未被访问，）：表示该页最近未被访问，但已被修改，并不是很好的淘汰页；但已被修改，并不是很好的淘汰页；u3类（类（A=1，M=0）：最近已被访问，但未被修）：最近已被访问，但未被修改，该页有可能再次被访问；改，该页有可能再次被访问；u4类（类（A=1，M=1）：最近已被访问且被修改，）：最近已被访问且被修改，该页可能再次被访问。该页可能再次被访问。82 4 页面置换算法页面置换算法 改进改进改进改进CLOCKCLOCKCLOCKCLOCK算法执行过程算法执行过程算法执行过程算法执行过程 从当前位置扫描循环队列，寻找从当前位置扫描循环队列，寻找 类页面类页面,找到找到后立即置换后立即置换。若步骤若步骤失败，开始第二轮扫描，寻找失败，开始第二轮扫描，寻找类页面类页面找到后立即置换找到后立即置换。并将所经过的页面的访问位置并将所经过的页面的访问位置0 0。若步骤若步骤也失败，重复步骤也失败，重复步骤 ，若仍失败，再重，若仍失败，再重复步骤复步骤 。82 5 请求分页系统的性能分析请求分页系统的性能分析 请求分页式存储管理系统的性能优越，较好请求分页式存储管理系统的性能优越，较好地解决了存储扩充问题。因此，它是目前最常用地解决了存储扩充问题。因此，它是目前最常用的存储管理方式。但进程在运行时所产生的缺页的存储管理方式。但进程在运行时所产生的缺页中断，会影响程序的运行速度及系统性能。而缺中断，会影响程序的运行速度及系统性能。而缺页率的高低又与分配给进程的物理块数直接相关。页率的高低又与分配给进程的物理块数直接相关。因此，本节所要介绍的主要内容是分析因此，本节所要介绍的主要内容是分析:1.缺页率对系统性能的影响程度缺页率对系统性能的影响程度 2.为每个进程分配多少物理块数目，才能把缺页为每个进程分配多少物理块数目，才能把缺页率保持在一个合理的水平上。率保持在一个合理的水平上。82 5 请求分页系统的性能分析请求分页系统的性能分析 n缺页率对有效访问时间的影响缺页率对有效访问时间的影响：u有效访问时间：有效访问时间：设设p为缺页率，为缺页率，t为存储器访问为存储器访问时间，则有效访问时间为：时间，则有效访问时间为：有效访问时间有效访问时间=（1p）t+p缺页中断时间缺页中断时间u缺页中断时间的组成：缺页中断时间的组成：缺页中断时间主要由三缺页中断时间主要由三部分组成：部分组成：p缺页中断服务时间；缺页中断服务时间；p将所缺的页读入的时间；将所缺的页读入的时间；p进程重新执行时间。进程重新执行时间。82 5 请求分页系统的性能分析请求分页系统的性能分析 u缺页中断率对访问时间的影响：缺页中断率对访问时间的影响：其中缺页中断其中缺页中断服务时间和进程重新执行时间之和可以不超过服务时间和进程重新执行时间之和可以不超过1ms,而将一磁盘块读入内存的时间大概是而将一磁盘块读入内存的时间大概是24ms。所以缺页中断时间约为所以缺页中断时间约为25ms。如果存储器的平。如果存储器的平均访问时间为均访问时间为100 ns，于是可得：，于是可得：有效访问时间有效访问时间=（1p）0.1+p25000 =0.1+24999.9p 如果希望在缺页时，仅使有效访问时间延如果希望在缺页时，仅使有效访问时间延长不超过长不超过10%，则可计算出缺页率，则可计算出缺页率p 0.1(1+10%)0.1+24999.9p 即即82 5 请求分页系统的性能分析请求分页系统的性能分析 由由此此可可知知，要要求求在在2500000次次的的访访问问中中，才才发发生生一一次次缺缺页页，即即请请求求分分页页式式存存储储管管理理应应保保持持非非常常低低的的缺缺页页率率，否否则则将将使使程程序序的的执执行行速速度度受受到到严严重重影影响响。此此外外，提提高高磁磁盘盘I/O速速度度，对对改改善善请请求求分分页页系系统统的的性性能能至至关关重重要要。为为此此，应应选选用用高高速速磁磁盘盘和和高高速速磁盘接口。磁盘接口。82 5 请求分页系统的性能分析请求分页系统的性能分析 例：例：现有一请求调页系统，页表保存在寄存器中。现有一请求调页系统，页表保存在寄存器中。若有一个被替换的页未被修改过，则处理一个缺页中若有一个被替换的页未被修改过，则处理一个缺页中断需要断需要8ms；若被替换的页被修改过，则处理一个缺；若被替换的页被修改过，则处理一个缺页中断需要页中断需要20ms。内存存取时间为。内存存取时间为1 s,访问页表的访问页表的时间可以忽略不计。假设时间可以忽略不计。假设70%被替换的页被修改过，被替换的页被修改过，为保证有效存取时间不超过为保证有效存取时间不超过2 s，则可接受的最大缺，则可接受的最大缺页率是多少？页率是多少？p*(0.7*20+0.3*8)+(1-p)*0.001=0.002P=1/16399 0.0000682 5 请求分页系统的性能分析请求分页系统的性能分析“抖动抖动”问题问题 在虚存中，页面在内存与外存之间频繁调度，以在虚存中，页面在内存与外存之间频繁调度，以至于调度页面所需时间比进程实际运行的时间还多，至于调度页面所需时间比进程实际运行的时间还多，此时系统效率急剧下降，甚至导致系统崩溃。这种现此时系统效率急剧下降，甚至导致系统崩溃。这种现象称为象称为颠簸颠簸或或抖动抖动原因：原因：页面淘汰算法不合理页面淘汰算法不合理分配给进程的物理页面数太少分配给进程的物理页面数太少82 5 请求分页系统的性能分析请求分页系统的性能分析驻留集驻留集 虚拟页式存储管理中给进程分配的物理块的集合；虚拟页式存储管理中给进程分配的物理块的集合；驻留集大小驻留集大小即是这个集合的元素个数即是这个集合的元素个数驻留集大小与系统效率驻留集大小与系统效率每个进程的驻留集越小，则同时驻留内存的进程每个进程的驻留集越小，则同时驻留内存的进程就越多，就越多，CPUCPU利用率越高利用率越高进程的驻留集太小的话，则缺页率高，使调页的进程的驻留集太小的话，则缺页率高，使调页的开销增大开销增大进程的驻留集大小达到一定数目之后，再给它分进程的驻留集大小达到一定数目之后，再给它分配更多页面，缺页率不再明显下降配更多页面，缺页率不再明显下降82 5 请求分页系统的性能分析请求分页系统的性能分析 拐点物理块数 n缺页率82 5 请求分页系统的性能分析请求分页系统的性能分析 n工作集：工作集：19681968年由年由DenningDenning提出，引入工作集的提出，引入工作集的目的目的是依据进是依据进程在过去的一段时间内访问的页面来调整驻留集大程在过去的一段时间内访问的页面来调整驻留集大小小工作集定义：工作集定义：工作集就是进程在某段时间段工作集就是进程在某段时间段里实际要里实际要访问的页面的集合。访问的页面的集合。82 5 请求分页系统的性能分析请求分页系统的性能分析n工作集（工作集（Working Set）模型）模型 基本思想：根据程序的局部性原理，一般情况下，进基本思想：根据程序的局部性原理，一般情况下，进程在程在一段时间内一段时间内总是集中访问一些页面，这些页面称总是集中访问一些页面，这些页面称为活跃页面，如果分配给一个进程的物理页面数太少为活跃页面，如果分配给一个进程的物理页面数太少了，使该进程所需的活跃页面不能全部装入内存，则了，使该进程所需的活跃页面不能全部装入内存，则进程在运行过程中将频繁发生中断进程在运行过程中将频繁发生中断-抖动抖动 进程要有效地运行，其工作集必须在内存中进程要有效地运行，其工作集必须在内存中82 5 请求分页系统的性能分析请求分页系统的性能分析 u工作集：工作集：工作集就是进程在某段时间段工作集就是进程在某段时间段里实际要访里实际要访问的页面的集合。问的页面的集合。具体地说，运行进程在时间具体地说，运行进程在时间t到到t这个时间段内所访问的页面的集合称为该进程在时间这个时间段内所访问的页面的集合称为该进程在时间t的工作集，记为，变量的工作集，记为，变量称为工作集称为工作集“窗口尺寸窗口尺寸”（Windows Size）。通常还把工作集中所包含的页面）。通常还把工作集中所包含的页面数称为数称为“工作集尺寸工作集尺寸”，记为，记为例：例：26157775162341234443434441327|t1|t2 ws(t1,)=1,2,5,6,7 ws(t2,)=3,482 5 请求分页系统的性能分析请求分页系统的性能分析大小确定大小确定如果如果过大，甚至把作业地址空间全包括在内，就成过大，甚至把作业地址空间全包括在内，就成了实存管理了实存管理;如果如果过小，则会引起频繁缺页过小，则会引起频繁缺页,降低了系统的效率。降低了系统的效率。82 5 请求分页系统的性能分析请求分页系统的性能分析工作集大小的变化工作集大小的变化进程开始执行后，随着访问新页面逐步建立进程开始执行后，随着访问新页面逐步建立较稳定的工较稳定的工作集作集。当内存访问的。当内存访问的局部性区域的位置局部性区域的位置大致稳定时，工作集大致稳定时，工作集大小也大致稳定；局部性区域的位置改变时，工作集大小也大致稳定；局部性区域的位置改变时，工作集快速扩快速扩张和收缩过渡张和收缩过渡到下一个稳定值。到下一个稳定值。82 5 请求分页系统的性能分析请求分页系统的性能分析利用工作集来进行驻留集调整的策略：利用工作集来进行驻留集调整的策略：记录一个进程的工作集变化记录一个进程的工作集变化定期删除驻留集中不在工作集中的页面定期删除驻留集中不在工作集中的页面总是让驻留集包含工作集（不能包含时则增大驻总是让驻留集包含工作集（不能包含时则增大驻留集）留集）82 5 请求分页系统的性能分析请求分页系统的性能分析影响缺页次数的因素影响缺页次数的因素(1)(1)分配给进程的物理块数分配给进程的物理块数一个程序运行时遇到缺页中断的次数，是和分配给该道程序一个程序运行时遇到缺页中断的次数，是和分配给该道程序的物理块数成反比的，但当主存容量达到某个值时，缺页次的物理块数成反比的，但当主存容量达到某个值时，缺页次数减少不再明显。多数程序都有一个确定值数减少不再明显。多数程序都有一个确定值拐点拐点(2)页面