第四章 虚拟存储管理优秀PPT.ppt

《第四章 虚拟存储管理优秀PPT.ppt》由会员分享，可在线阅读，更多相关《第四章 虚拟存储管理优秀PPT.ppt（70页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第四章第四章 虚拟存储管虚拟存储管理理第一页，本课件共有70页第第4 4章章 存储管理存储管理4.1 4.1 存储管理的原理存储管理的原理 4.2 4.2 连续分配存储管理连续分配存储管理 4.3 4.3 离散分配存储管理离散分配存储管理4.4 4.4 内核主存管理内核主存管理4.5 4.5 虚拟存储技术虚拟存储技术4.6 4.6 虚拟页式存储管理虚拟页式存储管理 4.7 4.7 虚拟段式存储管理虚拟段式存储管理4.8 4.8 存储管理实例存储管理实例第二页，本课件共有70页4.5 4.5 虚拟存储技术虚拟存储技术4.5.1 4.5.1 程序局部性原理程序局部性原理 4.5.2 4.5.2 虚

2、拟存储的实现虚拟存储的实现&虚拟内存技术(Virtual Memory)(Virtual Memory)诞生于1961年。&广泛使用是从上个世纪70年代初以后，今天几乎所有的操作系统都采用虚拟内存技术来管理内存。&这是一种利用虚拟存储器来逻辑扩充物理内存的技术。其基本思想是用用软软硬硬件件技技术术把把内内存存与与外外存存这这两两级级存存储储器器当当成成一一级级存存储储器器来来用用，从从而而给给用用户户提提供供了了一一个个比比内内存存也也比比任任何何应应用用程程序序大大得得多多的的虚虚拟拟存存储储器器，使使得得用用户户编编程程时时再再也也不不用用考考虑虑内内存存大大小小的的限限制制了了，给给用用

3、户户编编程程带来极大的方便。带来极大的方便。&虚拟内存技术的实现也利用了自动覆盖和交换技术。第三页，本课件共有70页4.5.1 4.5.1 程序局部性原理程序局部性原理&1.1.局部性原理局部性原理(principle of locality)：指程序在执行过程中的一个较短时期内，所执行的指令地址和指令的操作数地址，分别局限于一定区域。&2.2.局部性主要表现：局部性主要表现：F时间局部性：时间局部性：是指一段指令在某一时间段内会被反复是指一段指令在某一时间段内会被反复执行。即程序某一部分的数据或指令被重复性地访执行。即程序某一部分的数据或指令被重复性地访问，它们对应于程序结构中的循环、子程序

4、、常用问，它们对应于程序结构中的循环、子程序、常用到的变量及数据等到的变量及数据等；F空间局部性空间局部性：是指一旦某一个存储单元被访问，那么是指一旦某一个存储单元被访问，那么它附近的单元也将很快被访问。这对应于程序结构它附近的单元也将很快被访问。这对应于程序结构中的顺序执行的指令、线性数据结构以及在相邻位中的顺序执行的指令、线性数据结构以及在相邻位置存放的数据或变量等。而程序中的分支和调用子置存放的数据或变量等。而程序中的分支和调用子程序只是将程序的访问空间从一处移到另外一处，程序只是将程序的访问空间从一处移到另外一处，仍具有局部性。仍具有局部性。第四页，本课件共有70页F排他性：排他性：程

5、序运行不但体现在时间、空间的局部性，还体现在某些程序段执行的排他性。即程序设计者编程时要考虑程序执行时所能遇到的各种情况，但具体到一次程序的执行，并不会发生所有的状况。因而某些程序段在进程整个运行期间，可能根本因而某些程序段在进程整个运行期间，可能根本不使用，如出错处理、分支语句等。不使用，如出错处理、分支语句等。因而，没有用到的程序段就不必调入内存。另外，有些程序段仅执行一次，以后就再也不会用到，这样的程序段也没有必要一直占用内存空间。&综上所述：综上所述：程序只要装入内存一部分就可以运行，当程序只要装入内存一部分就可以运行，当用到不在内存的部分时，再将其装入内存。用到不在内存的部分时，再将

6、其装入内存。换句话就换句话就是说程序全部装入内存并不是程序运行的必要条件。是说程序全部装入内存并不是程序运行的必要条件。第五页，本课件共有70页4.5.2 4.5.2 虚拟存储的实现虚拟存储的实现1.1.虚拟存储技术虚拟存储技术如果把程序部分装入内存，其余大部分放在外存，而程序又能运行，这如果把程序部分装入内存，其余大部分放在外存，而程序又能运行，这样我们就拥有了一个比有限的实际内存空间大得多的、逻辑的虚拟内存样我们就拥有了一个比有限的实际内存空间大得多的、逻辑的虚拟内存空间。空间。即用大容量的外存来模拟内存，这种存储模式就称之为虚拟存储即用大容量的外存来模拟内存，这种存储模式就称之为虚拟存储

