第五章 存储器管理

1、1 2 本章内容本章内容 5.1 存储管理概述存储管理概述 5.2 程序的装入和链接程序的装入和链接 5.3 连续分配方式连续分配方式 5.4 基本分页存储管理方式基本分页存储管理方式 5.5 基本分段存储管理方式基本分段存储管理方式 5.6 基本段页式存储管理方式基本段页式存储管理方式 3 5.1 存储管理概述存储管理概述 5.1.1 存储器层次 4 5.1.2 存储存储管理管理任务任务 v操作系统须占用内存一部分存储空间存放自身的操作系统须占用内存一部分存储空间存放自身的 程序、数据、管理信息以及与硬件接口信息等，程序、数据、管理信息以及与硬件接口信息等， 一般称这部分内存空间为系统区。系

2、统区外的其一般称这部分内存空间为系统区。系统区外的其 余内存空间存放用户的程序和数据，称为用户区。余内存空间存放用户的程序和数据，称为用户区。 存储管理主要是对用户区进行管理，它包括以下存储管理主要是对用户区进行管理，它包括以下4 4 项任务项任务。 （1 1）内存分配和回收）内存分配和回收 （2 2）地址变换）地址变换 （3 3）内存保护）内存保护 （4 4）内存扩充）内存扩充 5 5.1.3 存储存储管理管理目标目标 (1)内存结构细节对于用户和用户程序要透明。在高内存结构细节对于用户和用户程序要透明。在高 级程序设计语言和汇编语言中将源程序和目标程级程序设计语言和汇编语言中将源程序和目标

3、程 序进行分离，源程序独立于内存物理地址。序进行分离，源程序独立于内存物理地址。 (2)提高内存的利用率，解决大程序和小内存之间的提高内存的利用率，解决大程序和小内存之间的 矛盾。通过对存储空间采取不同的管理方式，解矛盾。通过对存储空间采取不同的管理方式，解 决内存管理中的碎片问题，提高内存利用率。决内存管理中的碎片问题，提高内存利用率。 (3)为用户程序完成程序装入。编译程序产生可执行为用户程序完成程序装入。编译程序产生可执行 程序时，在可执行目标程序中生成地址重定位所程序时，在可执行目标程序中生成地址重定位所 需信息，例如程序长度、数据区长度等。需信息，例如程序长度、数据区长度等。 6 5

4、.1.3 存储存储管理管理目标目标 (4)解决内存速度与解决内存速度与CPU速度不匹配问题。为了解决速度不匹配问题。为了解决 内存速度与内存速度与CPU速度不匹配问题，引入了高速缓速度不匹配问题，引入了高速缓 存。存。 (5)实现内存保护和共享。内存保护是确保并发执行实现内存保护和共享。内存保护是确保并发执行 的各个进程在所分配的存储区内操作，互不干扰，的各个进程在所分配的存储区内操作，互不干扰， 通常由软硬件结合方式实现。通常由软硬件结合方式实现。 7 5.2 程序的装入和链接程序的装入和链接 链接 程序 装入模块 第二步第三步 装入 程序 内存 第一步 库 编译程序 产生的目 标模块 8

5、5.2.1 几个几个基本概念基本概念 1.相对地址与相对地址空间相对地址与相对地址空间 v在用汇编语言或高级语言编写的程序中，数据和在用汇编语言或高级语言编写的程序中，数据和 子程序通常用符号名进行访问。程序中各种符号子程序通常用符号名进行访问。程序中各种符号 名集合所限定的空间称作程序名字空间。名集合所限定的空间称作程序名字空间。 v经汇编或编译程序处理后，源程序中的各种符号经汇编或编译程序处理后，源程序中的各种符号 名转换成由机器指令和数据组成的目标程序，用名转换成由机器指令和数据组成的目标程序，用 相对地址替换符号地址。相对地址替换符号地址。 v相对地址：相对于程序首指令相对地址：相对于

6、程序首指令(通常为通常为0)的地址。的地址。 v目标程序中的逻辑地址集合称作该程序的相对地目标程序中的逻辑地址集合称作该程序的相对地 址空间，又称作逻辑地址空间。址空间，又称作逻辑地址空间。 9 5.2.1 几个几个基本概念基本概念 2.绝对地址与绝对地址空间绝对地址与绝对地址空间 v程序在内存空间中的实际存储单元地址称做物理程序在内存空间中的实际存储单元地址称做物理 地址或绝对地址。内存空间是指物理内存中全部地址或绝对地址。内存空间是指物理内存中全部 存储单元的集合所限定的空间。物理地址的总体存储单元的集合所限定的空间。物理地址的总体 构成运行用户程序的物理地址空间，又称绝对地构成运行用户程

7、序的物理地址空间，又称绝对地 址空间。址空间。 vCPU直接使用物理地址存取空间中的指令和数据，直接使用物理地址存取空间中的指令和数据， 完成用户程序或系统程序。相对地址空间的大小完成用户程序或系统程序。相对地址空间的大小 由源程序决定，绝对地址空间的大小由系统硬件由源程序决定，绝对地址空间的大小由系统硬件 配置决定。一个程序只有从相对地址空间装入绝配置决定。一个程序只有从相对地址空间装入绝 对地址空间后才能运行。对地址空间后才能运行。 10 5.2.1 几个几个基本概念基本概念 3.地址重定位地址重定位 v当一个程序的相对地址装入到与其逻辑地址空间当一个程序的相对地址装入到与其逻辑地址空间

