第四章虚拟存储管理_第1页
第四章虚拟存储管理_第2页
第四章虚拟存储管理_第3页
第四章虚拟存储管理_第4页
第四章虚拟存储管理_第5页
已阅读5页,还剩62页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

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 虚拟存储的实现虚拟存储的实现& 虚拟内存技术(V

2、irtual Memory)诞生于1961年。& 广泛使用是从上个世纪70年代初以后,今天几乎所有的操作系统都采用虚拟内存技术来管理内存。&这是一种利用虚拟存储器来逻辑扩充物理内存的技术。其基本思想是用软硬件技术把内存与外存这两级存储器当成一级存储器来用,从而给用户提供了一个比内存也比任何应用程序大得多的虚拟存储器,使得用户编程时再也不用考虑内存大小的限制了,给用户编程带来极大的方便。&虚拟内存技术的实现也利用了自动覆盖和交换技术。 4.5.1 4.5.1 程序局部性原理程序局部性原理&1.1.局部性原理局部性原理(principle of locality):

3、 指程序在执行过程中的一个较短时期内,所执行的指令地址和指令的操作数地址,分别局限于一定区域。&2.2.局部性主要表现:局部性主要表现:F时间局部性:是指一段指令在某一时间段内会被反复执行。即程序某一部时间局部性:是指一段指令在某一时间段内会被反复执行。即程序某一部分的数据或指令被重复性地访问,它们对应于程序结构中的循环、子程序、分的数据或指令被重复性地访问,它们对应于程序结构中的循环、子程序、常用到的变量及数据等常用到的变量及数据等 ;F 空间局部性空间局部性:是指一旦某一个存储单元被访问,那么它附近的单元也将很快被访问。是指一旦某一个存储单元被访问,那么它附近的单元也将很快被访问。

4、这对应于程序结构中的顺序执行的指令、线性数据结构以及在相邻位置存放的数据或这对应于程序结构中的顺序执行的指令、线性数据结构以及在相邻位置存放的数据或变量等。而程序中的分支和调用子程序只是将程序的访问空间从一处移到另外一处,变量等。而程序中的分支和调用子程序只是将程序的访问空间从一处移到另外一处,仍具有局部性。仍具有局部性。F排他性:排他性:程序运行不但体现在时间、空间的局部性,还体现在某些程序段执行的排他性。即程序设计者编程时要考虑程序执行时所能遇到的各种情况,但具体到一次程序的执行,并不会发生所有的状况。因而某些程序段因而某些程序段在进程整个运行期间,可能根本不使用,如出错处理、分支语在进程

5、整个运行期间,可能根本不使用,如出错处理、分支语句等。句等。因而,没有用到的程序段就不必调入内存。另外,有些程序段仅执行一次,以后就再也不会用到,这样的程序段也没有必要一直占用内存空间。 &综上所述:程序只要装入内存一部分就可以运行,当用到不在内综上所述:程序只要装入内存一部分就可以运行,当用到不在内存的部分时,再将其装入内存。换句话就是说程序全部装入内存存的部分时,再将其装入内存。换句话就是说程序全部装入内存并不是程序运行的必要条件。并不是程序运行的必要条件。 4.5.2 4.5.2 虚拟存储的实现虚拟存储的实现1.1.虚拟存储技术虚拟存储技术 如果把程序部分装入内存,其余大部分放在

6、外存,而程序又能运行,这样我们就拥有了一个比有限的实际内存空间大得多的、逻辑的虚拟内存空间。即用大容量的外存来模拟内存,这种存储模式就称之为虚拟存储技术。 2.2.虚拟技术实现的关键虚拟技术实现的关键(1)怎样才能发现欲执行的指令或数据不在内存怎样才能发现欲执行的指令或数据不在内存? 简单有效方法就是进行标识简单有效方法就是进行标识(2)怎样将不在内存的部分调入进来。怎样将不在内存的部分调入进来。 通常系统采用中断技术完成调入工作。通常系统采用中断技术完成调入工作。(3)在内存中的作业如何组织?在内存中的作业如何组织? 一个进程可被分为多次调入内存,这样很难保证进程在内存中占据一个连续的一个进