7、技术。技术。2.2.虚拟技术实现的关键虚拟技术实现的关键(1)怎样才能发现欲执行的指令或数据不在内存怎样才能发现欲执行的指令或数据不在内存?简单有效方法就是进行标识简单有效方法就是进行标识(2)怎样将不在内存的部分调入进来怎样将不在内存的部分调入进来。通常系统采用中断技术完成调入工作。通常系统采用中断技术完成调入工作。(3)在内存中的作业如何组织？在内存中的作业如何组织？一个进程可被分为多次调入内存，这样很难保证进程在内存中占据一个一个进程可被分为多次调入内存，这样很难保证进程在内存中占据一个连续的空间，实际上进程在内存中是离散存储的。连续的空间，实际上进程在内存中是离散存储的。第六页，本课件

8、共有70页虚拟技术进一步说明虚拟技术进一步说明因而因而系统要提供必要的硬件支持系统要提供必要的硬件支持，如虚拟页式存，如虚拟页式存储中的页表机制、缺页中断机构以及相应的地储中的页表机制、缺页中断机构以及相应的地址变换机构。址变换机构。虚拟存储技术是虚拟存储技术是将内存与外存有机地结合在一起，将内存与外存有机地结合在一起，从而得到一个容量很大的虚拟空间。从而得到一个容量很大的虚拟空间。使用户感到使用户感到有一个很大的内存，不用再考虑内存的容量限有一个很大的内存，不用再考虑内存的容量限制。制。虚存虽然比内存要大得多，但不可能无限大，虚存虽然比内存要大得多，但不可能无限大，其大小要受到外存空间的限制

9、以及其大小要受到外存空间的限制以及CPU地址地址所能表示范围的限制。所能表示范围的限制。第七页，本课件共有70页&大程序：可在较小的可用内存中执行较大的用户程序；&大的用户空间：提供给用户可用的虚拟内存空间通常大于物理内存(real memory)&并发：可在内存中容纳更多程序并发执行；&易于开发：与覆盖技术比较，不必影响编程时的程序结构3.3.引入虚拟存储技术的好处引入虚拟存储技术的好处F总容量不超过物理内存和外存交换区容量之和。其运总容量不超过物理内存和外存交换区容量之和。其运行速度接近于内存，每位的成本又接近于外存，是一种行速度接近于内存，每位的成本又接近于外存，是一种性能非常优越的存储

10、管理技术性能非常优越的存储管理技术 第八页，本课件共有70页4.4.虚拟存储技术的特征虚拟存储技术的特征&不连续性不连续性：物理内存分配的不连续，虚拟地址空间使用的不连续（数据段和栈段之间的空闲空间，共享段和动态链接库占用的空间）&部分交换：部分交换：与交换技术相比较，虚拟存储的调入和调出是对部分虚拟地址空间进行的；&大空间：大空间：通过物理内存和快速外存相结合，提供大范围的虚拟地址空间虚拟存储技术的种类：虚拟存储技术的种类：虚拟页式虚拟段式虚拟段页式第九页，本课件共有70页4.6 4.6 虚拟页式存储管理虚拟页式存储管理 4.6.1 4.6.1 虚拟页式存储的实现虚拟页式存储的实现 4.6.

11、2 4.6.2 页面分配策略页面分配策略 4.6.3 4.6.3 页面置换方法页面置换方法4.6.4 4.6.4 虚拟页式存储的优缺点虚拟页式存储的优缺点第十页，本课件共有70页返回&1.1.基本原理基本原理&系统自动地将作业的地址空间分页，将系统的主存空间分块，页与块等大小，在作业运行前，只把初始需要的一部分页面装入内存块里，运行中需要访问自己地址空间中的但当前不在内存的页面时产生缺页中断，由缺页中断服务程序将所需的页面调入内存，若此时内存中没有空闲物理块安置请求调入的新页面，则系统按预定的置换策略自动选择一个或一些在内存的页面，把它们换出到外存。&这里的请求调入和置换功能请求调入和置换功能

12、都是比实分页存储管理增加的内容，是实现虚拟存储的主要功能。4.6.1 4.6.1 虚拟页式存储的实现虚拟页式存储的实现 第十一页，本课件共有70页页面的动态调度步骤：页面的动态调度步骤：1、找到被访问页面在外存的地址；、找到被访问页面在外存的地址；2、在内存中找一个空闲页面；、在内存中找一个空闲页面；（1）如果没有，按照淘汰算法选择一个内存页）如果没有，按照淘汰算法选择一个内存页面；面；（2）将此内存页面写回外存，修改页表及页面）将此内存页面写回外存，修改页表及页面分配表；分配表；3、读入所需的页面，修改页表及页面分配表；、读入所需的页面，修改页表及页面分配表；4、重新启动进程执行被中断的指令