8、不一致的绝对地址空间中时，为了保证程序的正不一致的绝对地址空间中时，为了保证程序的正 确运行，必须把指令和数据的逻辑地址转换为物确运行，必须把指令和数据的逻辑地址转换为物 理地址，这项工作称为地址重定位。理地址，这项工作称为地址重定位。 v地址重定位通常有静态地址重定位和动态地址重地址重定位通常有静态地址重定位和动态地址重 定位两种方式。定位两种方式。 静态地址重定位静态地址重定位 动态地址重定位动态地址重定位 11 5.2.2 程序程序的装入的装入 v程序的程序的装入装入指给程序的指令和数据分配物指给程序的指令和数据分配物 理内存空间，也常被称为理内存空间，也常被称为加载加载。一个程序。一个

9、程序 要运行必须得装入内存，这需要将指令和要运行必须得装入内存，这需要将指令和 数据的逻辑地址转换为物理地址，即需要数据的逻辑地址转换为物理地址，即需要 进行地址变换。进行地址变换。 v根据地址变换发生时机，装入方式分为绝根据地址变换发生时机，装入方式分为绝 对装入方式、可重定位装入方式和动态运对装入方式、可重定位装入方式和动态运 行时装入方式三种。行时装入方式三种。 12 5.2.2 程序程序的装入的装入 1 1、绝对装入方式、绝对装入方式 v 在可执行文件中记录内存地址，装入时直接定位在上述在可执行文件中记录内存地址，装入时直接定位在上述( ( 即文件中记录的地址即文件中记录的地址) )内

10、存地址。内存地址。 v 优点：装入过程简单。优点：装入过程简单。 v 缺点：过于依赖于缺点：过于依赖于 硬件结构，不适于多道硬件结构，不适于多道 程序系统。程序系统。 13 5.2.2 程序程序的装入的装入 2、可重定位装入方式、可重定位装入方式 v当一个地址装入与其地址空间不一致的存储当一个地址装入与其地址空间不一致的存储 空间中，就得要进行地址变换。也就是说将空间中，就得要进行地址变换。也就是说将 虚地址映射为内存地址，把这种作法叫做虚地址映射为内存地址，把这种作法叫做地地 址重定位或地址映射。址重定位或地址映射。 v在在装入装入一个作业时，把作业中的指令相对地一个作业时，把作业中的指令相

11、对地 址址全部转换全部转换为绝对地址（地址转换工作是在为绝对地址（地址转换工作是在 作业执行前集中一次完成的）在作业执行过作业执行前集中一次完成的）在作业执行过 程中就无须再进行地址转换工作。又称程中就无须再进行地址转换工作。又称静态静态 重定位装入方式。重定位装入方式。 14 5.2.2 程序程序的装入的装入 2、可重定位装入方式、可重定位装入方式 v优点：不需硬件支持，优点：不需硬件支持， 可以装入有限多道程序可以装入有限多道程序 （如（如MS DOS中的中的TSR ）。）。 v缺点：一个程序通常需缺点：一个程序通常需 要占用连续的要占用连续的 内存空内存空 间，程序装间，程序装 入内存后

12、入内存后 不能移动。不能移动。 不易实现不易实现 共享。共享。 15 5.2.2 程序程序的装入的装入 3、动态运行时装入方式、动态运行时装入方式 v可重定位装入方式虽然可用于可重定位装入方式虽然可用于多道程序系统多道程序系统，但程，但程 序执行期间如果在内存中发生移动，则程序的物理序执行期间如果在内存中发生移动，则程序的物理 地址都发生改变，须修改全部物理地址，否则程序地址都发生改变，须修改全部物理地址，否则程序 将无法正确执行。所以，采用可重定位方式把程序将无法正确执行。所以，采用可重定位方式把程序 装入内存后，程序在内存中一般不再移动。装入内存后，程序在内存中一般不再移动。 v但实际应用

13、中，程序在内存中的位置可能经常需要但实际应用中，程序在内存中的位置可能经常需要 改变。改变。 v动态运行时装入方式是在动态运行时装入方式是在CPU执行访问指令执行访问指令时，时， 才将要访问的程序或数据的逻辑地址转换为物理地才将要访问的程序或数据的逻辑地址转换为物理地 址。址。 16 5.2.2 程序程序的装入的装入 3、动态运行时装入方式、动态运行时装入方式 v动态运行时装入方式的优点是操作系统可将一个动态运行时装入方式的优点是操作系统可将一个 程序离散地存放在内存空间。程序离散地存放在内存空间。 v在在程序的整个执行期间，允许程序在内存中改变程序的整个执行期间，允许程序在内存中改变 位置位

14、置。 v这种加载方式有利于提高内存利用率，也为实现这种加载方式有利于提高内存利用率，也为实现 虚拟存储器提供了基础。虚拟存储器提供了基础。 v动态运行时装入方式的缺点是需要硬件支持，操动态运行时装入方式的缺点是需要硬件支持，操 作系统实现较为复杂。作系统实现较为复杂。 17 动态地址重定位示意图动态地址重定位示意图 1500 12345 Load A 500 内存空间内存空间 500 1000 + VR BR 500 100 12345 Load A 500 0 虚拟空间（作业地址空间）虚拟空间（作业地址空间） . 3动态运行时装入方式动态运行时装入方式 18 5.2.3 程序程序的链接的链接

15、 v根据链接时间的不同，可把链接分成如下三根据链接时间的不同，可把链接分成如下三 种：种： (1) 静态链接静态链接 (2) 装入时动态链接装入时动态链接 (3) 运行时动态链接运行时动态链接 19 1静态链接方式静态链接方式(Static Linking) p在程序运行之前，先将各目标模块及它们在程序运行之前，先将各目标模块及它们 所需的库函数，链接成一个完整的装配模所需的库函数，链接成一个完整的装配模 块，以后块，以后不再拆开不再拆开。我们把这种。我们把这种事先事先进行进行 链接的方式称为静态链接方式。链接的方式称为静态链接方式。 p链接时需要进行下面的修改：链接时需要进行下面的修改： 2