7、程可被分为多次调入内存,这样很难保证进程在内存中占据一个连续的空间,实际上进程在内存中是离散存储的。空间,实际上进程在内存中是离散存储的。 虚拟技术进一步说明虚拟技术进一步说明 系统要提供必要的硬件支持,如虚拟页式存储中的页表机制、缺页中断机构以及相应的地址变换机构。 虚拟存储技术是将内存与外存有机地结合在一起,从而得到一个容量很大的虚拟空间。使用户感到有一个很大的内存,不用再考虑内存的容量限制。 虚存虽然比内存要大得多,但不可能无限大,其大小要受到外存空间的限制以及CPU地址所能表示范围的限制。&大程序:可在较小的可用内存中执行较大的用户程序;大程序:可在较小的可用内存中执行较大的用

8、户程序;&大的用户空间:提供给用户可用的虚拟内存空间通常大于大的用户空间:提供给用户可用的虚拟内存空间通常大于物理内存物理内存(real memory)(real memory)&并发:可在内存中容纳更多程序并发执行;并发:可在内存中容纳更多程序并发执行;&易于开发:与覆盖技术比较,不必影响编程时的程序结构易于开发:与覆盖技术比较,不必影响编程时的程序结构3.3.引入虚拟存储技术的好处引入虚拟存储技术的好处总容量不超过物理内存和外存交换区容量之和。其运行速度接近于内存,每位的成本又接近于外存,是一种性能非常优越的存储管理技术 4. 4. 虚拟存储技术的特征虚拟存储技术的

9、特征&不连续性:物理内存分配的不连续,虚拟地址空间使用的不连续(数据段和栈段之间的空闲空间,共享段和动态链接库占用的空间)&部分交换:与交换技术相比较,虚拟存储的调入和调出是对部分虚拟地址空间进行的;&大空间:通过物理内存和快速外存相结合,提供大范围的虚拟地址空间虚拟存储技术的种类:虚拟页式虚拟段式虚拟段页式 4.6 4.6 虚拟页式存储管理虚拟页式存储管理 4.6.1 4.6.1 虚拟页式存储的实现虚拟页式存储的实现 4.6.2 4.6.2 页面分配策略页面分配策略 4.6.3 4.6.3 页面置换方法页面置换方法 4.6.4 4.6.4 虚拟页式存储的优缺点虚拟页式

10、存储的优缺点返回&系统自动地将作业的地址空间分页,将系统的主存空间分块,页与块等大小。&在作业运行前,只把初始需要的一部分页面装入内存块里,运行中需要访问自己地址空间中的但当前不在内存的页面时产生缺页中断,由缺页中断服务程序将所需的页面调入内存。&若此时内存中没有空闲物理块安置请求调入的新页面,则系统按预定的置换策略自动选择一个或一些在内存的页面,把它们换出到外存。&这里的请求调入和置换功能都是比实分页存储管理增加的内容,是实现虚拟存储的主要功能。 4.6.1 4.6.1 虚拟页式存储的实现虚拟页式存储的实现 页面的动态调度步骤:页面的动态调度步骤:1、找到被访

11、问页面在外存的地址;2、在内存中找一个空闲页面; (1)如果没有,按照淘汰算法选择一个内存页面; (2)将此内存页面写回外存,修改页表及页面分配表;3、读入所需的页面,修改页表及页面分配表;4、重新启动进程执行被中断的指令。&标记某页是否在内存,用于查询标记某页是否在内存,用于查询要访问的页在不要访问的页在不在内存。页表如下:在内存。页表如下:页号 物理块号状态位P访问位A修改位M外存地址2.2.页表机制页表机制其中:外存地址外存地址指出该页在外存的地址,供调入该页时用;状态状态为指示该页是否在内存,供程序访问时用,也是检查是否缺页的标志位,如置1表示在内存 ;访问位访问位或访问字段则

12、是该页被访问过的标志或该页被访问过的次数;修改位修改位表示该页是否被修改过;存取控制字段则是用来限制页面被安全共享的。 3.3.动态地址变换动态地址变换& 在虚拟页式存储中,应采用动态地址变换方式,因为某一欲执行的指令可能不在虚拟页式存储中,应采用动态地址变换方式,因为某一欲执行的指令可能不在内存,只能在指令执行之前完成地址变换。任一作业都应在自己的虚拟地址在内存,只能在指令执行之前完成地址变换。任一作业都应在自己的虚拟地址空间中执行,所以要为用户作业设置一个虚拟地址指针空间中执行,所以要为用户作业设置一个虚拟地址指针VP,虚拟地址依然,虚拟地址依然是由页号和页内偏移地址组成的。是由页

