第6章存储器管理.pptx

《第6章存储器管理.pptx》由会员分享，可在线阅读，更多相关《第6章存储器管理.pptx（90页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第6章存储器管理计算机作为信息处理的工具，其重要的特点之一是具有存储能力。计算机的存储系统主要包括内存储器和外存储器。内存储器为执行内存，存放处理器执行时所需要的所有代码和数据。外存储器是辅助存储器，存放需要长期保存的信息。外存储器保存的信息必须进入内存储器后才能被处理器运行。存储器管理是操作系统的主要功能之一，本章所述的存储器管理是指对内存储器的管理。虽然计算机系统的内存容量不断增大，但仍然难以满足软件发展的需求。对内存资源管理是否有效，不仅关系到内存本身的利用率，还关系到整个系统性能和效率。内存管理分为连续管理方式和离散管理方式。连续管理方式将用户程序连续放置在内存，适合单道程序环境。离散

2、管理方式将用户程序以分页或分段方式放置在内存，适合多道程序环境。离散分配方式也是实现虚拟存储器管理的基础。本章针对传统存储器管理进行讲解，虚拟存储器管理在下一章中讲述。第1页/共90页本章的主要内容如下：l存储器管理概述l连续存储管理l分页式存储管理l分段式存储管理第2页/共90页6.1存储器管理概述6.1.1存储器的层次对计算机存储系统的基本要求是存储容量大、存取速度快、成本价格低。按照计算机的体系结构，计算机存储系统可以划分为3个层次，分别是：处理器寄存器和高速缓存、内存储器、外存储器，如图6.1所示。图图6.1 计算机存储系统层次划分计算机存储系统层次划分第3页/共90页6.1.2存储管

3、理目的和功能1 1、主存储器的分配和回收 内存分配的主要任务是为每一道程序分配内存空间，使它们“各得其所”。2 2、提高主存储器的利用率，减少不可用的存储空间（称为“零头），允许多道程序动态共享主存。3 3、存储保护 内存保护的任务是确保每道程序都在自己的内存空间运行，互不干扰。4、内存扩充 内存扩充的任务是从逻辑上来扩充内存容量，使用户认为系统所拥有的内存空间远比其实际的内存空间（硬件RAMRAM）大的多。5 5、地址重定位第4页/共90页6.1.3程序准备执行用户用高级语言编写的源用户用高级语言编写的源程序，需要经过编译、链程序，需要经过编译、链接和装入之后，才能被处接和装入之后，才能被处

4、理器运行。理器运行。编译将用户用高级语言编译将用户用高级语言编写的源程序转换为目标编写的源程序转换为目标模块；链接将用户程序需模块；链接将用户程序需要的所有目标模块链接在要的所有目标模块链接在一起，形成一个可执行模一起，形成一个可执行模块，即装入模块；装入将块，即装入模块；装入将装入模块放入内存。装入模块放入内存。用户程序的编译、链接用户程序的编译、链接和装入过程之间的关系如和装入过程之间的关系如图图6.2所示所示图图6.2 程序的编译、链接、加载程序的编译、链接、加载第5页/共90页6.1.3程序准备执行（续）1链接链接是将用户程序所需要的所有目标模块链接在一起的过程。链接的方式有静态链接、

5、装入时动态链接和运行时动态链接。（1）静态链接静态链接指链接过程在程序装入内存前完成并形成整个程序的逻辑地址空间。通常，由编译产生的所有目标模块的起始地址可能都是从0开始，每个模块中的程序代码地址都是相对于模块的起始地址。经过静态链接后，模块的地址重新编排，改写相关的地址。第6页/共90页6.1.3程序准备执行（续）图图6.3 程序链接程序链接模块ACALL Breturn模块BCALL Creturn模块Creturn0L-10M-10N-1模块AJSR Lreturn模块BJSR L+Mreturn模块Creturn链接后链接前第7页/共90页6.1.3程序准备执行（续）（2）装入时动态链

6、接经编译后的模块在装入内存准备运行前进行链接优点：便于修改和更新程序便于共享，节省外存空间缺点：共享模块并没有减少内存占用量（3）运行时动态链接在执行过程中若发现需要的某目标模块没有装入内存链接，则将它装入内存并链接。优点：模块共享提高内存利用率第8页/共90页6.1.3程序准备执行（续）2装入目标模块放入内存的过程为装入过程。装入过程实现了程序的逻辑地址和物理地址之间的变换。装入过程有三种方式，分别为：绝对装入方式、静态重定位装入方式和动态重定位装入方式。绝对装入：程序使用绝对地址编写，装入内存时装入到程序规定的地方，不需要进行地址变换。静态重定位装入：程序使用逻辑地址编写，装入内存后在执行

