第五章 存储器管理

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

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

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

4、速度与CPU速度不匹配问题。为了解决速度不匹配问题。为了解决内存速度与内存速度与CPU速度不匹配问题，引入了高速缓速度不匹配问题，引入了高速缓存。存。(5)实现内存保护和共享。内存保护是确保并发执行实现内存保护和共享。内存保护是确保并发执行的各个进程在所分配的存储区内操作，互不干扰，的各个进程在所分配的存储区内操作，互不干扰，通常由软硬件结合方式实现。通常由软硬件结合方式实现。75.2 程序的装入和链接程序的装入和链接链接程序装入模块第二步第三步装入程序内存第一步库编译程序产生的目标模块85.2.1 几个几个基本概念基本概念1.相对地址与相对地址空间相对地址与相对地址空间v在用汇编语言或高级语

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

6、的相对地址空间，又称作逻辑地址空间。址空间，又称作逻辑地址空间。95.2.1 几个几个基本概念基本概念2.绝对地址与绝对地址空间绝对地址与绝对地址空间v程序在内存空间中的实际存储单元地址称做物理程序在内存空间中的实际存储单元地址称做物理地址或绝对地址。内存空间是指物理内存中全部地址或绝对地址。内存空间是指物理内存中全部存储单元的集合所限定的空间。物理地址的总体存储单元的集合所限定的空间。物理地址的总体构成运行用户程序的物理地址空间，又称绝对地构成运行用户程序的物理地址空间，又称绝对地址空间。址空间。vCPU直接使用物理地址存取空间中的指令和数据，直接使用物理地址存取空间中的指令和数据，完成用户

7、程序或系统程序。相对地址空间的大小完成用户程序或系统程序。相对地址空间的大小由源程序决定，绝对地址空间的大小由系统硬件由源程序决定，绝对地址空间的大小由系统硬件配置决定。一个程序只有从相对地址空间装入绝配置决定。一个程序只有从相对地址空间装入绝对地址空间后才能运行。对地址空间后才能运行。105.2.1 几个几个基本概念基本概念3.地址重定位地址重定位v当一个程序的相对地址装入到与其逻辑地址空间当一个程序的相对地址装入到与其逻辑地址空间不一致的绝对地址空间中时，为了保证程序的正不一致的绝对地址空间中时，为了保证程序的正确运行，必须把指令和数据的逻辑地址转换为物确运行，必须把指令和数据的逻辑地址转

8、换为物理地址，这项工作称为地址重定位。理地址，这项工作称为地址重定位。v地址重定位通常有静态地址重定位和动态地址重地址重定位通常有静态地址重定位和动态地址重定位两种方式。定位两种方式。 静态地址重定位静态地址重定位 动态地址重定位动态地址重定位115.2.2 程序程序的装入的装入v程序的程序的装入装入指给程序的指令和数据分配物指给程序的指令和数据分配物理内存空间，也常被称为理内存空间，也常被称为加载加载。一个程序。一个程序要运行必须得装入内存，这需要将指令和要运行必须得装入内存，这需要将指令和数据的逻辑地址转换为物理地址，即需要数据的逻辑地址转换为物理地址，即需要进行地址变换。进行地址变换。v

9、根据地址变换发生时机，装入方式分为绝根据地址变换发生时机，装入方式分为绝对装入方式、可重定位装入方式和动态运对装入方式、可重定位装入方式和动态运行时装入方式三种。行时装入方式三种。125.2.2 程序程序的装入的装入1 1、绝对装入方式、绝对装入方式v 在可执行文件中记录内存地址，装入时直接定位在上述在可执行文件中记录内存地址，装入时直接定位在上述( (即文件中记录的地址即文件中记录的地址) )内存地址。内存地址。v 优点：装入过程简单。优点：装入过程简单。v 缺点：过于依赖于缺点：过于依赖于硬件结构，不适于多道硬件结构，不适于多道程序系统。程序系统。135.2.2 程序程序的装入的装入2、可

