第五章 虚拟存储器.pdf

第五章 虚拟存储器广东工业大学 计算机学院网络工程系 刘冬宁网络工程系 刘冬宁Outline5 1 虚拟存储器概述5.1 虚拟存储器概述5 2 请求分页存储管理方式5.2 请求分页存储管理方式页面置换算法5.3 页面置换算法5.4“抖动”与工作集（自学内容）5.5 请求分段存储管理方式5.1虚拟存储器的概述前面所介绍的各种存储器管理方式有一个共同的特点，即它们都要求将一个作业全部装入内存后方能运行，于是，出它们都要求将个作业全部装入内存后方能运行，于是，出现了下面这样两种情况：(1)有的作业很大，其所要求的内存空间超过了内存总容量，作业不能全部被装入内存，致使该作业无法运行。(2)有大量作业要求运行，但由于内存容量不足以容纳所有这些作业，只能将少数作业 装入内存让它们先运行，而将有这些作业，只能将少数作业 装入内存让它们先运行，而将其它大量的作业留在外存上等待。5.1.1虚拟存储器的引入1常规存储器管理方式的特征(1)一次性一次性地装入其全部程序是一种对内存空(1)一次性。一次性地装入其全部程序，是一种对内存空间的浪费。(2)驻留性。作业装入内存后，便一直驻留在内存中，直至作业运行结束。尽管运行中的进程会因I/O而长期等待，或有的程序模块在运行过一次后就不再需要(运行)了，但它们都仍将继续占用宝贵的内存资源。由此可以看出，上述的一次性及驻留性，使许多在程序运行中不用或暂不用的程序(数据)占据了大量的内存空间运行中不用或暂不用的程序(数据)占据了大量的内存空间，使得一些需要运行的作业无法装入运行。现在要研究的问题是次性及驻留性在程序运行时是否是必需的是：一次性及驻留性在程序运行时是否是必需的。2局部性原理早在1968年，Denning.P就曾指出：程序在执行时将呈现出局部性规律，即在一较短的时间内，程序的执行仅局限于某个部分；相应地它所访问的存储空间也某个区域他提出了述个应地，它所访问的存储空间也局限于某个区域。他提出了下述几个论点：(1)程序执行时，除了少部分的转移和过程调用指令外，在大多数情况下仍是顺序执行的。(2)过程调用将会使程序的执行轨迹由一部分区域转至另一部分区域，但经研究看出，过程调用的深度在大多数情况下都不超过5。分区域，但经研究看出，过程调用的深度在大多数情况下都不超过这就是说，程序将会在一段时间内都局限在这些过程的范围内运行。(3)程序中存在许多循环结构这些虽然只由少数指令构成(3)程序中存在许多循环结构，这些虽然只由少数指令构成，但是它们将多次执行。序中包括许多数结构的如数操作(4)程序中还包括许多对数据结构的处理，如对数组进行操作，它们往往都局限于很小的范围内。局限性还表现在下述两个方面：(1)时间局限性如果程序中的某条指令旦执行则(1)时间局限性。如果程序中的某条指令一旦执行，则不久以后该指令可能再次执行；如果某数据被访问过，则不久以后该数据可能再次被访问产生时间局限性的典型原因久以后该数据可能再次被访问。产生时间局限性的典型原因是由于在程序中存在着大量的循环操作。(2)空间局限性。一旦程序访问了某个存储单元，在不久之后，其附近的存储单元也将被访问，即程序在一段时间内之后，其附近的存储单元也将被访问，即程序在段时间内所访问的地址，可能集中在一定的范围之内，其典型情况便是程序的顺序执行。是程序的顺序执行。3虚拟存储器的基本工作情况3虚拟存储器的基本工作情况基于局部性原理，应用程序在运行之前，没有必要全部装入内存，仅须将那些当前要运行的少数页面或段先装入内存便可运行，其余部分暂留在盘上。程序在运行时，如果它存便可运行，其余部分暂留在盘上。程序在运行时，如果它所要访问的页(段)已调入内存，便可继续执行下去；但如果程序所要访问的页(段)尚未调入内存(称为缺页或缺段)此时程序所要访问的页(段)尚未调入内存(称为缺页或缺段)，此时程序应利用OS所提供的请求调页(段)功能，将它们调入内存，以使进程能继续执行去如果此时内存满无法再装入以使进程能继续执行下去。如果此时内存已满，无法再装入新的页(段)，则还须再利用页(段)的置换功能，将内存中暂时不用的页(段)调至盘上，腾出足够的内存空间后，再将要访问的页(段)调入内存，使程序继续执行下去。()5.1.2虚拟存储器的定义和特征虚拟存储器是指具有请求调入和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统。逻辑上对内存容量加以扩充的种存储器系统。其逻辑容量由内存容量和外存容量之和决定，运行速度接近与内存速度而每位的成本则接近于外存行速度接近与内存速度，而每位的成本则接近于外存。2）虚拟存储器的特征多次性指个作业被分成多次调入内存运行亦即在作业运行时1多次性：指一个作业被分成多次调入内存运行，亦即在作业运行时没有必要将其全部装入，只需将当前要运行的那部分程序和数据装入内存即可；以后每当要运行到尚未调入的那部分程序时再将它调入可；以后每当要运行到尚未调入的那部分程序时，再将它调入。2对换性：指允许在作业的运行过程中进行换进、换出，亦即，在进程运行期间允许将那些暂不使用的程序和数据从内存调至外存的对换区程运行期间，允许将那些暂不使用的程序和数据，从内存调至外存的对换区(换出)，待以后需要时再将它们从外存调至内存(换进)；甚至还允许将暂时不运行的进程调至外存待它们重又具备运行条件时再调入内存换进和换出运行的进程调至外存，待它们重又具备运行条件时再调入内存。换进和换出能有效地提高内存利用率。3虚拟性虚拟性是指能够从逻辑上扩充内存容量使用户所看到的3虚拟性：虚拟性是指能够从逻辑上扩充内存容量，使用户所看到的内存容量远大于实际内存容量。虚拟性是以多次性和对换性为基础的，或者说，仅当系统允许将作业分多次调入内存，并能将内存中暂时不运行的程序和数据换至盘上时，才有可能实现虚拟存储器而多次性和对换性又必须建立在离散分配的基础上能实现虚拟存储器；而多次性和对换性又必须建立在离散分配的基础上。5.1.3虚拟存储器的实现方法1分页请求系统1分页请求系统这是在分页系统的基础上，增加了请求调页功能和页面置换功能所形成的页式虚拟存储系统。它允许只装入少数页面的程序(及数据)，便启动运行。以后，再通过调页功能及页面置换功能，陆续地把即将要运行的页面调入内存，同时把暂不运行的页面换出到外存上。置换时以页面为单位。为了能实现请求调页和置换功能，系统必须提供必要的硬件支持和相应的软件。1)硬件支持 请求分页的页表机制，它是在纯分页的页表机制上增加若干项而形成的，作为请求分页的数据结构；若干项而形成的，作为请求分页的数据结构；缺页中断机构，即每当用户程序要访问的页面尚未调入内存时便产生缺页中断以请求OS将所缺的页调入内存内存时，便产生一缺页中断，以请求OS将所缺的页调入内存；地址变换机构，它同样是在纯分页地址变换机构的基础变换机构同样在分页变换机构的上发展形成的。2)实现请求分页的软件2)实现请求分页的软件这里包括有用于实现请求调页的软件和实现页面置换的软这里包括有用于实现请求调页的软件和实现页面置换的软件。它们在硬件的支持下，将程序正在运行时所需的页面(尚未在内存中的)调入内存再将内存中暂时不用的页面从内存置换在内存中的)调入内存，再将内存中暂时不用的页面从内存置换到磁盘上。2请求分段系统这是在分段系统的基础上，增加了请求调段及分段置换功能后所形成的段式虚拟存储系统。它允许只装入少数段(而非所有的段)的用形成的段式虚拟存储系统允许只装入少数段(而非所有的段)的用户程序和数据，即可启动运行。以后再通过调段功能和段的置换功能将暂不运行的段调出，同时调入即将运行的段。置换是以段为单位进将暂不运行的段调出，同时调入即将运行的段置换是以段为单位进行的。为了实现请求分段系统同样需要必要的硬件支持般需要下为了实现请求分段，系统同样需要必要的硬件支持。一般需要下列支持：(1)请求分段的段表机制。这是在纯分段的段表机制基础上增加若干项而形成的。(2)缺段中断机构。每当用户程序所要访问的段尚未调入内存时，产生一个缺段中断，请求OS将所缺的段调入内存。(3)地址变换机构。5.2请求分页存储管理方式5 2 1请求分页中的硬件支持5.2.1请求分页中的硬件支持1请求页表机制在请求分页系统中所需要的主要数据结构是页表。其基本作用仍然是将用户地址空间中的逻辑地址变换为内存空间本作用仍然是将用户地址空间中的逻辑地址变换为内存空间中的物理地址。由于只将应用程序的一部分调入内存，还有部分仍在盘上故须在页表中再增加若干项供程序(数据)一部分仍在盘上，故须在页表中再增加若干项，供程序(数据)在换进、换出时参考。在请求分页系统中的每个页表项如下所示所示：页号物理块号状态位P访问字段A修改位M外存地址 页号物理块号状态位访问字段修改位外存地址 各字段说明如下：(1)状态位P：用于指示该页是否已调入内存，供程序访问时参考。考(2)访问字段A：用于记录本页在一段时间内被访问的次数，或记录本页最近已有多长时间未被访问供选择换出页面时参考记录本页最近已有多长时间未被访问，供选择换出页面时参考。(3)修改位M：表示该页在调入内存后是否被修改过。由于内存中的每一页都在外存上保留一份副本，因此，若未被修改，在置换该页时就不需再将该页写回到外存上，以减少系统的开销和启动磁盘的次数；若已被修改，则必须将该页重写到外存上，以保证外存中所保留的始终是最新副本。简言之，M位供置换页面时参考。(4)外存地址：用于指出该页在外存上的地址，通常是物理块号，供调入该页时参考供调入该页时参考。2缺页中断机构在请求分页系统中，每当所要访问的页面不在内存时，便产生一缺页中断，请求OS将所缺之页调入内存。缺页中断作为中断，它们同样需要经历诸如保护CPU环境分析中断原因转入缺页中断处理程序样需要经历诸如保护CPU环境、分析中断原因、转入缺页中断处理程序进行处理、恢复CPU环境等几个步骤。但缺页中断又是一种特殊的中断，它与一般的中断相比，有着明显的区别，主要表现在下面两个方面：它与般的中断相比，有着明显的区别，主要表现在下面两个方面：(1)在指令执行期间产生和处理中断信号。通常，CPU都是在一条指令执行完后才检查是否有中断请求到达若有便去响应否则指令执行完后，才检查是否有中断请求到达。若有，便去响应，否则，继续执行下一条指令。然而，缺页中断是在指令执行期间，发现所要访问的指令或数据不在内存时所产生和处理的。访问的指令数据不在内存时所产和的(2)一条指令在执行期间，可能产生多次缺页中断。在图4-24中示出了一个例子。如在执行一条指令COPY A TO B时，可能要产生6次缺页出了个例子。如在执行条指令COPY A TO B时，可能要产生6次缺页中断，其中指令本身跨了两个页面，A和B又分别各是一个数据块，也都跨了两个页面。基于这些特征，系统中的硬件机构应能保存多次中断时的状态，并保证最后能返回到中断前产生缺页中断的指令处继续执行。页面B6B：5A：43指令21指令COPY ATO B图5 1 涉及6次缺页中断的指令1图5-1 涉及6次缺页中断的指令3地址变换机构程序请求访问页缺页中断处理保留CPU现场页号页表长度?开始程序请求访问一页越界中断是从外存中找到缺页内存满否？否CPU检索快表否是选择一页换出是否页表项在快表中？访问页表否是该页被修改否？将该页写回外存是否页在内存？产生缺页中断请求调页修改快表是OS命令CPU从外存读缺页启动I/O硬件修改访问位和修改位启动I/O硬件将一页从外存换入内存形成物理地址地址变换结束修改页表地址变换结束图5-2示出了请求分页系统中的地址变换过程。在进行地址变换时，首先去检索快表，试图从中找出所要访问的页。若找到，便修改页表项中的访问位。对于写指令，还须将修改位找到，便修改页表项中的访问位对于写指令，还须将修改位置成“1”，然后利用页表项中给出的物理块号和页内地址形成物理地址地址变换过程到此结束物理地址。地址变换过程到此结束。如果在快表中未找到该页的页表项时，应到内存中去查找页表，再从找到的页表项中的状态位P，来了解该页是否已调入内存。若该页已调入内存，这时应将此页的页表项写入快表，入内存若该页调入内存这时应将此页的页表项写入快表当快表已满时，应先调出按某种算法所确定的页的页表项，然后再写入该页的页表项；若该页尚未调入内存这时应产生缺后再写入该页的页表项；若该页尚未调入内存，这时应产生缺页中断，请求OS从外存把该页调入内存。5.2.2请求分页的内存分配1最小物理块数的确定这里所说的最小物理块数，是指能保证进程正常运行所需的最小物理块数。这里所说的最小物理块数，是指能保证进程正常运行所需的最小物理块数。当系统为进程分配的物理块数少于此值时，进程将无法运行。进程应获得的最少物理块数与计算机的硬件结构有关，取决于指令的格式、功能和寻址方式。对于某些简单的机器，若是单地址指令且采用直接寻址方式，则所需的最少物理块数为2。其中，一块是用于存放指令的页面，另一块则是用于存放数少物理块数为2。其中，块是用于存放指令的页面，另块则是用于存放数据的页面。如果该机器允许间接寻址时则至少要求有三个物理块对于某些功能如果该机器允许间接寻址时，则至少要求有三个物理块。对于某些功能较强的机器，其指令长度可能是两个或多于两个字节，因而其指令本身有可能跨两个页面，且源地址和目标地址所涉及的区域也都可能跨两个页面正如前跨两个页面，且源地址和目标地址所涉及的区域也都可能跨两个页面。正如前面所介绍的在缺页中断机构中要发生6次中断的情况一样，对于这种机器，至少要为每个进程分配6个物理块，以装入6个页面。少要为每个进程分配 个物理块，以装入 个页面2物理块的分配策略1)固 定 分 配 局 部 置 换(Fixed Allocation，LocalReplacement)这是指基于进程的类型(交互型或批处理型等)，或根据程序员、程序管理员的建议，为每个进程分配一定数目的物理块，序员、程序管理员的建议，为每个进程分配定数目的物理块，在整个运行期间都不再改变。采用该策略时，如果进程在运行中发现缺页，则只能从该进程在内存的n个页面中选出一个页换出，然后再调入一页，以保证分配给该进程的内存空间不变。实现这种策略的困难在于：应为每个进程分配多少个物理实现这种策略的困难在于：应为每个进程分配多少个物理块难以确定。若太少，会频繁地出现缺页中断，降低了系统的吞吐量；若太多，又必然使内存中驻留的进程数目减少，进而吞吐量；若太多，又必然使内存中驻留的进程数目减少，进而可能造成CPU空闲或其它资源空闲的情况，而且在实现进程对换时，会花费更多的时间。换会费2)可变分配全局置换(Variable Allocation，Global Replacement)这可能是最易于实现的一种物理块分配和置换策略，已用于若干个OS中。在采用这种策略时，先为系统中的每个进程分配一定数目的物理块，而OS自身也保持个空闲物理块队列当某进程发现缺页时由系统从空闲物理块身也保持一个空闲物理块队列。当某进程发现缺页时，由系统从空闲物理块队列中取出一个物理块分配给该进程，并将欲调入的(缺)页装入其中。这样，凡产生缺页(中断)的进程，都将获得新的物理块。仅当空闲物理块队列中的凡产生缺页(中断)的进程，都将获得新的物理块。仅当空闲物理块队列中的物理块用完时，OS才能从内存中选择一页调出，该页可能是系统中任一进程的页，这样，自然又会使那个进程的物理块减少，进而使其缺页率增加。3)可变分配局部置换(Variable Allocation，Local Replacement)这同样是基于进程的类型或根据程序员的要求为每个进程分配一定数这同样是基于进程的类型或根据程序员的要求，为每个进程分配定数目的物理块，但当某进程发现缺页时，只允许从该进程在内存的页面中选出一页换出，这样就不会影响其它进程的运行。如果进程在运行中频繁地发生缺页中断，则系统须再为该进程分配若干附加的物理块，直至该进程的缺页率减少到适当程度为止；反之，若一个进程在运行过程中的缺页率特别低，则此时可适当减少分配给该进程的物理块数但不应引起其缺页率的明显增则此时可适当减少分配给该进程的物理块数，但不应引起其缺页率的明显增加。3物理块分配算法1)平均分配算法：将系统中所有可供分配的物理块平均分配给各个进程。例如，当系统中有100个物理块，有5个进程在运行时，每个进程可分得20个物理块。这种方式貌似公平，但实际上是不公平的，因为它未考虑到各进程本身的大小。2)按比例分配算法：根据进程大小按比例分配物理块的算法。3)考虑优先权的分配算法：在实际应用中，为了照顾到重要的、紧迫的作业能尽快地完成，应为它分配较多的内存空间。通的、紧迫的作业能尽快地完成，应为它分配较多的内存空间。通常采取的方法是把内存中可供分配的所有物理块分成两部分：一部分按比例地分配给各进程另一部分则根据各进程的优先权部分按比例地分配给各进程；另一部分则根据各进程的优先权，适当地增加其相应份额后，分配给各进程。在有的系统中，如重要的实时控制系统则可能是完全按优先权来为各进程分配其物要的实时控制系统，则可能是完全按优先权来为各进程分配其物理块的。5.2.3调页策略调入的时机（）1调入页面的时机（When）1)预调页策略如果进程的许多页是存放在外存的一个连续区域中，则一次调入若干个相邻的页，会比一次调入一页更高效些。但如果调入的一批页面中的大多数都未被访问，则又是低效的。可采用一种以预测为基础的预调页策略，将那些预计在不久之后便会被访问的页面预先调入内存。如果预测较准确，那么，这种策略显然是很有吸引力的但遗憾的是目前预调页的成功率仅约50%这种策略显然是很有吸引力的。但遗憾的是，目前预调页的成功率仅约50%。故这种策略主要用于进程的首次调入时，由程序员指出应该先调入哪些页。2)请求调页策略2)请求调页策略当进程在运行中需要访问某部分程序和数据时，若发现其所在的页面不在内存，便立即提出请求，由OS将其所需页面调入内存。由请求调页策略所确定调入的页，是一定会被访问的，再加之请求调页策略比较易于实现，故在目前的虚拟存储器中大多采用此策略但这种策略每次仅调入页故须在目前的虚拟存储器中大多采用此策略。但这种策略每次仅调入一页，故须花费较大的系统开销，增加了磁盘I/O的启动频率。2确定从何处调入页面（Where）在请求分页系统中的外存分为两部分：用于存放文件的文件区和用于存放对换页面的对换区。通常，由于对换区是采用连续分配方式，而文件区是采用离散分配方式故对换区的磁盘I/O速度比文件区的高这样每当发生缺页请离散分配方式，故对换区的磁盘I/O速度比文件区的高。这样，每当发生缺页请求时，系统应从何处将缺页调入内存，可分成如下三种情况：系统拥有足够的对换区空间可以全部从对换区调入所需页面以提高(1)系统拥有足够的对换区空间，可以全部从对换区调入所需页面，以提高调页速度。在进程运行前，须将与该进程有关的文件从文件区拷贝到对换区。()系统缺少足够的对换区空间这时是不会被修改的文件都直接从文(2)系统缺少足够的对换区空间，这时凡是不会被修改的文件都直接从文件区调入；而当换出这些页面时，由于它们未被修改而不必再将它们换出，以后再调入时仍从文件区直接调入但对于那些可能被修改的部分在将它们后再调入时，仍从文件区直接调入。但对于那些可能被修改的部分，在将它们换出时，便须调到对换区，以后需要时，再从对换区调入。(3)UNIX方式由于与进程有关的文件都放在文件区故凡是未运行过的(3)UNIX方式。由于与进程有关的文件都放在文件区，故凡是未运行过的页面，都应从文件区调入。而对于曾经运行过但又被换出的页面，由于是被放在对换区，因此在下次调入时，应从对换区调入。由于UNIX系统允许页面共享，因此，某进程所请求的页面有可能已被其它进程调入内存，此时也就无须再从对换区调入。3页面调入过程（How）每当程序所要访问的页面未在内存时，便向CPU发出一缺页中断，中断处理程序首先保留CPU环境，分析中断原因后转入缺中断中断处程序首先保留环境分析中断原因后转缺页中断处理程序。该程序通过查找页表得到该页在外存的物理块后如果此该程序通过查找页表，得到该页在外存的物理块后，如果此时内存能容纳新页，则启动磁盘I/O将所缺之页调入内存，然后修改页表。如果内存已满，则须先按照某种置换算法从内存中选修改页表。如果内存已满，则须先按照某种置换算法从内存中选出一页准备换出；如果该页未被修改过，可不必将该页写回磁盘；但如果此页已被修改，则必须将它写回磁盘，然后再把所缺的页但如果此页已被修改，则必须将它写回磁盘，然后再把所缺的页调入内存，并修改页表中的相应表项，置其存在位为“1”，并将此页表项写入快表中。在缺页调入内存后，利用修改后的页表，去形成所要访问数据的物理地址，再去访问内存数据。整个页面的调入过程对用户是透明的整个页面的调入过程对用户是透明的。5.3页面置换算法5.3.1最佳置换算法和先进先出置换算法1最佳(Optimal)置换算法最佳(p)换算最佳置换算法是由Belady于1966年提出的一种理论上的算法。其所选择的被淘汰页面，将是以后永不使用的，或许是在最长(未来)时间内不再被访问被淘汰页面，将是以后永不使用的，或许是在最长(未来)时间内不再被访问的页面。该算法是无法实现的，但可以利用该算法去评价其它算法。假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串：假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1进程运行时先将701三个页面装入内存以后当进程要访问页面进程运行时，先将7，0，1三个页面装入内存。以后，当进程要访问页面2时，将会产生缺页中断。此时OS根据最佳置换算法，将选择页面7予以淘汰。这是因为页面0将作为第5个被访问的页面，页面1是第14个被访问的页面，而页面7则要在第18次页面访问时才需调入。下次访问页面0时，因它已在内存而不必产生缺页中断。当进程访问页面3时，又将引起页面1被淘汰；因为，它在现有的120三个页面中将是以后最晚才被访问的它在现有的1，2，0三个页面中，将是以后最晚才被访问的。引用率7012030423032120170177070202024207024113311页框(物理块）3图3利用最佳页面置换算法时的置换图页框(物块图 5-3利用最佳页面置换算法时的置换图2先进先出(FIFO)页面置换算法该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。该算法实现简单，只需把一个进留时间最久的页面予以淘汰。该算法实现简单，只需把个进程已调入内存的页面，按先后次序链接成一个队列，并设置一个指针，称为替换指针，使它总是指向最老的页面。但该算法个指针，称为替换指针，使它总是指向最老的页面。但该算法与进程实际运行的规律不相适应，因为在进程中，有些页面经常被访问，比如，含有全局变量、常用函数、例程等的页面，常被访问，比如，含有全局变量、常用函数、例程等的页面，FIFO算法并不能保证这些页面不被淘汰。就上例而言，当进程第一次访问页面2时，将把第7页换出，因为它是最先被调入内存的；在第一次访问页面3时，又将把第0页换出，因为它在现有的2，0，1 三个页面中是最老的页。由图5-4 可以看出，利用FIFO算法时进行了12次页面置换，比最佳置换算法正好多一倍（6次）。引用率70771722032044230321020177012440077770701201231430013702230420423023012712701111032页框0033221图 5-4利用FIFO置换算法时的置换图5.3.2最近最久未使用(LRU)置换算法1LRU(Least Recently Used)置换算法的描述FIFO置换算法性能之所以较差，是因为它所依据的条件是各个页面调入内存的时间，而页面调入的先后并不能反映页面的使用情况。最近最久未使用(LRU)的页面置换算法，是根据页面调入内存后的使用情况进行决策的。由于无法预测各页面将来的使用情况，只能利用“最近的过去”作为“最近的将来”的近似，因此，LRU置换算法是选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间t，当须淘汰一个页面时，选择现有页面中其t值最大的，即最近最久未使用的页面予以淘汰。利用LRU算法对上例进行页面置换的结果如图5 5 所示利用LRU算法对上例进行页面置换的结果如图5-5 所示。引用率7012030423032120170177070202040137040430310113321页框2222图5-5LRU页面置换算法自学内容：LRU置换算法的硬件支持、LFU置换算法5 3 3 Clk置换算法5.3.3 Clock置换算法5.3.4 页面缓冲算法5.3.5 访问内存的有效时间5.4“抖动”与工作集一大拨作业来袭：大拨作业来袭：）假定某计算机系统配置的主存储器容量为当采用页式1）假定某计算机系统配置的主存储器容量为1M。当采用页式虚拟存储管理时提供给用户使用的逻辑地址空间为4M，主存储器被分为长度为4K的等长块，请回答下列问题：器被分为长度为4K的等长块，请回答下列问题：（1）主存储器一共被划分为多少块？（2）用户作业最多可以有多少页？（3）画出该系统的地址结构示意图（3）画出该系统的地址结构示意图。2）某采用页式存储管理的系统接收了一个共7页的作业，作业执行时一次访问的页为：1，2，3，4，2，1，5，6，2，1，2，3，7。若把开始4页先装入主存，当分别用FIFO和LRU调度算法时，作业执行过程中会产生多少次缺页中断？写出依次产生缺页中作业执行过程中会产生多少次缺页中断？写出依次产生缺页中断后应淘汰的页。3）在一个采用也是虚拟存储器管理的系统中，有一用户作业依次要访问的字地址序列是：115，228，120，88，446，102，依次访字序列321，432，260，167。若该作业的第0页已经装入主存，现分配给该作业的主存共300字，页的大小为100字，则当页面调度算法采用和时将产生多少次缺页中断？缺页中断率为多法采用FIFO和LRU时将产生多少次缺页中断？缺页中断率为多少？4）请针对如下的页面引用串，当分配的页面块从3个增加到4个时，使用FIFO算法引起的缺页次数分别是多少？从结算结果你可以得出什么结论？1，2，3，4，1，2，5，1，2，3，4，55）在某请求页式存储管理系统中地址线为16位页大小为5）在某请求页式存储管理系统中，地址线为16位，页大小为1K，则作业的页表如下图所示：（1）指出页表中状态位、访问位、修改位、辅存地址的含义？（1）指出页表中状态位、访问位、修改位、辅存地址的含义（2）逻辑地址0A10该指令中的逻辑地址对应的内存物理地址是多少？（3）当指令中需要寻址C1C，按照LRU算法会发生什么现象？6）假如计算机系统采用页式虚存管理进程的驻留集为46）假如一计算机系统采用页式虚存管理，一进程的驻留集为4个页帧且已分配到4个页帧，如下表所示：当进程访问第4页时，产生页故障（缺页）中断，分别用FIFO，LRU决定页故障中断处理程序的处理过程。5.5请求分段存储管理方式5.5.1请求分段中的硬件支持1段表机制1段表机制在请求分段式管理中所需的主要数据结构是段表。由于在应用程序的许多段中，只有一部分段装入内存，其余的一些段仍留在外存上，故须在段表中增加若干项，以供程序在些段仍留在外存上，故须在段表中增加若干项，以供程序在调进、调出时参考。段名 段长 段的 基址 存取 方式 访问 字段A修改 位M 存在 位P 增补位外存 始址 在段表项中，除了段名(号)、段长、段在内存中的起始地址外，还增加了以下诸项还增加了以下诸项。(1)存取方式：用于标识本分段的存取属性是只执行、只读，还是允许读/写。(2)访问字段A：其含义与请求分页的相应字段相同，用于记录(2)访问字段A：其含义与请求分页的相应字段相同，用于记录该段被访问的频繁程度。(3)修改位M用于表示该页在进入内存后是否已被修改过供(3)修改位M：用于表示该页在进入内存后是否已被修改过，供置换页面时参考。(4)存在位P：指示本段是否已调入内存，供程序访问时参考。(5)增补位：这是请求分段式管理中所特有的字段，用于表示本(5)增补位：这是请求分段式管理中所特有的字段，用于表示本段在运行过程中是否做过动态增长。存始址指本在存中的起始地址起始盘块(6)外存始址：指示本段在外存中的起始地址，即起始盘块号。2缺段中断机构在请求分段系统中每当发现运行进程所要访问的段尚在请求分段系统中，每当发现运行进程所要访问的段尚未调入内存时，便由缺段中断机构产生一缺段中断信号，进入后由缺段中断处理程序将所需的段调入内存缺段中断入OS后由缺段中断处理程序将所需的段调入内存。缺段中断机构与缺页中断机构类似，它同样需要在一条指令的执行期间产生和处中断以在条指令执行期间能产生间，产生和处理中断，以及在一条指令执行期间，可能产生多次缺段中断。但由于分段是信息的逻辑单位，因而不可能出现一条指令被分割在两个分段中和一组信息被分割在两个分段中的情况。缺段中断的处理过程如图5-12所示。由于段不是定长的，这使对缺段中断的处理要比对缺页中断的处理复杂。虚段S不在内存阻塞请求进程内存中有合适的空闲区吗？否从外存读入段S空区容量总和能否满足？否是从外存读入段S修改段表及内存空区链空区拼接以形成淘汰一个或几个实段是唤醒请求进程空区拼接，以形成一个合适的空区淘汰个或几个实段，以形成一个合适空区返回图5-12请求分段系统中的中断处理过程3地址变换机构请求分段系统中的地址变换机构是在分段系统地址变请求分段系统中的地址变换机构是在分段系统地址变换机构的基础上形成的。因为被访问的段并非全在内存，所以在地址变换时，若发现所要访问的段不在内存，必须先将所缺的段调入内存，并修改段表，然后才能再利用段表进行地址变换。为此，在地址变换机构中又增加了某些功能，如缺段中断的请求及处理等。功能，如缺段中断的请求及处理等访问sww段长?分段越界中断处理是否符合存取方式?分段保护中断处理是否段S在主存?缺段中断处理是否修改访问字段 如写断处理是修改访问字段,如写访问,置修改位1形成访问主存地址(A)(主存始址)(位移量w)图5-13请求分段系统的地址变换过程返回5.5.2分段的共享与保护1共享段表为了实现分段共享，可在系统中配置一张共享段表，所有各共享段都在共享段表中占有一表项。表项中记录了共享段的段号、段长、内存始址、存在位等信息，并记录了共享此分段的每个进程的情况。(1)共享进程计数count。非共享段仅为一个进程所需要。当进程不再需要该段时，可立即释放该段，并由系统回收该段所占用的空间。而共享段是为多个进程所需要的，当某进程不再需要而释放它时，系统并不回收该段所占内存区，仅当所有共享该段的进程全都不再需要它时，才由系统回收该段所占内存区为了记录有多少个进程需要共享该分段特设置了个整型变量占内存区。为了记录有多少个进程需要共享该分段，特设置了一个整型变量count。存取控制字段对于个共享段应给不同的进程以不同的存取权限(2)存取控制字段。对于一个共享段，应给不同的进程以不同的存取权限。例如，对于文件主，通常允许他读和写；而对其它进程，则可能只允许读，甚至只允许执行。甚至只允许执行。(3)段号。对于一个共享段，不同的进程可以各用不同的段号去共享该段。段名段长内存始址状态外存始址段名段长内存始址状态外存始址共享进程计数count状态进程名进程号段号存取控制状态进程名进程号段号存取控制共享段表图3共享段表项共享段表图5-13共享段表项2共享段的分配与回收)共享段的分配1)共享段的分配在为共享段分配内存时，对第一个请求使用该共享段的进程，由系统为该共享段分配一物理区再把共享段调入该区同时将该区的始址填入请求该共享段分配一物理区，再把共享段调入该区，同时将该区的始址填入请求进程的段表的相应项中，还须在共享段表中增加一表项，填写有关数据，把count置为1；之后，当又有其它进程需要调用该共享段时，由于该共享段已被调入内存，故此时无须再为该段分配内存，而只需在调用进程的段表中增加一表项，填写该共享段的物理地址；在共享段的段表中，填上调用进程的进程名存取控制等再执行count:=count+1操作以表明有两个进程共享该段程名、存取控制等，再执行count:=count+1操作，以表明有两个进程共享该段。2)共享段的回收当共享此段的某进程不再需要该段时，应将该段释放，包括撤消在该进程段表中共享段所对应的表项，以及执行count:=count-1操作。若结果为0，则须由系统回收该共享段的物理内存以及取消在共享段表中该段所对应的表须由系统回收该共享段的物理内存，以及取消在共享段表中该段所对应的表项，表明此时已没有进程使用该段；否则(减1结果不为0)，只是取消调用者进程在共享段表中的有关记录。程在共享段表中的有关记录。3分段保护在系中每个在辑较容实息保在分段系统中，由于每个分段在逻辑上是独立的，因而比较容易实现信息保护。目前，常采用以下几种措施来确保信息的安全。1)越界检查1)越界检查在段表寄存器中放有段表长度信息；同样，在段表中也为每个段设置有段长字段。在进行存储访问时首先将逻辑地址空间的段号与段表长度进行比较如果段号等于在进行存储访问时，首先将逻辑地址空间的段号与段表长度进行比较，如果段号等于或大于段表长度，将发出地址越界中断信号；其次，还要检查段内地址是否等于或大于段长，若大于段长，将产生地址越界中断信号，从而保证了每个进程只能在自己的地址空间内运行。2)存取控制检查在段表的每个表项中，都设置了一个“存取控制”字段，用于规定对该段的访问方式。通常的访问方式有：(1)只读，即只允许进程对该段中的程序或数据进行读访问。(2)只执行，即只允许进程调用该段去执行，但不准读该段的内容，也不允许对该段执行写操作该段执行写操作。(3)读/写，即允许进程对该段进行读/写访问。3)环保护机构这是种功能较完善的保护机制在该机制中规定低编号的环具有高优先这是一种功能较完善的保护机制。在该机制中规定：低编号的环具有高优先权。OS核心处于0环内；某些重要的实用程序和操作系统服务占居中间环；而一般的应用程序则被安排在外环上。在环系统中，程序的访问和调用应遵循以下规则：(1)一个程序可以访问驻留在相同环或较低特权环中的数据。(2)一个程序可以调用驻留在相同环或较高特权环中的服务。()个程序可以调用驻留在相同环或较高特权环中的服务调用返回环0环1环0环1调用返回环2数据访问环2数据访问(a)程序间的控制传输(b)数据访问