7、之前进行地址变换。动态重定位装入：程序使用逻辑地址编写，装入内存后在执行每条指令存取内存前进行地址变换。第9页/共90页6 6.1 1.4 地址重定位1.名字空间、地址空间和存储空间 符号地址：在源程序中，是通过符号名来访问子程序和数据的，这些符号名实际代表了地址，称为符号地址。例如，变量，子程序名，函数名，标号等。名字空间：我们把程序中符号名的集合称为“名字空间”。逻辑地址/程序地址/虚地址：程序中使用的从0开始进行编址的地址，可以是一维或二维地址。（逻辑）地址空间/程序空间：程序中逻辑地址的集合。内存地址/物理地址/绝对地址：内存单元的地址物理空间/存储空间/内存空间:内存地址的集合，是一

8、维线性空间。第10页/共90页6 6.1 1.4 地址重定位-1-1地址重定位：要把它装入内存执行，就要确定装入内存的实际物理地址，并修改程序中与地址有关的代码，把逻辑地址变换为物理地址，这个过程称为地址重定位。程序的名字空间、地址空间和存储空间之间的关系如图所示 汇编/编译 地址重定位 连 接 装 入 名字空间 地址空间 存储空间 （相对地址/逻辑地址空间）（绝对地址/物理地址空间）符 号源 程 序相对目标程序（装配模块）绝对目标程序第11页/共90页6 6.1 1.4 4 地址重定位-2-2 地址重定位完成把相对地址转换成内存中的绝对地址，这个过程称为地址映射（map）。按照重定位的时机，

9、可分为静态重定位和动态重定位。静态重定位 静态重定位是在程序执行之前进行重定位。它根据装配模块将要装入的内存起始地址，直接修改装配模块中的有关使用地址的指令。在图中以“0”作为参考地址的装配模块，要装入以1000为起始地址的存储空间。显然在装入程序之前，程序必须做一些修改才能正确运行。第12页/共90页6 6.1 1.4 地址重定位-3-3 0 0：10000 10000：100：LOAD 1，(2500)10100：LOAD 1，(12500)2500：365 12500：365 2600：12600：程序的地址空间 内存的地址空间例如：LOAD 1，2500 这条指令是把相对地址为2500

10、的存储单元的内容365装入1号累加器。而这时内容为365的存储单元的实际物理地址为12500（起始地址10000+相对地址2500），所以LOAD 1，2500 这条指令中的直接地址码要作相应的修改，即改为LOAD 1，12500。第13页/共90页6 6.1 1.4 地址重定位-4-4 在程序中需要修改的位置称为重定位项。程序装入内存中的起始地址称为重定位因子。为了支持静态重定位，连接程序在生成统一地址空间和装配模块时，还应产生一个重定位项表。所以操作系统的装入程序要把装入模块和重定位项表一起装入内存。由装配模块的实际装入起始地址得到重定位因子，然后取重定位项，加上重定位因子得到欲修改位置的

11、实际地址，最后对实际地址中的内容再加上重定位因子，从而完成指令代码的修改。当完成重定位后，就可以启动程序执行。优点：无须硬件支持的优点 缺点：一是程序重定位以后就不能在内存中移动；二是要求程序的存储空间是连续的，不能把程序存储到若干个不连续的区域中。第14页/共90页6 6.1 1.4 地址重定位-5-5动态重定位 动态重定位是指在程序执行过程中进行地址重定位，即在每次访问内存单元前才进行地址变换。动态重定位可使装配模块不加任何修改就装入内存，但是它需要硬件重定位寄存器的支持。下图给出了动态重定位的示意图。程序的目标模块在装入内存时，与地址有关的指令都无须进行修改，如在图中LOAD 1，250

12、0这条指令中仍保持相对地址2500。当该模块被操作系统调度到处理机上执行时，操作系统首先把该模块装入的实际起始地址减去目标模块的相对基地址（图中该模块的基地址为0），然后将其差值装入重定位寄存器。当CPU取一条访问内存的指令时，地址变换硬件逻辑自动将指令中的相对地址与重定位寄存器中的值相加，再根据和值作为内存的绝对地址去访问该单元的数据。第15页/共90页 100006.1.4 6.1.4 地址重定位-6-6 重定位寄存器 0：10000：100:LOAD 1,(2500)10100:LOAD 1,(2500)+2500：365 12500：365 2600：12600：程序的地址空间 内存的