16、0 1静态链接方式静态链接方式(Static Linking) (1) 对相对地址进行修改。在由编译程序所产生的所对相对地址进行修改。在由编译程序所产生的所 有目标模块中，使用的都是相对地址，其起始地有目标模块中，使用的都是相对地址，其起始地 址都为址都为0，每个模块中的地址都是相对于起始地址，每个模块中的地址都是相对于起始地址 计算的。计算的。 (2) 变换外部调用符号。将每个模块中所用的外部调变换外部调用符号。将每个模块中所用的外部调 用符号也都变换为相对地址，如下图所示。这种用符号也都变换为相对地址，如下图所示。这种 先进行链接所形成的一个完整的装入模块，又称先进行链接所形成的一个完整的

17、装入模块，又称 为为可执行文件可执行文件。通常都不再拆开它，要运行时可。通常都不再拆开它，要运行时可 直接将它装入内存。这种事先进行链接，以后不直接将它装入内存。这种事先进行链接，以后不 再拆开的链接方式，称为再拆开的链接方式，称为静态链接静态链接方式。方式。 21 模块模块A CALL B； Return； 0 L-1 5.2.3 程序程序的链接的链接 模块模块B CALL C； Return； 0 M-1 模块模块C Return； 0 N-1 (a) 目标模块目标模块 模块模块A JMP L； Return； 0 L-1 模块模块B JMP L+M； Return； L L+M-1 模块

18、模块C Return； L+M L+M+N-1 (b) 装入模块装入模块 22 2装入时动态链接装入时动态链接(Load-time Dynamic Linking) v这是指将用户源程序编译后所得到的一组目标模这是指将用户源程序编译后所得到的一组目标模 块，在装入内存时，采用块，在装入内存时，采用边装入边链接边装入边链接的链接方的链接方 式。式。 v用户源程序经编译后所得的目标模块，是在装入用户源程序经编译后所得的目标模块，是在装入 内存时边装入边链接的，即在装入一个目标模块内存时边装入边链接的，即在装入一个目标模块 时，若发生一个外部模块调用事件，将引起装入时，若发生一个外部模块调用事件，将

19、引起装入 程序去找出相应的外部目标模块，并将它装入内程序去找出相应的外部目标模块，并将它装入内 存，还要修改目标模块中的相对地址。存，还要修改目标模块中的相对地址。 v装入时动态链接方式有以下优点：装入时动态链接方式有以下优点： (1) 便于修改和更新。便于修改和更新。 (2) 便于实现对目标模块的共享。便于实现对目标模块的共享。 23 3运行时动态链接运行时动态链接(Run-time Dynamic Linking) v在许多情况下，应用程序在运行时，每次要运行在许多情况下，应用程序在运行时，每次要运行 的模块可能是不相同的。的模块可能是不相同的。 v但由于事先无法知道本次要运行哪些模块，故

20、只但由于事先无法知道本次要运行哪些模块，故只 能是将所有可能要运行到的模块都全部装入内存能是将所有可能要运行到的模块都全部装入内存 ，并在装入时全部链接在一起。，并在装入时全部链接在一起。 v显然这是低效的。显然这是低效的。 v运行时动态链接运行时动态链接方式，是将对某些目标模块的链方式，是将对某些目标模块的链 接推迟到程序执行时需要该接推迟到程序执行时需要该(目标目标)模块时，才对模块时，才对 它进行的链接，亦即，在执行过程中，当发现一它进行的链接，亦即，在执行过程中，当发现一 个被调用模块尚未装入内存时，立即由个被调用模块尚未装入内存时，立即由OS去找到去找到 该模块并将之装入内存，把它链

21、接到调用者模块该模块并将之装入内存，把它链接到调用者模块 上。上。 24 5.3 连续分配方式连续分配方式 连续分配方式是指为用户进程分配连连续分配方式是指为用户进程分配连 续内存空间的内存管理方式。早期操作系续内存空间的内存管理方式。早期操作系 统都是采用连续分配方式管理内存。连续统都是采用连续分配方式管理内存。连续 分配方式通常分为：单一连续分配、固定分配方式通常分为：单一连续分配、固定 分区分配、可变分区分配、动态可重定位分区分配、可变分区分配、动态可重定位 分区分配等分区分配等 25 5.3.1 单一连续分配单一连续分配 v单一连续分配方式是最简单的一种存储管理方式，单一连续分配方式是

22、最简单的一种存储管理方式， 只能用于单用户、单任务的操作系统中。在此方只能用于单用户、单任务的操作系统中。在此方 式中，把内存分为系统区和用户区两部分。式中，把内存分为系统区和用户区两部分。 v系统区仅提供给操作系统使用；用户区是指除系系统区仅提供给操作系统使用；用户区是指除系 统区之外的全部内存空间，提供给用户作业使用，统区之外的全部内存空间，提供给用户作业使用， 一次只允许一个作业进入内存。作业往往只占用一次只允许一个作业进入内存。作业往往只占用 户区的一部分，其余部分空闲，内存利用率较低。户区的一部分，其余部分空闲，内存利用率较低。 v单一连续分配存储管理方式只适用于程序的绝对单一连续分