10、重定位装入方式、可重定位装入方式v当一个地址装入与其地址空间不一致的存储当一个地址装入与其地址空间不一致的存储空间中，就得要进行地址变换。也就是说将空间中，就得要进行地址变换。也就是说将虚地址映射为内存地址，把这种作法叫做虚地址映射为内存地址，把这种作法叫做地地址重定位或地址映射。址重定位或地址映射。v在在装入装入一个作业时，把作业中的指令相对地一个作业时，把作业中的指令相对地址址全部转换全部转换为绝对地址（地址转换工作是在为绝对地址（地址转换工作是在作业执行前集中一次完成的）在作业执行过作业执行前集中一次完成的）在作业执行过程中就无须再进行地址转换工作。又称程中就无须再进行地址转换工作。又称

11、静态静态重定位装入方式。重定位装入方式。145.2.2 程序程序的装入的装入2、可重定位装入方式、可重定位装入方式v优点：不需硬件支持，优点：不需硬件支持，可以装入有限多道程序可以装入有限多道程序（如（如MS DOS中的中的TSR）。）。v缺点：一个程序通常需缺点：一个程序通常需要占用连续的要占用连续的 内存空内存空间，程序装间，程序装 入内存后入内存后不能移动。不能移动。 不易实现不易实现共享。共享。155.2.2 程序程序的装入的装入3、动态运行时装入方式、动态运行时装入方式v可重定位装入方式虽然可用于可重定位装入方式虽然可用于多道程序系统多道程序系统，但程，但程序执行期间如果在内存中发生

12、移动，则程序的物理序执行期间如果在内存中发生移动，则程序的物理地址都发生改变，须修改全部物理地址，否则程序地址都发生改变，须修改全部物理地址，否则程序将无法正确执行。所以，采用可重定位方式把程序将无法正确执行。所以，采用可重定位方式把程序装入内存后，程序在内存中一般不再移动。装入内存后，程序在内存中一般不再移动。v但实际应用中，程序在内存中的位置可能经常需要但实际应用中，程序在内存中的位置可能经常需要改变。改变。v动态运行时装入方式是在动态运行时装入方式是在CPU执行访问指令执行访问指令时，时，才将要访问的程序或数据的逻辑地址转换为物理地才将要访问的程序或数据的逻辑地址转换为物理地址。址。16

13、5.2.2 程序程序的装入的装入3、动态运行时装入方式、动态运行时装入方式v动态运行时装入方式的优点是操作系统可将一个动态运行时装入方式的优点是操作系统可将一个程序离散地存放在内存空间。程序离散地存放在内存空间。v在在程序的整个执行期间，允许程序在内存中改变程序的整个执行期间，允许程序在内存中改变位置位置。v这种加载方式有利于提高内存利用率，也为实现这种加载方式有利于提高内存利用率，也为实现虚拟存储器提供了基础。虚拟存储器提供了基础。v动态运行时装入方式的缺点是需要硬件支持，操动态运行时装入方式的缺点是需要硬件支持，操作系统实现较为复杂。作系统实现较为复杂。17动态地址重定位示意图动态地址重定

14、位示意图 1500 12345Load A 500 内存空间内存空间5001000+ VR BR500100 12345Load A 500 0 虚拟空间（作业地址空间）虚拟空间（作业地址空间）.3动态运行时装入方式动态运行时装入方式185.2.3 程序程序的链接的链接v根据链接时间的不同，可把链接分成如下三根据链接时间的不同，可把链接分成如下三种：种：(1) 静态链接静态链接(2) 装入时动态链接装入时动态链接(3) 运行时动态链接运行时动态链接191静态链接方式静态链接方式(Static Linking)p在程序运行之前，先将各目标模块及它们在程序运行之前，先将各目标模块及它们所需的库函数