13、地址空间 第16页/共90页6 6.1 1.4 地址重定位-7-7 优点：（1）目标程序装入内存时无需任何修改，所以装入之后再移动也不会影响其正确运行，这便于存储器用紧缩来解决存储器的碎片问题。（2）一个程序由若干个相对独立的目标模块组成时，每个目标模块各装入一个存储区域，这些存储区域可以不相领接，只要各个模块有自己对应的重定位寄存器就可以了。（3）可以部分装入内存，程序就可以运行 （4）便于多个进程共享同一程序副本。缺点：（1）需要硬件支持 （2）实现存储管理的算法较复杂。第17页/共90页6.2连续分配存储方式6.2.1单一连续分配 思想：这是一种最简单的存储管理方式，但只能用于单用户、单

14、任务的操作系统，如在8位和16位微机上CP/M和MS-DOS操作系统。它将内存分为两个区：系统区：仅供操作系统使用，通常设置在内存的低段；用户区：指除系统区以外的全部内存空间，提供给用户使用。存储保护：设置基址界限寄存器对。缺点：只支持单道程序运行不能充分利用内存空间不能实现虚拟存储第18页/共90页6.2.2固定分区(FixedPartitioning)分配思想：固定式分区是在作业装入之前，内存就被划分成若干个分区。划分工作可以由系统管理员完成，也可以由操作系统实现。然而一旦划分完成，在系统运行期间不再重新划分，即分区的个数不可变，分区的大小不可变，所以，固定式分区又称为静态分区。这种分区方

15、式一般将内存的用户区域划分成大小不等的分区，以适应不同大小的作业的需要。管理机构：系统有一张分区说明表，每个表目说明一个分区的大小、起始地址和是否已分配的使用标志。分区说明表和内存分配图如下所示。第19页/共90页0k：20k：第1分区（16kb）36k：第2分区（32kb）（已分配）68k：第3分区（64kb）（已分配）132k：第4分区（124kb）（未分配）256k：（b）内存分配图6.2.2固定分区分配-1-1区号 大小 起址标志 1 16KB 20K已分配 2 32KB36K已分配 3 64KB 68K已分配 4 124KB 132K 未分配 (a)分区说明表 操作系统作业A（16k

16、）作业B（26k）作业C（56k）第20页/共90页内存管理：分配算法和回收算法存储保护：设置基址界限寄存器对评价优点：支持多道程序缺点：易产生碎片 不支持虚拟存储 不能充分利用内存，当空闲分区之和能满足某程序而单个不能满足时，程序不能运行。？PCBPCB中与该管理配套的参数第21页/共90页6.2.3动态/可变式(DynamicPartitioning)分区分配思想：可变式分区是指在作业装入内存时，从可用的内存中划出一块连续的区域分配给它，且分区大小正好等于该作业的大小。可变式分区中分区的大小和分区的个数都是可变的，而且是根据作业的大小和多少动态地划分，因此又称为动态式分区。这种存储管理技术

17、是固定式分区的改进，既可以获得较大的灵活性，又能提高内存的利用率。可变式分区的分配和释放的基本思想是：在分配时，首先找到一个足够大的空闲分区，即这个空闲区的大小比作业要求的要大，系统则将这个空闲分区分成两部分：一部分成为已分配的分区，剩余的部分仍作为空闲区。在回收撤除作业所占领的分区时，要检查回收的分区是否与前后空闲的分区相领接，若是，则加以合并，使之成为一个连续的大空间。第22页/共90页ExampleDynamicPartitioningOperating SystemProcess 1320 KProcess 2Process 3224 K288 K64 KOperating Syste

18、mProcess 1320 KProcess 3224 K288 K64 KOperating SystemProcess 1320 KProcess 3288 K64 KProcess 4128 K96 K第23页/共90页ExampleDynamicPartitioningOperating System320 KProcess 3288 K64 KProcess 4128 K96 KOperating SystemProcess 3288 K64 KProcess 4128 K96 KProcess 2224 k96 K第24页/共90页6.2.3动态/可变式分区分配-2管理机构空闲区表

19、形式 空闲分区表为每个尚未分配的分区设置一个表项，包括分区的序号、大小、始址和状态。空闲区链形式 为了实现对空闲分区的分配和链接，在每个分区的起始部分，设置一些用于控制分区分配的信息（如分区的大小和状态位），以及用于链接其它分区的前向指针；在分区尾部，则设置了一个后向指针，为了检索方便也设置了控制分区分配的信息。然后，通过前、后向指针将所有的分区链接成一个双向链表。第25页/共90页0k：20k：52k：116k：164k：260k：512k：（c）内存分配图可变式分区数据结构图表 序号P P大小起址状态 1 14848k k116k116k空闲 2 2252252k k260k260k空闲