23、配存储管理方式只适用于程序的绝对 装入。装入。 26 5.3.2 固定分区分配固定分区分配 v 基本思想：基本思想： 把内存划分成若干个把内存划分成若干个 大小固定，个数固定大小固定，个数固定 的存储区域，每个存的存储区域，每个存 储区域称为一个分区，储区域称为一个分区， 每个分区中装入一道每个分区中装入一道 作业，每个作业只装作业，每个作业只装 入一个分区中。入一个分区中。 20K 28K 60K 124K 256K OS 进程进程A（6K） 进程进程B（25K） 进程进程C（36K） 内存状态内存状态 27 5.3.2 固定分区分配固定分区分配 1. 划分分区的方法划分分区的方法 分区大小

24、相等，即所有内存分区大小相等。其缺分区大小相等，即所有内存分区大小相等。其缺 点是当分区太大时，会造成内存空间浪费；当点是当分区太大时，会造成内存空间浪费；当 分区太小时，会造成大作业无法运行。它主要分区太小时，会造成大作业无法运行。它主要 适用于一台计算机控制多个相同对象的场合。适用于一台计算机控制多个相同对象的场合。 分区大小不等，即所有内存分区大小不等。可以分区大小不等，即所有内存分区大小不等。可以 把内存划分成多个较小分区、适量中等分区及把内存划分成多个较小分区、适量中等分区及 少量大分区，以适应不同程序的需求。少量大分区，以适应不同程序的需求。 28 5.3.2 固定分区分配固定分区

25、分配 2. 内存的分配与回收内存的分配与回收 v为了便于内存分配，通常将分区按为了便于内存分配，通常将分区按大小进行排队大小进行排队 ，并为之建立一张分区使用表，其中各表项包括，并为之建立一张分区使用表，其中各表项包括 每个分区的起始地址、大小及状态每个分区的起始地址、大小及状态(是否已分配是否已分配) ，见下图，见下图a所示。所示。 v当有一用户程序要装入时，由内存分配程序检索当有一用户程序要装入时，由内存分配程序检索 该表，从中找出一个能满足要求的、尚未分配的该表，从中找出一个能满足要求的、尚未分配的 分区，将之分配给该程序，然后将该表项中的状分区，将之分配给该程序，然后将该表项中的状 态

26、置为态置为“已分配已分配”； v若未找到大小足够的分区，则拒绝为该用户程序若未找到大小足够的分区，则拒绝为该用户程序 分配内存。存储空间分配情况如下图分配内存。存储空间分配情况如下图b所示。所示。 29 20K 28K 60K 124K 256K 5.3.2 固定分区分配固定分区分配 OS 进程进程A（6K） 进程进程B（25K） 进程进程C（36K） （a）分区说明表）分区说明表 （b）内存状态）内存状态 区号区号分区长度分区长度起始地起始地 址址 状态状态 1 18K8K20K20K已分配已分配 2 232K32K28K28K已分配已分配 3 364K64K60K60K已分配已分配 4 4

27、132K132K124K124K未分配未分配 图图 固定分区使用表固定分区使用表 30 5.3.2 固定分区分配固定分区分配 v当用户程序要装入执行时当用户程序要装入执行时,通过请求表通过请求表 提出内存分配要求和所要求的内存空提出内存分配要求和所要求的内存空 间大小。从分区说明表中查询，从中间大小。从分区说明表中查询，从中 找出一个大小满足要求的空闲分区，找出一个大小满足要求的空闲分区， 并将其分配给申请者。并将其分配给申请者。 v 固定分区的回收，只需将对应的分区固定分区的回收，只需将对应的分区 状态置为未使用即可。状态置为未使用即可。 31 要求要求Xk大小分区大小分区 取分区说明表第一

28、项取分区说明表第一项 状态位置正在使用状态位置正在使用 取下一表项取下一表项 无法分配无法分配 该分区空闲？该分区空闲？ 分区长度分区长度Xk? 表结束？表结束？ 返回分区号返回分区号 否否 否否 否否 是是 是是 是是 图图5.10 5.10 固定分区分配算法固定分区分配算法 32 5.3.2 固定分区分配固定分区分配 3. 地址变换地址变换 v 固定分区存储的地址变换即可采用静态重固定分区存储的地址变换即可采用静态重 定位，也可采用动态重定位。定位，也可采用动态重定位。 33 5.3.2 固定分区分配固定分区分配 v优点：优点： 实现简单、开销小实现简单、开销小 v 缺点：缺点： 必须预先

29、能够估计作业要占用的空间，必须预先能够估计作业要占用的空间， 分区总数固定，限制了并发作业的的数分区总数固定，限制了并发作业的的数 目；目； 内碎片（占用分区之内未被利用的空间内碎片（占用分区之内未被利用的空间 ）造成浪费）造成浪费 34 5.3.3 可变分区分配可变分区分配 1.1. 可变分区的原理可变分区的原理 v固定分区主存利用率不高，使用起来不灵活，固定分区主存利用率不高，使用起来不灵活， 所以出现了可变分区的管理技术。所以出现了可变分区的管理技术。 v动态分区原则：存储空间的划分是在作业装入动态分区原则：存储空间的划分是在作业装入 时进行的。从可用的自由存储空间内，划出一时进行的。从

