操作系统ppt课件第5章内存管理.ppt

《操作系统ppt课件第5章内存管理.ppt》由会员分享，可在线阅读，更多相关《操作系统ppt课件第5章内存管理.ppt（108页珍藏版）》请在三一办公上搜索。

1、1,计算机操作系统,第5章 内存管理,2,内容,5.1 概述5.2 存储管理的基本技术 5.3 分页存储管理 5.4 分段存储管理5.5 段页式存储管理 5.6 虚拟内存的置换算法,3,5.1 概述,1）、基本概念存储器的层次结构地址逻辑地址与物理地址程序的链接和装入地址转换(重定位)2）、内存管理要解决的问题内存空间分配地址转换和重定位存储扩充存储保护和主存共享3）虚拟存储器,4,5.1.1基本概念,1）存储器的层次结构：任何一种存储装置，都无法同时从速度与容量两方面，满足用户的需求。它们组成了一个速度由快到慢，容量由小到大的存储装置层次。由操作系统协调这些存储器的使用,5,地址,主存的最小

2、单位是“位”主存对存储位置进行编号，这些编号称为“地址”，最小的编址单位是“字节”，一般包含八个“位”地址空间程序用来访问信息所用地址单元的集合,6,逻辑地址与物理地址,逻辑地址（相对地址，虚地址）：用户的程序经过汇编或编译后，形成目标代码，目标代码通常采用相对地址的形式，其首地址为0，其余指令中的地址都相对于首地址而编址。物理地址（绝对地址，实地址）内存中存储单元的地址，可直接寻址,7,程序的链接和装入,8,地址转换,把作业地址空间中使用的逻辑地址，变换成为-内存空间中的物理地址的过程。又称地址映射，重定位程序地址如果不反映其真实的存储位置，就不可能得到正确的执行但在多道程序设计环境下，用户

3、无法事先约定各自占用内存的哪个区域，也不知道自己的程序会放在内存的什么位置，,P135 5.1.3 重定位,9,静态重定位,当用户程序被装入内存时，一次性实现逻辑地址到物理地址的转换，以后不再转换,动态,10,动态重定位,动态重定位：动态重定位在指令执行过程中，每次访问内存前动态地进行地址转换。,静态重定位:当用户程序被装入内存时，一次性实现逻辑地址到物理地址的转换，以后不再转换,11,动态重定位,在程序运行过程中要访问数据时再进行地址变换。由地址变换机构进行的地址变换，硬件上需要重定位寄存器的支持。,静态,12,2）、主存管理要解决的问题P119,内存空间管理当用户需要内存时,系统为之分配相

4、应的存储空间；不需要时，及时回收，以供其它用户使用。记录内存的使用情况：设置相应的内存分配表 内存空间划分问题？静态或动态，等长或不等长。确定分配算法地址转换（重定位）把逻辑地址转换为相应的物理地址的过程,13,2）、主存管理要解决的问题,存储扩充用户在编制程序时，不应该受内存容量限制，所以要采用一定技术来“扩充”内存的容量，使用户得到比实际内存容量大的多的内存空间。存储保护和主存共享为多个程序共享内存提供保障，使在内存中的各道程序，只能访问它自己的区域，避免各道程序间相互干扰，特别是当一道程序发生错误时，不致于影响其他程序的运行,先考虑问题1、2、4；最后考虑问题3,14,5.1.2 虚拟存

5、储器,虚拟存储器是具有请求调入和交换功能、能从逻辑上对内存容量进行扩充、给用户提供了一个比真实的内存空间大得多的地址空间,在作业运行前可以只将一部分装入内存便可运行的、以逻辑方式存在的存储器。实质上是让程序的访问地址，和内存的可用地址相脱离。特性：虚拟性，还有离散性、多次性和交换性等。,15,内容,5.1 概述5.2 存储管理的基本技术 5.3 分页存储管理 5.4 分段存储管理5.5 段页式存储管理 5.6 虚拟内存的置换算法,16,5.2 存储管理的基本技术,最基本的4种存储管理技术：分区法、可重定位分区法、覆盖技术、交换技术。,17,5.2.1 分区法,最简单。基本原理：给每一个内存中的