20、3 3空表目 4 4空表目 5 5空表目 （a）空闲分区表 操作系统作业1（32k）作业2（64k）空闲区（48k）作业4（96k）空闲区（252k）前向指针 N+2 00后向指针 N+2 00N个字节可用第26页/共90页0k：20k：52k：116k：164k：260k：512k：（c）内存分配图可变式分区数据结构图表 序号P P大小起址状态 1 13232k k20k20k已分配 2 26464k k52k52k已分配 3 39696K K164k 164k 已分配 4 4空表目 5 5空表目 （a）已分配分区表 操作系统作业1（32k）作业2（64k）空闲区（48k）作业4（96k）空

21、闲区（252k）前向指针 N+2 00后向指针 N+2 00N个字节可用（b）已分配分区链结构第27页/共90页分区分配算法(PartitioningPlacementAlgorithm)最佳适应算法（Best Best FitFit）：它从全部空闲区中找出能满足作业要求的、且大小最小的空闲分区，这种方法能使碎片尽量小。为适应这种算法，空闲分区表（空闲区链）中的空闲分区要按大小从小到大进行排序，自表头开始查找到第一个满足要求的自由分区分配。首次适应算法（First First FitFit）：从空闲分区表的第一个表目起查找该表，把最先能够满足要求的空闲区分配给作业，这种方法目的在于减少查找时间

22、。为适应这种算法，空闲分区表（空闲区链）中的空闲分区要按地址由低到高进行排序。循环首次适应算法：该算法是首次适应算法的变种。在分配内存空间时，不再每次从表头（链首）开始查找，而是从上次找到的空闲区的下一个空闲区开始查找，直到找到第一个能满足要求的的空闲区为止，并从中划出一块与请求大小相等的内存空间分配给作业。该算法能使内存中的空闲区分布得比较均匀。最坏适应法：从所有未分配的分区中挑选最大的且大于和等于作业大小的分区分给要求的作业；空闲分区按大小由大到小排序。第28页/共90页DynamicPartitioningPlacementAlgorithmLastallocatedblock(14K)

23、BeforeAfter8K8K12K12K22K18K6K6K8K8K14K14K6K2K36K20KNext FitFree blockAllocated blockBest FitFirst Fit例：分配一个16KB分区第29页/共90页3。UNIX分配回收算法（采用空闲分区表结构和首次适应算法）UNIX空闲分区表数据结构 Coremap m_addrm_size.m_addrm_size=0.m_addrm_sizem_addrm_sizem_addrm_sizem_addrm_size空闲分区表中的空闲分区要按地址从低到高连续排序，最后一个空闲分区中 m_size为0表示以上表目空白

24、。空闲分区表起始地址为coremap分配和释放的基本思想是：在分配时，首先找到一个足够大的空闲分区，即这个空闲区的大小比作业要求的要大，系统则将这个空闲分区分成两部分：一部分成为已分配的分区，剩余的部分仍作为空闲区。在回收撤除作业所占领的分区时，要检查回收的分区是否与前后空闲的分区相领接，若是，则加以合并，使之成为一个连续的大空间。第30页/共90页UNIX分配算法框图申请分配一个u.size大小的分区从头开始查表是否检索完毕？本次无法分配m.size=u.size m.size-u.sizeaa或m.size=0不是第一个表目与前一可用区相 邻？与后一可用分区相邻且不为空表 目？把所释放的可

25、用区 与前一分区合并所释放的可用区与一可用区合并所 释 放 可用 区 的size=0?与后一可用 区 相邻？与后一可用区合并将该表目以上的所有表目下移一格 返 回mfree是否第34页/共90页存储保护：评价：优点：支持多道程序相对于固定分区，在一定程度上减少了碎片。缺点：仍然存在碎片不支持虚拟存储 不能充分利用内存，当空闲分区之和能满足某程序而单个不能满足时，程序不能运行。第35页/共90页6.2.4动态重定位分区分配思想：与动态分区一样，但分区可以移动以便把较小的空闲分区合并成一个较大的空闲分区，因而需要动态重定位的支持。1、拼接/紧凑 可变式分区也有零头问题。在系统不断地分配和回收中，必

26、定会出现一些不连续的小的空闲区，称为外零头。虽然可能所有零头的总和超过某一个作业的要求，但是由于不连续而无法分配。解决零头的方法是拼接（或称紧凑），即向一个方向（例如向低地址端）移动已分配的作业，使那些零散的小空闲区在另一方向连成一片。分区的拼接技术，一方面是要求能够对作业进行重定位，另一方面系统在拼接时要耗费较多的时间。2、动态重定位 实现紧凑所需的允许作业在运行过程中在内存中移动的技术必须获得硬件支持。只有具有动态重定位硬件机构的计算机系统，才有可能采取动态重定位可变分区多道管理技术，系统的硬件包括重定位寄存器和加法器。第36页/共90页动态重定位分区分配3动态重定位分区分配算法 动态重定