15、，链接成一个完整的装配模所需的库函数，链接成一个完整的装配模块，以后块，以后不再拆开不再拆开。我们把这种。我们把这种事先事先进行进行链接的方式称为静态链接方式。链接的方式称为静态链接方式。p链接时需要进行下面的修改：链接时需要进行下面的修改：201静态链接方式静态链接方式(Static Linking)(1) 对相对地址进行修改。在由编译程序所产生的所对相对地址进行修改。在由编译程序所产生的所有目标模块中，使用的都是相对地址，其起始地有目标模块中，使用的都是相对地址，其起始地址都为址都为0，每个模块中的地址都是相对于起始地址，每个模块中的地址都是相对于起始地址计算的。计算的。 (2) 变换外部

16、调用符号。将每个模块中所用的外部调变换外部调用符号。将每个模块中所用的外部调用符号也都变换为相对地址，如下图所示。这种用符号也都变换为相对地址，如下图所示。这种先进行链接所形成的一个完整的装入模块，又称先进行链接所形成的一个完整的装入模块，又称为为可执行文件可执行文件。通常都不再拆开它，要运行时可。通常都不再拆开它，要运行时可直接将它装入内存。这种事先进行链接，以后不直接将它装入内存。这种事先进行链接，以后不再拆开的链接方式，称为再拆开的链接方式，称为静态链接静态链接方式。方式。21模块模块ACALL B；Return；0L-15.2.3 程序程序的链接的链接模块模块BCALL C；Retur

17、n；0M-1模块模块CReturn；0N-1(a) 目标模块目标模块模块模块AJMP L；Return；0L-1模块模块BJMP L+M；Return；LL+M-1模块模块CReturn；L+ML+M+N-1(b) 装入模块装入模块222装入时动态链接装入时动态链接(Load-time Dynamic Linking)v这是指将用户源程序编译后所得到的一组目标模这是指将用户源程序编译后所得到的一组目标模块，在装入内存时，采用块，在装入内存时，采用边装入边链接边装入边链接的链接方的链接方式。式。v用户源程序经编译后所得的目标模块，是在装入用户源程序经编译后所得的目标模块，是在装入内存时边装入边链

18、接的，即在装入一个目标模块内存时边装入边链接的，即在装入一个目标模块时，若发生一个外部模块调用事件，将引起装入时，若发生一个外部模块调用事件，将引起装入程序去找出相应的外部目标模块，并将它装入内程序去找出相应的外部目标模块，并将它装入内存，还要修改目标模块中的相对地址。存，还要修改目标模块中的相对地址。v装入时动态链接方式有以下优点：装入时动态链接方式有以下优点：(1) 便于修改和更新。便于修改和更新。(2) 便于实现对目标模块的共享。便于实现对目标模块的共享。233运行时动态链接运行时动态链接(Run-time Dynamic Linking)v在许多情况下，应用程序在运行时，每次要运行在许

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

20、调用模块尚未装入内存时，立即由个被调用模块尚未装入内存时，立即由OS去找到去找到该模块并将之装入内存，把它链接到调用者模块该模块并将之装入内存，把它链接到调用者模块上。上。245.3 连续分配方式连续分配方式 连续分配方式是指为用户进程分配连连续分配方式是指为用户进程分配连续内存空间的内存管理方式。早期操作系续内存空间的内存管理方式。早期操作系统都是采用连续分配方式管理内存。连续统都是采用连续分配方式管理内存。连续分配方式通常分为：单一连续分配、固定分配方式通常分为：单一连续分配、固定分区分配、可变分区分配、动态可重定位分区分配、可变分区分配、动态可重定位分区分配等分区分配等255.3.1 单

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

22、，内存利用率较低。v单一连续分配存储管理方式只适用于程序的绝对单一连续分配存储管理方式只适用于程序的绝对装入。装入。265.3.2 固定分区分配固定分区分配v 基本思想：基本思想：把内存划分成若干个把内存划分成若干个大小固定，个数固定大小固定，个数固定的存储区域，每个存的存储区域，每个存储区域称为一个分区，储区域称为一个分区，每个分区中装入一道每个分区中装入一道作业，每个作业只装作业，每个作业只装入一个分区中。入一个分区中。20K28K60K124K256KOS进程进程A（6K）进程进程B（25K）进程进程C（36K）内存状态内存状态275.3.2 固定分区分配固定分区分配1. 划分分区的方法

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

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

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

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