13、号和页内偏移地址组成的。&系统总是执行系统总是执行VP虚指针所指向的指令,为了将虚拟地址虚指针所指向的指令,为了将虚拟地址VP变换为对应的实变换为对应的实存地址,因此先要查找页表。若从页表中查出此页不在内存(状态位为存地址,因此先要查找页表。若从页表中查出此页不在内存(状态位为0),则),则产生一个缺页中断。此时,进程暂停当前指令执行,产生一个缺页中断。此时,进程暂停当前指令执行,CPU转去执行缺转去执行缺页中断处理程序。若该页已在内存,则指令的地址映射过程与页式存储是一样的。页中断处理程序。若该页已在内存,则指令的地址映射过程与页式存储是一样的。即将块号和页内地址相拼接形成物理地址即

14、将块号和页内地址相拼接形成物理地址IP,处理器再从,处理器再从IP中取指令执行。中取指令执行。4.4.缺页中断缺页中断5.5.缺页率缺页率&虽然通过缺页中断将所需要的页调入内存,但缺页中断的频繁发生会严重影响程序执行的效率。为了标识缺页中断发生的频度,可以引入缺页率来表示。 &设进程在其执行期间共进行了S次访页操作,其中成功访页次数为A(访问时该页在主存),不成功的访页次数为B(即发生了缺页中断),显然有:S=A+B,&则该进程的缺页率f定义为:fB/S。&显然缺页率越低越好。 4.6.2 4.6.2 页面分配策略页面分配策略&虚拟存储管理在进行页面分配

15、时,要考虑这样的问题:虚拟存储管理在进行页面分配时,要考虑这样的问题:空闲页面如何管理;采用什么样的分配策略;为进程分空闲页面如何管理;采用什么样的分配策略;为进程分配多少物理块比较合适;在什么时间进行页面分配等。配多少物理块比较合适;在什么时间进行页面分配等。 1.1.空闲页面管理空闲页面管理&同页式存储管理相似,虚拟存储方式下的空闲页面的管理也可以采用位示图或空闲页面链的形式。&由于主存中所有进程的虚拟地址空间之和远大于主存空间,因此进程执行时常发生缺页中断,这样不断地调入新页,很快就使主存空间饱和。以后再发生缺页时,要先淘汰一页才能装入新页,这使得缺页处理时间过长,减缓了

16、进程的执行速度,从而影响到系统的性能。& 在实际的系统中,总是维持一定数量的空闲块,而不是耗尽所有的空闲块。即空闲块数可以在某一区间浮动,一旦空闲块数小于下限值,系统就进行页面置换,以释放出一些空闲块,使得总的空闲块数不超过系统规定的上限值即可。即系统设置专门的独立进程负责页面置换,以保证链表的适当规模。2 2 分配策略(内存)分配策略(内存)&可变分配:是指一个进程所拥有的物理块数是不定的,这种分配方可变分配:是指一个进程所拥有的物理块数是不定的,这种分配方式称之为可变分配。式称之为可变分配。&固定分配是指为每个进程分配一固定页数的内存空间,在整个运行期间都固定分配是

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

18、有很高的缺页率;而另一个进程只有很高的缺页率;而另一个进程只有10页,却有页,却有10个块在闲置未用。所以在平均个块在闲置未用。所以在平均的思想下,还要考虑进程的大小。的思想下,还要考虑进程的大小。& 按比例分配算法,根据进程的大小按比例分配空闲块。设系统中现有按比例分配算法,根据进程的大小按比例分配空闲块。设系统中现有m个进程、个进程、n个空闲块,每个进程拥有的页数为个空闲块,每个进程拥有的页数为Si,则系统中所有进程页数之和为:,则系统中所有进程页数之和为: S = S1 + S2 + S3 + + Sm 则为每个进程分配的物理块数为:则为每个进程分配的物理块数为: Bi = (S

19、i / S) n ,Bi应向下取整。应向下取整。& 优先权分配算法,为优先权高的作业分配较多的内存空间,这样可以使优先权分配算法,为优先权高的作业分配较多的内存空间,这样可以使重要或紧迫的任务尽快完成。这时可以将内存中的空闲块分成两部分:一重要或紧迫的任务尽快完成。这时可以将内存中的空闲块分成两部分:一部分按比例分配给各进程,另一部分则根据各进程的优先权,适当地为其部分按比例分配给各进程,另一部分则根据各进程的优先权,适当地为其增加相应份额。增加相应份额。2 2 分配策略(外存)分配策略(外存)1、静态分配、静态分配 一个进程在运行之前,将其页面全部装入外存。当某一外存页面被调入内存时