30、可用的自由存储空间内，划出一 个大小正好等于作业大小的存储区，并分配给个大小正好等于作业大小的存储区，并分配给 这一作业。这一作业。 v动态分区，在系统初启时，除了操作系统中常动态分区，在系统初启时，除了操作系统中常 驻内存部分之外，只有一个空闲分区。驻内存部分之外，只有一个空闲分区。 35 5.3.3 可变分区分配可变分区分配 进程进程 A A（8K8K）进程进程 D D（124K124K）进程进程 B B（16K16K）进程进程 C C（64K64K） OSOS 进程进程A(8K)A(8K) 进程进程B(16K)B(16K) 进程进程C(64K)C(64K) 进程进程D(124K)D(12

31、4K) OSOS 进程进程A(8K)A(8K) 进程进程B(16K)B(16K) 进程进程C(64K)C(64K) OSOS 进程进程A(8K)A(8K) 进程进程B(16K)B(16K) OSOS 进程进程A(8K)A(8K) 36 内存分配变化过程内存分配变化过程 OS A（8K） 8K空闲区空闲区 B（16K） E（50K） D（124K） 14K空闲区空闲区 F（16K） OS A（8K） 8K空闲区空闲区 空闲区空闲区16K E（50K） F（16K） 空闲合并空闲合并 124+14 =138K 进程进程E（50K） 进程进程F（16K） 进入内存进入内存 进程进程B（16K） 进程

32、进程D（124K） 完成完成 OS A（8K） 24K空闲区空闲区 B（16K） C完成（完成（64K） 空闲区空闲区 D（124K） 37 5.3.3 可变分区分配可变分区分配 2. 可变分区分配的数据结构可变分区分配的数据结构 为了便于内存的分配与回收，需设置用于记录为了便于内存的分配与回收，需设置用于记录 分区使用情况的数据结构。分区使用情况的数据结构。 空闲分区表。系统设置一张空闲分区表，记录内空闲分区表。系统设置一张空闲分区表，记录内 存中每个空闲分区的序号、大小和起始地址，存中每个空闲分区的序号、大小和起始地址， 每个空闲分区在空闲分区表中占一个表目。每个空闲分区在空闲分区表中占一

33、个表目。 38 5.3.3 可变分区分配可变分区分配 2. 可变分区分配的数据结构可变分区分配的数据结构 空闲分区链。为了实现对空闲分区的分配和链接，空闲分区链。为了实现对空闲分区的分配和链接， 在每个空闲分区的起始单元中存储两个值，一在每个空闲分区的起始单元中存储两个值，一 个是空闲分区的大小，另一个是指向下一空闲个是空闲分区的大小，另一个是指向下一空闲 分区的指针。分区的指针。 39 5.3.3 可变分区分配可变分区分配 2. 2. 可变分区分配的数据可变分区分配的数据 结构结构 已分配分区表。已分配分区表。系统设置系统设置 一张已分配分区表，记一张已分配分区表，记 录内存中每个已分配分录

34、内存中每个已分配分 区的大小、起始地址和区的大小、起始地址和 状态（记录存放的作业状态（记录存放的作业 名），每个已分配分区名），每个已分配分区 在已分配分区表中占一在已分配分区表中占一 个表目。个表目。 起始地址起始地址 长度长度状态状态 0K0K15K15KJ1J1 38K38K10K10KJ2J2 68K68K12K12KJ3J3 110K110K10K10KJ4J4 已分配分区表已分配分区表 40 5.3.3 可变分区分配可变分区分配 3.常用的空闲分区分配算法有以下四种：常用的空闲分区分配算法有以下四种： 首次适应（首次适应（first fit）算法）算法 循环首次适应（循环首次适应

35、（next fit）算法）算法 最佳适应（最佳适应（best fit）算法）算法 最差适应（最差适应（worst fit）算法）算法 41 3动态分区分配算法动态分区分配算法 首次适应算法首次适应算法(FF,FirstFit) v要求可用表或自由链按起始要求可用表或自由链按起始地址递增地址递增的次的次 序排列。序排列。 v从表头查询，一旦找到大小满足的分区就从表头查询，一旦找到大小满足的分区就 结束探索。结束探索。 v例题：如图所示是某一个时刻例题：如图所示是某一个时刻J1、J2、J3、J4在在 内存中的分配情况、空闲区表和已分区表，它们内存中的分配情况、空闲区表和已分区表，它们 的长度分别是

36、的长度分别是15KB、10KB、12KB、10KB。J5 和和J6两个新作业的长度分别为两个新作业的长度分别为5KB和和13KB。按照。按照 最先适应算法进行内存分配，描述分配后内存、最先适应算法进行内存分配，描述分配后内存、 空闲区表以及已分区表的情况。空闲区表以及已分区表的情况。 42 3动态分区分配算法动态分区分配算法 最先适应算法分配前的状态最先适应算法分配前的状态 起始地址起始地址 长度长度状态状态 0K0K15K15KJ1J1 38K38K10K10KJ2J2 68K68K12K12KJ3J3 110K110K10K10KJ4J4 已分区表已分区表 0 J1 J4 J3 J2 15

37、 38 48 68 80 110 120 起始地址起始地址 长度长度状态状态 15K15K23K23K未分配未分配 48K48K20K20K未分配未分配 80K80K30K30K未分配未分配 空闲区表空闲区表 J5J5和和J6J6两个新作业的长度分别为两个新作业的长度分别为5KB5KB和和13KB13KB。 43 3动态分区分配算法动态分区分配算法 最先适应算法分配后的状态最先适应算法分配后的状态 起始地址起始地址长度长度状态状态 0K0K15K15KJ1J1 38K38K10K10KJ2J2 68K68K12K12KJ3J3 110K110K10K10KJ4J4 15K15K5K5KJ5J5