27、分配无法分配该分区空闲？该分区空闲？分区长度分区长度Xk?表结束？表结束？返回分区号返回分区号否否否否否否是是是是是是图图5.10 5.10 固定分区分配算法固定分区分配算法325.3.2 固定分区分配固定分区分配3. 地址变换地址变换v 固定分区存储的地址变换即可采用静态重固定分区存储的地址变换即可采用静态重定位，也可采用动态重定位。定位，也可采用动态重定位。335.3.2 固定分区分配固定分区分配v优点：优点： 实现简单、开销小实现简单、开销小v 缺点：缺点： 必须预先能够估计作业要占用的空间，必须预先能够估计作业要占用的空间，分区总数固定，限制了并发作业的的数分区总数固定，限制了并发作业

28、的的数目；目； 内碎片（占用分区之内未被利用的空间内碎片（占用分区之内未被利用的空间）造成浪费）造成浪费345.3.3 可变分区分配可变分区分配v 可变分区的原理可变分区的原理v固定分区主存利用率不高，使用起来不灵活，固定分区主存利用率不高，使用起来不灵活，所以出现了可变分区的管理技术。所以出现了可变分区的管理技术。v动态分区原则：存储空间的划分是在作业装入动态分区原则：存储空间的划分是在作业装入时进行的。从可用的自由存储空间内，划出一时进行的。从可用的自由存储空间内，划出一个大小正好等于作业大小的存储区，并分配给个大小正好等于作业大小的存储区，并分配给这一作业。这一作业。v动态分区，在系统初

29、启时，除了操作系统中常动态分区，在系统初启时，除了操作系统中常驻内存部分之外，只有一个空闲分区。驻内存部分之外，只有一个空闲分区。355.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(124K)OSOS进程进程A(8K)A(8K)进程进程B(16K)B(16K)进程进程C(64K)C(64K)OSOS进程进程A(8K)A(8K)进程进程B(16K)B(16K

30、)OSOS进程进程A(8K)A(8K)36内存分配变化过程内存分配变化过程OSA（8K）8K空闲区空闲区B（16K）E（50K）D（124K）14K空闲区空闲区F（16K）OSA（8K）8K空闲区空闲区空闲区空闲区16KE（50K）F（16K）空闲合并空闲合并124+14=138K进程进程E（50K）进程进程F（16K）进入内存进入内存进程进程B（16K）进程进程D（124K）完成完成OSA（8K）24K空闲区空闲区B（16K）C完成（完成（64K）空闲区空闲区D（124K）375.3.3 可变分区分配可变分区分配2. 可变分区分配的数据结构可变分区分配的数据结构为了便于内存的分配与回收，需设

31、置用于记录为了便于内存的分配与回收，需设置用于记录分区使用情况的数据结构。分区使用情况的数据结构。 空闲分区表。系统设置一张空闲分区表，记录内空闲分区表。系统设置一张空闲分区表，记录内存中每个空闲分区的序号、大小和起始地址，存中每个空闲分区的序号、大小和起始地址，每个空闲分区在空闲分区表中占一个表目。每个空闲分区在空闲分区表中占一个表目。385.3.3 可变分区分配可变分区分配2. 可变分区分配的数据结构可变分区分配的数据结构 空闲分区链。为了实现对空闲分区的分配和链接，空闲分区链。为了实现对空闲分区的分配和链接，在每个空闲分区的起始单元中存储两个值，一在每个空闲分区的起始单元中存储两个值，一

