第46章操作系统课程.pptx

4.64.6虚拟存储器虚拟存储器1 1 虚拟存储器概述虚拟存储器概述1.1 常规存储管理方式的特征和局部性原理 1.1.常规存储器管理方式的特征常规存储器管理方式的特征 一次性一次性，是指作业必须一次性地全部装入内存，是指作业必须一次性地全部装入内存后，方能开始运行。这一特征导致了下述两种情况的后，方能开始运行。这一特征导致了下述两种情况的发生：发生：当作业很大时，它所要求的内存空间超过了内当作业很大时，它所要求的内存空间超过了内存总容量，无法将全部作业装入内存，致使该作业无存总容量，无法将全部作业装入内存，致使该作业无法运行；法运行；当有大量作业要求运行的情况下，由于每一个当有大量作业要求运行的情况下，由于每一个作业都需要全部装入内存后方能运行，所以每次只能作业都需要全部装入内存后方能运行，所以每次只能装入少量的作业，导致多道程序度的下降。装入少量的作业，导致多道程序度的下降。驻留性驻留性，是指作业被装入内存后，整个作业都，是指作业被装入内存后，整个作业都一直驻留在内存中，其中任何部分都不会被换出，直一直驻留在内存中，其中任何部分都不会被换出，直至作业运行结束。至作业运行结束。2.2.局部性原理局部性原理 程序执行时，除了少部分的转移和过程调用指令外，在大多数情程序执行时，除了少部分的转移和过程调用指令外，在大多数情况下是顺序执行的。况下是顺序执行的。过程调用将会使程序的执行轨迹，由一部分区域转至另一部分区过程调用将会使程序的执行轨迹，由一部分区域转至另一部分区域。即程序将会在一段时间内，都局限在这些过程的范围内运行。域。即程序将会在一段时间内，都局限在这些过程的范围内运行。程序中存在许多循环结构，这些虽然只由少数指令构成，但是它程序中存在许多循环结构，这些虽然只由少数指令构成，但是它们将多次执行。们将多次执行。程序中还包括许多对数据结构的处理，如对数组进行操作，它们程序中还包括许多对数据结构的处理，如对数组进行操作，它们往往都局限于很小的范围内。往往都局限于很小的范围内。局限性又表现在下述两个方面：局限性又表现在下述两个方面：时间局限性时间局限性:如果程序中的某条指令一旦执行，则不久以后该指如果程序中的某条指令一旦执行，则不久以后该指令可能再次执行；如果某数据被访问过，则不久以后该数据可能再次被令可能再次执行；如果某数据被访问过，则不久以后该数据可能再次被访问。访问。空间局限性空间局限性:一旦程序访问了某个存储单元，在不久之后，其附一旦程序访问了某个存储单元，在不久之后，其附近的存储单元也将被访问，即程序在一段时间内所访问的地址，可能集近的存储单元也将被访问，即程序在一段时间内所访问的地址，可能集中在一定的范围之内。中在一定的范围之内。1.1 常规存储管理方式的特征和局部性原理 3.3.虚拟存储器的基本工作情况虚拟存储器的基本工作情况 应用程序在运行之前，仅须将那些当前要运行的少数页面或段，先应用程序在运行之前，仅须将那些当前要运行的少数页面或段，先装入内存便可运行，其余部分暂留在盘上。装入内存便可运行，其余部分暂留在盘上。程序在运行时，如果它所要访问的页（段）已调入内存，便可继续程序在运行时，如果它所要访问的页（段）已调入内存，便可继续执行下去；但如果程序所要访问的页（段）尚未调入内存（称为缺页或执行下去；但如果程序所要访问的页（段）尚未调入内存（称为缺页或缺段），便发出缺页（段）中断请求，此时缺段），便发出缺页（段）中断请求，此时OSOS将利用请求调页（段）功将利用请求调页（段）功能，将它们调入内存，以使进程能继续执行下去。能，将它们调入内存，以使进程能继续执行下去。如果此时内存已满，无法再装入新的页（段），如果此时内存已满，无法再装入新的页（段），OSOS还须再利用页还须再利用页（段）的置换功能，将内存中暂时不用的页（段）调至盘上，腾出足够（段）的置换功能，将内存中暂时不用的页（段）调至盘上，腾出足够的内存空间后，再将要访问的页（段）调入内存，使程序继续执行下去。的内存空间后，再将要访问的页（段）调入内存，使程序继续执行下去。1.1 常规存储管理方式的特征和局部性原理1.2 虚拟存储器的定义和特征 1.1.虚拟存储器的定义虚拟存储器的定义 具有请求调入功能和置换功能，能从逻辑上具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统。其逻辑对内存容量加以扩充的一种存储器系统。其逻辑容量由内存容量和外存容量之和所决定，其运行容量由内存容量和外存容量之和所决定，其运行速度接近于内存速度，而每位的成本却又接近于速度接近于内存速度，而每位的成本却又接近于外存。外存。虚拟存储技术是一种性能非常优越的存储器虚拟存储技术是一种性能非常优越的存储器管理技术，故被广泛地应用于大、中、小型机器管理技术，故被广泛地应用于大、中、小型机器和微型机中。和微型机中。1.2 虚拟存储器的定义和特征 2.2.虚拟存储器的特征虚拟存储器的特征 多次性多次性 对换性对换性 虚拟性虚拟性 虚拟性是以多次性和对换性为基础的，或者虚拟性是以多次性和对换性为基础的，或者说，仅当系统允许将作业分多次调入内存，并能说，仅当系统允许将作业分多次调入内存，并能将内存中暂时不运行的程序和数据换至盘上时，将内存中暂时不运行的程序和数据换至盘上时，才有可能实现虚拟存储器；而多次性和对换性，才有可能实现虚拟存储器；而多次性和对换性，显然又必须建立在离散分配的基础上。显然又必须建立在离散分配的基础上。1.1.分页请求系统分页请求系统 在分页系统的基础上，增加了请求调页功能和页面置换功能，所形成在分页系统的基础上，增加了请求调页功能和页面置换功能，所形成的页式虚拟存储系统。置换时以页面为单位。的页式虚拟存储系统。置换时以页面为单位。（1 1）硬件支持：请求分页的页表机制、缺页中断机构、地址变换机构。）硬件支持：请求分页的页表机制、缺页中断机构、地址变换机构。（2 2）实现请求分页的软件：实现请求调页的软件和实现页面置换的软）实现请求分页的软件：实现请求调页的软件和实现页面置换的软件。件。2.2.请求分段系统请求分段系统 在分段系统的基础上，增加了请求调段及分段置换功能后，所形成的在分段系统的基础上，增加了请求调段及分段置换功能后，所形成的段式虚拟存储系统。置换是以段为单位进行的。段式虚拟存储系统。置换是以段为单位进行的。为了实现请求分段，系统同样需要必要的硬件和软件支持。为了实现请求分段，系统同样需要必要的硬件和软件支持。（1 1）硬件支持：请求分段的段表机制、缺段中断机构、地址变换机构。）硬件支持：请求分段的段表机制、缺段中断机构、地址变换机构。（2 2）实现请求分段的软件：实现请求调段的软件和实现段置换的软件。）实现请求分段的软件：实现请求调段的软件和实现段置换的软件。1.3 虚拟存储器的实现方法返回4.6 4.6 虚拟存储器虚拟存储器2 2 请求分页存储管理方式请求分页存储管理方式2.1 2.1 请求分页中的硬件支持请求分页中的硬件支持 1.1.请求页表机制请求页表机制 2.2.缺页中断机构缺页中断机构 3.3.地址变换机构地址变换机构2.2 2.2 请求分页中的内存分配请求分页中的内存分配2.3 2.3 页面调入策略页面调入策略2.1 请求分页中的硬件支持1.1.请求页表机制请求页表机制页号页号物理块号物理块号状态位状态位P P访问字段访问字段A A修改位修改位M M外存地址外存地址 状态位（存在位）状态位（存在位）P P：仅有一位，故又称位字，用于指示该页是仅有一位，故又称位字，用于指示该页是否已调入内存，供程序访问时参考。否已调入内存，供程序访问时参考。访问字段访问字段A A：记录本页在一段时间内被访问的次数，或记录本页记录本页在一段时间内被访问的次数，或记录本页最近已有多长时间未被访问，提供给置换算法（程序）选择换出页面时最近已有多长时间未被访问，提供给置换算法（程序）选择换出页面时参考。参考。修改位修改位M M：标识该页在调入内存后是否被修改过。供置换页面时标识该页在调入内存后是否被修改过。供置换页面时参考。参考。外存地址：外存地址：用于指出该页在外存上的地址，通常是物理块号，供用于指出该页在外存上的地址，通常是物理块号，供调入该页时参考。调入该页时参考。2.1 请求分页中的硬件支持 2.2.缺页中断机构缺页中断机构 缺页中断作为中断，同样需要经历缺页中断作为中断，同样需要经历诸如保护诸如保护CPUCPU环境、分析中断原因、转环境、分析中断原因、转入缺页中断处理程序进行处理，以及在入缺页中断处理程序进行处理，以及在中断处理完成后再恢复中断处理完成后再恢复CPUCPU环境等几个环境等几个步骤。步骤。缺页中断又是一种特殊的中断，它缺页中断又是一种特殊的中断，它与一般的中断相比，有着明显的区别：与一般的中断相比，有着明显的区别：在指令执行期间，产生和处理中在指令执行期间，产生和处理中断信号。断信号。一条指令在执行期间，可能产生一条指令在执行期间，可能产生多次缺页中断。多次缺页中断。2.1 请求分页中的硬件支持3.3.地址变换机构地址变换机构 1.1.最小物理块数的确定最小物理块数的确定 随着为每个进程所分配的物理块的减少，将使进程在执行中的缺页率上升，随着为每个进程所分配的物理块的减少，将使进程在执行中的缺页率上升，从而会降低进程的执行速度。从而会降低进程的执行速度。最小物理块数是指，能保证进程正常运行所需的最小物理块数，当系统为最小物理块数是指，能保证进程正常运行所需的最小物理块数，当系统为进程分配的物理块数少于此值时，进程将无法运行。进程分配的物理块数少于此值时，进程将无法运行。进程应获得的最少物理块数，与计算机的硬件结构有关，取决于指令的格进程应获得的最少物理块数，与计算机的硬件结构有关，取决于指令的格式、功能和寻址方式。式、功能和寻址方式。对于某些简单的机器，若是单地址指令，且采用直接寻址方式，则所需的对于某些简单的机器，若是单地址指令，且采用直接寻址方式，则所需的最少物理块数为最少物理块数为2 2。其中，一块是用于存放指令的页面，另一块则是用于存放。其中，一块是用于存放指令的页面，另一块则是用于存放数据的页面。数据的页面。如果该机器允许间接寻址时，则至少要求有三个物理块。如果该机器允许间接寻址时，则至少要求有三个物理块。对于某些功能较强的机器，其指令长度可能是两个或多于两个字节，因而对于某些功能较强的机器，其指令长度可能是两个或多于两个字节，因而其指令本身有可能跨两个页面，且源地址和目标地址所涉及的区域，也都可能其指令本身有可能跨两个页面，且源地址和目标地址所涉及的区域，也都可能跨两个页面。跨两个页面。2.2 请求分页中的内存分配 2.2.内存分配策略内存分配策略 （1 1）固定分配局部置换）固定分配局部置换 固定分配是指，为每个进程分配一组固定数目的物理块，在进程运行期间固定分配是指，为每个进程分配一组固定数目的物理块，在进程运行期间不再改变。不再改变。局部置换是指，如果进程在运行中发现缺页，则只能从分配给该进程的局部置换是指，如果进程在运行中发现缺页，则只能从分配给该进程的n n个个页面中，选出一页换出，然后再调入一页。页面中，选出一页换出，然后再调入一页。（2 2）可变分配全局置换）可变分配全局置换 可变分配是指，先为每个进程分配一定数目的物理块，在进程运行期间，可变分配是指，先为每个进程分配一定数目的物理块，在进程运行期间，可根据情况做适当地改变。可根据情况做适当地改变。全局置换是指，如果进程在运行中发现缺页，则将全局置换是指，如果进程在运行中发现缺页，则将OSOS所保留的空闲物理块所保留的空闲物理块或者以所有进程的全部物理块为标的，选择一块换出，然后将所缺之页调入。或者以所有进程的全部物理块为标的，选择一块换出，然后将所缺之页调入。（3 3）可变分配局部置换）可变分配局部置换 为每个进程分配一定数目的物理块，但当某进程发现缺页时，只允许从该为每个进程分配一定数目的物理块，但当某进程发现缺页时，只允许从该进程在内存的页面中，选择一页换出，如果进程在运行中，频繁地发生缺页中进程在内存的页面中，选择一页换出，如果进程在运行中，频繁地发生缺页中断，则系统须再为该进程分配若干附加的物理块，直至该进程的缺页率减少到断，则系统须再为该进程分配若干附加的物理块，直至该进程的缺页率减少到适当程度为止。适当程度为止。2.2 请求分页中的内存分配 3.3.物理块分配算法物理块分配算法 （1 1）平均分配算法）平均分配算法：将系统中所有可供分配的物理块，平均分配给各个进：将系统中所有可供分配的物理块，平均分配给各个进程。程。（2 2）按比例分配算法：）按比例分配算法：根据进程的大小按比例分配物理块的算法。根据进程的大小按比例分配物理块的算法。系统中各进程页面数的总和为：系统中各进程页面数的总和为：每个进程所能分到的物理块数为每个进程所能分到的物理块数为bibi：（3 3）考虑优先权的分配算法：）考虑优先权的分配算法：把内存中可供分配的所有物理块分成两部分：把内存中可供分配的所有物理块分成两部分：一部分按比例地分配给各进程；另一部分则根据各进程的优先权进行分配，为一部分按比例地分配给各进程；另一部分则根据各进程的优先权进行分配，为高优先进程适当地增加其相应份额高优先进程适当地增加其相应份额。2.2 请求分页中的内存分配 1.1.何时调入页面何时调入页面 预调页策略：那些预计在不久之后便会被访问的页面，预先调入内存。预调页策略：那些预计在不久之后便会被访问的页面，预先调入内存。请请求求调调页页策策略略：当当进进程程在在运运行行中中需需要要访访问问某某部部分分程程序序和和数数据据时时，若若发发现其所在的页面不在内存，便立即提出请求，由现其所在的页面不在内存，便立即提出请求，由OSOS将其所需页面调入内存。将其所需页面调入内存。2.2.从何处调入页面从何处调入页面 在在请请求求分分页页系系统统中中的的外外存存分分为为两两部部分分：用用于于存存放放文文件件的的文文件件区区和和用用于于存存放放对换页面的对换区。对换页面的对换区。系统拥有足够的对换区空间。系统拥有足够的对换区空间。系统缺少足够的对换区空间。系统缺少足够的对换区空间。UNIXUNIX方式。方式。2.3 页面调入策略 3.3.页面调入过程页面调入过程 每每当当程程序序所所要要访访问问的的页页面面未未在在内内存存时时（存存在在位位为为“0 0”），便便向向CPUCPU发发出出一一缺缺页页中中断断，中中断断处处理理程程序序首首先先保保留留CPUCPU环环境境，分分析析中中断断原原因因后后，转转入入缺缺页页中中断断处处理理程程序序。该该程程序序通通过过查查找找页页表表，得得到到该该页页在在外外存存的的物物理理块块后后，如如果果此此时时内内存存能能容容纳纳新新页页，则则启启动动磁磁盘盘I/OI/O，将将所所缺缺之之页页调调入入内内存存，然然后后修修改改页页表表。如如果果内内存存已已满满，则则须须先先按按照照某某种种置置换换算算法法，从从内内存存中中选选出出一一页页准准备备换换出出；如如果果该该页页未未被被修修改改过过（修修改改位位为为“O O”），可可不不必必将将该该页页写写回回磁磁盘盘；但但如如果果此此页页已已被被修修改改（修修改改位位为为“1 1”），则则必必须须将将它它写写回回磁磁盘盘，然然后后再再把把所所缺缺的的页页调调入入内内存存，并并修修改改页页表表中中的的相相应应表表项项，置置其其存存在在位位为为“1 1”，并并将将此此页页表表项项写写入入快快表表中中。在在缺缺页页调调入入内内存存后后，利利用用修修改改后后的的页页表表，去去形形成成所所要要访访问问数数据据的物理地址，再去访问内存数据。整个页面的调入过程对用户是透明的。的物理地址，再去访问内存数据。整个页面的调入过程对用户是透明的。2.3 页面调入策略返回4.6 4.6 虚拟存储器虚拟存储器3 3 页面置换算法页面置换算法3.1 最佳置换算法和先进先出置换算法 1.1.最佳置换算法最佳置换算法 由由BeladyBelady于于19661966年提出的一种理论上的算法。年提出的一种理论上的算法。其所选择的被淘汰页其所选择的被淘汰页面，将是以后永不使用的，面，将是以后永不使用的，或许是在最长或许是在最长(未来未来)时间内不再被访问的页面。时间内不再被访问的页面。采用最佳置换算法，通常可保证获得最低的缺页率。采用最佳置换算法，通常可保证获得最低的缺页率。假定系统为某进程分配了三个物理块，假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用并考虑有以下的页面号引用串：串：7 7，0 0，1 1，2 2，0 0，3 3，0 0，4 4，2 2，3 3，0 0，3 3，2 2，1 1，2 2，0 0，1 1，7 7，0 0，1 1 进程运行时，进程运行时，先将先将7 7，0 0，1 1三个页面装入内存。三个页面装入内存。以后，以后，当进程要访当进程要访问页面问页面2 2时，时，将会产生缺页中断。此时将会产生缺页中断。此时OSOS根据最佳置换算法，根据最佳置换算法，将选择页面将选择页面7 7予以淘汰。予以淘汰。3.1 最佳置换算法和先进先出置换算法 2.2.先进先出页面置换算法先进先出页面置换算法 置换时，选择在内存中驻留时间最长的页并予以淘汰。3.2 最近最久未使用和最少使用置换算法 1.LRU1.LRU置换算法的描述置换算法的描述 选择最后一次访问时间距离当前时间最长的一页并淘汰之。即淘汰没选择最后一次访问时间距离当前时间最长的一页并淘汰之。即淘汰没有使用的时间最长的页。实现代价很高（时间戳或硬件方法）。有使用的时间最长的页。实现代价很高（时间戳或硬件方法）。3.2 最近最久未使用和最少使用置换算法 2.LRU2.LRU置换算法的硬件支持置换算法的硬件支持 寄存器寄存器 为了记录某进程在内存中各页的使用情况，须为每个在内存中的页面为了记录某进程在内存中各页的使用情况，须为每个在内存中的页面配置一个移位寄存器，可表示为配置一个移位寄存器，可表示为 :R=R:R=Rn-1n-1R Rn-2n-2R Rn-3n-3 R R2 2R R1 1R R0 0 。3.2 最近最久未使用和最少使用置换算法 2.LRU2.LRU置换算法的硬件支持置换算法的硬件支持 （2 2）栈）栈 3.2 最近最久未使用和最少使用置换算法 3.3.最少使用最少使用LFULFU置换算法置换算法 选择在最近时期使用最少的页面作为淘汰页。选择在最近时期使用最少的页面作为淘汰页。LFULFU置换算法的页面访问图，与置换算法的页面访问图，与LRULRU置换算法的访问图完全相同；或者置换算法的访问图完全相同；或者说，利用这样一套硬件既可实现说，利用这样一套硬件既可实现LRULRU算法，又可实现算法，又可实现LFULFU算法。算法。这种算法并不能真正反映出页面的使用情况，因为在每一时间间隔内，这种算法并不能真正反映出页面的使用情况，因为在每一时间间隔内，只是用寄存器的一位来记录页的使用情况，因此，在该时间间隔内，对某只是用寄存器的一位来记录页的使用情况，因此，在该时间间隔内，对某页访问一次和访问页访问一次和访问10001000次是完全等效的。次是完全等效的。4.3.3 Clock置换算法 1.1.简单的简单的ClockClock置换算法置换算法 4.3.3 Clock置换算法 2.2.改进型改进型ClockClock置换算法置换算法 由访问位由访问位A A和修改位和修改位M M可以组合成下面四种类型的页面：可以组合成下面四种类型的页面：1 1类类(A=0,M=0):(A=0,M=0):该页最近既未被访问，又未被修改，是最佳淘汰页。该页最近既未被访问，又未被修改，是最佳淘汰页。2 2类类(A=0,M=1)(A=0,M=1)：该页最近未被访问，但已被修改，并不是很好的淘汰：该页最近未被访问，但已被修改，并不是很好的淘汰页。页。3 3类类(A=1,M=0)(A=1,M=0)：最近已被访问，但未被修改，该页有可能再被访问。：最近已被访问，但未被修改，该页有可能再被访问。4 4类类(A=1,M=1):(A=1,M=1):最近已被访问且被修改，最近已被访问且被修改，该页可能再被访问。该页可能再被访问。其执行过程可分成以下三步：其执行过程可分成以下三步：(1)(1)从指针所指示的当前位置开始，扫描循环队列，寻找从指针所指示的当前位置开始，扫描循环队列，寻找A=0A=0且且M=0M=0的第的第一类页面，将所遇到的第一个页面作为所选中的淘汰页。在第一次扫描期间一类页面，将所遇到的第一个页面作为所选中的淘汰页。在第一次扫描期间不改变访问位不改变访问位A A。(2)(2)如果第一步失败，则开始第二轮扫描，寻找如果第一步失败，则开始第二轮扫描，寻找A=0A=0且且M=1M=1的第二类页面，的第二类页面，将所遇到的第一个这类页面作为淘汰页。在第二轮扫描期间，将所有扫描过将所遇到的第一个这类页面作为淘汰页。在第二轮扫描期间，将所有扫描过的页面的访问位都置的页面的访问位都置0 0。(3)(3)如果第二步也失败，则将指针返回到开始的位置，并将所有的访问如果第二步也失败，则将指针返回到开始的位置，并将所有的访问位复位复0 0。然后重复第一步。然后重复第一步。4.3.4 页面缓冲算法PBA 1.1.影响页面换进换出效率的若干因素影响页面换进换出效率的若干因素 页面置换算法：页面置换算法：影响页面换进换出效率最重要的因素，直接影响进程影响页面换进换出效率最重要的因素，直接影响进程在运行过程中的缺页率，影响页面换进换出的开销。在运行过程中的缺页率，影响页面换进换出的开销。写回磁盘的频率：写回磁盘的频率：如果是采取每个页面换出时，就将它写回磁盘的策如果是采取每个页面换出时，就将它写回磁盘的策略，这意味着每换出一个页面，便需要启动一次磁盘。但如果在系统中建立略，这意味着每换出一个页面，便需要启动一次磁盘。但如果在系统中建立了一个已修改换出页面链表，对每一个要被换出的页面（已修改），系统可了一个已修改换出页面链表，对每一个要被换出的页面（已修改），系统可暂不把它们写回磁盘，而是将它们挂在已修改换出页面链表上，仅当被换出暂不把它们写回磁盘，而是将它们挂在已修改换出页面链表上，仅当被换出页面数目达到一定值时，再将它们一起写回到磁盘上，这样就显著地减少了页面数目达到一定值时，再将它们一起写回到磁盘上，这样就显著地减少了磁盘磁盘I/OI/O的操作次数。或者说，减少已修改页面换出的开销。的操作次数。或者说，减少已修改页面换出的开销。读入内存的频率：读入内存的频率：在设置了已修改换出页面链表后，在该链表上就暂在设置了已修改换出页面链表后，在该链表上就暂时有一批装有数据的页面，如果需要再次访问这些页面时，就不需从外存上时有一批装有数据的页面，如果需要再次访问这些页面时，就不需从外存上调入，而直接从已修改换出页面链表中获取，这样也可以减少将页面从磁盘调入，而直接从已修改换出页面链表中获取，这样也可以减少将页面从磁盘读入内存的频率，减少页面换进的开销。或者说，只需花费很小的开销，便读入内存的频率，减少页面换进的开销。或者说，只需花费很小的开销，便可使这些页面，又回到该进程的驻留集中。可使这些页面，又回到该进程的驻留集中。4.3.4 页面缓冲算法PBA 2.2.页面缓冲算法页面缓冲算法PBAPBA 页面缓冲算法页面缓冲算法PBAPBA的主要特点的主要特点 显著地降低了页面换进、换出的频率，使磁盘显著地降低了页面换进、换出的频率，使磁盘I/OI/O的操作次数大为减少，的操作次数大为减少，因而减少了页面换进、换出的开销；因而减少了页面换进、换出的开销；由于换入换出的开销大幅度减小，才能使其采用一种较简单的置换策由于换入换出的开销大幅度减小，才能使其采用一种较简单的置换策略，如先进先出（略，如先进先出（FIFOFIFO）算法，它不需要特殊硬件的支持，实现起来非常简）算法，它不需要特殊硬件的支持，实现起来非常简单。单。VAX/VMSVAX/VMS操作系统中所使用页面缓冲算法操作系统中所使用页面缓冲算法 在该系统中，内存分配策略上采用了可变分配和局部置换方式。为了能在该系统中，内存分配策略上采用了可变分配和局部置换方式。为了能显著地降低了页面换进、换出的频率，在内存中设置了如下两个链表：显著地降低了页面换进、换出的频率，在内存中设置了如下两个链表：空闲页面链表：是一个空闲物理块链表，用于分配给频繁发生缺页的空闲页面链表：是一个空闲物理块链表，用于分配给频繁发生缺页的进程，以降低该进程的缺页率。当有一个未被修改的页要换出时，实际上并进程，以降低该进程的缺页率。当有一个未被修改的页要换出时，实际上并不将它换出到外存，而是把它们所在的物理块，挂在空闲链表的末尾。不将它换出到外存，而是把它们所在的物理块，挂在空闲链表的末尾。修改页面链表：由已修改的页面所形成的链表。设置该链表的目的，修改页面链表：由已修改的页面所形成的链表。设置该链表的目的，是为了减少已修改页面换出的次数。降低将已修该页面写回磁盘的频率，以是为了减少已修改页面换出的次数。降低将已修该页面写回磁盘的频率，以及降低将磁盘内容读入内存的频率。及降低将磁盘内容读入内存的频率。返回4.64.6虚拟存储器虚拟存储器4“4“抖动抖动”与工作集与工作集1.多道程序度与“抖动”多道程序度与处理机的利多道程序度与处理机的利用率用率 由于虚拟存储器系统能从逻辑由于虚拟存储器系统能从逻辑上扩大内存，人们希望在系统中能上扩大内存，人们希望在系统中能运行更多的进程，即增加多道程序运行更多的进程，即增加多道程序度，以提高处理机的利用率。度，以提高处理机的利用率。在虚存中，页面在内存与外存在虚存中，页面在内存与外存之间频繁调度，以至于调度页面所之间频繁调度，以至于调度页面所需时间比进程实际运行的时间还多，需时间比进程实际运行的时间还多，此时系统效率急剧下降，甚至导致此时系统效率急剧下降，甚至导致系统崩溃。这种现象称为颠簸或抖系统崩溃。这种现象称为颠簸或抖动。动。产生产生“抖动抖动”的原因的原因 页面淘汰算法不合理页面淘汰算法不合理 分配给进程的物理页面数太少分配给进程的物理页面数太少2.工作集 工作集的基本概念工作集的基本概念 进程发生缺页率的时间间隔，进程发生缺页率的时间间隔，与进程所获得的物理块数有关。与进程所获得的物理块数有关。图图6-106-10示出了缺页率与物理块示出了缺页率与物理块数之间的关系。数之间的关系。基于程序运行时的局部性原理，基于程序运行时的局部性原理，得知程序在运行期间，对页面的访得知程序在运行期间，对页面的访问是不均匀的，在一段时间内仅局问是不均匀的，在一段时间内仅局限于较少的页面，在另一段时间内，限于较少的页面，在另一段时间内，又可能仅局限于对另一些较少的页又可能仅局限于对另一些较少的页面进行访问。这些页面被称为活跃面进行访问。这些页面被称为活跃页面。如果能够预知程序在某段时页面。如果能够预知程序在某段时间间隔内，要访问哪些页面，并将间间隔内，要访问哪些页面，并将它们调入内存，将会大大降低缺页它们调入内存，将会大大降低缺页率，从而可显著地提高处理机的利率，从而可显著地提高处理机的利用率。用率。4.4.2 工作集 工作集的定义工作集的定义 在某段时间间隔在某段时间间隔里，进程实际里，进程实际要要访问页面的集合。要要访问页面的集合。具体地说，是把某进程在时间具体地说，是把某进程在时间t t的的工作集记为工作集记为w(tw(t，),),其中的变量其中的变量称称为工作集的为工作集的“窗口尺寸窗口尺寸”。图。图6-116-11示示出了某进程访问页面的序列和窗口大出了某进程访问页面的序列和窗口大小分别为小分别为3 3、4 4、5 5时的工作集。时的工作集。由此可将工作集定义为：由此可将工作集定义为：进程在进程在时间间隔（时间间隔（t-t-，t t）中引用页面的集）中引用页面的集合。合。工作集工作集w(tw(t，)是二元函数，即是二元函数，即在不同时间在不同时间t t的工作集大小不同，所含的工作集大小不同，所含的页面数也不同；与窗口尺寸的页面数也不同；与窗口尺寸有关。有关。工作集大小是窗口尺寸工作集大小是窗口尺寸的非降函数：的非降函数：3.“抖动”的预防方法 采取局部置换策略采取局部置换策略 在在页页面面分分配配和和置置换换策策略略中中，如如果果采采取取的的是是可可变变分分配配方方式式时时，为为了预防发生了预防发生“抖动抖动”，可采取局部置换策略。，可采取局部置换策略。把工作集算法融入到处理机调度中把工作集算法融入到处理机调度中 在在调调度度中中融融入入了了工工作作集集算算法法，则则在在调调度度程程序序从从外外存存调调入入作作业业之之前前，必须先检查每个进程在内存的驻留页面是否足够多。必须先检查每个进程在内存的驻留页面是否足够多。利用利用“L=S”L=S”准则调节缺页率准则调节缺页率 于于19801980年年DenningDenning提提出出了了“L=SL=S”的的准准则则，来来调调节节多多道道程程序序度度，其其中中L L是是缺缺页页之之间间的的平平均均时时间间，S S是是平平均均缺缺页页服服务务时时间间，即即用用于于置置换换一一个个页页面面所所需需的的时时间间。利利用用“L=SL=S”准准则则，对对于于调调节节缺缺页页率率是是十十分分有有效效的。的。选择暂停的进程选择暂停的进程 当当多多道道程程序序度度偏偏高高时时，已已影影响响到到处处理理机机的的利利用用率率，为为了了防防止止发发生生“抖动抖动”，系统必须减少多道程序的数目。，系统必须减少多道程序的数目。返回4.6 4.6 虚拟存储器虚拟存储器5 5 请求分段存储管理方式请求分段存储管理方式p请求分段中的硬件支持请求分段中的硬件支持p分段的共享与保护分段的共享与保护1.请求分段中的硬件支持 请求段表机制请求段表机制 段名段名段长段长段的段的基址基址存取存取方式方式访问字访问字段段A A修改修改位位M M存在存在位位P P增补增补位位外存始址外存始址 在段表项中，除了段名（号）、段长、段在内存中的起始地址外，还在段表项中，除了段名（号）、段长、段在内存中的起始地址外，还增加了以下字段：增加了以下字段：存取方式：由于在应用程序的段是信息的逻辑单位，可根据该信息存取方式：由于在应用程序的段是信息的逻辑单位，可根据该信息的属性，对它实施保护，故在段表中增加存取方式字段，如果该字段为两的属性，对它实施保护，故在段表中增加存取方式字段，如果该字段为两位，则存取属性是只执行、只读，还是允许读位，则存取属性是只执行、只读，还是允许读/写。写。访问字段访问字段A A：记录该段被访问的频繁程度。提供给置换算法选择换出：记录该段被访问的频繁程度。提供给置换算法选择换出页面时参考。页面时参考。修改位修改位M M：用于表示该页在进入内存后，是否已被修改过，供置换页：用于表示该页在进入内存后，是否已被修改过，供置换页面时参考。面时参考。存在位存在位P P：用于指示本段是否已调入内存，供程序访问时参考。：用于指示本段是否已调入内存，供程序访问时参考。增补位：用于表示本段在运行过程中，是否做过动态增长。增补位：用于表示本段在运行过程中，是否做过动态增长。外存始址：指示本段在外存中的起始地址，即起始盘块号。外存始址：指示本段在外存中的起始地址，即起始盘块号。1.请求分段中的硬件支持 缺段中断机构缺段中断机构1.请求分段中的硬件支持 地址变换机构地址变换机构2.分段的共享与保护 共享段表共享段表 在系统中配置一张共享段表，所有各共享段都在共享段表中占有在系统中配置一张共享段表，所有各共享段都在共享段表中占有一表项。在表项的上面记录了共享段的段号、段长、内存始址、状态一表项。在表项的上面记录了共享段的段号、段长、内存始址、状态（存在）位、外存始址以及共享计数等信息。接下去就是记录了共享（存在）位、外存始址以及共享计数等信息。接下去就是记录了共享此分段的每个进程的情况。此分段的每个进程的情况。共享进程计数共享进程计数countcount：记录有多少进程正在共享该分段。：记录有多少进程正在共享该分段。存取控制字段：对于一个共享段，应为不同的进程赋予不存取控制字段：对于一个共享段，应为不同的进程赋予不同的存取权限。同的存取权限。段号：每个进程可用自己进程的段号，去访问该共享段。段号：每个进程可用自己进程的段号，去访问该共享段。2.分段的共享与保护 共享段的分配与回收共享段的分配与回收 共享段的分配：共享段的分配：在为共享段分配内存时，对第一个在为共享段分配内存时，对第一个请求使用该共享段的进程，由系统为该共享段分配一物理请求使用该共享段的进程，由系统为该共享段分配一物理区，当又有其它进程需要调用该共享段时，无须再为该段区，当又有其它进程需要调用该共享段时，无须再为该段分配内存。分配内存。共享段的回收：共享段的回收：当共享此段的某进程不再需要该段当共享此段的某进程不再需要该段时，若无其他进程使用该段，则由系统回收该共享段的物时，若无其他进程使用该段，则由系统回收该共享段的物理内存，否则只是取消调用者进程在共享段表中的有关记理内存，否则只是取消调用者进程在共享段表中的有关记录。录。2.分段的共享与保护 分段保护分段保护 由于每个分段在逻辑上是相对独立的，因而比较由于每个分段在逻辑上是相对独立的，因而比较容易实现信息保护：容易实现信息保护：越界检查：在进行地址变换时，利用地址变换越界检查：在进行地址变换时，利用地址变换机构完成的，从而保证了每个进程只能在自己的地址机构完成的，从而保证了每个进程只能在自己的地址空间内运行。空间内运行。存取控制检查：以段为基本单位进行，在段表存取控制检查：以段为基本单位进行，在段表的每个表项中，都设置了一个的每个表项中，都设置了一个“存取控制存取控制”字段，用字段，用于规定对该段的访问方式。通常的访问方式有：只读、于规定对该段的访问方式。通常的访问方式有：只读、只执行、读只执行、读/写。写。环保护机构：低编号的环具有高优先权。在环环保护机构：低编号的环具有高优先权。在环系统中，程序的访问和调用应遵循以下规则：系统中，程序的访问和调用应遵循以下规则：一个程序可以访问驻留在相同环或较低特权环一个程序可以访问驻留在相同环或较低特权环（外环）中的数据；（外环）中的数据；一个程序可以调用驻留在相同环或较高特权环一个程序可以调用驻留在相同环或较高特权环（内环）中的服务。（内环）中的服务。返回