27、位分区管理中何时进行存储器紧缩有二种不同的解决办法：在某个分区被释放后立即进行紧缩，系统总是只有一个连续的分区而无碎片，此法很花费机时。当“请求分配模块”找不到足够大的自由分区分给用户时再进行紧缩，这样紧缩的次数比上种方法少得多，但表格管理复杂。采用此法的动态重定位分区分配算法框图如下：第37页/共90页动态重定位分区分配算法框图 N N Y Y 请求分配u.size分区检索空闲分区链（表）无法分配 返回空 闲 分 区总和u.size找到大于u.size的可用 区否？进行紧凑形成 连续空闲区修改有关的数据结构 按动态分区方式 进行分配修改有关的 数据结构返回分区号 及首址第38页/共90页4、

28、存储保护5、评价优点：支持多道程序比动态分区前进一步，当空闲分区之和能满足某程序而单个不能满足时可以通过合并空闲分区的办法让程序装入。缺点：不能解决虚拟存储 移动合并需要增加系统开销仍然存在碎片第39页/共90页6.3覆盖与交换技术6.3.1覆盖技术 为了能在小的内存空间中运行大的作业，许多机器（如PDP11，IBMPC）都采用了“覆盖”技术。覆盖是指一个作业的若干程序段（或数据段）间，或者几个作业的某些程序段间共享某主存空间。覆盖技术通常与单用户连续分配、固定分区和可变分区等存储管理技术配合使用。它不但用于用户作业的运行中，而且还常用于操作系统本身的运行中。第40页/共90页6.3.1覆盖技

29、术-1-1 覆盖技术的基本概念可用下图来加以说明，一个作业由一个主程序段MAINMAIN主若干程序数据段组成，其调用关系如a a所示，我们把树形关系中常驻内存的段主程序段MAINMAIN叫根段，其余覆盖部分分成层次，A A0 0与B B0 0为一层，组成一个覆盖段0 0，同理A A1 1、A A2 2与B B1 1组成覆盖段1 1，在A A3 3和A A4 4组成覆盖段2 2，同一时间内同一覆盖段的各程序段（称为覆盖），只有一个覆盖在执行可被引用，它不能调用同层中的其它覆盖。如不采用覆盖技术，该作业要求270K主存，采用覆盖技术后只要求160K主存。第41页/共90页6.3.1覆盖技术-2-2

30、 （a）(b)MAIN 20KA030KB040KA160KA230KB130KA320KA440K覆盖段040K覆盖段160K覆盖段2 40KMAIN A0 A1A2A3A4B1B0第42页/共90页6.3.1覆盖技术-3-3覆盖结构的输入 PDP11的RSX22H提供覆盖描述语言ODL来描述结构，并构成覆盖描述文件，如上图用ODL语言表示如下：ROOT MAIN（A0（A1，A2（A3，A4），B0（B1，B2）；ENDl覆盖数据结构 用户将覆盖描述文件随目标程序一起提交系统，系统根据覆盖描述文件形成一个覆盖数据结构。该数据结构对每个覆盖段有一个描述信息，它包括覆盖段号、覆盖数、当前覆盖号

31、、覆盖区始址、覆盖区长度、起始盘区号等。系统根据覆盖调度程序和覆盖调度结构自动地将各程序段装入运行。第43页/共90页6.3.2 交换（对换）技术 交换技术最早用在麻省理工学院的兼容分时系统CTSS中，该系统是单用户系统，所有用户都驻留在外存的后备队列中，每次只调入一个作业进入内存运行，此作业的时间的时间片用完时，又将该作业调至外存，再将后备队列中的一个作业调入内存运行一个时间片。这是早期的简单分时系统，它采用早期的交换（调进凋出）来满足多个程序共享主存的需要。1。多道程序环境下的对换 在多道程序环境下为了提高内存和CPU的利用率，增加系统吞吐量，系统中增设了对换，把内存中暂不能运行的进程调出