32、个是空闲分区的大小，另一个是指向下一空闲个是空闲分区的大小，另一个是指向下一空闲分区的指针。分区的指针。395.3.3 可变分区分配可变分区分配2. 2. 可变分区分配的数据可变分区分配的数据结构结构已分配分区表。已分配分区表。系统设置系统设置一张已分配分区表，记一张已分配分区表，记录内存中每个已分配分录内存中每个已分配分区的大小、起始地址和区的大小、起始地址和状态（记录存放的作业状态（记录存放的作业名），每个已分配分区名），每个已分配分区在已分配分区表中占一在已分配分区表中占一个表目。个表目。起始地址起始地址 长度长度状态状态0K0K15K15KJ1J138K38K10K10KJ2J268K

33、68K12K12KJ3J3110K110K10K10KJ4J4已分配分区表已分配分区表405.3.3 可变分区分配可变分区分配3.常用的空闲分区分配算法有以下四种：常用的空闲分区分配算法有以下四种： 首次适应（首次适应（first fit）算法）算法 循环首次适应（循环首次适应（next fit）算法）算法 最佳适应（最佳适应（best fit）算法）算法 最差适应（最差适应（worst fit）算法）算法413动态分区分配算法动态分区分配算法 首次适应算法首次适应算法(FF,FirstFit)v要求可用表或自由链按起始要求可用表或自由链按起始地址递增地址递增的次的次序排列。序排列。v从表头查

34、询，一旦找到大小满足的分区就从表头查询，一旦找到大小满足的分区就结束探索。结束探索。v例题：如图所示是某一个时刻例题：如图所示是某一个时刻J1、J2、J3、J4在在内存中的分配情况、空闲区表和已分区表，它们内存中的分配情况、空闲区表和已分区表，它们的长度分别是的长度分别是15KB、10KB、12KB、10KB。J5和和J6两个新作业的长度分别为两个新作业的长度分别为5KB和和13KB。按照。按照最先适应算法进行内存分配，描述分配后内存、最先适应算法进行内存分配，描述分配后内存、空闲区表以及已分区表的情况。空闲区表以及已分区表的情况。423动态分区分配算法动态分区分配算法最先适应算法分配前的状态

35、最先适应算法分配前的状态起始地址起始地址 长度长度状态状态0K0K15K15KJ1J138K38K10K10KJ2J268K68K12K12KJ3J3110K110K10K10KJ4J4已分区表已分区表0J1J4J3J21538486880110120起始地址起始地址 长度长度状态状态15K15K23K23K未分配未分配48K48K20K20K未分配未分配80K80K30K30K未分配未分配空闲区表空闲区表J5J5和和J6J6两个新作业的长度分别为两个新作业的长度分别为5KB5KB和和13KB13KB。433动态分区分配算法动态分区分配算法最先适应算法分配后的状态最先适应算法分配后的状态起始地

36、址起始地址长度长度状态状态0K0K15K15KJ1J138K38K10K10KJ2J268K68K12K12KJ3J3110K110K10K10KJ4J415K15K5K5KJ5J520K20K13K13KJ6J6已分区表起始地址起始地址长度长度状态状态33K33K5K5K未分配未分配48K48K20K20K未分配未分配80K80K30K30K未分配未分配空闲区表3848110J6J1J4J3J20156880120J533J5J5和和J6J6两个新作业的长度分别为两个新作业的长度分别为5KB5KB和和13KB13KB。44重点回顾重点回顾v死锁的避免：银行家算法死锁的避免：银行家算法v死锁的

37、检测与解除死锁的检测与解除45重点回顾重点回顾v相对地址与相对地址空间相对地址与相对地址空间v绝对地址与绝对地址空间绝对地址与绝对地址空间v地址重定位地址重定位46重点回顾重点回顾v程序程序的装入的装入 绝对装入方式绝对装入方式 可重定位装入方式可重定位装入方式 动态运行时装入方式动态运行时装入方式v程序链接程序链接 (1) (1) 静态链接静态链接 (2) (2) 装入时动态链接装入时动态链接(3) (3) 运行时动态链接运行时动态链接47重点回顾重点回顾v连续分配方式：是指为用户进程分配连续连续分配方式：是指为用户进程分配连续内存空间的内存管理方式。内存空间的内存管理方式。 单一连续分配单

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