13、。、重新启动进程执行被中断的指令。第十二页，本课件共有70页&标记某页是否在内存，用于查询标记某页是否在内存，用于查询要访问的要访问的页在不在内存。页表如下：页在不在内存。页表如下：页号 物理块号 状态位P访问位A修改位M外存地址2.2.页表机制页表机制其中：外存地址指出该页在外存的地址，供调入该页时用；状态为指示该页是否在内存，供程序访问时用，也是检查是否缺页的标志位，如置1表示在内存；访问位或访问字段则是该页被访问过的标志或该页被访问过的次数；修改位表示该页是否被修改过；存取控制字段则是用来限制页面被安全共享的。第十三页，本课件共有70页3.3.动态地址变换动态地址变换&在虚拟页式存储中，

14、应采用动态地址变换方式，因为某一欲执行的在虚拟页式存储中，应采用动态地址变换方式，因为某一欲执行的指令可能不在内存，只能在指令执行之前完成地址变换。指令可能不在内存，只能在指令执行之前完成地址变换。任一作任一作业都应在自己的虚拟地址空间中执行，业都应在自己的虚拟地址空间中执行，所以要为用户作业设置所以要为用户作业设置一个虚拟地址指针一个虚拟地址指针VP，虚拟地址依然是由页号和页内偏移地址组，虚拟地址依然是由页号和页内偏移地址组成的。成的。&系统总是执行系统总是执行VP虚指针所指向的指令，为了将虚拟地址虚指针所指向的指令，为了将虚拟地址VP变变换为对应的实存地址，因此换为对应的实存地址，因此先要

15、查找页表。若从页表中查出先要查找页表。若从页表中查出此页不在内存（状态位为此页不在内存（状态位为0），则产生一个缺页中断。），则产生一个缺页中断。此时，此时，进程暂停当前指令执行，进程暂停当前指令执行，CPU转去执行缺页中断处理程序。转去执行缺页中断处理程序。若该页已在内存，若该页已在内存，则指令的地址映射过程与页式存储是一样的。则指令的地址映射过程与页式存储是一样的。即将块号和页内地址相并接形成物理地址即将块号和页内地址相并接形成物理地址IP，处理器再从，处理器再从IP中取指令执行。中取指令执行。第十四页，本课件共有70页4.4.缺页中断缺页中断第十五页，本课件共有70页5.5.缺页率缺页率

16、&虽然通过缺页中断将所需要的页调入内存，但缺页中断的频虽然通过缺页中断将所需要的页调入内存，但缺页中断的频繁发生会严重影响程序执行的效率。为了标识缺页中断发生繁发生会严重影响程序执行的效率。为了标识缺页中断发生的频度，可以引入缺页率来表示。的频度，可以引入缺页率来表示。&设进程在其执行期间共进行了设进程在其执行期间共进行了S S次访页操作，其中成功次访页操作，其中成功访页次数为访页次数为A A（访问时该页在主存），不成功的访页次数（访问时该页在主存），不成功的访页次数为为B B（即发生了缺页中断），显然有：（即发生了缺页中断），显然有：S=A+BS=A+B，&则该进程的缺页率则该进程的缺页率f

17、 f定义为：定义为：f fB/SB/S。&显然缺页率越低越好。显然缺页率越低越好。第十六页，本课件共有70页4.6.2 4.6.2 页面分配策略页面分配策略&虚拟存储管理在进行页面分配时，要考虑这样的虚拟存储管理在进行页面分配时，要考虑这样的问题：空闲页面如何管理；采用什么样的分配策略；问题：空闲页面如何管理；采用什么样的分配策略；为进程分配多少物理块比较合适；在什么时间进行为进程分配多少物理块比较合适；在什么时间进行页面分配等。页面分配等。第十七页，本课件共有70页1.1.空闲页面管理空闲页面管理&同页式存储管理相似，虚拟存储方式下的空闲页面的管理也可以同页式存储管理相似，虚拟存储方式下的空

18、闲页面的管理也可以采用采用位示图位示图或或空闲页面链空闲页面链的形式。的形式。&由于主存中所有进程的虚拟地址空间之和远大于主存空间，因此由于主存中所有进程的虚拟地址空间之和远大于主存空间，因此进程执行时常发生缺页中断，这样不断地调入新页，很快就使主进程执行时常发生缺页中断，这样不断地调入新页，很快就使主存空间饱和。以后再发生缺页时，要先淘汰一页才能装入新页，存空间饱和。以后再发生缺页时，要先淘汰一页才能装入新页，这使得这使得缺页处理时间过长，减缓了进程的执行速度，从而影响到系统缺页处理时间过长，减缓了进程的执行速度，从而影响到系统的性能。的性能。&在实际的系统中，总是维持一定数量的空闲块，而不