32、到外存上，以腾出足够的内存空间，把已具备运行条件的进程换入内存。UNIX早期已引入对换功能并一直保留至今，UNIX系统设置一个对换进程完成以上功能。为了实现进程对换，系统必须能实现对对换空间的管理，进程换入和进程换出等三项功能。第44页/共90页6.3.2 交换（对换）技术-22。对换空间的管理 外存分为文件区和对换区。文件区用户存放文件，对文件区管理目标是提高文件存储空间的利用率，为此系统采用离散分配方式；对换区用于存放从内存频繁换出的进程，它的管理目标是提高进程换入换出速度，为此系统采用连续分配方式。UNIX对换区采用空闲分区表和首次适应算法的动态分区管理，类同早期内存管理。3。进程的换出

33、与换入当内核发现内存不足时调用对换进程，对换进程检查驻留在内存的进程，选择处于阻塞和睡眠状态的进程换出，如无则选择优先级低的驻留内存时间长的处于就绪状态的进程换出。而当内存又空时对换进程在对换区中选择换出时间长的处于就绪态的进程调入。第45页/共90页6.4 6.4 分页存储管理6.4.1 6.4.1 分页存储管理原理1分页 分页存储管理是将一个进程的地址空间划分成若干个大小相等的区域，称为页，相应地，将内存空间划分成与页相同大小的若干个物理块，称为块或页框。在为进程分配内存时，将进程中的若干页分别装入多个不相邻接的块中。2 2.地址结构 分页系统的地址结构如下图所示，它由两部分组成：前一部分

34、为页号P P；后一部分为位移量W W，即页内地址。图中的地址长度为3232位，其中0 01111位为页内地址（每页的大小为4 4K K），12123131位为页号，所以允许地址空间的大小最多为1 1M M个页。31 12 11 031 12 11 0 页号 P 位移量W第46页/共90页6.4.1 6.4.1 分页存储管理原理-1-13 3.页表 在将进程的每一页离散地分配到内存的多个物理块中后，系统应能保证能在内存中找到每个页面所对应的物理块。为此，系统为每个进程建立了一张页面映射表，简称页表（如下图所示）。每个页在页表中占一个表项，记录该页在内存中对应的物理块号。进程在执行时，通过查找页表

35、，就可以找到每页所对应的物理块号。可见，页表的作用是实现从页号到物理块号的地址映射。第47页/共90页分页存储管理原理-2-2第48页/共90页6.4.2 地址变换机构1.基本的地址变换机构 地址变换机构的基本任务是利用页表把用户程序中的逻辑地址变换成内存中的物理地址，实际上就要将用户程序中的页号变换成内存中的物理块号。为了实现地址变换功能，在系统中设置页表寄存器，用来存放页表的始址和页表的长度。在进程未执行时，每个进程对应的页表的始址和长度存放在进程的PCB中，当该进程被调度时，就将它们装入页表寄存器。在进行地址变换时，系统将页号与页表长度进行比较，如果页号大于页表寄存器中的页表长度，则访问

36、越界，产生越界中断。如未出现越界，则根据页表寄存器中的页表始址和页号计算出该页在页表项中的位置，得到该页的物理块号，将此物理块号装入物理地址寄存器中。与此同时，将有效地址（逻辑地址）寄存器中页内地址直接装入物理地址寄存器的块内地址字段中，这样便完成了从逻辑地址到物理地址的变换。第49页/共90页6.4.2 地址变换机构-1第50页/共90页2.具有快表的地址变换机构如果页表存放在内存中，则每次访问内存时，都要先访问内存中的页表，然后根据所形成的物理地址再访问内存。这样CPU存一个数据必须访问两次内存，从而使计算机的处理速度降低了1/2。为了提高地址变换的速度，在地址变换机构中增设了一个具有并行

37、查询功能的特殊的高速缓冲存储器，称为“联想存储器”或“快表”，用以存放当前访问的那些页表项。此时地址变换过程为：在CPU给出有效地址后，地址变换机构自动地将页号送入高速缓存，确定所需要的页是否在快表中。若是，则直接读出该页所对应的物理块号，送入物理地址寄存器；若在快表中未找到对应的页表项，则需再访问内存中的页表，找到后，把从页表中读出的页表项存入快表中的一个寄存器单元中，以取代一个旧的页表项。第51页/共90页2.具有快表的地址变换机构-1由于成本的原因，快表不可能做得很大，通常只能存放16512个页表项。例如，在Intel80486中有32个。这对中、小型作业来说，已可能把全部页表项放入快表

38、中；但对于大型作业来说，则只能将一部分页表放入快表中。由于对程序和数据的访问往往带有局限性，所以快表的命中率可以达到80%90%。例如，假设检索联想存储器的时间为20ns，访问内存的时间为100ns，访问联想存储器的的命中率为85%，则CPU存取一个数据的平均时间为T=0.85*120+0.15*220=135ns，所以访问时间只增加35%。如果不引入联想存储器，其访问将延长一倍（达200ns）。第52页/共90页2.具有快表的地址变换机构-2第53页/共90页6.4.3 6.4.3 两级页表机制 80386 80386的逻辑地址有232B，如页面大小为4 4KBKB（2 21212B B），