39、？表目查完？表目查完？返回分配起始地址返回分配起始地址否否否否是是是是是是否否图图 最先适应算法最先适应算法请求请求SIZESIZE大小的分区大小的分区503动态分区分配算法动态分区分配算法动态分区存储管理可采用多动态分区存储管理可采用多种数据结构对内存进行管理种数据结构对内存进行管理v每个空闲区用每个空闲区用map数据结数据结构构vstrut mapvunsigned m_size;vchar * m_addr;vstruct map cornmapN; m_addrm_addrm_sizem_sizem_addrm_addrm_sizem_size空闲区空闲区已分配已分配空闲区空闲区已分配

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

41、=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_addrm_sizem_sizem_addrm_addrm_sizem_size空闲区空闲区已分配已分配空闲区空闲区已分配已分配空闲区空闲区已分配已分配mp533动态分区分配算法动态分区分配算法 最先适应算法最先适应算法缺点：缺点： 由于查找总是从表首开始，

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

43、38K10K10KJ2J268K68K12K12KJ3J3110K110K10K10KJ4J4已分区表起始地址起始地址 长度长度 状态状态15K15K23K23K未分配未分配48K48K20K20K未分配未分配80K80K30K30K未分配未分配空闲区表J5J5和和J6J6两个新作业的长度分别为两个新作业的长度分别为5KB5KB和和13KB13KB。起始地址起始地址 长度长度 状态状态48K48K20K20K未分配未分配15K15K23K23K未分配未分配80K80K30K30K未分配未分配空闲区表0J1J4J3J2153848688011012056 最佳适应算法分配后的状态最佳适应算法分配

44、后的状态起始地址起始地址长度长度状态状态0K0K15K15KJ1J138K38K10K10KJ2J268K68K12K12KJ3J3110K110K10K10KJ4J448K48K5K5KJ5J553K53K13K13KJ6J6已分区表起始地址起始地址长度长度状态状态66K66K2K2K未分配未分配15K15K23K23K未分配未分配80K80K30K30K未分配未分配空闲区表J6J3J1J4J201538486880110120J566J5J5和和J6J6两个新作业的长度分别为两个新作业的长度分别为5KB5KB和和13KB13KB。3动态分区分配算法动态分区分配算法573动态分区分配算法动态

45、分区分配算法最佳适应法最佳适应法v优点：优点： 分配后所剩余的空白块会最小分配后所剩余的空白块会最小 平均而言，只要查找一半的表格便能找到平均而言，只要查找一半的表格便能找到v缺点：缺点： 由于空闲区是按大小而不是按地址排序，因此由于空闲区是按大小而不是按地址排序，因此释放时，要在整个链表上搜索地址相邻的空闲区释放时，要在整个链表上搜索地址相邻的空闲区 空闲区分配后剩余部分成为碎片空闲区分配后剩余部分成为碎片583动态分区分配算法动态分区分配算法最差适应算法最差适应算法(WF)v按空闲区按空闲区大小递减大小递减的顺序组成空闲区可用表的顺序组成空闲区可用表或自由链。或自由链。v最坏适应算法的思想

46、与最佳适应算法相反，最坏适应算法的思想与最佳适应算法相反，将所有的空白分区按容量递减的顺序排列，最将所有的空白分区按容量递减的顺序排列，最前面的最大的空闲区就是找到的分区。该算法前面的最大的空闲区就是找到的分区。该算法是取所有空闲区中最大的一块，把剩余的块再是取所有空闲区中最大的一块，把剩余的块再变成一个新小一点的空闲区。变成一个新小一点的空闲区。59分配前的状态分配前的状态起始地址起始地址长度长度状态状态0K0K15K15KJ1J138K38K10K10KJ2J268K68K12K12KJ3J3110K110K10K10KJ4J4已分区表起始地址起始地址长度长度 状态状态15K15K23K2

