第6章存储器管理.pptx

计算机操作系统计算机操作系统主讲主讲:四川大学计算机学院四川大学计算机学院杜忠军杜忠军第第6章章 存储器管理存储器管理 计算机作为信息处理的工具，其重要的特点之一是具有存储能力。计算机的存储系统主要包括内存储器和外存储器。内存储器为执行内存，存放处理器执行时所需要的所有代码和数据。外存储器是辅助存储器，存放需要长期保存的信息。外存储器保存的信息必须进入内存储器后才能被处理器运行。存储器管理是操作系统的主要功能之一，本章所述的存储器管理是指对内存储器的管理。虽然计算机系统的内存容量不断增大，但仍然难以满足软件发展的需求。对内存资源管理是否有效，不仅关系到内存本身的利用率，还关系到整个系统性能和效率。内存管理分为连续管理方式和离散管理方式。连续管理方式将用户程序连续放置在内存，适合单道程序环境。离散管理方式将用户程序以分页或分段方式放置在内存，适合多道程序环境。离散分配方式也是实现虚拟存储器管理的基础。本章针对传统存储器管理进行讲解，虚拟存储器管理在下一章中讲述。本章的主要内容如下：l存储器管理概述l连续存储管理l分页式存储管理l分段式存储管理6.1 存储器管理概述存储器管理概述6.1.1存储器的层次存储器的层次 对计算机存储系统对计算机存储系统的基本要求是存储容的基本要求是存储容量大、存取速度快、量大、存取速度快、成本价格低。按照计成本价格低。按照计算机的体系结构，计算机的体系结构，计算机存储系统可以划算机存储系统可以划分为分为3个层次，分别是：个层次，分别是：处理器寄存器和高速处理器寄存器和高速缓存、内存储器、外缓存、内存储器、外存储器，如图存储器，如图6.1所示。所示。图图6.1计算机存储系统层次划分计算机存储系统层次划分6.1.2存储管理目的和存储管理目的和功能功能1 1、主存储器的分配和回收、主存储器的分配和回收 内内存存分分配配的的主主要要任任务务是是为为每每一一道道程程序序分分配配内内存存空空间间，使使它它们们“各得其所各得其所”。2 2、提提高高主主存存储储器器的的利利用用率率，减减少少不不可可用用的的存存储储空空间间（称称为为“零零头），允许头），允许多道程序多道程序动态共享主存。动态共享主存。3 3、存储保护、存储保护 内内存存保保护护的的任任务务是是确确保保每每道道程程序序都都在在自自己己的的内内存存空空间间运运行行，互不干扰。互不干扰。4、内存、内存扩充扩充 内内存存扩扩充充的的任任务务是是从从逻逻辑辑上上来来扩扩充充内内存存容容量量，使使用用户户认认为为系系统统所所拥拥有有的的内内存存空空间间远远比比其其实实际际的的内内存存空空间间（硬硬件件RAMRAM）大大的的多。多。5 5、地址重定位、地址重定位6.1.3程序准备执行程序准备执行用户用高级语言编写的源用户用高级语言编写的源程序，需要经过编译、链程序，需要经过编译、链接和装入之后，才能被处接和装入之后，才能被处理器运行。理器运行。编译将用户用高级语言编译将用户用高级语言编写的源程序转换为目标编写的源程序转换为目标模块；链接将用户程序需模块；链接将用户程序需要的所有目标模块链接在要的所有目标模块链接在一起，形成一个可执行模一起，形成一个可执行模块，即装入模块；装入将块，即装入模块；装入将装入模块放入内存。装入模块放入内存。用户程序的编译、链接用户程序的编译、链接和装入过程之间的关系如和装入过程之间的关系如图图6.2所示所示图图6.2程序的编译、链接、加载程序的编译、链接、加载6.1.3程序准备执行（续）程序准备执行（续）1链接链接 链接是将用户程序所需要的所有目标模块链接在一起链接是将用户程序所需要的所有目标模块链接在一起的过程。链接的方式有静态链接、装入时动态链接和运行的过程。链接的方式有静态链接、装入时动态链接和运行时动态链接。时动态链接。（1）静态链接）静态链接 静态链接指链接过程在程序装入内存前完成并形成整静态链接指链接过程在程序装入内存前完成并形成整个程序的逻辑地址空间。通常，由编译产生的所有目标模个程序的逻辑地址空间。通常，由编译产生的所有目标模块的起始地址可能都是从块的起始地址可能都是从0开始，每个模块中的程序代码开始，每个模块中的程序代码地址都是相对于模块的起始地址。经过静态链接后，模块地址都是相对于模块的起始地址。经过静态链接后，模块的地址重新编排，改写相关的地址。的地址重新编排，改写相关的地址。6.1.3程序准备执行（续）程序准备执行（续）图图6.3程序链接程序链接模块ACALL Breturn模块BCALL Creturn模块Creturn0L-10M-10N-1模块AJSR Lreturn模块BJSR L+Mreturn模块Creturn链接后链接后链接前链接前6.1.3程序准备执行（续）程序准备执行（续）（2）装入时动态链接）装入时动态链接经编译后的模块在装入内存准备运行前进行链接经编译后的模块在装入内存准备运行前进行链接优点：优点：便于修改和更新程序便于修改和更新程序便于共享，节省外存空间便于共享，节省外存空间缺点：共享模块并没有减少内存占用量缺点：共享模块并没有减少内存占用量（3）运行时动态链接）运行时动态链接在执行过程中若发现需要的某目标模块没有装入内存链在执行过程中若发现需要的某目标模块没有装入内存链接，则将它装入内存并链接。接，则将它装入内存并链接。优点：优点：模块共享模块共享提高内存利用率提高内存利用率6.1.3程序准备执行（续）程序准备执行（续）2装入装入 目标模块放入内存的过程为装入过程。装入目标模块放入内存的过程为装入过程。装入过程实现了程序的逻辑地址和物理地址之间的变过程实现了程序的逻辑地址和物理地址之间的变换。装入过程有三种方式，分别为：绝对装入方换。装入过程有三种方式，分别为：绝对装入方式、静态重定位装入方式和动态重定位装入方式。式、静态重定位装入方式和动态重定位装入方式。绝对装入绝对装入：程序使用绝对地址编写，装入内：程序使用绝对地址编写，装入内存时装入到程序规定的地方，不需要进行存时装入到程序规定的地方，不需要进行地址变换。地址变换。静态重定位装入静态重定位装入：程序使用逻辑地址编写，：程序使用逻辑地址编写，装入内存后在执行之前进行地址变换。装入内存后在执行之前进行地址变换。动态重定位装入动态重定位装入：程序使用逻辑地址编写，：程序使用逻辑地址编写，装入内存后在执行每条指令存取内存前进装入内存后在执行每条指令存取内存前进行地址变换。行地址变换。6 6.1 1.4 地址重定位地址重定位1.名字空间、地址空间和存储空间名字空间、地址空间和存储空间 符号地址符号地址：在源程序中，是通过符号名来访问子程序和数据的，这些符号名实际代表了地址，称为符号地址。例如，变量，子程序名，函数名，标号等。名字空间名字空间：我们把程序中符号名的集合称为“名字空名字空间间”。逻辑地址逻辑地址/程序地址程序地址/虚地址虚地址：程序中使用的从0开始进行编址的地址，可以是一维或二维地址。（逻辑）地址空间（逻辑）地址空间/程序空间程序空间：程序中逻辑地址的集合。内存地址内存地址/物理地址物理地址/绝对地址绝对地址：内存单元的地址物理空间物理空间/存储空间存储空间/内存空间内存空间:内存地址的集合，是一维线性空间。6 6.1 1.4 地址重定位地址重定位-1-1地地址址重重定定位位：要把它装入内存执行，就要确定装入内存的实际物理地址，并修改程序中与地址有关的代码，把逻辑地址变换为物理地址，这个过程称为地址重定位。程 序 的 名 字 空 间、地 址 空 间 和 存 储 空 间 之 间 的 关 系 如 图 所 示 汇编/编译 地址重定位 连 接 装 入 名字空间 地址空间 存储空间 （相对地址/逻辑地址空间）（绝对地址/物理地址空间）符 号源 程 序相对目标程序（装配模块）绝对目标程序6 6.1 1.4 4 地址重定位地址重定位-2-2 地址重定位完成把相对地址转换成内存中的绝对地址，这个过程称为地址映射（map）。按照重定位的时机，可分为静态重定位和动态重定位。静态重定位静态重定位 静态重定位是在程序执行之前进行重定位。它根据装配模块将要装入的内存起始地址，直接修改装配模块中的有关使用地址的指令。在图中以“0”作为参考地址的装配模块，要装入以1000为起始地址的存储空间。显然在装入程序之前，程序必须做一些修改才能正确运行。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的的存存储储单单元元的的内内容容365装装入入1号号累累加加器器。而而这这时时内内容容为为365的的存存储储单单元元的的实实际际物物理理地地址址为为12500（起起始始地地址址10000+相相对对地地址址2500），所所以以LOAD 1，2500 这这条条指指令令中中的的直直接接地地址址码码要要作作相相应应的的修修改改，即即改为改为LOAD 1，12500。6 6.1 1.4 地址重定位地址重定位-4-4 在程序中需要修改的位置称为重定位项。程序装入内存中的起始地址称为重定位因子。为了支持静态重定位，连接程序在生成统一地址空间和装配模块时，还应产生一个重定位项表。所以操作系统的装入程序要把装入模块和重定位项表一起装入内存。由装配模块的实际装入起始地址得到重定位因子，然后取重定位项，加上重定位因子得到欲修改位置的实际地址，最后对实际地址中的内容再加上重定位因子，从而完成指令代码的修改。当完成重定位后，就可以启动程序执行。优点优点：无须硬件支持的优点 缺点缺点：一是程序重定位以后就不能在内存中移动；二是要求程序的存储空间是连续的，不能把程序存储到若干个不连续的区域中。6 6.1 1.4 地址重定位地址重定位-5-5动态重定位动态重定位 动态重定位是指在程序执行过程中进行地址重定位，即在每次访问内存单元前才进行地址变换。动态重定位可使装配模块不加任何修改就装入内存，但是它需要硬件重定位寄存器的支持。下图给出了动态重定位的示意图。程序的目标模块在装入内存时，与地址有关的指令都无须进行修改，如在图中LOAD 1，2500这条指令中仍保持相对地址2500。当该模块被操作系统调度到处理机上执行时，操作系统首先把该模块装入的实际起始地址减去目标模块的相对基地址（图中该模块的基地址为0），然后将其差值装入重定位寄存器。当CPU取一条访问内存的指令时，地址变换硬件逻辑自动将指令中的相对地址与重定位寄存器中的值相加，再根据和值作为内存的绝对地址去访问该单元的数据。100006.1.4 6.1.4 地址重定位地址重定位-6-6 重定位寄存器重定位寄存器 0：10000：100:LOAD 1,(2500)10100:LOAD 1,(2500)+2500：365 12500：365 2600：12600：程序的地址空间程序的地址空间 内存的地址空间内存的地址空间 6 6.1 1.4 地址重定位地址重定位-7-7 优点优点：（1）目标程序装入内存时无需任何修改，所以装入之后再移动也不会影响其正确运行，这便于存储器用紧缩来解决存储器的碎片问题。（2）一个程序由若干个相对独立的目标模块组成时，每个目标模块各装入一个存储区域，这些存储区域可以不相领接，只要各个模块有自己对应的重定位寄存器就可以了。（3）可以部分装入内存，程序就可以运行 （4）便于多个进程共享同一程序副本。缺点缺点：（1）需要硬件支持 （2）实现存储管理的算法较复杂。6.2连续分配存储方式连续分配存储方式6.2.1单一连续分配单一连续分配 思想：思想：这是一种最简单的存储管理方式，但只能用于单用户、单任务的操作系统，如在8位和16位微机上CP/M和MS-DOS操作系统。它将内存分为两个区：系统区：仅供操作系统使用，通常设置在内存的低段；用户区：指除系统区以外的全部内存空间，提供给用户使用。存储保护存储保护：设置基址界限寄存器对。缺点缺点：只支持单道程序运行不能充分利用内存空间不能实现虚拟存储6.2.2固定分区固定分区(FixedPartitioning)分配分配思想：固定式分区是在作业装入之前，内存就被划分成若干个分区。划分工作可以由系统管理员完成，也可以由操作系统实现。然而一旦划分完成，在系统运行期间不再重新划分，即分区的个数不可变，分区的大小不可变，所以，固定式分区又称为静态分区。这种分区方式一般将内存的用户区域划分成大小不等的分区，以适应不同大小的作业的需要。管理机构管理机构：系统有一张分区说明表，每个表目说明一个分区的大小、起始地址和是否已分配的使用标志。分区说明表和内存分配图如下所示。0k：20k：第1分区（16kb）36k：第2分区（32kb）（已分配）68k：第3分区（64kb）（已分配）132k：第4分区（124kb）（未分配）256k：（b）内存分配图 6.2.2固定分区分配固定分区分配-1-1区号 大小 起址标志 1 16KB20K已分配 2 32KB36K已分配 3 64KB68K已分配 4 124KB 132K未分配 (a)分区说明表 操作系统作业A（16k）作业B（26k）作业C（56k）内存管理内存管理：分配算法和回收算法分配算法和回收算法存储保护存储保护：设置基址界限寄存器对设置基址界限寄存器对评价评价优点：支持多道程序优点：支持多道程序缺点：易产生碎片缺点：易产生碎片 不支持虚拟存储不支持虚拟存储 不能充分利用内存，当空闲分区之和能满足不能充分利用内存，当空闲分区之和能满足某程序而单个不能满足时，程序不能运行。某程序而单个不能满足时，程序不能运行。？PCBPCB中与该管理配套的参数中与该管理配套的参数6.2.3动态动态/可变式可变式 (DynamicPartitioning)分区分配分区分配思思想想：可变式分区是指在作业装入内存时，从可用的内存中划出一块连续的区域分配给它，且分区大小正好等于该作业的大小。可变式分区中分区的大小和分区的个数都是可变的，而且是根据作业的大小和多少动态地划分，因此又称为动态式分区。这种存储管理技术是固定式分区的改进，既可以获得较大的灵活性，又能提高内存的利用率。可变式分区的分配和释放的基本思想是：在分配时，首先找到一个足够大的空闲分区，即这个空闲区的大小比作业要求的要大，系统则将这个空闲分区分成两部分：一部分成为已分配的分区，剩余的部分仍作为空闲区。在回收撤除作业所占领的分区时，要检查回收的分区是否与前后空闲的分区相领接，若是，则加以合并，使之成为一个连续的大空间。ExampleDynamicPartitioningOperating SystemProcess 1320 KProcess 2Process 3224 K288 K64 KOperating SystemProcess 1320 KProcess 3224 K288 K64 KOperating SystemProcess 1320 KProcess 3288 K64 KProcess 4128 K96 KExampleDynamicPartitioningOperating System320 KProcess 3288 K64 KProcess 4128 K96 KOperating SystemProcess 3288 K64 KProcess 4128 K96 KProcess 2224 k96 K6.2.3动态动态/可变式分区分配可变式分区分配-2管理机构管理机构空闲区表形式 空闲分区表为每个尚未分配的分区设置一个表项，包括分区的序号、大小、始址和状态。空闲区链形式 为了实现对空闲分区的分配和链接，在每个分区的起始部分，设置一些用于控制分区分配的信息（如分区的大小和状态位），以及用于链接其它分区的前向指针；在分区尾部，则设置了一个后向指针，为了检索方便也设置了控制分区分配的信息。然后，通过前、后向指针将所有的分区链接成一个双向链表。0k：20k：52k：116k：164k：260k：512k：（c）内存分配图可变式分区数据结构图表可变式分区数据结构图表 序号序号P P 大小大小起址起址状态状态 1 14848k k116k116k空闲空闲 2 2252252k k260k260k空闲空闲 3 3空表目空表目 4 4空表目空表目 5 5空表目空表目 （a）空闲分区表 操作系统操作系统作业作业1（32k）作业作业2（64k）空闲区（空闲区（48k）作业作业4（96k）空空闲闲区区（252k）前前向向指指针针 N+2 00后后向向指指针针 N+2 00N个字节可用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）空空闲闲区区（252k）前前向向指指针针 N+2 00后后向向指指针针 N+2 00N个字节可用（b）已分配分区链结构分区分配分区分配算法算法(PartitioningPlacementAlgorithm)最最佳佳适适应应算算法法（Best Best FitFit）：它从全部空闲区中找出能满足作业要求的、且大小最小的空闲分区，这种方法能使碎片尽量小。为适应这种算法，空闲分区表（空闲区链）中的空闲分区要按大小从小到大进行排序，自表头开始查找到第一个满足要求的自由分区分配。首首次次适适应应算算法法（First First FitFit）：从空闲分区表的第一个表目起查找该表，把最先能够满足要求的空闲区分配给作业，这种方法目的在于减少查找时间。为适应这种算法，空闲分区表（空闲区链）中的空闲分区要按地址由低到高进行排序。循循环环首首次次适适应应算算法法：该算法是首次适应算法的变种。在分配内存空间时，不再每次从表头（链首）开始查找，而是从上次找到的空闲区的下一个空闲区开始查找，直到找到第一个能满足要求的的空闲区为止，并从中划出一块与请求大小相等的内存空间分配给作业。该算法能使内存中的空闲区分布得比较均匀。最最坏坏适适应应法法：从所有未分配的分区中挑选最大的且大于和等于作业大小的分区分给要求的作业；空闲分区按大小由大到小排序。DynamicPartitioningPlacementAlgorithmLastallocatedblock(14K)BeforeAfter8K8K12K12K22K18K6K6K8K8K14K14K6K2K36K20KNext FitFree blockAllocated blockBest FitFirst Fit例：分配一个16KB分区3。UNIX分配分配回收算法（采用回收算法（采用空闲分区表空闲分区表结构和结构和首次首次适应算法）适应算法）UNIX空闲分区表空闲分区表数据结构数据结构 Coremap m_addrm_size.m_addrm_size=0.m_addrm_sizem_addrm_sizem_addrm_sizem_addrm_size空闲分区表中的空闲分区要按地址从低到高连续排序，最后一个空闲分区中 m_size为0表示以上表目空白。空闲分区表起始地址为coremap分配和释放的基本思想是：在分配时，首先找到一个足够大的空闲分区，即这个空闲区的大小比作业要求的要大，系统则将这个空闲分区分成两部分：一部分成为已分配的分区，剩余的部分仍作为空闲区。在回收撤除作业所占领的分区时，要检查回收的分区是否与前后空闲的分区相领接，若是，则加以合并，使之成为一个连续的大空间。UNIX分配分配算法框图算法框图申申请请分分配配一一个个u.size大大小小的的分分区区从头开始查表从头开始查表是是否否检检索索完完毕毕？本本次次无无法法分分配配m.size=u.size m.size-u.sizeaa或或m.size=0不不是是第第一一个个表表目目与与前前一一可可用用区相区相 邻？邻？与与后后一一可可用用分分区区相相邻邻且且不不为为空表空表 目？目？把所释放的可用区把所释放的可用区 与前一分区合并与前一分区合并所所释释放放的的可可用用区区与与一一可可用用区区合并合并所所 释释 放放 可可用用 区区 的的size=0?与与后后一一可可用用 区区 相相邻邻？与与后后一一可可用用区区合合并并将将该该表表目目以以上上的的所所有有表表目目下下移移一一格格 返返 回回mfree是是否存储保护：存储保护：评价：评价：优点：支持多道程序优点：支持多道程序 相对于固定分区，在一定程度上减少了碎片。相对于固定分区，在一定程度上减少了碎片。缺点：仍然存在碎片缺点：仍然存在碎片 不支持虚拟存储不支持虚拟存储 不能充分利用内存，当空闲分区之和能满足某程序而单个不能充分利用内存，当空闲分区之和能满足某程序而单个不能满足时，程序不能运行。不能满足时，程序不能运行。6.2.4动态重定位分区分配动态重定位分区分配思想思想：与动态分区一样，但分区可以移动以便把较小的空闲分区合并成一个较大的空闲分区，因而需要动态重定位的支持。1、拼接拼接/紧凑紧凑 可变式分区也有零头问题。在系统不断地分配和回收中，必定会出现一些不连续的小的空闲区，称为外零头。虽然可能所有零头的总和超过某一个作业的要求，但是由于不连续而无法分配。解决零头的方法是拼接（或称紧凑），即向一个方向（例如向低地址端）移动已分配的作业，使那些零散的小空闲区在另一方向连成一片。分区的拼接技术，一方面是要求能够对作业进行重定位，另一方面系统在拼接时要耗费较多的时间。2、动态重定位动态重定位 实现紧凑所需的允许作业在运行过程中在内存中移动的技术必须获得硬件支持。只有具有动态重定位硬件机构的计算机系统，才有可能采取动态重定位可变分区多道管理技术，系统的硬件包括重定位寄存器和加法器。动态重定位分区分配动态重定位分区分配3动态重定位分区分配算法动态重定位分区分配算法 动态重定位分区管理中何时进行存储器紧缩有二种不同的解决办法：在某个分区被释放后立即进行紧缩，系统总是只有一个连续的分区而无碎片，此法很花费机时。当“请求分配模块”找不到足够大的自由分区分给用户时再进行紧缩，这样紧缩的次数比上种方法少得多，但表格管理复杂。采用此法的动态重定位分区分配算法框图如下：动态重定位分区分配动态重定位分区分配算法框图算法框图 N N Y Y 请求分配请求分配u.size分区分区检索空闲分区链（表）检索空闲分区链（表）无法分配无法分配 返回返回空空 闲闲 分分 区区总总和和u.size找到大于找到大于u.size的可用的可用 区否？区否？进行紧凑形成进行紧凑形成 连续空闲区连续空闲区修改有关的修改有关的数据结构数据结构 按动态分区方式按动态分区方式 进行分配进行分配修改有关的修改有关的 数据结构数据结构返回分区号返回分区号 及首址及首址4 4、存储保护、存储保护5 5、评价、评价 优点：支持多道程序优点：支持多道程序 比动态分区前进一步，比动态分区前进一步，当空闲分区之和能满当空闲分区之和能满足某程序而单个不能满足时可以通过合并空闲分区的办足某程序而单个不能满足时可以通过合并空闲分区的办法让程序装入。法让程序装入。缺点：不能解决虚拟存储缺点：不能解决虚拟存储 移动合并需要增加系统开销移动合并需要增加系统开销 仍然存在碎片仍然存在碎片6.3覆盖与交换技术覆盖与交换技术6.3.1覆盖技术覆盖技术 为了能在小的内存空间中运行大的作业，许多机器（如PDP11，IBMPC）都采用了“覆盖”技术。覆盖是指一个作业的若干程序段（或数据段）间，或者几个作业的某些程序段间共享某主存空间。覆盖技术通常与单用户连续分配、固定分区和可变分区等存储管理技术配合使用。它不但用于用户作业的运行中，而且还常用于操作系统本身的运行中。6.3.1覆盖技术覆盖技术-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主存。主存。6.3.1覆盖技术覆盖技术-2-2 （a）(b)MAIN 20KA030KB040KA160KA230KB130KA320KA440K覆盖段覆盖段040K覆盖段覆盖段160K覆盖段覆盖段2 40KMAIN A0 A1A2A3A4B1B06.3.1覆盖技术覆盖技术-3-3覆盖结构的输入 PDP11的RSX22H提供覆盖描述语言ODL来描述结构，并构成覆盖描述文件，如上图用ODL语言表示如下：ROOT MAIN（A0（A1，A2（A3，A4），B0（B1，B2）；ENDl覆盖数据结构 用户将覆盖描述文件随目标程序一起提交系统，系统根据覆盖描述文件形成一个覆盖数据结构。该数据结构对每个覆盖段有一个描述信息，它包括覆盖段号、覆盖数、当前覆盖号、覆盖区始址、覆盖区长度、起始盘区号等。系统根据覆盖调度程序和覆盖调度结构自动地将各程序段装入运行。6.3.2 交换（对换）技术交换（对换）技术 交换技术最早用在麻省理工学院的兼容分时系统CTSS中，该系统是单用户系统，所有用户都驻留在外存的后备队列中，每次只调入一个作业进入内存运行，此作业的时间的时间片用完时，又将该作业调至外存，再将后备队列中的一个作业调入内存运行一个时间片。这是早期的简单分时系统，它采用早期的交换（调进凋出）来满足多个程序共享主存的需要。1。多道程序环境下的对换。多道程序环境下的对换 在多道程序环境下为了提高内存和CPU的利用率，增加系统吞吐量，系统中增设了对换，把内存中暂不能运行的进程调出到外存上，以腾出足够的内存空间，把已具备运行条件的进程换入内存。UNIX早期已引入对换功能并一直保留至今，UNIX系统设置一个对换进程完成以上功能。为了实现进程对换，系统必须能实现对对换空间的管理，进程换入和进程换出等三项功能。6.3.2 交换（对换）技术交换（对换）技术-22。对换空间的管理。对换空间的管理 外存分为文件区和对换区。文件区用户存放文件，对文件区管理目标是提高文件存储空间的利用率，为此系统采用离散分配方式；对换区用于存放从内存频繁换出的进程，它的管理目标是提高进程换入换出速度，为此系统采用连续分配方式。UNIX对换区采用空闲分区表和首次适应算法的动态分区管理，类同早期内存管理。3。进程的换出与换入。进程的换出与换入当内核发现内存不足时调用对换进程，对换进程检查驻留在内存的进程，选择处于阻塞和睡眠状态的进程换出，如无则选择优先级低的驻留内存时间长的处于就绪状态的进程换出。而当内存又空时对换进程在对换区中选择换出时间长的处于就绪态的进程调入。6.4 6.4 分页存储管理分页存储管理6.4.1 6.4.1 分页存储管理原理分页存储管理原理1分页分页 分分页页存存储储管管理理是是将将一一个个进进程程的的地地址址空空间间划划分分成成若若干干个个大大小小相相等等的的区区域域，称称为为页页，相相应应地地，将将内内存存空空间间划划分分成成与与页页相相同同大大小小的的若若干干个个物物理理块块，称称为为块块或或页页框框。在在为为进进程程分分配配内内存时，将进程中的若干页分别装入多个不相邻接的块中。存时，将进程中的若干页分别装入多个不相邻接的块中。2 2.地址结构地址结构 分分页页系系统统的的地地址址结结构构如如下下图图所所示示，它它由由两两部部分分组组成成：前前一一部部分分为为页页号号P P；后后一一部部分分为为位位移移量量W W，即即页页内内地地址址。图图中中的的地地址址长长度度为为3232位位，其其中中0 01111位位为为页页内内地地址址（每每页页的的大大小小为为4 4K K），12123131位位为为页页号号，所所以以允允许许地地址址空空间间的的大大小小最最多多为为1 1M M个页。个页。31 12 11 031 12 11 0 页号 P 位移量W6.4.1 6.4.1 分页存储管理原理分页存储管理原理-1-13 3.页表页表 在将进程的每一页离散地分配到内存的多个物理在将进程的每一页离散地分配到内存的多个物理块中后，系统应能保证能在内存中找到每个页面块中后，系统应能保证能在内存中找到每个页面所对应的物理块。为此，系统为每个进程建立了所对应的物理块。为此，系统为每个进程建立了一张页面映射表，简称页表（如下图一张页面映射表，简称页表（如下图所示所示）。每）。每个页在页表中占一个表项，记录该页在内存中对个页在页表中占一个表项，记录该页在内存中对应的物理块号。进程在执行时，通过查找页表，应的物理块号。进程在执行时，通过查找页表，就可以找到每页所对应的物理块号。可见，页表就可以找到每页所对应的物理块号。可见，页表的作用是实现从页号到物理块号的地址映射。的作用是实现从页号到物理块号的地址映射。分页存储管理原理分页存储管理原理-2-26.4.2 地址变换机构地址变换机构1.基本的地址变换机构基本的地址变换机构 地址变换机构的基本任务是利用页表把用户程序中的逻地址变换机构的基本任务是利用页表把用户程序中的逻辑地址变换成内存中的物理地址，实际上就要将用户程序中辑地址变换成内存中的物理地址，实际上就要将用户程序中的页号变换成内存中的物理块号。为了实现地址变换功能，的页号变换成内存中的物理块号。为了实现地址变换功能，在系统中设置页表寄存器，用来存放页表的始址和页表的长在系统中设置页表寄存器，用来存放页表的始址和页表的长度。在进程未执行时，每个进程对应的页表的始址和长度存度。在进程未执行时，每个进程对应的页表的始址和长度存放在进程的放在进程的PCB中，当该进程被调度时，就将它们装入页表中，当该进程被调度时，就将它们装入页表寄存器。在进行地址变换时，系统将页号与页表长度进行比寄存器。在进行地址变换时，系统将页号与页表长度进行比较，如果页号大于页表寄存器中的页表长度，则访问越界，较，如果页号大于页表寄存器中的页表长度，则访问越界，产生越界中断。如未出现越界，则根据页表寄存器中的页表产生越界中断。如未出现越界，则根据页表寄存器中的页表始址和页号计算出该页在页表项中的位置，得到该页的物理始址和页号计算出该页在页表项中的位置，得到该页的物理块号，将此物理块号装入物理地址寄存器中。与此同时，将块号，将此物理块号装入物理地址寄存器中。与此同时，将有效地址（逻辑地址）寄存器中页内地址直接装入物理地址有效地址（逻辑地址）寄存器中页内地址直接装入物理地址寄存器的块内地址字段中，这样便完成了从逻辑地址到物理寄存器的块内地址字段中，这样便完成了从逻辑地址到物理地址的变换。地址的变换。6.4.2 地址变换机构地址变换机构-12.具有快表的地址变换机构具有快表的地址变换机构如如果果页页表表存存放放在在内内存存中中，则则每每次次访访问问内内存存时时，都都要要先先访访问问内内存存中中的的页页表表，然然后后根根据据所所形形成成的的物物理理地地址址再再访访问问内内存存。这这样样CPU存存一一个个数数据据必必须须访访问问两两次次内内存存，从从而使计算机的处理速度降低了而使计算机的处理速度降低了1/2。为为了了提提高高地地址址变变换换的的速速度度，在在地地址址变变换换机机构构中中增增设设了了一一个个具具有有并并行行查查询询功功能能的的特特殊殊的的高高速速缓缓冲冲存存储储器器，称称为为“联联想想存存储储器器”或或“快快表表”，用用以以存存放放当当前前访访问问的的那那些些页页表表项项。此此时时地地址址变变换换过过程程为为：在在CPU给给出出有有效效地地址址后后，地地址址变变换换机机构构自自动动地地将将页页号号送送入入高高速速缓缓存存，确确定定所所需需要要的的页页是是否否在在快快表表中中。若若是是，则则直直接接读读出出该该页页所所对对应应的的物物理理块块号号，送送入入物物理理地地址址寄寄存存器器；若若在在快快表表中中未未找找到到对对应应的的页页表表项项，则则需需再再访访问问内内存存中中的的页页表表，找找到到后后，把把从从页页表表中中读读出出的的页页表表项项存存入入快快表表中中的的一一个个寄存器单元中，以取代一个旧的页表项。寄存器单元中，以取代一个旧的页表项。2.具有快表的地址变换机构具有快表的地址变换机构-1由于成本的原因，快表不可能做得很大，通常只能存放由于成本的原因，快表不可能做得很大，通常只能存放16512个页表项。例如，在个页表项。例如，在Intel80486中有中有32个。这对个。这对中、小型作业来说，已可能把全部页表项放入快表中；中、小型作业来说，已可能把全部页表项放入快表中；但对于大型作业来说，则只能将一部分页表放入快表中。但对于大型作业来说，则只能将一部分页表放入快表中。由于对程序和数据的访问往往带有局限性，所以快表的由于对程序和数据的访问往往带有局限性，所以快表的命中率可以达到命中率可以达到80%90%。例如，假设检索联想存储。例如，假设检索联想存储器的时间为器的时间为20ns，访问内存的时间为访问内存的时间为100ns，访问联想访问联想存储器的的命中率为存储器的的命中率为85%，则，则CPU存取一个数据的平均存取一个数据的平均时间为时间为T=0.85*120+0.15*220=135ns，所以访问时间只所以访问时间只增加增加35%。如果不引入联想存储器，其访问将延长一倍。如果不引入联想存储器，其访问将延长一倍（达（达200ns）。）。2.具有快表的地址变换机构具有快表的地址变换机构-26.4.3 6.4.3 两级页表机制两级页表机制 80386 80386的逻辑地址有的逻辑地址有232B，如如页面大小为页面大小为4 4KBKB（2 21212B B），），则页表项则页表项(页数页数)达达1 1M M个，每个页表项（页表中的一个，每个页表项（页表中的一行）占用行）占用4 4B B，故每个进程的页表占用故每个进程的页表占用4 4MBMB内存空间，内存空间，还要求是连续的，显然这是不现实的。还要求是连续的，显然这是不现实的。在在8038680386中，为了减少页表所占用的连续的内存空间，中，为了减少页表所占用的连续的内存空间，采用了两级页表机制：基本方法是将页表进行分页，采用了两级页表机制：基本方法是将页表进行分页，每个页面的大小与内存物理块的大小相同，并为它每个页面的大小与内存物理块的大小相同，并为它们进行编号，可以离散地将各个页面分别存放在不们进行编号，可以离散地将各个页面分别存放在不同的物理块中，为此再建立一张页表，称为外层页同的物理块中，为此再建立一张页表，称为外层页表（页表目录），即第一级页表，其中的每个表目表（页表目录），即第一级页表，其中的每个表目是存放某个页表的物理地址。第二级才是页表，其是存放某个页表的物理地址。第二级才是页表，其中的每个表目所存放的才是页的物理块号。中的每个表目所存放的才是页的物理块号。6.4.3 6.4.3 两级