6、进程，划分一块适当大小的存储块，以连续存储。管理方式：固定分区动态分区（可变分区）回顾内存管理的3/4个问题,18,5.2.1 分区法,1.固定分区法 主存分成若干个固定大小的连续区域（存储块）每个存储区分给某一个作业使用，分区长度和个数不变。简单，内存利用率不高。,19,分区说明表,记录存储分区情况及存储区使用状况的信息,分区的碎片：分区内没有使用的剩下的部分,大大的问题：有资源但没法使用,20,5.2.1 分区法,2.动态分区法 根据进程的实际需要，动态地为它分配连续的内存空间。各个分区是在相应作业装入内存时建立的，其大小恰好等于作业的大小。系统中设置了相应的数据结构，来记录内存的使用情况

7、：有空闲分区表空闲分区链,21,动态分区法,固定分区法,22,OS,312K,318K,333K,369K,512K,(6K),进程C(36K),进程B(25K),固定分区法,动态分区法,23,存储分配算法,(1)最佳适应法 挑选最接近作业尺寸且大于或等于作业大小的分区，从而使分区内未用部分(又称碎片)浪费的最少。(2)最先适应法 即按分区序号最先找到的且大于或等于作业大小的未分配分区，分给要求的作业。着眼点是在于缩短查找时间。(3)最坏适应法 挑选最大的且大于和等于作业大小的分区分给要求的作业。为什么？,24,算法的利弊,最佳适应算法：尽量多保留些大的分区，使被选中分区剩下尽可能小的未用碎片

8、。但也正是这种做法使得系统中产生了许多小得无法再用的碎片。最先适应算法：尽可能缩短存储分配时间。为此目的许多设计者不但在算法上想办法，而且对空闲块的管理上也采取了不同方法。最坏适应算法：保证分配后剩下的分区足够大，以便满足后续要求。,25,碎片大大的问题：有资源但没法使用,内存碎片：由于各作业请求和释放主存块的结果，会导致内存中经常出现大量分散的小空闲区。内存中这种容量太小，无法被利用的小分区称为碎片。内碎片 固定分区中外碎片 可变分区中问题：减少了内存中作业的并发数内存浪费、利用率低存储分配和释放速度慢解决方法,26,方法1：把小碎片合并起来使之成为一个大分区。实现方法：移动各用户分区中的程

9、序，使他们集中于主存的一端(顶部或底部)，而使碎片集中于另一端，从而连成一个完整的大分区，这种技术通常称为存储器的“紧凑”。方法2：把程序分成几部分装入不同的分区中去，也就是改变程序连续存放的要求。实现方法：分页、分段等存储管理技术。,碎片问题的解决办法,27,5.2.2 可重定位分区法,解决碎片问题引出的新问题：在找不到足够大的空闲分区来满足用户需求时，进行紧凑处理，用户程序需要在主存中移动。程序移动后会无法正确执行（为什么？）,用户程序(60K),28,解决方法（程序移动后会无法正确执行）,回顾原来地址转换的方法：当用户程序被装入内存时，一次性实现逻辑地址到物理地址的转换，以后不再转换。无

10、法确定何时发生程序移动，移动到何处。所以不能预先转换地址 在执行指令的时候进行地址转换（动态重定位）,29,5.2.2 可重定位分区法,动态分区加动态重定位 实现过程，需要额外硬件 作业3大小为24KB，被装入起始地址为64KB的内存空间,30,5.2.3 覆盖技术,早期，当程序的长度大于内存的容量，怎么办？,部分装入！覆盖、交换！对主存进行了逻辑扩充,覆盖技术，是在多道环境下扩充内存的方法，用以解决在较小的存储空间中，运行较大程序时遇到的矛盾。在程序运行过程中，把同一存储区,在不同时刻,分配给不同的程序段或数据段来共享。缺点是，程序员必须小心地设计程序及其数据结构，使得要覆盖的段块具有相对独