19、是耗尽所在实际的系统中，总是维持一定数量的空闲块，而不是耗尽所有的空闲块。即有的空闲块。即空闲块数可以在某一区间浮动空闲块数可以在某一区间浮动，一旦空闲块数小，一旦空闲块数小于下限值，系统就进行页面置换，以释放出一些空闲块，使得总于下限值，系统就进行页面置换，以释放出一些空闲块，使得总的空闲块数不超过系统规定的上限值即可。即系统设置专门的独的空闲块数不超过系统规定的上限值即可。即系统设置专门的独立进程负责页面置换，以保证链表的适当规模。立进程负责页面置换，以保证链表的适当规模。第十八页，本课件共有70页2 2 分配策略（内存）分配策略（内存）&可变分配：可变分配：是指一个进程所拥有的物理块数是

20、不定的，这种分是指一个进程所拥有的物理块数是不定的，这种分配方式称之为可变分配。配方式称之为可变分配。&固定分配固定分配是指为每个进程分配一固定页数的内存空间，在整个是指为每个进程分配一固定页数的内存空间，在整个运行期间都不再改变。运行期间都不再改变。&平均分配算法，平均分配算法，是将系统中所有可供分配的物理块，平均分是将系统中所有可供分配的物理块，平均分配给每一个进程。例如，当系统中有配给每一个进程。例如，当系统中有80个空闲块，个空闲块，4个进程时，个进程时，每个进程可分得每个进程可分得20个物理块。这种平均分配方式因其未考虑各个物理块。这种平均分配方式因其未考虑各进程本身的大小，会造成事

21、实上的不公平。如有一个进程其大进程本身的大小，会造成事实上的不公平。如有一个进程其大小为小为100页，只分配给它页，只分配给它20个块，这样它必将会有很高的缺页率；个块，这样它必将会有很高的缺页率；而另一个进程只有而另一个进程只有10页，却有页，却有10个块在闲置未用。所以在平均的个块在闲置未用。所以在平均的思想下，还要考虑进程的大小。思想下，还要考虑进程的大小。第十九页，本课件共有70页&按比例分配算法，按比例分配算法，根据进程的大小按比例分配空闲块。设系根据进程的大小按比例分配空闲块。设系统中现有统中现有m个进程、个进程、n个空闲块，每个进程拥有的页数为个空闲块，每个进程拥有的页数为Si，

22、则，则系统中所有进程页数之和为：系统中所有进程页数之和为：S=S1+S2+S3+Sm 则为每个进程分配的物理块数为：则为每个进程分配的物理块数为：Bi=（Si/S）n，Bi应向下取整。应向下取整。&优先权分配算法，优先权分配算法，为优先权高的作业分配较多的内存空间，为优先权高的作业分配较多的内存空间，这样可以使重要或紧迫的任务尽快完成。这时可以将内存中这样可以使重要或紧迫的任务尽快完成。这时可以将内存中的空闲块分成两部分：一部分按比例分配给各进程，另一部的空闲块分成两部分：一部分按比例分配给各进程，另一部分则根据各进程的优先权，适当地为其增加相应份额。分则根据各进程的优先权，适当地为其增加相应

23、份额。第二十页，本课件共有70页2 2 分配策略（外存）分配策略（外存）1、静态分配、静态分配 一个进程在运行之前，将其页面全部装一个进程在运行之前，将其页面全部装入外存。当某一外存页面被调入内存时，入外存。当某一外存页面被调入内存时，并不释放所占用的外存页面。并不释放所占用的外存页面。2、动态分配、动态分配 一个进程在运行之前，仅将未装入内存一个进程在运行之前，仅将未装入内存的那部分页面装入外存。当某一外存页的那部分页面装入外存。当某一外存页面被调入内存时，释放所占用的外存页面被调入内存时，释放所占用的外存页面。面。第二十一页，本课件共有70页3.3.工作集工作集&(1)(1)为保证进程能正

24、常运行最少需要多少物理块。为保证进程能正常运行最少需要多少物理块。从理论上讲，进程只要获得从理论上讲，进程只要获得一个物理块一个物理块就可以运行。但是进程正常就可以运行。但是进程正常运行所需的最少物理块数与计算机的硬件结构有关，取决于指令的格运行所需的最少物理块数与计算机的硬件结构有关，取决于指令的格式、功能和寻址方式。式、功能和寻址方式。由于分页是系统的行为，由于分页是系统的行为，可能会出现下面可能会出现下面的情景：的情景：由此可见，由此可见，系统应保证任一条指令执行系统应保证任一条指令执行时，其所涉及的虚拟地址所在的页时，其所涉及的虚拟地址所在的页都应在内存中。这个页数就是进程都应在内存中

25、。这个页数就是进程所需要的最小块数所需要的最小块数，若系统为进程，若系统为进程所分配的物理块数少于此值时，进所分配的物理块数少于此值时，进程将无法运行。程将无法运行。123456涉涉及及6 6次次缺缺页页中中断断的的指指令令指令指令copy A to B数据数据A：数据数据B：第二十二页，本课件共有70页&(2)(2)为使进程能有效地工作，应为它分配多少物理块合适为使进程能有效地工作，应为它分配多少物理块合适&随着为每个进程所分配物理块数目的减少，将使进程执行中的缺页率随着为每个进程所分配物理块数目的减少，将使进程执行中的缺页率提高，导致非生产性开销过大，从而降低了进程的执行速度，严重时提高，