20、,并不释放所占用的外存页面。2、动态分配、动态分配 一个进程在运行之前,仅将未装入内存的那部分页面装入外存。当某一外存页面被调入内存时,释放所占用的外存页面。3.3.工作集工作集& (1)(1)为保证进程能正常运行最少需要多少物理块。为保证进程能正常运行最少需要多少物理块。 从理论上讲,进程只要获得一个物理块就可以运行。但是进程正常运行所需的最少物理块数与计算机的硬件结构有关,取决于指令的格式、功能和寻址方式。由于分页是系统的行为,可能会出现下面的情景: 由此可见,系统应保证任一条指令执行时,其所涉及的虚拟地址所在的页都应在内存中。这个页数就是进程所需要的最小块数,若系统为进程所分配的

21、物理块数少于此值时,进程将无法运行。 123456涉及涉及6 6次缺页中断的指令次缺页中断的指令指令指令copy A to B数据数据A:数据数据B:& (2)(2)为使进程能有效地工作,应为它分配多少物理块合适为使进程能有效地工作,应为它分配多少物理块合适& 随着为每个进程所分配物理块数目的减少,将使进程执行中的缺页率提高,导致非生产性开销过大,从而降低了进程的执行速度,严重时导致进程不能向前推进。最少物理块数只能保证程序能执行下去,而不是最合适的块数。&在1968年,Denning提出了工作集理论。所谓工作集就是进程在某段时间里实际上要访问的页的集合。依据程序执行时

22、的局部特性,可以利用程序过去的行为来估计它未来的行为。故定义运行进程在定义运行进程在t tw w到到t t这个时间间隔内这个时间间隔内所访问的页的集合为该进程在时间所访问的页的集合为该进程在时间t t的工作集,记为的工作集,记为WW(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,

23、5,7,8,9(3)(3)工作集的应用工作集的应用&工作集工作集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

24、+a)|,a0a0。& 工作集窗口尺寸与缺页率关系密切,若工作集窗口尺寸与缺页率关系密切,若w w增大,工作集尺寸增大,工作集尺寸|W|W|随之增加(即所含的随之增加(即所含的页面数增多),缺页率就会下降。倘若页面数增多),缺页率就会下降。倘若w w含盖了整个作业虚拟空间,缺页率降含盖了整个作业虚拟空间,缺页率降为为0 0,也就失去了虚存意义;反之若,也就失去了虚存意义;反之若w w选取过小,将引起频繁缺页,导致系统性能下选取过小,将引起频繁缺页,导致系统性能下降。二者之间的关系可以如图所示。降。二者之间的关系可以如图所示。& 虚存中并不是要取消缺页率,而是要使缺页率维持在一个

25、较低的水平上。因虚存中并不是要取消缺页率,而是要使缺页率维持在一个较低的水平上。因此可以取拐点所对应的工作集尺寸作为分给进程的物理块数,实验分析表明,此可以取拐点所对应的工作集尺寸作为分给进程的物理块数,实验分析表明,这个数应是进程总页面数的一半。即一个进程应获得其所需页数一半的空间这个数应是进程总页面数的一半。即一个进程应获得其所需页数一半的空间时,再进入内存执行。时,再进入内存执行。 4.4.页面调入时机页面调入时机 何时将一个页面由外存调入内存。 预调页策略 & 也称先行调度,即一页面被访问前就已经预先置入内存,以减少今后的缺页率。&主要适于进程的许多页存放在外存的连续区

26、域中的情况。有的系统结合请求调入使用,即每次缺页时装入多个页面。优点:提高调页的I/O效率。缺点:基于预测,若调入的页在以后很少被访问,则效率低。预调页的成功率仅约50%,常用于程序装入时的调页。& 请求调页策略&当发生页面故障时进行调度,即当进程访问不在内存的页面引发缺页中断时,由系统根据这种访问请求把所缺页面装入内存。&优点:由请求调入策略装入的页一定会被访问,再加之比较容易实现,故在目前的虚拟存储器中,大多采用此策略。&缺点:每次仅调入一页,增加了磁盘I/O的启动频率。&在请求分页系统中,常把外存分为两部分:一部分是文件区,用于存放文件;另一部分是

27、对换区,用于存放对换页面。通常,对换区的磁盘输入输出速度比文件区的高,这是因为对换区所规定的盘块要比文件区的大得多。 从交换区调入&若系统拥有足够的对换区空间,可在进程运行前,将与该进程有关的文件拷贝到对换区。以后就从对换区调入所需页面,以提高调页速度。 5.5.从何处调入页面从何处调入页面 从交换区及文件区调入& 若系统缺少足够的对换区空间,则在交换区中只保存被修改过的页面。因为未被修改的页面在文件区中有副本。因此凡是没被修改的页,均从文件区调入;而已修改过的页面则从交换区调入。 UNIX方式& 与进程有关的文件都放在文件区,故凡是未运行过的页面,都应从文件区调入。而