11、立性，不存在直接联系或相互交叉访问。,31,覆盖技术,32,5.2.4 交换技术,交换是指将一个进程从内存拷贝到磁盘上，以腾出空间给其他进程使用。需要时，再将该进程调入内存。由换出和换进两个过程组成，换出是把内存中的数据和程序，换到外存的交换区,换进则是把外存交换区中的数据和程序，换到内存的分区中。在交换系统中，交换所占用的时间相当多。,33,交换与覆盖 比较,都是解决大作业与小主存矛盾的存贮管理技术，实质上是对主存进行了逻辑扩充。交换技术不要求用户给出程序段之间的逻辑覆盖结构；交换发生在进程或作业之间，而覆盖发生在同一进程或作业内。覆盖只能覆盖那些与覆盖段无关的程序段,34,小结,基本概念地

12、址、逻辑地址与物理地址、程序的链接和装入地址转换(重定位)内存管理要解决的问题1,内存空间管理2,地址转换（重定位）3,存储扩充4,存储保护和主存共享最基本的4种存储管理技术：分区法：固定分区、可变分区、内存碎片及解决方法可重定位分区法：程序移动带来的问题、动态重定位覆盖技术、交换技术,35,内容,5.1 概述5.2 存储管理的基本技术 5.3 分页存储管理 5.4 分段存储管理5.5 段页式存储管理 5.6 虚拟内存的置换算法,36,5.3 分页存储管理,碎片问题的解决方法1：紧凑技术可重定位分区法让储存器去适应程序对连续性的要求。碎片问题的解决方法2：把程序分成几部分，装入不同的分区中去，

13、也就是改变程序连续存放的要求。分页管理允许程序的存储空间是不连续的，用户程序的地址空间，被划分为若干个固定大小的区域。,37,5.3.1 基本概念 分页的基本思想,1）、主存空间划分物理块（页框、页架）：把主存划分成相同大小的存储块；物理块号：各物理块从0开始依次编号，称为页架号。2）、逻辑地址空间划分页（页面）：把用户的逻辑地址空间按照物理块大小，划分成若干个页面；页号：各页从0开始依次编号，称为页号(逻辑页号)；页内地址：将逻辑页面中的所有单元从0开始依次编址。如此划分后，可将任一页放在内存的任一块中（有什么好处？）,38,3）、逻辑地址的表示划分后逻辑地址由两部分组成：可用一个数对(p，

14、d)来表示；若给定一个逻辑地址A，页面大小为L；则 p=INTA/L，d=A MOD L4）、主存分配 分配主存时，以页架为单位，按用户程序的页数进行分配；逻辑上相邻的页在主存中不一定相邻。,5.3.1 基本概念 分页的基本思想,39,逻辑地址A为1005H，页的大小L为1024Byte，则A的页号、页内地址：A=1005H=4096+5=212+22+20，L=1024=210。,例：划分后逻辑地址,40,5.3.1 基本概念 页表,2.页表数据结构 每个进程都有自己的页面映象表，简称页表，页表中包含每个帧的基址及相应的页号。页表的作用是实现从页号到物理块号的地址映射。页表的表项中常设置一存

15、取控制字段，用于对该存储块中的内容进行保护。如果要利用分页系统去实现虚拟存储器，还需要增加另外的数据项。,41,例：页表,页表：由页号和页面号组成，指出逻辑地址中页号与主存中块号（页架号）的对应关系,42,5.3.1 基本概念 地址转换,3.分页系统中的地址转换 地址转换机构，就是将逻辑地址中的页号，转换为内存中的物理块号。地址转换任务是借助于页表来完成的，有时也把页表称为地址变换表或地址映像表。,43,5.3.1 基本概念(1)基本的地址转换P129,(1)地址转换机制把CPU给出的逻辑地址分为两部分：页号p和页内地址d；(2)将逻辑页号p与页表长度寄存器的内容比较，则为越界；(3)根据页表

