操作系统_虚拟内存_CCH10

Silberschatz,Galvin,andGagne199910.1AppliedOperatingSystemConceptsModule10:VirtualMemory•Background（背景）•DemandPaging（请求页式）•PerformanceofDemandPaging（请求页式的性能）•PageReplacement（页置换）•Page-ReplacementAlgorithms（页置换算法）•AllocationofFrames（页框的分配）•Thrashing（颠簸）•OtherConsiderations（其他考虑）•DemandSegmenation（请求段式）Silberschatz,Galvin,andGagne199910.2AppliedOperatingSystemConceptsBackground•Virtualmemory–separationofuserlogicalmemoryfromphysicalmemory.（虚拟内存—物理内存和用户逻辑内存的区分）–局部性原理(principleoflocality)时间局部性，空间局部性–Onlypartoftheprogramneedstobeinmemoryforexecution（只有部分运行的程序需要在内存中）.–Logicaladdressspacecanthereforebemuchlargerthanphysicaladdressspace（因此，逻辑地址空间能够比物理地址空间大）.–Needtoallowpagestobeswappedinandout（必须允许页面能够被换入和换出）.•Virtualmemorycanbeimplementedvia（虚拟内存能够通过以下手段来执行）:–Demandpaging（请求页式）–Demandsegmentation（请求段式）Silberschatz,Galvin,andGagne199910.3AppliedOperatingSystemConcepts（1）虚拟存储器的基本概念1.虚拟存储器的引入1)局部性原理在一段时间内，程序的执行仅局限于某个部分；相应地，它所访问的存储空间也局限于某个区域内。那么程序为什么会出现局部性规律呢？原因可以归结为以下几点：•程序在执行时，除了少部分的转移和过程调用指令外，大多数仍是顺序执行的。•子程序调用将会使程序的执行由一部分内存区域转至另一部分区域。但在大多数情况下，过程调用的深度都不超过5。•程序中存在许多循环结构，循环体中的指令被多次执行。•程序中还包括许多对数据结构的处理，如对连续的存储空间——数组的访问，往往局限于很小的范围内。Silberschatz,Galvin,andGagne199910.4AppliedOperatingSystemConcepts局限性表现为：•时间局限性：如果程序中的某条指令一旦执行，则不久的将来该指令可能再次被执行；如果某个存储单元被访问，则不久以后该存储单元可能再次被访问。产生时间局限性的典型原因是在程序中存在着大量的循环操作。•空间局限性：一旦程序访问了某个存储单元，则在不久的将来，其附近的存储单元也最有可能被访问。即程序在一段时间内所访问的地址，可能集中在一定的范围内，其典型原因是程序是顺序执行的。Silberschatz,Galvin,andGagne199910.5AppliedOperatingSystemConceptsBackground虚拟存储的基本原理根据局部性原理，一个作业在运行之前，没有必要把全部作业装入内存，而仅将那些当前要运行的那部分页面或段，先装入内存便可启动运行，其余部分暂时留在磁盘上•程序在运行时如果它所要访问的页（段）已调入内存，便可继续执行下去；但如果程序所要访问的页（段）尚未调入内存（称为缺页或缺段），此时程序应利用OS所提供的请求调页（段）功能，将它们调入内存，以使进程能继续执行下去。•如果内存已满，无法再装入新的页（段），则还须再利用页（段）的置换功能，将内存中暂时不用的页（段）调出至磁盘上，腾出足够的内存空间后，再将所要访问的页（段）调入内存，使程序继续执行下去。这样，便可使一个大的用户程序在较小的内存空间中运行；也可使内存中同时装入更多的进程并发执行。从用户角度看，该系统所具有的内存容量，将比实际内存容量大得多，人们把这样的存储器称为虚拟存储器。Silberschatz,Galvin,andGagne199910.6AppliedOperatingSystemConceptsBackground引入虚拟存储技术的好处可在较小的可用内存中执行较大的用户程序可在内存中容纳更多程序并发执行不必影响编程时的程序结构（与覆盖技术比较）提供给用户可用的虚拟内存空间通常大于物理内存(realmemory)Silberschatz,Galvin,andGagne199910.7AppliedOperatingSystemConceptsBackground虚拟存储技术的特征离散性：指在内存分配时采用离散的分配方式，它是虚拟存储器的最基本的特征。多次性：指一个作业被分成多次调入内存运行，即在作业运行时没有必要将其全部装入，只须将当前要运行的那部分程序和数据装入内存即可。多次性是虚拟存储器最重要的特征。对换性：指允许在作业的运行过程中在内存和外存的对换区之间换进、换出。虚拟性：指能够从逻辑上扩充内存容量，使用户所看到的内存容量远大于实际内存容量。Silberschatz,Galvin,andGagne199910.8AppliedOperatingSystemConceptsBackgroundpage0...PagenVirtualmemoryMemorymapPhysicalmemorySilberschatz,Galvin,andGagne199910.9AppliedOperatingSystemConcepts虚拟存储器实现方式1)请求分页系统：在分页系统的基础上，增加了请求调页功能和页面置换功能所形成的页式虚拟存储系统。它允许只装入若干页（而非全部程序）的用户程序和数据，就可以启动运行，以后再通过调页功能和页面置换功能，陆续把将要运行的页面调入内存，同时把暂不运行的页面置换到外存上，置换时以页面为单位。2)请求分段系统：在分段系统的基础上，增加了请求调段和分段置换功能所形成的段式虚拟存储系统。它允许只装入若干段（而非全部段）的用户程序和数据，就可以启动运行，以后再通过调段功能和置换功能将不运行的段调出，同时调入将要运行的段，置换以段为单位。3)请求段页式系统：它是在段页式系统的基础上，增加了请求调页和页面置换功能所形成的段页式虚拟存储系统。Silberschatz,Galvin,andGagne199910.10AppliedOperatingSystemConceptsDemandPaging•Bringapageintomemoryonlywhenitisneeded（只有在一个页需要的时候才把它换入内存）.–LessI/Oneeded（需要很少的I/O）–Lessmemoryneeded（需要很少的内存）–Fasterresponse（快速响应）–Moreusers（多用户）•Pageisneeded（需要页）referencetoit（查阅此页）–invalidreference（无效的访问）abort（中止）–not-in-memory（不在内存）bringtomemory（换入内存）取页--将哪部分装入内存置页--将调入的页放在什么地方淘汰--内存不足时，将哪些页换出内存。Silberschatz,Galvin,andGagne199910.11AppliedOperatingSystemConcepts请求分页存储管理方式1.请求分页中的硬件支持它是在纯分页系统的基础上，增加了请求调页功能、页面置换功能所形成的页式虚拟存储系统，它是目前常用的一种虚拟存储器的方式。1)请求分页的页表机制它是在纯分页的页表机制上形成的，由于只将应用程序的一部分调入内存，还有一部分仍在磁盘上，故需在页表中再增加若干项，供程序(数据)在换进、换出时参考。在请求分页系统中的每个页表项如图所示。页号物理块号状态位P访问字段A修改位M外存地址Silberschatz,Galvin,andGagne199910.12AppliedOperatingSystemConcepts其中各字段说明如下：•状态位（存在位P）：用于指示该页是否已调入内存，供程序访问时参考。•访问字段A：用于记录本页在一段时间内被访问的次数，或最近已有多长时间未被访问，提供给置换算法选择换出页面时参考。•修改位M：表示该页在调入内存后是否被修改过。由于内存中的每一页都在外存上保留一份副本，因此，若未被修改，在置换该页时就不需将该页写回到外存上，以减少系统的开销和启动磁盘的次数；若已被修改，则必须将该页重写到外存上，以保证外存中所保留的始终是最新副本。•外存地址：用于指出该页在外存上的地址，通常是物理块号，供调入该页时使用。Silberschatz,Galvin,andGagne199910.13AppliedOperatingSystemConcepts请求分页中的硬件支持2）缺页中断机构在请求分页系统中，每当所要访问的页面不在内存时，便要产生一缺页中断，请求OS将所缺页调入内存。与一般中断的主要区别在于：•缺页中断在指令执行期间产生和处理中断信号，而一般中断在一条指令执行完后检查和处理中断信号。•缺页中断返回到该指令的开始重新执行该指令，而一般中断返回到该指令的下一条指令执行。•一条指令在执行期间，可能产生多次缺页中断。Silberschatz,Galvin,andGagne199910.14AppliedOperatingSystemConcepts请求分页中的硬件支持3)地址变换机构请求分页系统中的地址变换机构，是在分页系统的地址变换机构的基础上，再为实现虚拟存储器而增加了某些功能所形成的，如产生和处理缺页中断，以及从内存中换出一页的功能等等，下图给出了请求分页系统的地址变换过程。Silberschatz,Galvin,andGagne199910.15AppliedOperatingSystemConcepts缺页中断处理是否否是是否产生缺页中否是断请求调页是开始（程序请求访问一页)越界中断CPU检索快表页表项是否在快表中？访问页表页是否在内存中？修改快表修改访问位和修改位形成物理地址地址变换结束保留CPU现场从外存中找到缺页页号页表长度？内存满否？选择一页换出该页是否被修改？将该页写回外存将一页从外存换入内存修改页表CPU从外存读缺页启动I/O硬件Silberschatz,Galvin,andGagne199910.16AppliedOperatingSystemConceptsValid-InvalidBit•Witheachpagetableentryavalid–invalidbitisassociated(1in-memory,0not-in-memory)（在每一个页表的表项有一个有效-无效位相关联，1表示在内存，0表示不内存）•Initiallyvalid–invalidbutissetto0onallentries（在所有的表项，这个位被初始化为0）.•Exampleofapagetablesnapshot（一个页表映象的例子）.•Duringaddresstranslation,ifvalid–invalidbitinpagetableentryis0（在地址转换中，如果页表表项位的值是0）pagefault（缺页）.1111000Frame#valid-invalidbitpagetableSilberschatz,Galvin,andGagne199910.17AppliedOperat