26、导致非生产性开销过大，从而降低了进程的执行速度，严重时导致进程不能向前推进。最少物理块数只能保证程序能执行下去，而导致进程不能向前推进。最少物理块数只能保证程序能执行下去，而不是最合适的块数。不是最合适的块数。&!在在19681968年，年，DenningDenning提出了工作集理论。提出了工作集理论。所谓所谓工作集工作集就是进程在就是进程在某段时间里实际上要访问的页的集合。某段时间里实际上要访问的页的集合。依据程序执行时的局部特性，依据程序执行时的局部特性，可以利用程序过去的行为来估计它未来的行为。故可以利用程序过去的行为来估计它未来的行为。故定义运行进程在定义运行进程在t tw w到到t

27、 t这个时间间隔内所访问的页的集合为该进程在时间这个时间间隔内所访问的页的集合为该进程在时间t t的工的工作集，记为作集，记为W W（t t，w w）。）。并把变量并把变量w w称之为称之为“工作集窗口尺寸工作集窗口尺寸”，工作集中所包含的页面数称为工作集中所包含的页面数称为“工作集尺寸工作集尺寸”，记为，记为|W(t,w)|W(t,w)|。第二十三页，本课件共有70页例如例如:访问页面：访问页面：Twt-wtW(t,w)=2,3,5,8访问页面：访问页面：Twwt1t2W(t1,w)=2,3,5,8W(t2,w)=3,5,7,8,9第二十四页，本课件共有70页(3)(3)工作集的应用工作集的

28、应用&工作集工作集W W（t t，w w）是二元函数，随）是二元函数，随t t、w w的值而改变。的值而改变。首先工作集与首先工作集与时间有关，即不同时间的工作集其所包含的页面可能不同，其所包含时间有关，即不同时间的工作集其所包含的页面可能不同，其所包含的页面个数也可能不同；的页面个数也可能不同；其次工作集也是工作集窗口尺寸其次工作集也是工作集窗口尺寸w w的函数，的函数，体现在工作集尺寸体现在工作集尺寸|W(t,w)|W(t,w)|随随w w的增加而变大，即满足的增加而变大，即满足|W(t,w)|W(t,w+a)|W(t,w)|W(t,w+a)|，a0a0。&工作集窗口尺寸与缺页率关系密切，

29、工作集窗口尺寸与缺页率关系密切，若若w w增大，工作集尺寸增大，工作集尺寸|W|W|随之增加（即所含的页面数增多），缺页率就会下降。随之增加（即所含的页面数增多），缺页率就会下降。倘若倘若w w含盖了整个作业虚拟空间，缺页率降为含盖了整个作业虚拟空间，缺页率降为0 0，也就失去了虚存意，也就失去了虚存意义；反之若义；反之若w w选取过小，将引起频繁缺页，导致系统性能下降。二选取过小，将引起频繁缺页，导致系统性能下降。二者之间的关系可以如图所示。者之间的关系可以如图所示。第二十五页，本课件共有70页&虚存中并不是要取消缺页率，而是要使缺页率维持在一个较低的水虚存中并不是要取消缺页率，而是要使缺页

30、率维持在一个较低的水平上。因此可以取拐点所对应的工作集尺寸作为分给进程的物理块平上。因此可以取拐点所对应的工作集尺寸作为分给进程的物理块数，实验分析表明，这个数应是进程总页面数的一半。数，实验分析表明，这个数应是进程总页面数的一半。即一个进程即一个进程应获得其所需页数一半的空间时，再进入内存执行应获得其所需页数一半的空间时，再进入内存执行。第二十六页，本课件共有70页4.4.页面调入时机页面调入时机 即何时将一个页面由外存调入内存。即何时将一个页面由外存调入内存。预调页策略预调页策略&也称先行调度，即一页面被访问前就已经预先置入内也称先行调度，即一页面被访问前就已经预先置入内存，以减少今后的缺

31、页率。存，以减少今后的缺页率。&主要适于进程的许多页存放在外存的连续区域中的情况。主要适于进程的许多页存放在外存的连续区域中的情况。有的系统结合请求调入使用，即每次缺页时装入多个页有的系统结合请求调入使用，即每次缺页时装入多个页面。面。优点：优点：提高调页的提高调页的I/OI/O效率。效率。缺点：缺点：基于预测，若调入的页在以后很少被访问，则效率基于预测，若调入的页在以后很少被访问，则效率低。预调页的成功率仅约低。预调页的成功率仅约50%50%，常用于程序装入时的调页。，常用于程序装入时的调页。第二十七页，本课件共有70页&请求调页策略请求调页策略&当当发发生生页页面面故故障障时时进进行行调调