16、地址B得到页表在内存的首地址，并根据逻辑页号p在页表中找到对应的页架号p；(4)把页架号p与逻辑地址中的页内地址d合并成为物理地址。,44,缺点,页表放在主存中系统表格区，导致：增加了系统在存储上的花销，降低了CPU的访问速度。每次对某一地址的访问，首先要访问内存中的页表，形成绝对地址后，才能进行所需要的真正访问。要两次访问内存储器才能实现，处理机执行速度降低50%。,45,页表大小,主存页架数N 主存大小/页大小例：128M的物理内存，每页4k 主存页架数N 128M/4K 32 kilo进程页表表目数 虚拟地址空间/页大小 32位虚拟地址空间 232，每页4k，有220 表目占4byte，

17、则页表 220 X 4byte 4MB,46,多级页表地址转换,对页表本身也采取分页措施：把页表本身分成页面，每个页面中存放n个页表表目，设置一个页表目录管理小页表。解决了页表非常大的问题但是，增加一级页表，增加一次访存次数。,47,快表,为了提高地址的转换速度，用一组快速的硬件寄存器构成页表。TLB（Translation Lookaside Buffers）硬件把页号与寄存器组中所有的表项同时并行比较，立即输出与该页号匹配的块号。这种做法无须访问内存，并且通过硬件并行匹配直接完成地址的变换，因此速度是极快的。由于快速寄存器价格昂贵，因此完全由它来组成页表的方案是不可取的。大多数程序在一次调

18、度运行时，倾向于在少数页面中进行频繁的访问（这被称为程序的“局部性”原理），内存页表与快速寄存器组相结合,48,例,如果查找快表花费的时间是50ns，访问内存的时间是750ns，页号在快表：存取时间为50+750=800ns页号在慢表：存取时间为750+750=1500ns命中率为90%存取时间为0.9*800+0.1*1500=870ns命中率为97%存取时间为0.97*800+0.03*1500=821ns时间延迟命中率为90%（870-750）/750=16%命中率为97%（821-750）/750=9.5%,49,5.3.1 基本概念,(2)快表的地址转换,50,5.3.2 纯分页系统

19、（静态页式）,纯分页系统是指作业运行时，该作业所有的页必须一次全部装入，如果没有足够的内存则拒绝运行该作业。纯分页系统的地址转换过程如下：,N,51,5.3.3 请求式（动态）分页系统,请求式分页系统是目前常用的一种实现虚拟存储器的方式。其基本思想是：作业请求运行时，只把当前需要的一部分页面装入内存，当用到不在内存中的页面时从辅存中调入；如果内存中没有空闲块，则按某种算法从内存中选择一些页交换到辅存，并调入所需的页面到内存。在请求式分页系统中，其地址转换类似于纯分页系统的地址转换，如果访问的页已在内存中，则与纯分页系统的地址转换过程类似；如果发生缺页，通常的作法是由硬件发出中断信号，再由操作系

20、统的相应软件负责调入其所缺的页面。,52,5.3.4 硬件支持及缺页处理,为了实现请求式分页，系统必须有一定的硬件支持，这包括:页表、快表硬件设施，内存管理单元(完成地址转换的任务)，当出现缺页时，在硬件方面，还须增加缺页中断响应机构。,53,5.3.4 硬件支持及缺页处理,1.页表 分页系统中的从逻辑地址到物理地址的转换是通过页表来实现的。页表是数组，每一表目对应进程中的一个虚页，页表表目通常为32位，它不仅包含该页在内存的基地址，还包含有页面、内存块号、改变位、状态位、引用位和保护权限等信息。,54,5.3.4 硬件支持及缺页处理,2.快表快表是为了加快地址转换速度而使用的一个联想高速缓存

21、，使用快表进行地址转换的速度比页表要快很多倍。快表由硬件实现，每个表目对应一个物理页框，包含如下信息：页号、物理块号、数据快表、指令快表和保护权限。,55,5.3.4 硬件支持及缺页处理,3.内存管理单元 内存管理单元MMU主要是用来完成地址转换，它具有如下功能：（1）将逻辑地址分为页号和页内位移，在页表中先找到与该页对应的物理块号，再将其与页内位移一起组成物理地址；（2）管理硬件的页表地址寄存器；（3）当页表中的状态位为“0”，或页面访问越界，或出现保护性错误时，内存管理单元会出现页面失效异常，并将控制权交给操作系统内核的相应程序处理；（4）设置页表中相应的引用位、改变位、状态位和保护权限等