47、3K未分配未分配48K48K20K20K未分配未分配80K80K30K30K未分配未分配空闲区表J5J5和和J6J6两个新作业的长度分别为两个新作业的长度分别为5KB5KB和和13KB13KB。起始地址起始地址 长度长度 状态状态80K80K30K30K未分配未分配15K15K23K23K未分配未分配48K48K20K20K未分配未分配空闲区表0J1J4J3J2153848688011012060 最坏适应算法分配后的状态起始地址起始地址长度长度状态状态0K0K15K15KJ1J138K38K10K10KJ2J268K68K12K12KJ3J3110K110K10K10KJ4J480K80K5

48、K5KJ5J585K85K13K13KJ6J6已分区表起始地址起始地址长度长度状态状态15K15K23K23K未分配未分配48K48K20K20K未分配未分配98K98K12K12K未分配未分配空闲区表J5J5和和J6J6两个新作业的长度分别为两个新作业的长度分别为5KB5KB和和13KB13KB。1538486880110120J1J4J3J20J5J6 98613动态分区分配算法动态分区分配算法最坏适应算法最坏适应算法v优点：优点： 分配时只需查找一次就可以成功分配时只需查找一次就可以成功v缺点：缺点：过早用掉大的空闲区，剩余的分区越过早用掉大的空闲区，剩余的分区越来越小来越小 ，无法运行

49、大程序，无法运行大程序623动态分区分配算法动态分区分配算法循环首次适应算法循环首次适应算法(next fit)v该算法是由首次适应算法演变而成的。在为进程该算法是由首次适应算法演变而成的。在为进程分配内存空间时，分配内存空间时，不再是不再是每次都从每次都从链首链首开始查找开始查找，而是，而是从上次找到从上次找到的空闲分区的的空闲分区的下一个下一个空闲分区空闲分区开始查找，直至找到一个能满足要求的空闲分区开始查找，直至找到一个能满足要求的空闲分区。v为实现该算法，应设置一起始查寻指针，用于指为实现该算法，应设置一起始查寻指针，用于指示下一次起始查寻的空闲分区。示下一次起始查寻的空闲分区。v该算

50、法能使内存中的空闲分区分布得更均匀，从该算法能使内存中的空闲分区分布得更均匀，从而减少了查找空闲分区时的开销，但这样会缺乏而减少了查找空闲分区时的开销，但这样会缺乏大的空闲分区。大的空闲分区。634动态分区时的回收与拼接动态分区时的回收与拼接当某一个用户作业完成释放所占分区时，系统当某一个用户作业完成释放所占分区时，系统应进行回收。应进行回收。在可变式分区中，应该检查回收区与内存中前在可变式分区中，应该检查回收区与内存中前后空闲区是否相邻，后空闲区是否相邻，若相邻，则应进行合并，形成一个较大的空闲若相邻，则应进行合并，形成一个较大的空闲区，并对相应的链表指针进行修改；区，并对相应的链表指针进行

51、修改；若不相邻，应将空闲区插入到空闲区链表的适若不相邻，应将空闲区插入到空闲区链表的适当位置。当位置。644动态分区时的回收与拼接动态分区时的回收与拼接654动态分区时的回收与拼接动态分区时的回收与拼接v释放区邻接的分区情况可能是：释放区邻接释放区邻接的分区情况可能是：释放区邻接的是另一进程的已分配区，或者是空闲区。的是另一进程的已分配区，或者是空闲区。v下面以首次适应法说明了系统回收该进程占下面以首次适应法说明了系统回收该进程占用区存在的四种可能情况。用区存在的四种可能情况。v设进程的释放区为设进程的释放区为R，与，与R相邻的两个空闲区相邻的两个空闲区分别为分别为F1和和F2。R的首地址送的

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

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