32、度度，即即当当进进程程访访问问不不在在内内存存的的页页面面引引发发缺缺页页中中断断时时，由由系系统统根根据据这这种种访访问请求把所缺页面装入内存。问请求把所缺页面装入内存。&优优点点：由由请请求求调调入入策策略略装装入入的的页页一一定定会会被被访访问问，再再加加之之比比较较容容易易实实现现，故故在在目目前前的的虚虚拟拟存存储储器器中中，大大多采用此策略。多采用此策略。&缺点：缺点：每次仅调入一页，增加了磁盘每次仅调入一页，增加了磁盘I/OI/O的启动频率。的启动频率。第二十八页，本课件共有70页&在请求分页系统中，常把外存分为两部分：在请求分页系统中，常把外存分为两部分：一部分一部分是文件区，

33、用于存放文件；是文件区，用于存放文件；另一部分是对换区，用于存另一部分是对换区，用于存放对换页面。放对换页面。通常，对换区的磁盘输入输出速度比文通常，对换区的磁盘输入输出速度比文件区的高，这是因为对换区所规定的盘块要比文件件区的高，这是因为对换区所规定的盘块要比文件区的大得多。区的大得多。从交换区调入从交换区调入&若系统拥有足够的对换区空间，可在进程运行前，将与若系统拥有足够的对换区空间，可在进程运行前，将与该进程有关的文件拷贝到对换区。以后就从对换区调入该进程有关的文件拷贝到对换区。以后就从对换区调入所需页面，以提高调页速度。所需页面，以提高调页速度。5.5.从何处调入页面从何处调入页面 第

34、二十九页，本课件共有70页 从交换区及文件区调入从交换区及文件区调入&若系统缺少足够的对换区空间，则在交换区中只保存被修改过的若系统缺少足够的对换区空间，则在交换区中只保存被修改过的页面。因为未被修改的页面在文件区中有副本。因此凡是没被修页面。因为未被修改的页面在文件区中有副本。因此凡是没被修改的页，均从文件区调入；而已修改过的页面则从交换区调入。改的页，均从文件区调入；而已修改过的页面则从交换区调入。UNIX方式方式&与进程有关的文件都放在文件区，故凡是未运行过的页面，都应与进程有关的文件都放在文件区，故凡是未运行过的页面，都应从文件区调入。而对于曾经运行过而又被换出的页面，总是存放从文件区

35、调入。而对于曾经运行过而又被换出的页面，总是存放在对换区中。因此在下次调入时，应从对换区调入。由于在在对换区中。因此在下次调入时，应从对换区调入。由于在UNIX系统中允许页面共享，因此，某进程所请求的页面有系统中允许页面共享，因此，某进程所请求的页面有可能已由其它进程调入内存，此时也就无须再从对换区调入。可能已由其它进程调入内存，此时也就无须再从对换区调入。第三十页，本课件共有70页1.1.页面置换方式页面置换方式当内存空间已没有空闲页面而又要调入新页时，必须当内存空间已没有空闲页面而又要调入新页时，必须采用一定的采用一定的算法在内存中选择某一页面淘汰，所采用的算法称之为页面置算法在内存中选择

36、某一页面淘汰，所采用的算法称之为页面置换算法。换算法。如果被淘汰的页面在内存期间曾被修改过，还要将此页重新写如果被淘汰的页面在内存期间曾被修改过，还要将此页重新写回到外存，以便保留最新的副本。然后再换进新的页面。回到外存，以便保留最新的副本。然后再换进新的页面。(1)页面置换方式页面置换方式页面淘汰可以在整个内存空间范围内进行，称之为页面淘汰可以在整个内存空间范围内进行，称之为全局置换全局置换。也。也可以只在一个进程空间范围内考虑，称之为可以只在一个进程空间范围内考虑，称之为局部置换局部置换。即当某即当某一进程请求新页时，而该进程又没有空闲块，则只能淘汰自己的一个一进程请求新页时，而该进程又没

37、有空闲块，则只能淘汰自己的一个页面而不能淘汰其它进程的页面。页面而不能淘汰其它进程的页面。4.6.3 4.6.3 页面置换方法页面置换方法第三十一页，本课件共有70页 (2)(2)空闲块分配方式空闲块分配方式&若为进程分配固定的物理块数，在其执行期间再也不改变，若为进程分配固定的物理块数，在其执行期间再也不改变，则称为则称为固定分配。固定分配。初始进程块数的多少难以确定。若太少，初始进程块数的多少难以确定。若太少，则缺页频繁，系统开销大；若太多，则并发进程数目少，造成则缺页频繁，系统开销大；若太多，则并发进程数目少，造成CPUCPU空闲或其它资源空闲的情况。空闲或其它资源空闲的情况。&为进程分