28、对于曾经运行过而又被换出的页面,总是存放在对换区中。因此在下次调入时,应从对换区调入。由于在UNIX系统中允许页面共享,因此,某进程所请求的页面有可能已由其它进程调入内存,此时也就无须再从对换区调入。1.页面置换方式 当内存空间已没有空闲页面而又要调入新页时,必须采用一定的算法在内存中选择某一页面淘汰,所采用的算法称之为页面置换算法。 如果被淘汰的页面在内存期间曾被修改过,还要将此页重新写回到外存,以便保留最新的副本。然后再换进新的页面。(1)页面置换方式 页面淘汰可以在整个内存空间范围内进行,称之为全局置换。也可以只在一个进程空间范围内考虑,称之为局部置换。即当某一进程请求新页时,而该进程又

29、没有空闲块,则只能淘汰自己的一个页面而不能淘汰其它进程的页面。 4.6.3 4.6.3 页面置换方法页面置换方法 (2) (2) 空闲块分配方式空闲块分配方式& 若为进程分配固定的物理块数,在其执行期间再也不改变,则称为固定分配。初始进程块数的多少难以确定。若太少,则缺页频繁,系统开销大;若太多,则并发进程数目少,造成CPU空闲或其它资源空闲的情况。& 为进程分配的物理块数在其运行期间是可变的,则称为可变分配。进程在运行中,系统可调整为该进程分配的物理块,直至进程的缺页率达到适当程度。在页面置换算法讨论中,为了比较各种方法的优劣,总是限定为固定分配局部置换。固定分配局部置换:固

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

31、,0,3,0,4,2,3,0,3,2,1,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,成功访问次数7次,缺页率f=8/15=53.33%(2 2)先进先出淘汰算法)先进先出淘汰算法FIFOFIFO&这是最早出现的淘汰算法。&总是淘汰最先进入内存的页面。它实现简单,只需把进程中已调入内存的页面,按先后次序链成一个队列,并设置一个所谓的替

32、换指针,使它总是指向内存中最老的页面。&缺点:效率不高,因为它与进程实际的运行规律不相适应,比如常用的全局变量所在的页面或者循环体所在页面都可能被它选为淘汰对象。出现belady现象。 &Belady现象:采用FIFO算法时,如果对一个进程未分配它所要求的全部页面,有时就会出现分配的页面数增多,缺页率反而提高的异常现象。&Belady现象的描述:一个进程P要访问M个页,OS分配N个内存页面给进程P;对一个访问序列S,发生缺页次数为PE(S,N)。当N增大时,PE(S, N)时而增大,时而减小。&Belady现象的原因:FIFO算法的置换特征与进程访问内存的动态特

33、征是矛盾的,即被置换的页面并不是进程不会访问的。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=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

34、 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时,缺页率各是多少?(3)(3)最近最久未使用算法最近最久未使用算法(LRU, (LRU, Least Recently UsedLeast Recently Used) 根据页面调入内存后的使用情况,选择内存中最久未使用的页面被置换

35、。这是局部性原理的合理近似,性能接近最佳算法。 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 2 *4 3 2 *0 3 2 *0 3 20 3 21 3 2 *1 3 2 10次,缺页率次,缺页率f=10/15=66.67%LRULRU的两个实现算法:的两个实现算法: &计时法:计时法:对于每一页面增设一个访问时间计时器,每当一个

36、页面被访问时,就将当时的绝对时钟拷贝到对应的访问时间计时器中,这样系统记录了内存中所有页面最后一次被访问的时间。淘汰时,选取访问时间计时器的值最小的页面。&堆栈法:堆栈法:每当进程访问某页面时,便将该页面的页号从栈中移出,将它压入栈顶。栈顶始终是最新被访问的页面的编号。栈底则是最近最久未被使用的页面的页面号。 假定现有一进程所访问的页面的页面号序列为:假定现有一进程所访问的页面的页面号序列为: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

37、,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 8LRU的开销是很大的,必须有硬件的支持,完全由软件实现其速度至少会减少10倍,因此LRU近似算法更实用些。 &这是一种LRU的近似算法,是通过对FIFO算法进行简单改造,结合页表中的访问位而得来一种淘汰算法。&该算法首先检查位于FIFO链链首的页,如果它的访问位为0,则选择该页淘汰;如果它的访问位为1,则清除其访问位,将它移至FIFO链的链尾,重复此算法的查找过程,直至遇到新链首页是一个访问位为0的较早进入内

38、存的页为止,把它选为被淘汰的页。 (4)(4)二次机会淘汰算法二次机会淘汰算法SC(Second Chance)SC(Second Chance)(5 5)时钟)时钟(Clock)(Clock)淘汰算法淘汰算法 &缺点:就是需要把访问位为1的处于链首的页移至链尾,这需要一定的开销。一种改进的方法就是把进程所访问的页面链成一个环形链表,再设一个指针指向最老的页面,于是形成了一种简单实用的LRU近似算法时钟淘汰算法。&该算法首先检测指针所指的页面,如果它的访问位为0,则淘汰该页,新装入的页插入到此位置,然后指针前进一个位置;如果它的访问位为1,则清除为0,并将指针前进一个位置,继续

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

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