54、OC+SIZE=F2的首地址，说明的首地址，说明R与与F2相邻接。需相邻接。需修改修改F2的首地址的首地址=LOC，F2的大小的大小= F2的大小的大小+SIZE。694动态分区时的回收与拼接动态分区时的回收与拼接(b)合并后合并后低地址低地址 高地址高地址占用区占用区1 进程进程 P 空闲区空闲区F2低地址低地址 高地址高地址空闲区空闲区F2占用区占用区1704动态分区时的回收与拼接动态分区时的回收与拼接(c) 若释放区若释放区R的高、低地址部分都邻接一个空闲区。的高、低地址部分都邻接一个空闲区。应将三个分区合并为一个大空闲区，并记为应将三个分区合并为一个大空闲区，并记为F1。 先将先将R与

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

56、和硬件中设置两个专门控制寄存器：基址寄存器和限长寄存器。基址寄存器存放分给作业使用的分区限长寄存器。基址寄存器存放分给作业使用的分区的起始地址，限长寄存器存放作业占用的分区的长的起始地址，限长寄存器存放作业占用的分区的长度。当作业占用度。当作业占用CPU 运行时，操作系统把该区的起运行时，操作系统把该区的起始地址和长度存入基址寄存器和限长寄存器。作业始地址和长度存入基址寄存器和限长寄存器。作业执行时，硬件根据基址寄存器进行地址转换。执行时，硬件根据基址寄存器进行地址转换。735. 地址变换和分区保护地址变换和分区保护 分区保护分区保护 基址基址/限长保护法限长保护法 保护键法保护键法 74动态

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

58、移动作业的物理地址进行相紧凑之后要对被移动作业的物理地址进行相应修改。应修改。765.3.4 动态可重定位分区分配动态可重定位分区分配775.3.4 动态可重定位分区分配动态可重定位分区分配2.动态重定位的实现过程动态重定位的实现过程v动态可重定位分区法中加载程序时采用动态可重定位分区法中加载程序时采用动态运行动态运行时装入时装入方式，作业装入内存后的所有地址仍是逻方式，作业装入内存后的所有地址仍是逻辑地址，将逻辑地址转换为物理地址的工作推迟辑地址，将逻辑地址转换为物理地址的工作推迟到程序指令执行时进行。到程序指令执行时进行。v系统中增设一个重定位寄存器，用它来存放程序系统中增设一个重定位寄存

59、器，用它来存放程序或数据在内存中的起始地址。程序执行时，真正或数据在内存中的起始地址。程序执行时，真正访问的物理地址是逻辑地址与重定位寄存器中的访问的物理地址是逻辑地址与重定位寄存器中的地址相加而形成的。地址相加而形成的。785.3.4 动态可重定位分区分配动态可重定位分区分配795.4 基本分页存储管理方式基本分页存储管理方式5.4.1 基本概念基本概念1页面页面v分页存储管理是将一个进程的逻辑地址空间分成分页存储管理是将一个进程的逻辑地址空间分成大小相等的若干片，这样的片被称为页或页面。大小相等的若干片，这样的片被称为页或页面。程序的页面从程序的页面从0开始编号，称为页号。一般情况下开始编

60、号，称为页号。一般情况下，进程长度不会刚好是页面大小的整数倍，进程，进程长度不会刚好是页面大小的整数倍，进程的最后一页往往装不满，形成页内碎片。的最后一页往往装不满，形成页内碎片。v页式存储管理中，页面大小应适中。若页面太小页式存储管理中，页面大小应适中。若页面太小，虽可减小页内碎片，提高内存利用率，但会使，虽可减小页内碎片，提高内存利用率，但会使每个进程占用较多页面，进程的页表过长，增加每个进程占用较多页面，进程的页表过长，增加内存存放页表的开销。反之，若页面太大，虽可内存存放页表的开销。反之，若页面太大，虽可减小页表长度，但会增大页内碎片。减小页表长度，但会增大页内碎片。805.4.1 基