搜索
操作系统OperatingSystem第4章存储管理§4.1存储管理的原理§4.2连续分配存储管理§4.3离散分配存储管理§4.4内核主存管理§4.5虚拟存储技术§4.6虚拟页式存储管理§4.7虚拟段式存储管理§4.8存储管理实例§4.5虚拟存储技术§4.5.1程序局部性原理§4.5.2虚拟存储的实现虚拟内存技术(VirtualMemory)诞生于1961年。广泛使用是从上个世纪70年代初以后，今天几乎所有的操作系统都采用虚拟内存技术来管理内存。这是一种利用虚拟存储器来逻辑扩充物理内存的技术。其基本思想是用软硬件技术把内存与外存这两级存储器当成一级存储器来用，从而给用户提供了一个比内存也比任何应用程序大得多的虚拟存储器，使得用户编程时再也不用考虑内存大小的限制了，给用户编程带来极大的方便。虚拟内存技术的实现也利用了自动覆盖和交换技术。§4.5.1程序局部性原理1.局部性原理(principleoflocality)：指程序在执行过程中的一个较短时期内，所执行的指令地址和指令的操作数地址，分别局限于一定区域。2.局部性主要表现：时间局部性：是指一段指令在某一时间段内会被反复执行。即程序某一部分的数据或指令被重复性地访问，它们对应于程序结构中的循环、子程序、常用到的变量及数据等；空间局部性：是指一旦某一个存储单元被访问，那么它附近的单元也将很快被访问。这对应于程序结构中的顺序执行的指令、线性数据结构以及在相邻位置存放的数据或变量等。而程序中的分支和调用子程序只是将程序的访问空间从一处移到另外一处，仍具有局部性。排他性：程序运行不但体现在时间、空间的局部性，还体现在某些程序段执行的排他性。即程序设计者编程时要考虑程序执行时所能遇到的各种情况，但具体到一次程序的执行，并不会发生所有的状况。因而某些程序段在进程整个运行期间，可能根本不使用，如出错处理、分支语句等。因而，没有用到的程序段就不必调入内存。另外，有些程序段仅执行一次，以后就再也不会用到，这样的程序段也没有必要一直占用内存空间。综上所述：程序只要装入内存一部分就可以运行，当用到不在内存的部分时，再将其装入内存。换句话就是说程序全部装入内存并不是程序运行的必要条件。§4.5.2虚拟存储的实现1.虚拟存储技术如果把程序部分装入内存，其余大部分放在外存，而程序又能运行，这样我们就拥有了一个比有限的实际内存空间大得多的、逻辑的虚拟内存空间。即用大容量的外存来模拟内存，这种存储模式就称之为虚拟存储技术。2.虚拟技术实现的关键(1)怎样才能发现欲执行的指令或数据不在内存?简单有效方法就是进行标识(2)怎样将不在内存的部分调入进来。通常系统采用中断技术完成调入工作。(3)在内存中的作业如何组织？一个进程可被分为多次调入内存，这样很难保证进程在内存中占据一个连续的空间，实际上进程在内存中是离散存储的。虚拟技术进一步说明系统要提供必要的硬件支持，如虚拟页式存储中的页表机制、缺页中断机构以及相应的地址变换机构。虚拟存储技术是将内存与外存有机地结合在一起，从而得到一个容量很大的虚拟空间。使用户感到有一个很大的内存，不用再考虑内存的容量限制。虚存虽然比内存要大得多，但不可能无限大，其大小要受到外存空间的限制以及CPU地址所能表示范围的限制。大程序：可在较小的可用内存中执行较大的用户程序；大的用户空间：提供给用户可用的虚拟内存空间通常大于物理内存(realmemory)并发：可在内存中容纳更多程序并发执行；易于开发：与覆盖技术比较，不必影响编程时的程序结构3.引入虚拟存储技术的好处总容量不超过物理内存和外存交换区容量之和。其运行速度接近于内存，每位的成本又接近于外存，是一种性能非常优越的存储管理技术4.虚拟存储技术的特征不连续性：物理内存分配的不连续，虚拟地址空间使用的不连续（数据段和栈段之间的空闲空间，共享段和动态链接库占用的空间）部分交换：与交换技术相比较，虚拟存储的调入和调出是对部分虚拟地址空间进行的；大空间：通过物理内存和快速外存相结合，提供大范围的虚拟地址空间虚拟存储技术的种类：虚拟页式虚拟段式虚拟段页式§4.6虚拟页式存储管理§4.6.1虚拟页式存储的实现§4.6.2页面分配策略§4.6.3页面置换方法§4.6.4虚拟页式存储的优缺点返回1.基本原理系统自动地将作业的地址空间分页，将系统的主存空间分块，页与块等大小。在作业运行前，只把初始需要的一部分页面装入内存块里，运行中需要访问自己地址空间中的但当前不在内存的页面时产生缺页中断，由缺页中断服务程序将所需的页面调入内存。若此时内存中没有空闲物理块安置请求调入的新页面，则系统按预定的置换策略自动选择一个或一些在内存的页面，把它们换出到外存。这里的请求调入和置换功能都是比实分页存储管理增加的内容，是实现虚拟存储的主要功能。§4.6.1虚拟页式存储的实现页面的动态调度步骤：1、找到被访问页面在外存的地址；2、在内存中找一个空闲页面；（1）如果没有，按照淘汰算法选择一个内存页面；（2）将此内存页面写回外存，修改页表及页面分配表；3、读入所需的页面，修改页表及页面分配表；4、重新启动进程执行被中断的指令。标记某页是否在内存，用于查询要访问的页在不在内存。页表如下：页号物理块号状态位P访问位A修改位M外存地址2.页表机制其中：外存地址指出该页在外存的地址，供调入该页时用；状态为指示该页是否在内存，供程序访问时用，也是检查是否缺页的标志位，如置1表示在内存；访问位或访问字段则是该页被访问过的标志或该页被访问过的次数；修改位表示该页是否被修改过；存取控制字段则是用来限制页面被安全共享的。3.动态地址变换在虚拟页式存储中，应采用动态地址变换方式，因为某一欲执行的指令可能不在内存，只能在指令执行之前完成地址变换。任一作业都应在自己的虚拟地址空间中执行，所以要为用户作业设置一个虚拟地址指针VP，虚拟地址依然是由页号和页内偏移地址组成的。系统总是执行VP虚指针所指向的指令，为了将虚拟地址VP变换为对应的实存地址，因此先要查找页表。若从页表中查出此页不在内存（状态位为0），则产生一个缺页中断。此时，进程暂停当前指令执行，CPU转去执行缺页中断处理程序。若该页已在内存，则指令的地址映射过程与页式存储是一样的。即将块号和页内地址相拼接形成物理地址IP，处理器再从IP中取指令执行。4.缺页中断noyesnoyesyesno硬件部分软件部分图4.30缺页中断处理流程进程被创建后，进入就绪队列进程被调度执行启动待执行指令VP计算虚页号与页内地址该页在内存？地址映射执行下一条指令访问内存完成该指令保留当前进程现场按某算法选一页淘汰调入所需页面该页已改过调整页表及空闲页面表恢复被中断进程现场把该页写回外存有空闲页面吗？5.缺页率虽然通过缺页中断将所需要的页调入内存，但缺页中断的频繁发生会严重影响程序执行的效率。为了标识缺页中断发生的频度，可以引入缺页率来表示。设进程在其执行期间共进行了S次访页操作，其中成功访页次数为A（访问时该页在主存），不成功的访页次数为B（即发生了缺页中断），显然有：S=A+B，则该进程的缺页率f定义为：f＝B/S。显然缺页率越低越好。§4.6.2页面分配策略虚拟存储管理在进行页面分配时，要考虑这样的问题：空闲页面如何管理；采用什么样的分配策略；为进程分配多少物理块比较合适；在什么时间进行页面分配等。1.空闲页面管理同页式存储管理相似，虚拟存储方式下的空闲页面的管理也可以采用位示图或空闲页面链的形式。由于主存中所有进程的虚拟地址空间之和远大于主存空间，因此进程执行时常发生缺页中断，这样不断地调入新页，很快就使主存空间饱和。以后再发生缺页时，要先淘汰一页才能装入新页，这使得缺页处理时间过长，减缓了进程的执行速度，从而影响到系统的性能。在实际的系统中，总是维持一定数量的空闲块，而不是耗尽所有的空闲块。即空闲块数可以在某一区间浮动，一旦空闲块数小于下限值，系统就进行页面置换，以释放出一些空闲块，使得总的空闲块数不超过系统规定的上限值即可。即系统设置专门的独立进程负责页面置换，以保证链表的适当规模。2分配策略（内存）可变分配：是指一个进程所拥有的物理块数是不定的，这种分配方式称之为可变分配。固定分配是指为每个进程分配一固定页数的内存空间，在整个运行期间都不再改变。⑴平均分配算法，是将系统中所有可供分配的物理块，平均分配给每一个进程。例如，当系统中有80个空闲块，4个进程时，每个进程可分得20个物理块。这种平均分配方式因其未考虑各进程本身的大小，会造成事实上的不公平。如有一个进程其大小为100页，只分配给它20个块，这样它必将会有很高的缺页率；而另一个进程只有10页，却有10个块在闲置未用。所以在平均的思想下，还要考虑进程的大小。⑵按比例分配算法，根据进程的大小按比例分配空闲块。设系统中现有m个进程、n个空闲块，每个进程拥有的页数为Si，则系统中所有进程页数之和为：S=S1+S2+S3+…+Sm则为每个进程分配的物理块数为：Bi=（Si/S）×n，Bi应向下取整。⑶优先权分配算法，为优先权高的作业分配较多的内存空间，这样可以使重要或紧迫的任务尽快完成。这时可以将内存中的空闲块分成两部分：一部分按比例分配给各进程，另一部分则根据各进程的优先权，适当地为其增加相应份额。2分配策略（外存）1、静态分配一个进程在运行之前，将其页面全部装入外存。当某一外存页面被调入内存时，并不释放所占用的外存页面。2、动态分配一个进程在运行之前，仅将未装入内存的那部分页面装入外存。当某一外存页面被调入内存时，释放所占用的外存页面。3.工作集(1)为保证进程能正常运行最少需要多少物理块。从理论上讲，进程只要获得一个物理块就可以运行。但是进程正常运行所需的最少物理块数与计算机的硬件结构有关，取决于指令的格式、功能和寻址方式。由于分页是系统的行为，可能会出现下面的情景：由此可见，系统应保证任一条指令执行时，其所涉及的虚拟地址所在的页都应在内存中。这个页数就是进程所需要的最小块数，若系统为进程所分配的物理块数少于此值时，进程将无法运行。123456涉及6次缺页中断的指令指令copyAtoB数据A：数据B：(2)为使进程能有效地工作，应为它分配多少物理块合适随着为每个进程所分配物理块数目的减少，将使进程执行中的缺页率提高，导致非生产性开销过大，从而降低了进程的执行速度，严重时导致进程不能向前推进。最少物理块数只能保证程序能执行下去，而不是最合适的块数。在1968年，Denning提出了工作集理论。所谓工作集就是进程在某段时间里实际上要访问的页的集合。依据程序执行时的局部特性，可以利用程序过去的行为来估计它未来的行为。故定义运行进程在t－w到t这个时间间隔内所访问的页的集合为该进程在时间t的工作集，记为W（t，w）。并把变量w称之为“工作集窗口尺寸”，工作集中所包含的页面数称为“工作集尺寸”，记为|W(t,w)|。例如:访问页面：２３３３２３２５５８５Twt-wtW(t,w)={2,3,5,8}访问页面：２３３３２３２５５８５５８５３９８９５８７８Twwt1t2W(t1,w)={2,3,5,8}W(t2,w)={3,5,7,8,9}(3)工作集的应用工作集W（t，w）是二元函数，随t、w的值而改变。首先工作集与时间有关，即不同时间的工作集其所包含的页面可能不同，其所包含的页面个数也可能不同；其次工作集也是工作集窗口尺寸w的函数，体现在工作集尺寸|W(t,w)|随w的增加而变大，即满足|W(t,w)|≤|W(t,w+a)|，a0。工作集窗口尺寸与缺页率关系密切，若w增大，工作集尺寸|W|随之增加（即所含的页面数增多），缺页率就会下降。倘若w含盖了整个作业虚拟空间，缺页率降为0，也就失去了虚存意义；反之若w选取过小，将引起频繁缺页，导致系统性能下降。二者之间的关系可以如图所示。虚存中并不是要取消缺页率，而是要使缺页率维持在一个较低的水平上。因此可以取拐点所对应的工作集尺寸作为分给进程的物理块数，实验