39、则页表项(页数)达1 1M M个，每个页表项（页表中的一行）占用4 4B B，故每个进程的页表占用4 4MBMB内存空间，还要求是连续的，显然这是不现实的。在8038680386中，为了减少页表所占用的连续的内存空间，采用了两级页表机制：基本方法是将页表进行分页，每个页面的大小与内存物理块的大小相同，并为它们进行编号，可以离散地将各个页面分别存放在不同的物理块中，为此再建立一张页表，称为外层页表（页表目录），即第一级页表，其中的每个表目是存放某个页表的物理地址。第二级才是页表，其中的每个表目所存放的才是页的物理块号。第54页/共90页6.4.3 6.4.3 两级页表机制-1-1两级页表系统将3

40、232位逻辑地址空间的地址分成三段：其中，页表目录号（外层页号p1p1）和页号（外层页内地址p2p2）两项各占1010位，偏移量（页内地址d d）占1212位。每页的大小为4 4KBKB。由于物理块号和页表的物理地址都占4 4个字节，使每页中包含10241024个页表项，所以页表目录和页表的大小也都是4 4KBKB，即一页。在8038680386中设置了一个外层页表寄存器（CR3CR3），用于存放页表目录的基址。两级页表的逻辑地址结构和两级页表的地址变换机构图如下：第55页/共90页6.4.3 6.4.3 两级页表机制-2-2第56页/共90页6.4.4存储管理算法1.数据结构在PCB中记录页

41、表的地址和长度设置内存块表，记录每个块的状态（已分配/空闲），整个系统一张。页表：每个进程一张2.分配和释放算法分配：第57页/共90页请求分配X大小的空间计算所需块数N=向上取整（X/每页大小）在PCB中填写页表长度N有N个可用块吗？N失败分配页表，在PCB中填写页表地址检查内存块表，分配N个空闲块，在每块的状态栏填写已分配，同时块号填入页表返回第58页/共90页释放算法:6.4.5评价优点：支持多道程序设计克服可重定位动态分区要移动合并的工作，程序不必连续存放。大大减少碎片缺点：动态地址变换需要增加计算机的成本并降低处理机速度。各种表格要占用一定空间，需要一些系统时间来维护不支持虚拟存储最

42、后一页仍有碎片。第59页/共90页6.4.5多级页表（续）如果一个系统的逻辑地址为32位，页面占12位，即页表页内为12位；页表页占10位，页目录占10位。逻辑地址为4206596（十进制），所对应的物理地址通过如下方法获得：逻辑地址4206596（十进制）对应的32位二进制码为00000000010000000011000000000100；这样，页内偏移为000000000100（为4），即页表页内号或页内偏移为4；二级页表（页表页）为0000000011（为3），即页表页号为3；一级页表（页目录表）为0000000001（为1），即页目录号为1；首先，地址变换机构通过页目录表寄存器得到页

43、目录表的起始地址，通过页目录表的起始地址得到页目录表，查找页目录表（一级页表）中的表项1，得到页表页（二级页表）中某页在内存的物理块号为n1；然后，通过物理块号n1得到页表某页（二级页表中的页），查找该页表页的表项3得到内存中的物理块号n2；最后，将物理块号n2的起始地址加上页内偏移4得到了逻辑地址4206596在内存中的物理地址n3。二级页表地址变换获取内存信息需要三次访问内存，第一次访问的是页目录，第二次访问的是页表页，第三次访问通过物理地址获取内存信息。同样，为了节约时间，系统也可以采用快表获取内存信息。第60页/共90页6.4.5多级页表（续）当逻辑地址的位数更多时，系统会采用三级、四

44、级，甚至更多级的页表。级别更多，灵活性越大，但是管理也更复杂。SUN公司的Solaris操作系统基于SPACE处理器，采用了三级页表，如图6.17所示。32位逻辑地址分为四部分：高8位部分作为一级页表，之后的6位作为二级页表，再向后6位作为三级页表，最后12位作为页内地址。因此，页面大小为4K。在地址变换之前，操作系统会给每个新进程分配一个上下文号，进程保留自己的上下文号直到结束。系统硬件支持高达4096个上下文号。地址变换过程是将上下文号与逻辑地址一起输入给地址变换机构。上下文号作为上下文表的索引得到进程的第一级页表起始地址；逻辑地址中的高8位作为索引查找一级页表，得到二级页表的起始地址；逻