38、配的物理块数在其运行期间是可变的，则称为为进程分配的物理块数在其运行期间是可变的，则称为可变分配可变分配。进程在运行中，系统可调整为该进程分配的物理块，直至进程的缺进程在运行中，系统可调整为该进程分配的物理块，直至进程的缺页率达到适当程度。页率达到适当程度。在页面置换算法讨论中，为了比较各种方法的在页面置换算法讨论中，为了比较各种方法的优劣，总是限定为固定分配局部置换。优劣，总是限定为固定分配局部置换。固定分配局部置换：固定分配局部置换：固定分配全局置换：固定分配全局置换：可变分配局部置换可变分配局部置换可变分配全局置换可变分配全局置换(3)内存管理策略内存管理策略不可能不可能第三十二页，本课

39、件共有70页&(1)(1)最佳淘汰算法最佳淘汰算法OPT(Optimal)OPT(Optimal)&这是Belady于1966年提出的一种理论上的算法。该算法每次都淘汰以后永不使用的，或者过最长的时间后才会被访问的页面。&显然，采用这种算法会保证最低的缺页率，但它是无法实现的，因为它必须知道页面“将来”的访问情况。不过，该算法仍有一定意义，可作为衡量其他算法优劣的一个标准。2.2.页面置换算法页面置换算法 第三十三页，本课件共有70页假定系统为某个进程分配了三个物理块，进程的访问顺假定系统为某个进程分配了三个物理块，进程的访问顺序为序为7 7，0 0，1 1，2 2，0 0，3 3，0 0，4

40、 4，2 2，3 3，0 0，3 3，2 2，1 1，2 2OPTOPT置换算法示例：置换算法示例：7，0，1，2，0，3，0，4，2，3，0，3，2，1，27 *7 0 *7 0 1 *2 0 1 *2 0 12 0 3 *2 0 32 4 3 *2 4 32 4 32 0 3 *2 0 32 0 32 1 3 *2 1 3缺页次数缺页次数8 8，成功访问次数，成功访问次数7 7次，次，缺页率缺页率f=8/15=53.33%f=8/15=53.33%第三十四页，本课件共有70页（2 2）先进先出淘汰算法）先进先出淘汰算法FIFOFIFO&这是最早出现的淘汰算法。&总是淘汰最先进入内存的页面。

41、总是淘汰最先进入内存的页面。它实现简单实现简单，只需把进程中已调入内存的页面，按先后次序链成一个队列，并设置一个所谓的替换指针，使它总是指向内存中最老的页面。&缺点：效率不高，缺点：效率不高，因为它与进程实际的运行规律不相适应，比如常用的全局变量所在的页面或者循环体所在页面都可能被它选为淘汰对象。出现belady现象。第三十五页，本课件共有70页&BeladyBelady现象：现象：采用FIFO算法时，如果对一个进程未分配它所要求的全部页面，有时就会出现分配的页面数增多，缺页率反而提高的异常现象。&BeladyBelady现象的描述：现象的描述：一个进程P要访问M个页，OS分配N个内存页面给进

42、程P；对一个访问序列S，发生缺页次数为PE（S,N）。当N增大时，PE(S,N)时而增大，时而减小。&BeladyBelady现象的原因：现象的原因：FIFO算法的置换特征与进程访问内存的动态特征是矛盾的，即被置换的页面并不是进程不会访问的。第三十六页，本课件共有70页FIFOFIFO淘汰算法示例：淘汰算法示例：7，0，1，2，0，3，0，4，2，3，0，3，2，1，27 *7 0 *7 0 1 *2 0 1 *2 0 12 3 1 *2 3 0 *4 3 0 *4 2 0 *4 2 3 *0 2 3 *0 2 30 2 30 1 3 *0 1 2 *3 3块内存时，缺页率块内存时，缺页率f=

43、12/15=80%f=12/15=80%；4 4块块f=8/15=53.33%f=8/15=53.33%7，0，1，2，0，3，0，4，2，3，0，3，2，1，27 *7 0 *7 0 1 *7 0 1 2*7 0 1 23 0 1 2*3 0 1 2 3 4 1 2*3 4 1 2 3 4 1 2 3 4 0 2*3 4 0 23 4 0 23 4 0 1*2 4 0 1*第三十七页，本课件共有70页练习练习:对如下的页面访问序列对如下的页面访问序列:1 2 3 4 1 2 5 1 2 3 4 5设进程开始运行时所有页面均在外存设进程开始运行时所有页面均在外存,采用采用FIFO淘汰算法淘汰算