41、未被修改过表示该页未被修改过 1 1 表示该页已被修改过表示该页已被修改过(1)(1)分配给作业的内存块数分配给作业的内存块数 & 作业的缺页中断率与作业所占内存块数成反比。分配给作业的内存块数太少是导致抖动现象发生的最主要的原因;& 实验分析表明:对所有的程序来说,要使其有效地工作,它在内存中的页面数不应少于它的总页面数的一半。 3.影响缺页中断率的因素 (2)(2)页面大小的选择页面大小的选择&虽然缺页中断率与页面尺寸成反比,但页面尺寸却不能一味地求大,它一般在0.5KB4KB之间,是个实验统计值。因为页面大时,页表较小,占空间少,查表速度快,缺页中断次数少,但页面

42、调度时间长,页内碎片较大。页面小时,恰恰相反。 (3)(3)用户程序编制的方法用户程序编制的方法 作业的缺页中断率与程序的局部化(包括时间局部化和空间作业的缺页中断率与程序的局部化(包括时间局部化和空间局部化)程度成反比。用户程序编制的方法不合适可能导致程序局部化)程度成反比。用户程序编制的方法不合适可能导致程序运行的时空复杂度高,缺页次数多。运行的时空复杂度高,缺页次数多。 例如:一个程序将例如:一个程序将128*128的数组置初值的数组置初值“0”,假定它仅,假定它仅分得一个主存块,页面尺寸为分得一个主存块,页面尺寸为128个字,数组中的元素各个字,数组中的元素各行分别存放在一页中,开始时

43、第一页在主存中,若程序如下行分别存放在一页中,开始时第一页在主存中,若程序如下两种方式编写:两种方式编写:int A128128;for(int j=0;j128;j+) for(int i=0;i128;i+)Aij=0;缺页中断缺页中断(128*128-1)次次int A128128;for(int i=0;i128;i+) for(int j=0;j128;j+)Aij=0; 缺页中断(缺页中断(128-1)次)次&(4)(4)页面调度算法页面调度算法 &抖动又叫颠簸,是指一段时间里,页面在内存与外存之间频繁地调度或换入换出,以至于系统用于调度页面所需要的时间比进程实际运

44、行所占用的时间还要多。& 好的淘汰算法会维持一个较低的缺页率。若页面置换算法不好,会使系统出现抖动现象。 & 显然,抖动是由于缺页中断率很高而引起的一种坏现象,它将严重影响系统的效率,甚至可能使系统全面崩溃。 防止抖动现象的产生和扩展,具体方法防止抖动现象的产生和扩展,具体方法:采取局部置换策略采取局部置换策略 这样,即使有某个进程发生了这样,即使有某个进程发生了“抖动抖动”,也不致引起其它进程也产生抖,也不致引起其它进程也产生抖动,从而把抖动局限于较小的范围内。动,从而把抖动局限于较小的范围内。 这种方法并不很好,因为它不能从根本上防止抖动的发生;而且在某进这种方法并不很好,

45、因为它不能从根本上防止抖动的发生;而且在某进程发生抖动后,还会长期地处于磁盘输入输出的等待队列中,这又会使其程发生抖动后,还会长期地处于磁盘输入输出的等待队列中,这又会使其它进程缺页中断的处理时间增长,从而延长了等效的访问时间。它进程缺页中断的处理时间增长,从而延长了等效的访问时间。 L=S准则准则 Denning于于202X年提出了年提出了“L=S准则准则”,用来调整多道程序度,以使产生缺,用来调整多道程序度,以使产生缺页的平均时间页的平均时间L等于系统处理进程缺页的平均时间等于系统处理进程缺页的平均时间S。理论和实践表明,此时的。理论和实践表明,此时的CPU利用得最好。该准则也得到其它研究