38、 20K20K13K13KJ6J6 已分区表 起始地址起始地址长度长度状态状态 33K33K5K5K未分配未分配 48K48K20K20K未分配未分配 80K80K30K30K未分配未分配 空闲区表 38 48 110 J6 J1 J4 J3 J2 0 15 68 80 120 J5 33 J5J5和和J6J6两个新作业的长度分别为两个新作业的长度分别为5KB5KB和和13KB13KB。 44 重点回顾重点回顾 v死锁的避免：银行家算法死锁的避免：银行家算法 v死锁的检测与解除死锁的检测与解除 45 重点回顾重点回顾 v相对地址与相对地址空间相对地址与相对地址空间 v绝对地址与绝对地址空间绝对

39、地址与绝对地址空间 v地址重定位地址重定位 46 重点回顾重点回顾 v程序程序的装入的装入 绝对装入方式绝对装入方式 可重定位装入方式可重定位装入方式 动态运行时装入方式动态运行时装入方式 v程序链接程序链接 (1) (1) 静态链接静态链接 (2) (2) 装入时动态链接装入时动态链接 (3) (3) 运行时动态链接运行时动态链接 47 重点回顾重点回顾 v连续分配方式：是指为用户进程分配连续连续分配方式：是指为用户进程分配连续 内存空间的内存管理方式。内存空间的内存管理方式。 单一连续分配单一连续分配 固定分区分配：分区大小和个数固定固定分区分配：分区大小和个数固定 可变分区分配：分区大小

40、和个数随内存的动态可变分区分配：分区大小和个数随内存的动态 分配和回收变化分配和回收变化 48 重点回顾重点回顾 可变分区分配算法可变分区分配算法 首次适应（首次适应（first fit）算法）算法 49 从该空闲区中截取所需从该空闲区中截取所需 大小，修改调整可用表大小，修改调整可用表 从空闲区表第一从空闲区表第一 表目顺序查找表目顺序查找 从可用表中移去该从可用表中移去该 表目，调整可用表表目，调整可用表 取下一表项取下一表项 无法分配无法分配 该该 空闲区空闲区 长度长度SIZE？ 该该 空闲区空闲区 长度长度=SIZE？ 表目查完？表目查完？ 返回分配起始地址返回分配起始地址 否否 否

41、否 是是 是是 是是 否否 图图 最先适应算法最先适应算法 请求请求SIZESIZE大小的分区大小的分区 50 3动态分区分配算法动态分区分配算法 动态分区存储管理可采用多动态分区存储管理可采用多 种数据结构对内存进行管理种数据结构对内存进行管理 v每个空闲区用每个空闲区用map数据结数据结 构构 vstrut map vunsigned m_size; vchar * m_addr; vstruct map cornmapN; m_addrm_addr m_sizem_size m_addrm_addr m_sizem_size 空闲区空闲区 已分配已分配 空闲区空闲区 已分配已分配 空闲区

42、空闲区 已分配已分配 51 3动态分区分配算法动态分区分配算法 最先适应法最先适应法 vChar *malloc(struct map *mp,int size) /空闲表指针，空闲表指针， 作业大小作业大小 vint regint; vstruct map *bp; v/从从mp开始，只要开始，只要size不等于不等于0 ，逐个地址检查，逐个地址检查 m_addrm_addr m_sizem_size m_addrm_addr m_sizem_size 空闲区空闲区 已分配已分配 空闲区空闲区 已分配已分配 空闲区空闲区 已分配已分配 mp 52 for(bp=mp;bp-m_size;bp

43、+) if(bp-m_size=size) regint=bp-m_addr; bp-m_addr+=size; if(bp-m_size-=size)=0) /赋值并判断赋值并判断 do bp+; (bp-1)-m_addr=bp-m_addr; while(bp-1)-m_size=bp-m_size); return(regint); return(0); m_addrm_addr m_sizem_size m_addrm_addr m_sizem_size 空闲区空闲区 已分配已分配 空闲区空闲区 已分配已分配 空闲区空闲区 已分配已分配 mp 53 3动态分区分配算法动态分区分配算法

44、 最先适应算法最先适应算法 缺点：缺点： 由于查找总是从表首开始，前面的空闲区由于查找总是从表首开始，前面的空闲区 被分割的很小时，能满足分配要求的可能被分割的很小时，能满足分配要求的可能 性就越小，查找次数越多性就越小，查找次数越多 碎片问题碎片问题 54 3动态分区分配算法动态分区分配算法 最佳适应算法最佳适应算法(BF,Best Fit) v要求可用表（空闲表）或自由链按分区要求可用表（空闲表）或自由链按分区 大小递增大小递增的次序排列。的次序排列。 v从表头查询，一旦找到大小满足的分区从表头查询，一旦找到大小满足的分区 就结束探索就结束探索。 55 3动态分区分配算法动态分区分配算法

45、分配前的状态分配前的状态 起始地址起始地址长度长度状态状态 0K0K15K15KJ1J1 38K38K10K10KJ2J2 68K68K12K12KJ3J3 110K110K10K10KJ4J4 已分区表 起始地址起始地址 长度长度 状态状态 15K15K23K23K未分配未分配 48K48K20K20K未分配未分配 80K80K30K30K未分配未分配 空闲区表 J5J5和和J6J6两个新作业的长度分别为两个新作业的长度分别为5KB5KB和和13KB13KB。 起始地址起始地址 长度长度 状态状态 48K48K20K20K未分配未分配 15K15K23K23K未分配未分配 80K80K30K

46、30K未分配未分配 空闲区表 0 J1 J4 J3 J2 15 38 48 68 80 110 120 56 最佳适应算法分配后的状态最佳适应算法分配后的状态 起始地址起始地址长度长度状态状态 0K0K15K15KJ1J1 38K38K10K10KJ2J2 68K68K12K12KJ3J3 110K110K10K10KJ4J4 48K48K5K5KJ5J5 53K53K13K13KJ6J6 已分区表 起始地址起始地址长度长度状态状态 66K66K2K2K未分配未分配 15K15K23K23K未分配未分配 80K80K30K30K未分配未分配 空闲区表 J6 J3 J1 J4 J2 0 15 3