45、辑地址中的高8位之后的6位作为索引查找二级页表，得到三级页表的起始地址，逻辑地址中的再后面6位作为索引得到三级页表中的物理块号；最后将逻辑地址中的低12位作为块内偏移，得到物理地址。第61页/共90页6.3.5多级页表（续）图6.17 SUN Solaris三级页表结构 虽然，多级页表解决了分散存放页表的问题，但是，并未解决页表占用大量内存空间的问题。解决该问题初步的办法是将换出内存的进程的页表与进程一起换出，在虚拟存储器管理中将进一步处理该问题。第62页/共90页6.3.6反置页表（InvertedPageTable）如果是64位逻辑地址，页面大小为4KB，则有252个逻辑页面，相应地，可能

46、会有252个页表项，页表非常大。如果逻辑地址位数更多，则页表更大。虽然系统可以采用多级页表，但是对于内存，这仍然是一个巨大的负担。IBMAS/400操作系统采用了一种反置页表（InvertedPageTable），该种页表从内存物理块出发，如果进程占用一个内存物理块，则在页表中有一页表项。页表中所有的页表项是已经进入内存的物理块。反置页表根据进程占用的物理块的块号进行排序，如果进程页面没有全部进入内存，则页表项数小于进程的页面数。反置页表在虚拟存储器管理方式下具有很大的优势。虽然反置页表节约了内存空间，但是，采用反置页表将使从逻辑地址到物理地址的变换变得更加复杂。当地址变换机构从逻辑地址得到了

47、页号后，CPU不能直接从页表中定位页表项，必须搜索整个页表，查找该页号对应的页表项。对每一个地址变换都需要作全表的搜索，这降低了系统的运行效率。第63页/共90页6.3.6反置页表（InvertedPageTable）（续）为了快速完成地址变换过程，系统可以采用哈希表技术。地址变换机构将进程标志和页号输入给哈希函数，得到一个哈希值。该哈希值指向反置页表中的一个表项，所有哈希值相同的组织成一组散列队列链。CPU遍历散列队列链找到进程的页号，而对应该页号的索引则为物理块号，如图6.18所示。物理块号加上页内偏移便为物理地址。如果整个反置页表中不能找到对应的物理块，则说明该页没有进入内存，系统发出缺

48、页中断。用反置页表进行地址变换时，系统需要访问两次内存，一次是访问哈希表，一次是访问反置页表。为了加快速度，系统也可以用联想寄存器。CPU虽然可以用反置页表完成地址变换，但在实现过程中，因为不在内存中的页面信息不能体现在反置页表中，所以，系统仍然需要创建一般的页表。一般的页表不放在内存中，而放在磁盘上，当某页面进入内存时，需要从磁盘的一般页表中将该页信息放入反置页表，这时，系统需要多访问一次磁盘，速度会很慢。第64页/共90页6.3.6反置页表（InvertedPageTable）（续）图6.18 反置页表实现地址变换第65页/共90页6.3.7分页存储管理中的页面共享和保护在多道程序环境下，

49、许多公共程序，如编辑程序、编译程序、解释程序、公共子程序和公用数据等，是可以共享的。共享的部分只需要在内存中保留一个副本。分页存储管理能够为多个进程提供共享的程序和数据，但是，必须区分数据共享和程序共享。实现数据共享时，允许不同的进程对共享的数据页面采用不同的页号，只要共享进程页表中的相关表项指向同一个共享的数据块的物理块号即可。实现程序共享时，分页存储结构要求逻辑地址空间连续。如果采用静态链接，则进程运行前共享部分在每个进程中的页号是确定的。而内存中共享则需要将这些不同页号的页面统一为一个页号。因此，当共享的进程道数较多时，页号的统一比较困难。如果采用运行时再链接，则实现起来相对容易。共享使

50、得内存中只存在一个副本，节约了内存空间。但是，共享也会带来一些问题，最常见的是对某个页面的进程读写发生冲突而产生的问题，以及共享带来的信息泄漏问题。因此，分页管理必须实现页面保护。常用的页面保护措施是在页表中增加页的读写访问标志，对不允许访问的进程则停止执行并发出中断信号。第66页/共90页6.5 分段存储管理6.5.1分段存储管理方式的引入1.便于编程 通常用户常常把自己的作业按照逻辑关系划分成若干个段，每个段都有自己的名字，且都从零开始编址，这样，用户程序再执行中可用段名和段内地址进行访问。例如：LOAD 1，A|这条指令的含义是将分段A中的D单元内的值读入寄存器1。2.分段共享 在实现程