《第四章 虚拟存储管理精选文档.ppt》由会员分享，可在线阅读，更多相关《第四章 虚拟存储管理精选文档.ppt（70页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第四章第四章 虚拟存储管理虚拟存储管理本讲稿第一页，共七十页第第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 存储管理实例存储管理实例本讲稿第二页，共七十页4.5 4.5 虚拟存储技术虚拟存储技术4.5.1 4.5.1 程序局部性原理程序局部性原理 4.5.2 4.5.2 虚拟存
2、储的实现虚拟存储的实现&虚拟内存技术(Virtual Memory)(Virtual Memory)诞生于1961年。&广泛使用是从上个世纪70年代初以后，今天几乎所有的操作系统都采用虚拟内存技术来管理内存。&这是一种利用虚拟存储器来逻辑扩充物理内存的技术。其基本思想是用用软软硬硬件件技技术术把把内内存存与与外外存存这这两两级级存存储储器器当当成成一一级级存存储储器器来来用用，从从而而给给用用户户提提供供了了一一个个比比内内存存也也比比任任何何应应用用程程序序大大得得多多的的虚虚拟拟存存储储器器，使使得得用用户户编编程程时时再再也也不不用用考考虑虑内内存存大大小小的的限限制了，给用户编程带来极
3、大的方便。制了，给用户编程带来极大的方便。&虚拟内存技术的实现也利用了自动覆盖和交换技术。本讲稿第三页，共七十页4.5.1 4.5.1 程序局部性原理程序局部性原理&1.1.局部性原理局部性原理(principle of locality)：指程序在执行过程中的一个较短时期内，所执行的指令地址和指令的操作数地址，分别局限于一定区域。&2.2.局部性主要表现：局部性主要表现：F时间局部性：时间局部性：是指一段指令在某一时间段内会被反复执行。是指一段指令在某一时间段内会被反复执行。即程序某一部分的数据或指令被重复性地访问，它们对应于即程序某一部分的数据或指令被重复性地访问，它们对应于程序结构中的循
4、环、子程序、常用到的变量及数据等程序结构中的循环、子程序、常用到的变量及数据等；F空间局部性空间局部性：是指一旦某一个存储单元被访问，那么它附是指一旦某一个存储单元被访问，那么它附近的单元也将很快被访问。这对应于程序结构中的顺序执行近的单元也将很快被访问。这对应于程序结构中的顺序执行的指令、线性数据结构以及在相邻位置存放的数据或变量等。的指令、线性数据结构以及在相邻位置存放的数据或变量等。而程序中的分支和调用子程序只是将程序的访问空间从一处而程序中的分支和调用子程序只是将程序的访问空间从一处移到另外一处，仍具有局部性。移到另外一处，仍具有局部性。本讲稿第四页，共七十页F排他性：排他性：程序运行
5、不但体现在时间、空间的局部性，还体现在某些程序段执行的排他性。即程序设计者编程时要考虑程序执行时所能遇到的各种情况，但具体到一次程序的执行，并不会发生所有的状况。因而因而某些程序段在进程整个运行期间，可能根本不使用，某些程序段在进程整个运行期间，可能根本不使用，如出错处理、分支语句等。如出错处理、分支语句等。因而，没有用到的程序段就不必调入内存。另外，有些程序段仅执行一次，以后就再也不会用到，这样的程序段也没有必要一直占用内存空间。&综上所述：综上所述：程序只要装入内存一部分就可以运行，当用到程序只要装入内存一部分就可以运行，当用到不在内存的部分时，再将其装入内存。不在内存的部分时，再将其装入
6、内存。换句话就是说程换句话就是说程序全部装入内存并不是程序运行的必要条件。序全部装入内存并不是程序运行的必要条件。本讲稿第五页，共七十页4.5.2 4.5.2 虚拟存储的实现虚拟存储的实现1.1.虚拟存储技术虚拟存储技术如果把程序部分装入内存，其余大部分放在外存，而程序又能运行，这样如果把程序部分装入内存，其余大部分放在外存，而程序又能运行，这样我们就拥有了一个比有限的实际内存空间大得多的、逻辑的虚拟内存空间。我们就拥有了一个比有限的实际内存空间大得多的、逻辑的虚拟内存空间。即用大容量的外存来模拟内存，这种存储模式就称之为虚拟存储技术。即用大容量的外存来模拟内存，这种存储模式就称之为虚拟存储技
7、术。2.2.虚拟技术实现的关键虚拟技术实现的关键(1)怎样才能发现欲执行的指令或数据不在内存怎样才能发现欲执行的指令或数据不在内存?简单有效方法就是进行标识简单有效方法就是进行标识(2)怎样将不在内存的部分调入进来怎样将不在内存的部分调入进来。通常系统采用中断技术完成调入工作。通常系统采用中断技术完成调入工作。(3)在内存中的作业如何组织？在内存中的作业如何组织？一个进程可被分为多次调入内存，这样很难保证进程在内存中占据一个连续的一个进程可被分为多次调入内存，这样很难保证进程在内存中占据一个连续的空间，实际上进程在内存中是离散存储的。空间，实际上进程在内存中是离散存储的。本讲稿第六页，共七十页
8、虚拟技术进一步说明虚拟技术进一步说明因而因而系统要提供必要的硬件支持系统要提供必要的硬件支持，如虚拟页式存，如虚拟页式存储中的页表机制、缺页中断机构以及相应的地址储中的页表机制、缺页中断机构以及相应的地址变换机构。变换机构。虚拟存储技术是虚拟存储技术是将内存与外存有机地结合在一起，从将内存与外存有机地结合在一起，从而得到一个容量很大的虚拟空间。而得到一个容量很大的虚拟空间。使用户感到有使用户感到有一个很大的内存，不用再考虑内存的容量限制。一个很大的内存，不用再考虑内存的容量限制。虚存虽然比内存要大得多，但不可能无限大，虚存虽然比内存要大得多，但不可能无限大，其其大小要受到外存空间的限制以及大小
9、要受到外存空间的限制以及CPU地址所能表示地址所能表示范围的限制。范围的限制。本讲稿第七页，共七十页&大程序：可在较小的可用内存中执行较大的用户程序；&大的用户空间：提供给用户可用的虚拟内存空间通常大于物理内存(real memory)&并发：可在内存中容纳更多程序并发执行；&易于开发：与覆盖技术比较，不必影响编程时的程序结构3.3.引入虚拟存储技术的好处引入虚拟存储技术的好处F总容量不超过物理内存和外存交换区容量之和。其运行速总容量不超过物理内存和外存交换区容量之和。其运行速度接近于内存，每位的成本又接近于外存，是一种性能非常度接近于内存，每位的成本又接近于外存，是一种性能非常优越的存储管理
10、技术优越的存储管理技术 本讲稿第八页，共七十页4.4.虚拟存储技术的特征虚拟存储技术的特征&不连续性不连续性：物理内存分配的不连续，虚拟地址空间使用的不连续（数据段和栈段之间的空闲空间，共享段和动态链接库占用的空间）&部分交换：部分交换：与交换技术相比较，虚拟存储的调入和调出是对部分虚拟地址空间进行的；&大空间：大空间：通过物理内存和快速外存相结合，提供大范围的虚拟地址空间虚拟存储技术的种类：虚拟存储技术的种类：虚拟页式虚拟段式虚拟段页式本讲稿第九页，共七十页4.6 4.6 虚拟页式存储管理虚拟页式存储管理 4.6.1 4.6.1 虚拟页式存储的实现虚拟页式存储的实现 4.6.2 4.6.2
11、页面分配策略页面分配策略 4.6.3 4.6.3 页面置换方法页面置换方法4.6.4 4.6.4 虚拟页式存储的优缺点虚拟页式存储的优缺点本讲稿第十页，共七十页返回&1.1.基本原理基本原理&系统自动地将作业的地址空间分页，将系统的主存空间分块，页与块等大小，在作业运行前，只把初始需要的一部分页面装入内存块里，运行中需要访问自己地址空间中的但当前不在内存的页面时产生缺页中断，由缺页中断服务程序将所需的页面调入内存，若此时内存中没有空闲物理块安置请求调入的新页面，则系统按预定的置换策略自动选择一个或一些在内存的页面，把它们换出到外存。&这里的请求调入和置换功能请求调入和置换功能都是比实分页存储管
12、理增加的内容，是实现虚拟存储的主要功能。4.6.1 4.6.1 虚拟页式存储的实现虚拟页式存储的实现 本讲稿第十一页，共七十页页面的动态调度步骤：页面的动态调度步骤：1、找到被访问页面在外存的地址；、找到被访问页面在外存的地址；2、在内存中找一个空闲页面；、在内存中找一个空闲页面；（1）如果没有，按照淘汰算法选择一个内存页）如果没有，按照淘汰算法选择一个内存页面；面；（2）将此内存页面写回外存，修改页表及页）将此内存页面写回外存，修改页表及页面分配表；面分配表；3、读入所需的页面，修改页表及页面分配表；、读入所需的页面，修改页表及页面分配表；4、重新启动进程执行被中断的指令。、重新启动进程执行
13、被中断的指令。本讲稿第十二页，共七十页&标记某页是否在内存，用于查询标记某页是否在内存，用于查询要访问的要访问的页在不在内存。页表如下：页在不在内存。页表如下：页号 物理块号 状态位P访问位A修改位M外存地址2.2.页表机制页表机制其中：外存地址指出该页在外存的地址，供调入该页时用；状态为指示该页是否在内存，供程序访问时用，也是检查是否缺页的标志位，如置1表示在内存；访问位或访问字段则是该页被访问过的标志或该页被访问过的次数；修改位表示该页是否被修改过；存取控制字段则是用来限制页面被安全共享的。本讲稿第十三页，共七十页3.3.动态地址变换动态地址变换&在虚拟页式存储中，应采用动态地址变换方式，
14、因为某一欲执行的指在虚拟页式存储中，应采用动态地址变换方式，因为某一欲执行的指令可能不在内存，只能在指令执行之前完成地址变换。令可能不在内存，只能在指令执行之前完成地址变换。任一作业都应任一作业都应在自己的虚拟地址空间中执行，在自己的虚拟地址空间中执行，所以要为用户作业设置一个虚拟地所以要为用户作业设置一个虚拟地址指针址指针VP，虚拟地址依然是由页号和页内偏移地址组成的。，虚拟地址依然是由页号和页内偏移地址组成的。&系统总是执行系统总是执行VP虚指针所指向的指令，为了将虚拟地址虚指针所指向的指令，为了将虚拟地址VP变换为对变换为对应的实存地址，因此应的实存地址，因此先要查找页表。若从页表中查出
15、此页不在内存（状先要查找页表。若从页表中查出此页不在内存（状态位为态位为0），则产生一个缺页中断。），则产生一个缺页中断。此时，进程暂停当前指令执行，此时，进程暂停当前指令执行，CPU转去执行缺页中断处理程序。转去执行缺页中断处理程序。若该页已在内存，若该页已在内存，则指令的地址映则指令的地址映射过程与页式存储是一样的。即将块号和页内地址相并接形成物理地射过程与页式存储是一样的。即将块号和页内地址相并接形成物理地址址IP，处理器再从，处理器再从IP中取指令执行。中取指令执行。本讲稿第十四页，共七十页4.4.缺页中断缺页中断本讲稿第十五页，共七十页5.5.缺页率缺页率&虽然通过缺页中断将所需要的
16、页调入内存，但缺页中断虽然通过缺页中断将所需要的页调入内存，但缺页中断的频繁发生会严重影响程序执行的效率。为了标识缺页的频繁发生会严重影响程序执行的效率。为了标识缺页中断发生的频度，可以引入缺页率来表示。中断发生的频度，可以引入缺页率来表示。&设进程在其执行期间共进行了设进程在其执行期间共进行了S S次访页操作，其中成功访页次访页操作，其中成功访页次数为次数为A A（访问时该页在主存），不成功的访页次数为（访问时该页在主存），不成功的访页次数为B B（即发生了缺页中断），显然有：（即发生了缺页中断），显然有：S=A+BS=A+B，&则该进程的缺页率则该进程的缺页率f f定义为：定义为：f fB
17、/SB/S。&显然缺页率越低越好。显然缺页率越低越好。本讲稿第十六页，共七十页4.6.2 4.6.2 页面分配策略页面分配策略&虚拟存储管理在进行页面分配时，要考虑这样虚拟存储管理在进行页面分配时，要考虑这样的问题：空闲页面如何管理；采用什么样的分的问题：空闲页面如何管理；采用什么样的分配策略；为进程分配多少物理块比较合适；在配策略；为进程分配多少物理块比较合适；在什么时间进行页面分配等。什么时间进行页面分配等。本讲稿第十七页，共七十页1.1.空闲页面管理空闲页面管理&同页式存储管理相似，虚拟存储方式下的空闲页面的管理也可以采用同页式存储管理相似，虚拟存储方式下的空闲页面的管理也可以采用位示位
18、示图图或或空闲页面链空闲页面链的形式。的形式。&由于主存中所有进程的虚拟地址空间之和远大于主存空间，因此进由于主存中所有进程的虚拟地址空间之和远大于主存空间，因此进程执行时常发生缺页中断，这样不断地调入新页，很快就使主存空程执行时常发生缺页中断，这样不断地调入新页，很快就使主存空间饱和。以后再发生缺页时，要先淘汰一页才能装入新页，这使得间饱和。以后再发生缺页时，要先淘汰一页才能装入新页，这使得缺页处理时间过长，减缓了进程的执行速度，从而影响到系统的性缺页处理时间过长，减缓了进程的执行速度，从而影响到系统的性能。能。&在实际的系统中，总是维持一定数量的空闲块，而不是耗尽所有在实际的系统中，总是维
19、持一定数量的空闲块，而不是耗尽所有的空闲块。即的空闲块。即空闲块数可以在某一区间浮动空闲块数可以在某一区间浮动，一旦空闲块数小于下，一旦空闲块数小于下限值，系统就进行页面置换，以释放出一些空闲块，使得总的空限值，系统就进行页面置换，以释放出一些空闲块，使得总的空闲块数不超过系统规定的上限值即可。即系统设置专门的独立进闲块数不超过系统规定的上限值即可。即系统设置专门的独立进程负责页面置换，以保证链表的适当规模。程负责页面置换，以保证链表的适当规模。本讲稿第十八页，共七十页2 2 分配策略（内存）分配策略（内存）&可变分配：可变分配：是指一个进程所拥有的物理块数是不定的，这种分配方式是指一个进程所
20、拥有的物理块数是不定的，这种分配方式称之为可变分配。称之为可变分配。&固定分配固定分配是指为每个进程分配一固定页数的内存空间，在整个运行是指为每个进程分配一固定页数的内存空间，在整个运行期间都不再改变。期间都不再改变。&平均分配算法，平均分配算法，是将系统中所有可供分配的物理块，平均分配给每是将系统中所有可供分配的物理块，平均分配给每一个进程。例如，当系统中有一个进程。例如，当系统中有80个空闲块，个空闲块，4个进程时，每个进程可分个进程时，每个进程可分得得20个物理块。这种平均分配方式因其未考虑各进程本身的大小，会个物理块。这种平均分配方式因其未考虑各进程本身的大小，会造成事实上的不公平。如
21、有一个进程其大小为造成事实上的不公平。如有一个进程其大小为100页，只分配给它页，只分配给它20个块，这样它必将会有很高的缺页率；而另一个进程只有个块，这样它必将会有很高的缺页率；而另一个进程只有10页，却页，却有有10个块在闲置未用。所以在平均的思想下，还要考虑进程的个块在闲置未用。所以在平均的思想下，还要考虑进程的大小。大小。本讲稿第十九页，共七十页&按比例分配算法，按比例分配算法，根据进程的大小按比例分配空闲块。设系统根据进程的大小按比例分配空闲块。设系统中现有中现有m个进程、个进程、n个空闲块，每个进程拥有的页数为个空闲块，每个进程拥有的页数为Si，则系统中，则系统中所有进程页数之和为
22、：所有进程页数之和为：S=S1+S2+S3+Sm 则为每个进程分配的物理块数为：则为每个进程分配的物理块数为：Bi=（Si/S）n，Bi应向下取整。应向下取整。&优先权分配算法，优先权分配算法，为优先权高的作业分配较多的内存空间，这为优先权高的作业分配较多的内存空间，这样可以使重要或紧迫的任务尽快完成。这时可以将内存中的空闲块样可以使重要或紧迫的任务尽快完成。这时可以将内存中的空闲块分成两部分：一部分按比例分配给各进程，另一部分则根据各进程分成两部分：一部分按比例分配给各进程，另一部分则根据各进程的优先权，适当地为其增加相应份额。的优先权，适当地为其增加相应份额。本讲稿第二十页，共七十页2 2
23、 分配策略（外存）分配策略（外存）1、静态分配、静态分配 一个进程在运行之前，将其页面全部装一个进程在运行之前，将其页面全部装入外存。当某一外存页面被调入内存时，入外存。当某一外存页面被调入内存时，并不释放所占用的外存页面。并不释放所占用的外存页面。2、动态分配、动态分配 一个进程在运行之前，仅将未装入内存一个进程在运行之前，仅将未装入内存的那部分页面装入外存。当某一外存页的那部分页面装入外存。当某一外存页面被调入内存时，释放所占用的外存页面被调入内存时，释放所占用的外存页面。面。本讲稿第二十一页，共七十页3.3.工作集工作集&(1)(1)为保证进程能正常运行最少需要多少物理块。为保证进程能正
24、常运行最少需要多少物理块。从理论上讲，进程只要获得从理论上讲，进程只要获得一个物理块一个物理块就可以运行。但是进程正常运行就可以运行。但是进程正常运行所需的最少物理块数与计算机的硬件结构有关，取决于指令的格式、功所需的最少物理块数与计算机的硬件结构有关，取决于指令的格式、功能和寻址方式。能和寻址方式。由于分页是系统的行为，由于分页是系统的行为，可能会出现下面的情景：可能会出现下面的情景：由此可见，由此可见，系统应保证任一条指令执行系统应保证任一条指令执行时，其所涉及的虚拟地址所在的页都时，其所涉及的虚拟地址所在的页都应在内存中。这个页数就是进程所需应在内存中。这个页数就是进程所需要的最小块数要
25、的最小块数，若系统为进程所分配的，若系统为进程所分配的物理块数少于此值时，进程将无法运行。物理块数少于此值时，进程将无法运行。123456涉涉及及6 6次次缺缺页页中中断断的的指指令令指令指令copy A to B数据数据A：数据数据B：本讲稿第二十二页，共七十页&(2)(2)为使进程能有效地工作，应为它分配多少物理块合适为使进程能有效地工作，应为它分配多少物理块合适&随着为每个进程所分配物理块数目的减少，将使进程执行中的缺页率随着为每个进程所分配物理块数目的减少，将使进程执行中的缺页率提高，导致非生产性开销过大，从而降低了进程的执行速度，严重时提高，导致非生产性开销过大，从而降低了进程的执行
26、速度，严重时导致进程不能向前推进。最少物理块数只能保证程序能执行下去，而导致进程不能向前推进。最少物理块数只能保证程序能执行下去，而不是最合适的块数。不是最合适的块数。&!在在19681968年，年，DenningDenning提出了工作集理论。提出了工作集理论。所谓所谓工作集工作集就是进程在就是进程在某段时间里实际上要访问的页的集合。某段时间里实际上要访问的页的集合。依据程序执行时的局部特依据程序执行时的局部特性，可以利用程序过去的行为来估计它未来的行为。故性，可以利用程序过去的行为来估计它未来的行为。故定义运行进定义运行进程在程在t tw w到到t t这个时间间隔内所访问的页的集合为该进程
27、在时间这个时间间隔内所访问的页的集合为该进程在时间t t的工作的工作集，记为集，记为W W（t t，w w）。）。并把变量并把变量w w称之为称之为“工作集窗口尺寸工作集窗口尺寸”，工作集，工作集中所包含的页面数称为中所包含的页面数称为“工作集尺寸工作集尺寸”，记为，记为|W(t,w)|W(t,w)|。本讲稿第二十三页，共七十页例如例如:访问页面：访问页面：Twt-wtW(t,w)=2,3,5,8访问页面：访问页面：Twwt1t2W(t1,w)=2,3,5,8W(t2,w)=3,5,7,8,9本讲稿第二十四页，共七十页(3)(3)工作集的应用工作集的应用&工作集工作集W W（t t，w w）是
28、二元函数，随）是二元函数，随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。&工作集窗口尺寸与缺页率关系密切，工作集窗口尺寸与缺页率关系密切，若若w w增
29、大，工作集尺寸增大，工作集尺寸|W|W|随之增加随之增加（即所含的页面数增多），缺页率就会下降。（即所含的页面数增多），缺页率就会下降。倘若倘若w w含盖了整个含盖了整个作业虚拟空间，缺页率降为作业虚拟空间，缺页率降为0 0，也就失去了虚存意义；反之若，也就失去了虚存意义；反之若w w选取选取过小，将引起频繁缺页，导致系统性能下降。二者之间的关系可以过小，将引起频繁缺页，导致系统性能下降。二者之间的关系可以如图所示。如图所示。本讲稿第二十五页，共七十页&虚存中并不是要取消缺页率，而是要使缺页率维持在一个较低虚存中并不是要取消缺页率，而是要使缺页率维持在一个较低的水平上。因此可以取拐点所对应的工
30、作集尺寸作为分给进程的水平上。因此可以取拐点所对应的工作集尺寸作为分给进程的物理块数，实验分析表明，这个数应是进程总页面数的一半。的物理块数，实验分析表明，这个数应是进程总页面数的一半。即一个进程应获得其所需页数一半的空间时，再进入内存执行即一个进程应获得其所需页数一半的空间时，再进入内存执行。本讲稿第二十六页，共七十页4.4.页面调入时机页面调入时机 即何时将一个页面由外存调入内存。即何时将一个页面由外存调入内存。预调页策略预调页策略&也称先行调度，即一页面被访问前就已经预先置入内存，也称先行调度，即一页面被访问前就已经预先置入内存，以减少今后的缺页率。以减少今后的缺页率。&主要适于进程的许
31、多页存放在外存的连续区域中的情况。有主要适于进程的许多页存放在外存的连续区域中的情况。有的系统结合请求调入使用，即每次缺页时装入多个页面。的系统结合请求调入使用，即每次缺页时装入多个页面。优点：优点：提高调页的提高调页的I/OI/O效率。效率。缺点：缺点：基于预测，若调入的页在以后很少被访问，则效率低。基于预测，若调入的页在以后很少被访问，则效率低。预调页的成功率仅约预调页的成功率仅约50%50%，常用于程序装入时的调页。，常用于程序装入时的调页。本讲稿第二十七页，共七十页&请求调页策略请求调页策略&当当发发生生页页面面故故障障时时进进行行调调度度，即即当当进进程程访访问问不不在在内内存存的的
32、页页面面引引发发缺缺页页中中断断时时，由由系系统统根根据据这这种种访访问问请请求求把把所所缺缺页面装入内存。页面装入内存。&优优点点：由由请请求求调调入入策策略略装装入入的的页页一一定定会会被被访访问问，再再加加之之比比较较容容易易实实现现，故故在在目目前前的的虚虚拟拟存存储储器器中中，大大多多采采用用此此策策略。略。&缺点：缺点：每次仅调入一页，增加了磁盘每次仅调入一页，增加了磁盘I/OI/O的启动频率。的启动频率。本讲稿第二十八页，共七十页&在请求分页系统中，常把外存分为两部分：在请求分页系统中，常把外存分为两部分：一部分是文一部分是文件区，用于存放文件；件区，用于存放文件；另一部分是对换
33、区，用于存放另一部分是对换区，用于存放对换页面。对换页面。通常，对换区的磁盘输入输出速度比文件区通常，对换区的磁盘输入输出速度比文件区的高，这是因为对换区所规定的盘块要比文件区的大得的高，这是因为对换区所规定的盘块要比文件区的大得多。多。从交换区调入从交换区调入&若系统拥有足够的对换区空间，可在进程运行前，将与该进若系统拥有足够的对换区空间，可在进程运行前，将与该进程有关的文件拷贝到对换区。以后就从对换区调入所需页面，程有关的文件拷贝到对换区。以后就从对换区调入所需页面，以提高调页速度。以提高调页速度。5.5.从何处调入页面从何处调入页面 本讲稿第二十九页，共七十页 从交换区及文件区调入从交换
34、区及文件区调入&若系统缺少足够的对换区空间，则在交换区中只保存被修改过的若系统缺少足够的对换区空间，则在交换区中只保存被修改过的页面。因为未被修改的页面在文件区中有副本。因此凡是没被修页面。因为未被修改的页面在文件区中有副本。因此凡是没被修改的页，均从文件区调入；而已修改过的页面则从交换区调入。改的页，均从文件区调入；而已修改过的页面则从交换区调入。UNIX方式方式&与进程有关的文件都放在文件区，故凡是未运行过的页面，都应从文件与进程有关的文件都放在文件区，故凡是未运行过的页面，都应从文件区调入。而对于曾经运行过而又被换出的页面，总是存放在对换区中。区调入。而对于曾经运行过而又被换出的页面，总
35、是存放在对换区中。因此在下次调入时，应从对换区调入。由于在因此在下次调入时，应从对换区调入。由于在UNIX系统中允许页面系统中允许页面共享，因此，某进程所请求的页面有可能已由其它进程调入内存，共享，因此，某进程所请求的页面有可能已由其它进程调入内存，此时也就无须再从对换区调入。此时也就无须再从对换区调入。本讲稿第三十页，共七十页1.1.页面置换方式页面置换方式当内存空间已没有空闲页面而又要调入新页时，必须当内存空间已没有空闲页面而又要调入新页时，必须采用一定的算采用一定的算法在内存中选择某一页面淘汰，所采用的算法称之为页面置换算法。法在内存中选择某一页面淘汰，所采用的算法称之为页面置换算法。如
36、果被淘汰的页面在内存期间曾被修改过，还要将此页重新写回到外存，以如果被淘汰的页面在内存期间曾被修改过，还要将此页重新写回到外存，以便保留最新的副本。然后再换进新的页面。便保留最新的副本。然后再换进新的页面。(1)页面置换方式页面置换方式页面淘汰可以在整个内存空间范围内进行，称之为页面淘汰可以在整个内存空间范围内进行，称之为全局置换全局置换。也可以只。也可以只在一个进程空间范围内考虑，称之为在一个进程空间范围内考虑，称之为局部置换局部置换。即当某一进程请求即当某一进程请求新页时，而该进程又没有空闲块，则只能淘汰自己的一个页面而不新页时，而该进程又没有空闲块，则只能淘汰自己的一个页面而不能淘汰其它
37、进程的页面。能淘汰其它进程的页面。4.6.3 4.6.3 页面置换方法页面置换方法本讲稿第三十一页，共七十页 (2)(2)空闲块分配方式空闲块分配方式&若为进程分配固定的物理块数，在其执行期间再也不改变，则称若为进程分配固定的物理块数，在其执行期间再也不改变，则称为为固定分配。固定分配。初始进程块数的多少难以确定。若太少，则缺页频繁，初始进程块数的多少难以确定。若太少，则缺页频繁，系统开销大；若太多，则并发进程数目少，造成系统开销大；若太多，则并发进程数目少，造成CPUCPU空闲或其它资源空闲或其它资源空闲的情况。空闲的情况。&为进程分配的物理块数在其运行期间是可变的，则称为为进程分配的物理块
38、数在其运行期间是可变的，则称为可变分配可变分配。进程在运行中，系统可调整为该进程分配的物理块，直至进程的缺进程在运行中，系统可调整为该进程分配的物理块，直至进程的缺页率达到适当程度。页率达到适当程度。在页面置换算法讨论中，为了比较各种方法的优劣，总在页面置换算法讨论中，为了比较各种方法的优劣，总是限定为固定分配局部置换。是限定为固定分配局部置换。固定分配局部置换：固定分配局部置换：固定分配全局置换：固定分配全局置换：可变分配局部置换可变分配局部置换可变分配全局置换可变分配全局置换(3)内存管理策略内存管理策略不可能不可能本讲稿第三十二页，共七十页&(1)(1)最佳淘汰算法最佳淘汰算法OPT(O
39、ptimal)OPT(Optimal)&这是Belady于1966年提出的一种理论上的算法。该算法每次都淘汰以后永不使用的，或者过最长的时间后才会被访问的页面。&显然，采用这种算法会保证最低的缺页率，但它是无法实现的，因为它必须知道页面“将来”的访问情况。不过，该算法仍有一定意义，可作为衡量其他算法优劣的一个标准。2.2.页面置换算法页面置换算法 本讲稿第三十三页，共七十页假定系统为某个进程分配了三个物理块，进程的访问顺序假定系统为某个进程分配了三个物理块，进程的访问顺序为为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 2O
40、PTOPT置换算法示例：置换算法示例：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%本讲稿第三十四页，共七十页（2 2）先进先出淘汰算法）先进先出淘汰算法FIFOFIFO&这是最早出现的淘汰算法。&总是淘汰最先进入内存的页面。总是淘汰最先进入内存的页面。它实现简单实现简单，只需把进程中已调
41、入内存的页面，按先后次序链成一个队列，并设置一个所谓的替换指针，使它总是指向内存中最老的页面。&缺点：效率不高，缺点：效率不高，因为它与进程实际的运行规律不相适应，比如常用的全局变量所在的页面或者循环体所在页面都可能被它选为淘汰对象。出现belady现象。本讲稿第三十五页，共七十页&BeladyBelady现象：现象：采用FIFO算法时，如果对一个进程未分配它所要求的全部页面，有时就会出现分配的页面数增多，缺页率反而提高的异常现象。&BeladyBelady现象的描述：现象的描述：一个进程P要访问M个页，OS分配N个内存页面给进程P；对一个访问序列S，发生缺页次数为PE（S,N）。当N增大时，
42、PE(S,N)时而增大，时而减小。&BeladyBelady现象的原因：现象的原因：FIFO算法的置换特征与进程访问内存的动态特征是矛盾的，即被置换的页面并不是进程不会访问的。本讲稿第三十六页，共七十页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=12/15=80%f=12/15=80%；4 4块块f=8/15=5
43、3.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*本讲稿第三十七页，共七十页练习练习:对如下的页面访问序列对如下的页面访问序列:1 2 3 4 1 2 5 1 2 3 4 5设进程开始运行时所有页面均在外存设进程开始运行时所有页面均在外存,采用采用FIFO淘汰算法淘汰算法,计算进程所分的物理块计算进程所分的物理块分别为分别为3和和4时时,
44、缺页率各是多少缺页率各是多少?本讲稿第三十八页，共七十页(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 *2 0 1 *2 0 12 0 3 *2 0 34 0 3 *4 0
45、2 *4 3 2 *0 3 2 *0 3 20 3 21 3 2 *1 3 2 10次，缺页率次，缺页率f=10/15=66.67%本讲稿第三十九页，共七十页LRULRU的两个实现算法：的两个实现算法：&计计时时法法：对于每一页面增设一个访问时间计时器，每当一个页面被访问时，就将当时的绝对时钟拷贝到对应的访问时间计时器中，这样系统记录了内存中所有页面最后一次被访问的时间。淘汰时，选取访问时间计时器的值最小的页面。&堆栈法：堆栈法：每当进程访问某页面时，便将该页面的页号从栈中移出，将它压入栈顶。栈顶始终是最新被访问的页面的编号。栈底则是最近最久未被使用的页面的页面号。本讲稿第四十页，共七十页假定
46、现有一进程所访问的页面的页面号序列为：假定现有一进程所访问的页面的页面号序列为：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的开销是很大的，必须有硬件的支持，完全由软件实现的开销是很大的，必须有硬件的支持，完全由软件实现其速度至少会减少其速度至少会减少1010倍，因此倍，
47、因此LRULRU近似算法更实用些。近似算法更实用些。本讲稿第四十一页，共七十页&这是一种LRU的近似算法，是通过对FIFO算法进行简单改造，结合页表中的访问位而得来一种淘汰算法。&该算法首先检查位于FIFO链链首的页，如果它的访问位为0，则选择该页淘汰；如果它的访问位为1，则清除其访问位，将它移至FIFO链的链尾，重复此算法的查找过程，直至遇到新链首页是一个访问位为0的较早进入内存的页为止，把它选为被淘汰的页。(4)(4)二次机会淘汰算法二次机会淘汰算法SC(Second Chance)SC(Second Chance)本讲稿第四十二页，共七十页（5 5）时钟）时钟(Clock)(Clock)
48、淘汰算法淘汰算法&缺点：就是需要把访问位为1的处于链首的页移至链尾，这需要一定的开销。一种改进的方法就是把进程所访问的页面链成一个环形链表，再设一个指针指向最老的页面，于是形成了一种简单实用的LRU近似算法时钟淘汰算法。&该算法首先检测指针所指的页面，如果它的访问位为0，则淘汰该页，新装入的页插入到此位置，然后指针前进一个位置；如果它的访问位为1，则清除为0，并将指针前进一个位置，继续检查访问位。重复此过程，直到找到访问位为0的页面为止。本讲稿第四十三页，共七十页算法流程参见书上第算法流程参见书上第153页。页。本讲稿第四十四页，共七十页(6)(6)最近未用淘汰算法最近未用淘汰算法NUR(NU
49、R(Not Used RecentlyNot Used Recently)&它把FIFO算法的思想与页面的访问位和修改位结合起来确定一个接近LRU算法的淘汰对象。&该算法每次都尽量选择最近最久未被写过的页面淘汰，这种干净的页面可以不被写回到磁盘。在实现时，为每一个页面设置初始值为0的访问位和修改位。当对某页面执行写操作时，其修改位和访问位均由硬件置成1；当对某页面执行读操作时，只有其访问位被硬件置成1。本讲稿第四十五页，共七十页按照下列次序选择被淘汰的页面：按照下列次序选择被淘汰的页面：访问位，修改位；直接淘汰；访问位，修改位；淘汰之前写回外存；访问位，修改位；直接淘汰；访问位，修改位；淘汰之
50、前写回外存；最近未使用淘汰算法就是最近未使用淘汰算法就是LRULRU的一种近似算法，它总是淘汰最近未使用的一种近似算法，它总是淘汰最近未使用的页，如果被淘汰的页在内存期间没有被修改过，该页可不必重新写入的页，如果被淘汰的页在内存期间没有被修改过，该页可不必重新写入外存，将新页覆盖到被淘汰的页上即可。外存，将新页覆盖到被淘汰的页上即可。访问位访问位A A0 0 表示该页未被访问过；表示该页未被访问过；1 1 表示该页已被访问过；表示该页已被访问过；修改位修改位M M 0 0 表示该页未被修改过表示该页未被修改过 1 1 表示该页已被修改过表示该页已被修改过本讲稿第四十六页，共七十页算法步骤：见书