47、8 48 68 80 110 120 J5 66 J5J5和和J6J6两个新作业的长度分别为两个新作业的长度分别为5KB5KB和和13KB13KB。 3动态分区分配算法动态分区分配算法 57 3动态分区分配算法动态分区分配算法 最佳适应法最佳适应法 v优点：优点： 分配后所剩余的空白块会最小分配后所剩余的空白块会最小 平均而言，只要查找一半的表格便能找到平均而言，只要查找一半的表格便能找到 v缺点：缺点： 由于空闲区是按大小而不是按地址排序，因此由于空闲区是按大小而不是按地址排序，因此 释放时，要在整个链表上搜索地址相邻的空闲区释放时，要在整个链表上搜索地址相邻的空闲区 空闲区分配后剩余部分成

48、为碎片空闲区分配后剩余部分成为碎片 58 3动态分区分配算法动态分区分配算法 最差适应算法最差适应算法(WF) v按空闲区按空闲区大小递减大小递减的顺序组成空闲区可用表的顺序组成空闲区可用表 或自由链。或自由链。 v最坏适应算法的思想与最佳适应算法相反，最坏适应算法的思想与最佳适应算法相反， 将所有的空白分区按容量递减的顺序排列，最将所有的空白分区按容量递减的顺序排列，最 前面的最大的空闲区就是找到的分区。该算法前面的最大的空闲区就是找到的分区。该算法 是取所有空闲区中最大的一块，把剩余的块再是取所有空闲区中最大的一块，把剩余的块再 变成一个新小一点的空闲区。变成一个新小一点的空闲区。 59

49、分配前的状态分配前的状态 起始地址起始地址长度长度状态状态 0K0K15K15KJ1J1 38K38K10K10KJ2J2 68K68K12K12KJ3J3 110K110K10K10KJ4J4 已分区表 起始地址起始地址长度长度 状态状态 15K15K23K23K未分配未分配 48K48K20K20K未分配未分配 80K80K30K30K未分配未分配 空闲区表 J5J5和和J6J6两个新作业的长度分别为两个新作业的长度分别为5KB5KB和和13KB13KB。 起始地址起始地址 长度长度 状态状态 80K80K30K30K未分配未分配 15K15K23K23K未分配未分配 48K48K20K2

50、0K未分配未分配 空闲区表 0 J1 J4 J3 J2 15 38 48 68 80 110 120 60 最坏适应算法分配后的状态 起始地址起始地址长度长度状态状态 0K0K15K15KJ1J1 38K38K10K10KJ2J2 68K68K12K12KJ3J3 110K110K10K10KJ4J4 80K80K5K5KJ5J5 85K85K13K13KJ6J6 已分区表 起始地址起始地址长度长度状态状态 15K15K23K23K未分配未分配 48K48K20K20K未分配未分配 98K98K12K12K未分配未分配 空闲区表 J5J5和和J6J6两个新作业的长度分别为两个新作业的长度分别为

51、5KB5KB和和13KB13KB。 15 38 48 68 80 110 120 J1 J4 J3 J2 0 J5 J6 98 61 3动态分区分配算法动态分区分配算法 最坏适应算法最坏适应算法 v优点：优点： 分配时只需查找一次就可以成功分配时只需查找一次就可以成功 v缺点：缺点： 过早用掉大的空闲区，剩余的分区越过早用掉大的空闲区，剩余的分区越 来越小来越小 ，无法运行大程序，无法运行大程序 62 3动态分区分配算法动态分区分配算法 循环首次适应算法循环首次适应算法(next fit) v该算法是由首次适应算法演变而成的。在为进程该算法是由首次适应算法演变而成的。在为进程 分配内存空间时，

52、分配内存空间时，不再是不再是每次都从每次都从链首链首开始查找开始查找 ，而是，而是从上次找到从上次找到的空闲分区的的空闲分区的下一个下一个空闲分区空闲分区 开始查找，直至找到一个能满足要求的空闲分区开始查找，直至找到一个能满足要求的空闲分区 。 v为实现该算法，应设置一起始查寻指针，用于指为实现该算法，应设置一起始查寻指针，用于指 示下一次起始查寻的空闲分区。示下一次起始查寻的空闲分区。 v该算法能使内存中的空闲分区分布得更均匀，从该算法能使内存中的空闲分区分布得更均匀，从 而减少了查找空闲分区时的开销，但这样会缺乏而减少了查找空闲分区时的开销，但这样会缺乏 大的空闲分区。大的空闲分区。 63

53、 4动态分区时的回收与拼接动态分区时的回收与拼接 当某一个用户作业完成释放所占分区时，系统当某一个用户作业完成释放所占分区时，系统 应进行回收。应进行回收。 在可变式分区中，应该检查回收区与内存中前在可变式分区中，应该检查回收区与内存中前 后空闲区是否相邻，后空闲区是否相邻， 若相邻，则应进行合并，形成一个较大的空闲若相邻，则应进行合并，形成一个较大的空闲 区，并对相应的链表指针进行修改；区，并对相应的链表指针进行修改； 若不相邻，应将空闲区插入到空闲区链表的适若不相邻，应将空闲区插入到空闲区链表的适 当位置。当位置。 64 4动态分区时的回收与拼接动态分区时的回收与拼接 65 4动态分区时的