46、人员的证实。利用得最好。该准则也得到其它研究人员的证实。防止抖动现象的产生和扩展,具体方法防止抖动现象的产生和扩展,具体方法:挂起若干进程挂起若干进程 为了防止发生“抖动”,可用的一个简单易行的办法是挂起一些进程,以便腾出内存空间来分配给抖动的进程。 被挂起的进程通常是选择优先权最低或较低的;当内存非常拥挤时,也可以选择一个并不很重要的、但确较大的进程挂起,以便能一次释放出较大的内存空间;或者是将具有最多剩余执行时间的进程挂起。 4.6.4 4.6.4 虚拟页式存储的优缺点虚拟页式存储的优缺点&1.1.优点优点& 主存利用率比较高。平均每个用户作业只浪费一半的页空间,内主存利用

47、率比较高。平均每个用户作业只浪费一半的页空间,内存规范易于管理。存规范易于管理。& 对磁盘管理比较容易。因为页的大小一般取磁盘物理块对磁盘管理比较容易。因为页的大小一般取磁盘物理块大小的整数倍。大小的整数倍。& 地址映射和变换的速度比较快。在把用户程序装入到主存储器的过地址映射和变换的速度比较快。在把用户程序装入到主存储器的过程中,只要建立用户程序的虚页号与主存储器的实页号之间的对应关系程中,只要建立用户程序的虚页号与主存储器的实页号之间的对应关系即可(拼接得到物理地址),不必使用整个主存的地址长度,也不必考即可(拼接得到物理地址),不必使用整个主存的地址长度,也不必考虑每页的

48、长度等。虑每页的长度等。& 2. 2.缺点缺点& 程序的模块化性能不好。程序的模块化性能不好。&由于用户程序是强制按照固定大小的页来划分的,而程序段的实际长度一由于用户程序是强制按照固定大小的页来划分的,而程序段的实际长度一般是不固定的。因此,虚拟页式存储器中一页通常不能表示一个完整的程般是不固定的。因此,虚拟页式存储器中一页通常不能表示一个完整的程序功能。一页可能只是一个程序段中的一部分,也可能在一页中包含了两序功能。一页可能只是一个程序段中的一部分,也可能在一页中包含了两个或两个以上程序段。个或两个以上程序段。& 页表很长,需要占用很大的存储空间。页表很长,

49、需要占用很大的存储空间。& 通常,虚拟存储器中的每一页在页表中都要占一个页表项。假设有一个虚拟页式存储通常,虚拟存储器中的每一页在页表中都要占一个页表项。假设有一个虚拟页式存储器,它的虚拟存储空间大小为器,它的虚拟存储空间大小为4GB,每一页的大小为,每一页的大小为1KB,则页表的容量为,则页表的容量为4M(个页表项)。如果每个页表项占用(个页表项)。如果每个页表项占用4个字节,则页表的存储容量为个字节,则页表的存储容量为16MB。 4.7 4.7 虚拟段式存储管理虚拟段式存储管理 4.7.1 4.7.1 虚拟段式存储的实现虚拟段式存储的实现 4.7.2 4.7.2 段的共享和保护段的

50、共享和保护 虚拟段式存储管理的优缺点虚拟段式存储管理的优缺点 4.7.4 4.7.4 虚拟段页式存储管理虚拟段页式存储管理 4.7.1 4.7.1 虚拟段式存储的实现虚拟段式存储的实现1.1.虚拟段式存储原理虚拟段式存储原理 逻辑地址空间中的程序段在运行时并不全部装入逻辑地址空间中的程序段在运行时并不全部装入内存。内存。 首先调入一个或若干个程序段运行,在运行过程中首先调入一个或若干个程序段运行,在运行过程中调用到哪段时,就根据该段长度在内存分配一个连续的调用到哪段时,就根据该段长度在内存分配一个连续的分区给它使用。分区给它使用。 若内存中没有足够大的空闲分区,则考虑进行若内存中没有足够大的空

51、闲分区,则考虑进行段的紧凑或将某段或某些段淘汰出去。段的紧凑或将某段或某些段淘汰出去。2.2.段表段表 &为了实现动态地址变换和存储保护,系统要为每一个作业建立一张段表。为了实现动态地址变换和存储保护,系统要为每一个作业建立一张段表。段表中的每一个表目对应着作业地址空间的一个程序段,其一般格式为:段表中的每一个表目对应着作业地址空间的一个程序段,其一般格式为: 逻辑地址同前:逻辑地址同前:段号存在位P访问位A修改位M存取方式增补位段长度段的基址外存地址存在位存在位P P表示该段是否在内存,如为表示该段是否在内存,如为0 0表示不在,为表示不在,为1 1表示在内存;表示在内存;存取方式表