22、。,56,5.3.4 硬件支持及缺页处理,4.缺页中断机构 缺页中断是一种特殊的中断，它与一般中断的区别为：在指令执行期间产生和处理中断信号；一条指令在执行期间可能产生多次缺页中断。右图为页面中断处理算法流程图。,57,5.3.5 页的共享和保护,每个作业分别存储在内存的不连续的存储块中，这种灵活性允许两个和多个作业，共享程序库中的例程或公共数据段的同一副本.共享的方法:使这些相关进程的逻辑空间中的页指向相同的内存块。并非所有页面都可共享，故实现信息共享的前提是提供附加的保护措施，对共享信息加以保护。,58,分页存储管理方法的优缺点,优点：(1)有效解决了主存碎片问题，主存利用率高；(2)分配

23、和释放页架都很快。缺点：(1)不能按用户程序模块的自然逻辑关系划分；(2)不便于共享和保护。,59,内容,5.1 概述5.2 存储管理的基本技术 5.3 分页存储管理 5.4 分段存储管理5.5 段页式存储管理 5.6 虚拟内存的置换算法,60,5.4 分段存储管理 分段的引入,分段的引入：每个作业的地址空间，都有一定的逻辑结构关系，一个作业通常是由若干个程序段和数据段所组成的，例如、主程序、若干子程序以及数据区等。在页式存储管理中把一维线性的作业地址空间机械地划分成若干大小相等的页面，常常会把逻辑相关的部分划分到不同的页面。显然、这样做破坏了程序内部自然的逻辑结构，造成页共享和保护的困难。,

24、61,程序的结构示例,CALL X,CALL Y,LOAD R，A,0,K,CALL X 表示从入口点E调用子程序XLOAD R,A 表示将数组A的116单元读入寄存器R,主程序,62,5.4 分段存储管理,分段存储管理的方法，是按程序的自然逻辑结构将程序分成若干逻辑段，并对这些段分别分配存储空间。这些段的长度可以不同，也不必连续进行分配。这种存储管理方式已成为当今所有存储管理方式的基础。,63,主存空间划分物理段：主存空间被动态地划分为若干个长度不相同的区域，每个区域称作一个物理段。段首址：每个物理段在内存中的起始地址。2.逻辑地址空间划分逻辑段：用户程序按逻辑上有完整意义的段来划分，称为逻

25、辑段，简称段。段号：将用户的所有逻辑段从0开始编号，称为段号。段内地址：将逻辑段中的所有单元从0开始依次编址。,分段存储管理基本思想,64,3 逻辑地址的表示划分后逻辑地址由两部分组成：可用一个数对(S，W)来表示；4 主存分配 分配主存时，以段为单位，为每一个逻辑段分配一个连续的主存区（物理段）；逻辑上连续的段在主存中不一定连续存放。,65,5.4.1 基本概念,1.分段段是一组逻辑信息的集合。每个段都有自己的名字和长度，通常编译后用一个段号来代替段名，每个段都从0开始编址，并采用一段连续的地址空间，段的长度由相应的逻辑信息组的长度决定。分段系统中的逻辑地址由段号s和段内地址d组成。,66,

26、5.4.1 基本概念,段表,67,5.4.1 基本概念,2.分页和分段的主要区别 页是信息的物理单位，分页是为了便于系统管理；而段是信息的逻辑单位，分段是为了满足用户需要。分页式存储管理的作业地址空间是一维的；而分段式存储管理作业地址空间是二维的。思考：页式管理中逻辑地址表示为p和d为什么说是一维的？页的长度由系统确定，是等长的；而段的长度由具有相对完整意义的信息长度确定，是不固定的。,68,5.4.2 基本原理,分段管理，就是管理由若干段组成的作业，并且按分段来进行存储分配；由于分段的作业地址空间是二维的，所以分段的关键在于如何把分段地址结构变成一维的地址结构。和分页管理一样，可以采用动态重