44、法,计算进程所分的物理块计算进程所分的物理块分别为分别为3和和4时时,缺页率各是多少缺页率各是多少?第三十八页，本课件共有70页(3)(3)最近最久未使用算法最近最久未使用算法(LRU,(LRU,Least Recently UsedLeast Recently Used）根据页面调入内存后的使用情况，选择内存中最久未使用的页面被置换。这是局部性原理的合理近似，性能接近最佳算法。OPT算法使用页面将要被访问的时间，LRU算法使用页面最后一次被访问的时间。二者唯一的差别是：OPT是向后看的，而LRU是向前看的。7，0，1，2，0，3，0，4，2，3，0，3，2，1，27 *7 0 *7 0 1

45、*2 0 1 *2 0 12 0 3 *2 0 34 0 3 *4 0 2 *4 3 2 *0 3 2 *0 3 20 3 21 3 2 *1 3 2 10次，缺页率次，缺页率f=10/15=66.67%第三十九页，本课件共有70页LRULRU的两个实现算法：的两个实现算法：&计计时时法法：对于每一页面增设一个访问时间计时器，每当一个页面被访问时，就将当时的绝对时钟拷贝到对应的访问时间计时器中，这样系统记录了内存中所有页面最后一次被访问的时间。淘汰时，选取访问时间计时器的值最小的页面。&堆栈法：堆栈法：每当进程访问某页面时，便将该页面的页号从栈中移出，将它压入栈顶。栈顶始终是最新被访问的页面的

46、编号。栈底则是最近最久未被使用的页面的页面号。第四十页，本课件共有70页假定现有一进程所访问的页面的页面号序列为：假定现有一进程所访问的页面的页面号序列为：4 4，8 8，0 0，8 8，1 1，0 0，2 2，1 1，2 2，6 6&随着进程的访问，栈中页面号的变化情况随着进程的访问，栈中页面号的变化情况：4，8，0，8，1，0，1，2，1，2，6 2 1 2 6 1 0 1 1 2 1 2 0 8 8 1 0 0 0 0 1 8 8 0 0 8 8 8 8 8 0 4 4 4 4 4 4 4 4 4 4 8LRULRU的开销是很大的，必须有硬件的支持，完全由软件实现其的开销是很大的，必须有

47、硬件的支持，完全由软件实现其速度至少会减少速度至少会减少1010倍，因此倍，因此LRULRU近似算法更实用些。近似算法更实用些。第四十一页，本课件共有70页&这是一种LRU的近似算法，是通过对FIFO算法进行简单改造，结合页表中的访问位而得来一种淘汰算法。&该算法首先检查位于FIFO链链首的页，如果它的访问位为0，则选择该页淘汰；如果它的访问位为1，则清除其访问位，将它移至FIFO链的链尾，重复此算法的查找过程，直至遇到新链首页是一个访问位为0的较早进入内存的页为止，把它选为被淘汰的页。(4)(4)二次机会淘汰算法二次机会淘汰算法SC(Second Chance)SC(Second Chanc

48、e)第四十二页，本课件共有70页（5 5）时钟）时钟(Clock)(Clock)淘汰算法淘汰算法&缺点：就是需要把访问位为1的处于链首的页移至链尾，这需要一定的开销。一种改进的方法就是把进程所访问的页面链成一个环形链表，再设一个指针指向最老的页面，于是形成了一种简单实用的LRU近似算法时钟淘汰算法。&该算法首先检测指针所指的页面，如果它的访问位为0，则淘汰该页，新装入的页插入到此位置，然后指针前进一个位置；如果它的访问位为1，则清除为0，并将指针前进一个位置，继续检查访问位。重复此过程，直到找到访问位为0的页面为止。第四十三页，本课件共有70页算法流程参见书上第算法流程参见书上第153页。页。

49、第四十四页，本课件共有70页(6)(6)最近未用淘汰算法最近未用淘汰算法NUR(NUR(Not Used RecentlyNot Used Recently)&它把FIFO算法的思想与页面的访问位和修改位结合起来确定一个接近LRU算法的淘汰对象。&该算法每次都尽量选择最近最久未被写过的页面淘汰，这种干净的页面可以不被写回到磁盘。在实现时，为每一个页面设置初始值为0的访问位和修改位。当对某页面执行写操作时，其修改位和访问位均由硬件置成1；当对某页面执行读操作时，只有其访问位被硬件置成1。第四十五页，本课件共有70页按照下列次序选择被淘汰的页面：按照下列次序选择被淘汰的页面：访问位，修改位；直接淘

50、汰；访问位，修改位；淘汰之前写回外存；访问位，修改位；直接淘汰；访问位，修改位；淘汰之前写回外存；最近未使用淘汰算法就是最近未使用淘汰算法就是LRULRU的一种近似算法，它总是淘汰最近未的一种近似算法，它总是淘汰最近未使用的页，如果被淘汰的页在内存期间没有被修改过，该页可使用的页，如果被淘汰的页在内存期间没有被修改过，该页可不必重新写入外存，将新页覆盖到被淘汰的页上即可。不必重新写入外存，将新页覆盖到被淘汰的页上即可。访问位访问位A A0 0 表示该页未被访问过；表示该页未被访问过；1 1 表示该页已被访问过；表示该页已被访问过；修改位修改位M M 0 0 表示该页未被修改过表示该页未被修改过