52、示可对该段施加的操作,如只读、读写、还是执行。存取方式表示可对该段施加的操作,如只读、读写、还是执行。增补位表示该段在运行期间是否可以扩展空间增补位表示该段在运行期间是否可以扩展空间 3.3.请求式分段动态地址变换过程请求式分段动态地址变换过程 图图4.32 地址变换与中断处理流程地址变换与中断处理流程4.4.缺段中断缺段中断&在虚拟段式存储系统中,采用的是请求调段策略。在虚拟段式存储系统中,采用的是请求调段策略。&再调入新段时,也会有内存空间不够用的情况,也需要淘汰内存中的一个再调入新段时,也会有内存空间不够用的情况,也需要淘汰内存中的一个或多个段。如果此程序段从装入内存起一

53、直没有被修改过,只要用新调入或多个段。如果此程序段从装入内存起一直没有被修改过,只要用新调入的程序段把它覆盖掉即可。若这个程序段被修改过,则必须先把该程序段的程序段把它覆盖掉即可。若这个程序段被修改过,则必须先把该程序段全部写回到磁盘存储器中,才能占用被淘汰段原来存放的空间。全部写回到磁盘存储器中,才能占用被淘汰段原来存放的空间。&因为段要占用连续的空间,因此当内存中没有能够满足段长需要的因为段要占用连续的空间,因此当内存中没有能够满足段长需要的空闲区时,系统还要合并空闲区,以便满足分段的需求。空闲区时,系统还要合并空闲区,以便满足分段的需求。 4.7.2 4.7.2 段的共享和保护段

54、的共享和保护&1.1.段的共享段的共享& 在多道环境下,常常有许多子程序和应用程序是被多用户所使用的。最好的办法在多道环境下,常常有许多子程序和应用程序是被多用户所使用的。最好的办法是在内存中只保留一个副本,供多个用户使用,称为共享。是在内存中只保留一个副本,供多个用户使用,称为共享。& 段共享时,用户可以使用不相同的段名来共享同一个段。进程将共享段填写到自己的段共享时,用户可以使用不相同的段名来共享同一个段。进程将共享段填写到自己的段表中,并置以适当的读写控制权,就可以做到共享一个逻辑上完整的内存段信息。段表中,并置以适当的读写控制权,就可以做到共享一个逻辑上完整的内

55、存段信息。& 由于系统中有许多的共享段,而每一个共享段都可能被多个进程共享。因此系统由于系统中有许多的共享段,而每一个共享段都可能被多个进程共享。因此系统需要对共享段进行统一的管理,设一张共享段表,每一个共享段都在表中占据一需要对共享段进行统一的管理,设一张共享段表,每一个共享段都在表中占据一个表项。个表项。&共享段应该是可重入的。共享段应该是可重入的。 图图4.33 段式系统中共享内存副本示意图段式系统中共享内存副本示意图共享段表共享段表& 其中存在位表示该共享段是否已被调入内存,共享计数是用来统计当前有多少个进程其中存在位表示该共享段是否已被调入内存,共享计数是用来

56、统计当前有多少个进程共享该段。系统可以为不同的进程使用该段设置不同的权限,以防止进程越权操作。共享该段。系统可以为不同的进程使用该段设置不同的权限,以防止进程越权操作。& 当进程请求共享段时,若该共享段未在内存,也是由缺段中断将其调入内存,同当进程请求共享段时,若该共享段未在内存,也是由缺段中断将其调入内存,同时为该段建立相应的共享段表项,共享计数设为时为该段建立相应的共享段表项,共享计数设为1,将进程填写到共享段表项,将进程填写到共享段表项中,再将共享段填写到进程的段表中。若该共享段已在内存,只要将共享计中,再将共享段填写到进程的段表中。若该共享段已在内存,只要将共享计数加数加1,再修改相应的表项即可。不用时做相反工作。,再修改相应的表项即可。不用时做相反工作。段名段长存在位共享计数内存基址外存始址 共享该段的进程登记表状态进程名进程号段号存取权限2.2.段的保护段的保护( (两种保护方式两种保护方式) )&(1)(1)地址越界保护法。地址越界保护法。&(2)(2)存取方式控制保护法。存取

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论