54、回收与拼接动态分区时的回收与拼接 v释放区邻接的分区情况可能是：释放区邻接释放区邻接的分区情况可能是：释放区邻接 的是另一进程的已分配区，或者是空闲区。的是另一进程的已分配区，或者是空闲区。 v下面以首次适应法说明了系统回收该进程占下面以首次适应法说明了系统回收该进程占 用区存在的四种可能情况。用区存在的四种可能情况。 v设进程的释放区为设进程的释放区为R，与，与R相邻的两个空闲区相邻的两个空闲区 分别为分别为F1和和F2。R的首地址送的首地址送LOC，R的尾地的尾地 址送址送LOC1，R的大小送的大小送SIZE。 66 (a)若释放区若释放区R与与F1相邻接，即其低地址部分邻相邻接，即其低地

55、址部分邻 接一空闲区。将接一空闲区。将R与与F1合并，合并后的空闲区合并，合并后的空闲区 仍记为仍记为F1。 4动态分区时的回收与拼接动态分区时的回收与拼接 低地址低地址 高地址高地址 空闲区空闲区 F1进程进程 P 占用区占用区2 低地址低地址 高地址高地址 占用区占用区2空闲区空闲区 F1 (a)合并后合并后 67 4动态分区时的回收与拼接动态分区时的回收与拼接 如何判断释放区如何判断释放区R 是否与某个空闲区相邻呢？是否与某个空闲区相邻呢？ 只要从链首开始查找即可：若只要从链首开始查找即可：若F1的首地址的首地址+F1 的大小的大小=R的首地址，说明的首地址，说明R与与F1相邻接。相邻接

56、。 只要修改只要修改F1的大小的大小= F1的大小的大小+LOC，其它参，其它参 数不变和在链中的位置不变。数不变和在链中的位置不变。 68 4动态分区时的回收与拼接动态分区时的回收与拼接 (b)若释放区若释放区R与与F2相邻接，即其高地址部分邻接一空相邻接，即其高地址部分邻接一空 闲区。将闲区。将R与与F2合并，合并后的空闲区记仍记为合并，合并后的空闲区记仍记为F2。 判断释放区判断释放区R 是否与是否与F2空闲区相邻，只要从链首开空闲区相邻，只要从链首开 始查找。始查找。 若若LOC+SIZE=F2的首地址，说明的首地址，说明R与与F2相邻接。需相邻接。需 修改修改F2的首地址的首地址=L

57、OC，F2的大小的大小= F2的大小的大小+SIZE 。 69 4动态分区时的回收与拼接动态分区时的回收与拼接 (b)合并后合并后 低地址低地址 高地址高地址 占用区占用区1 进程进程 P 空闲区空闲区F2 低地址低地址 高地址高地址 空闲区空闲区F2占用区占用区1 70 4动态分区时的回收与拼接动态分区时的回收与拼接 (c) 若释放区若释放区R的高、低地址部分都邻接一个空闲区。的高、低地址部分都邻接一个空闲区。 应将三个分区合并为一个大空闲区，并记为应将三个分区合并为一个大空闲区，并记为F1。 先将先将 R与与F2合并，记为合并，记为F2。 再将再将F 2与与F1合并，并将合并，并将F2从链

58、中删除。从链中删除。 空闲区空闲区F1 释放区释放区R空闲区空闲区F2空闲区空闲区F1 合并后合并后 71 4动态分区时的回收与拼接动态分区时的回收与拼接 (d)若释放区若释放区R上下都不邻接空闲区，将其插入上下都不邻接空闲区，将其插入 空闲区链的适当位置即可。空闲区链的适当位置即可。 72 5. 地址变换和分区保护地址变换和分区保护 地址变换地址变换 对动态分区可采用动态重定位装入方式，程序和对动态分区可采用动态重定位装入方式，程序和 数据的地址转换由硬件完成。数据的地址转换由硬件完成。 硬件中设置两个专门控制寄存器：基址寄存器和硬件中设置两个专门控制寄存器：基址寄存器和 限长寄存器。基址寄

59、存器存放分给作业使用的分区限长寄存器。基址寄存器存放分给作业使用的分区 的起始地址，限长寄存器存放作业占用的分区的长的起始地址，限长寄存器存放作业占用的分区的长 度。当作业占用度。当作业占用CPU 运行时，操作系统把该区的起运行时，操作系统把该区的起 始地址和长度存入基址寄存器和限长寄存器。作业始地址和长度存入基址寄存器和限长寄存器。作业 执行时，硬件根据基址寄存器进行地址转换。执行时，硬件根据基址寄存器进行地址转换。 73 5. 地址变换和分区保护地址变换和分区保护 分区保护分区保护 基址基址/限长保护法限长保护法 保护键法保护键法 74 动态分区优缺点动态分区优缺点 v优点：优点： 内存利

60、用率提高，避免了内碎片内存利用率提高，避免了内碎片 v 缺点：缺点： 出现了外碎片（分区之间未被利用出现了外碎片（分区之间未被利用 的空间）的空间） 75 5.3.4 动态可重定位分区分配动态可重定位分区分配 1.紧凑（拼接）技术紧凑（拼接）技术 紧凑（拼接）技术将内存中的所有作业进行紧凑（拼接）技术将内存中的所有作业进行 移动，同时修改每个程序的起始地址，使空移动，同时修改每个程序的起始地址，使空 闲区全都相邻接。这样把分散的多个小分区闲区全都相邻接。这样把分散的多个小分区 拼接成一个大分区，大作业可装入该分区。拼接成一个大分区，大作业可装入该分区。 紧凑之后要对被移动作业的物理地址进行相紧