27、定位技术来进行地址转换。,69,5.4.2 基本原理 分段地址转换过程,LA,CPU,段号s 段内位移d,+,段表长度ts 段表始址ta,段表寄存器STCR,Y,地址越界中断,段长 段始址 ss L,+,PA,内存,段表,s,ta,越界中断,思考：（1）这个图与哪个图类似？（2）为什么段式管理要对段内位移进行判断，而页式管理不要对页内位移进行判断？,段长,ts,70,5.4.3 硬件支持和缺段处理,为了实现分段式存储管理，系统必须有一定的硬件支持，以完成快速请求分段的功能，这包括：段表、快表机构、地址转换机构，当出现缺段（段式虚拟存储器）的问题时，需要有缺段中断机构来进行及时地处理。,71,5

28、.4.3 硬件支持和缺段处理,段表机制 请求式分段管理中的主要数据结构是段表，在段表项中，除了段号(名)、段长、段在内存的始址外，它还包含存取方式、访问字段、改变位、状态位、增补位、外存起址。段表可以存放在一组寄存器中，这样有利于提高地址转换速度；但更常见的是将段表放在内存中。在配置了段表后，执行中的进程可通过查找段表，找到每个段所对应的内存区。,72,5.4.3 硬件支持和缺段处理,2.地址转换机构 请求分段式的地址转换过程如右图所示,73,5.4.3 硬件支持和缺段处理,3.缺段中断机构,请求分段系统中的中断处理过程,74,5.4.4 段的共享和保护,1.段的共享 段的共享是指两个以上的作

29、业，使用某个子程序或数据段，而在内存中只保留该信息的一个副本。只需在每个进程的段表中，用相应的表项来指向共享段在内存的起始地址即可（参见图5.22）。,75,5.4.4 段的共享和保护,2.段的保护 在分段系统中，由于每个分段在逻辑上是独立的，因而比较容易实现信息保护。段的保护是为了实现段的共享和保证作业正常运行的一种措施。分段存储管理中的保护主要有：地址越界保护和存取方式控制保护。,76,5.4.4分段（请求）式存储管理的优点,优点：提供了内外存统一管理的虚存，每次调入一段有意义的信息。允许段长动态增长，不影响其他段。便于对具有完整逻辑功能的信息段进行共享。便于实现动态链接。缺点：需要更多的

30、硬件支持，诸多功能会使系统的复杂性大大增加；段的长度受内存可用区大小的限制；若替换算法选择不恰当就有可能产生“抖动”现象。碎片问题,77,内容,5.1 概述5.2 存储管理的基本技术 5.3 分页存储管理 5.4 分段存储管理5.5 段页式存储管理 5.6 虚拟内存的置换算法,78,分段和分页各有长处,分页对程序员是透明的，它消除了外部碎片，因而可以更有效地使用主存分段对程序员是可见的，它支持处理不断增长的数据结构的能力，以及支持共享和保护的能力,79,5.5 段页式存储管理,分页对程序员是透明的，它消除了外部碎片，因而可以更有效地使用主存分段对程序员是可见的，它支持处理不断增长的数据结构的能

31、力，以及支持共享和保护的能力段页式存储管理则是分页和分段两种存储管理方式的结合，它同时具备了两者的优点。,80,5.5.1 基本概念,段页式存储管理，既方便使用又提高了内存利用率，是目前用得较多的一种存储管理方式。等分内存与页式存储管理对内存的分块一样 作业或进程的地址空间与段式存储管理对作业地址 空间的处理一样 段内分页-与页式存储管理对作业地址空间的处理一样 逻辑地址结构由段号、段内页号和页内位移组成 内存分配以页为单位 段表、页表和段表地址寄存器,81,用分页方法来分配和管理主存空间，即把内存划分为若干大小相等的页面；用分段方法对用户程序按其内在的逻辑关系划分成若干段；最后把每一段划分成

32、若干大小相等的页面。用户程序的逻辑地址的组成,基本思想,82,段号 页号 页架号,页表 页表首址 长度,S，(p,d),B L,B,逻辑地址,段表地址寄存器,L,段表长度寄存器,页内地址,段号 页号,比较,段号0,S,物理地址,段表,若SL,则地址越界,图：引入快表后段页式存储管理的地址转换,快表,S p p,比较,若p L,则地址越界,p,页号0 页架号,p,页表,p,d,页架号 页内地址,5.5.2 地址转换,83,5.5.3 管理算法,在地址转换过程中，软、硬件应密切配合，这在分页和分段式存储管理中已体现出来，段页式存储管理也是如此。地址转换过程中硬、软件的相互作用如下图所示：,84,进

33、程表、段表和页表与主存中页架的关系,85,5.5.3段页式存储管理的优缺点,优点：提供了虚存的功能无紧缩问题，也没有页外碎片的存在便于处理变化的数据结构便于共享和控制存取访问权限。仅存在着页内碎片缺点：增加了软件的复杂性和管理开销，需要更多的硬件支持；各种表格要占用一定的存储空间；存在着系统抖动现象。,86,内容,5.1 概述5.2 存储管理的基本技术 5.3 分页存储管理 5.4 分段存储管理5.5 段页式存储管理 5.6 虚拟内存的置换算法,87,5.6 虚拟内存（页式）的置换算法,存储扩充 虚拟存储器（部分装入）要访问没有被装入的部分？当进程访问一个当前不在内存的页，并且没有空闲的内存块

34、来装入该页！这时操作系统可能：终止该进程。或者操作系统可能交换出该进程。不想终止或换出该进程，用磁盘上所需要的页置换内存中的一个页。,88,5.6 虚拟内存（页式）的置换算法,系统产生“缺页中断（页面错误）”采用页面置换怎么做呢？首先，查找所需页在磁盘上的位置。第二，查找一个空闲内存块以装该页。如果有空闲块，就使用它。如果没有空闲块，就使用页置换算法以选择一个“牺牲”块。如果“牺牲”块自磁盘读出后被改写过（即它是“脏的”），那么它首先要写回磁盘。,89,5.6 虚拟内存（页式）的置换算法,第三，将所需页从磁盘读入新的空闲块；并改变页表和空闲块表。最后，重新执行产生缺页中断（页面错误）的指令。,

35、90,5.6 虚拟内存（页式）的置换算法,实现请求式调页，必须解决的主要问题是选择合适的页面置换算法和块分配算法。在置换页面时，通常选择这样一些牺牲者，即在对它们进行替换时，可达到最低缺页中断率。可利用访问串对替换算法的性能进行评价。访问串是由程序规定的内存地址访问表列。,91,访问串,例如，如果跟踪一个特定进程，那么可记录如下地址顺序：0722,0050,0121,0212,0012,0310,0019,0421,0289,0302,0076,0365,0196CPU 从物理地址 0722 取数据，然后从 0050，然后从 0121，按每页100 个字节（即页面大小为100 B），那么就得到

36、如下引用串：,7,0,1,2,0,3,0,4,2,3,0,3,1,92,刚被淘汰出去的页，不久又要被访问，又需把它调入而将另一页淘汰出去，很可能又把刚调入的或很快要用的页淘汰出去了。如此反复频繁地更换页面，以致系统的大部分机时花在页面的调度和传输上了，系统的实际效率很低。这种现象称为“抖动”。,“抖动”现象,93,(1)先进先出置换算法(FIFO)。(2)最佳置换算法(OPT)。(3)最近最少使用置换算法(LRU)。(4)二次机会置换算法。(5)时钟页面置换算法。(6)其他页面置换算法1.最近未使用置换算法（NUR）2.页面缓冲算法,5.6.1常见的页面置换算法,94,5.6.1 先进先出页面

37、置换算法,将最先进入队列的页号所对应的页面，最先选择为牺牲者。易于理解，但性能不是在任何场合都是好的。使用FIFO方法可能会出现Belady异态，这是一种在增加帧的情况下反而使缺页中断率增加的异常情况。最早进入主存的页面，有可能是最经常被使用的页(如常用子程序，常用的数组，循环等)。,95,FIFO 算法示例,访问串（页面序列）7 0 1 2 0 3 0 4 2 3 0 3 1,11 次缺页中断（页面错误）,练习：设访问串为：1、2、3、4、1、2、5、1、2、3、4、5试比较当内存块数为 3 时与为4 时的缺页中断次数和缺页中断率？,96,5.6.2 最佳页面置换算法,总是替换将来不被使用的

38、，或是在很久以后才被使用的那个页面。这种算法理论上能保证有最少的缺页率。然而，问题是如何知道哪个页将在最长的时间中不会被使用呢？因此该算法无法实现，通常用来同其他方法进行比较以衡量其它算法的优劣。,97,最佳页置换（Optimal）-示例,访问串7 0 1 2 0 3 0 4 2 3 0 3 1,8 次缺页中断（页面错误）,98,5.6.3 最近最少使用页面置换算法,最近最少使用(Least Recently Used，LRU)页面置换算法，是根据页面调入内存后的使用情况，选择最近最少使用的页面予以淘汰。该算法的主要出发点是如果某页被访问了，则它可能马上又要被访问；如果某页长时间未被访问，则它

39、在最近一段时间内不会被访问。,99,LRU 示例,访问串7 0 1 2 0 3 0 4 2 3 0 3 1,10次缺页中断（页面错误），比 FIFO 低,100,5.6.4 第2次机会页面置换算法,最早进入主存的页面，有可能是最经常被使用的页(如常用子程序，常用的数组，循环等)。第2次机会页面置换方法，将页面按FIFO次序安排，且每个页有一个引用位，表示最近访问过。先选择“最老”的页，若其引用位为 0，则它就是牺牲者；若它的引用位已为 1，则先清除它（置 0），再将该页放到链表的尾端，修改其装入时间，即该页获得第 2 次机会，然后选择下一页，重复前述过程。,101,5.6.4 第2次机会页面置

40、换算法（例）,如果所有的引用位都是 1。那么二次机会算法就与 FIFO 算法一样。,引用位为”1”,引用位改为”0”,102,5.6.5 时钟页面置换算法,把所有的页面保存在一个类似钟表面的环形链表中，用一个指针指向最老的页面，就如表针指向某一时刻一样。它和第2次机会算法的区别仅是实现的方法不同。,图,103,5.6.4时钟页面置换算法（续）,产生缺页中断并要求页面置换时，先检查指针指向页面的引用位。如果该位为“1”，则将其置“0”，并把指针前移一位，再重复这个过程；如果该位为“0”，就淘汰它，让新的页面进入它原来占用的内存块，并把指针前移一位。,104,5.6.6 其他页面置换算法,1.最近

41、未使用置换算法（NUR）,105,5.6.6 其他页面置换算法,2.页面缓冲算法 该算法规定将一个被淘汰的页放入两个链表中的一个，即如果页面未被修改，就将它直接放入空闲链表中，否则便放入已修改页面的链表中。这时页面在内存中并不做物理上的移动，而只是将页表中的表项移到上述两个链表之一中。,106,5.6.6 其他页面置换算法,2.页面缓冲算法 该算法规定将一个被淘汰的页放入两个链表中的一个，即如果页面未被修改，就将它直接放入空闲链表中，否则便放入已修改页面的链表中。这时页面在内存中并不做物理上的移动，而只是将页表中的表项移到上述两个链表之一中。,107,小结,5.1 概述5.2 存储管理的基本技术 5.3 分页存储管理 5.4 分段存储管理5.5 段页式存储管理 5.6 虚拟内存的置换算法,108,何谓虚拟存储器?其容量通常由什么因素决定，虚拟存储器容量能大于主存容量与辅存容量之和吗?比较FIFO与LRU置换算法的优缺点。什么是二次机会置换算法?,