chapter4_存储管理

1、3计算机操作系统计算机操作系统4课程主要内容课程主要内容操作系统引论（操作系统引论（1章）章）进程管理（进程管理（2-3章）章）存储管理（存储管理（4章）章）设备管理（设备管理（5章）章）文件管理（文件管理（6章）章）操作系统接口（操作系统接口（7章）章）系统安全性（系统安全性（9章）章）*分布式操作系统分布式操作系统5第第4 4章章 存储器管理存储器管理 存储管理的主要任务是为多道程序的运行提供存储管理的主要任务是为多道程序的运行提供良好的环境，方便用户使用存储器，提高存储器的良好的环境，方便用户使用存储器，提高存储器的利用率以及从逻辑上扩充存储器。为此存储管理应利用率以及从逻辑上扩充存储器

2、。为此存储管理应具有以下功能具有以下功能:v实现内存的分配和回收实现内存的分配和回收v地址变换地址变换v“扩充扩充”内存容量内存容量v进行存储保护进行存储保护64.1存储器的层次结构存储器的层次结构4.2程序的装入和链接程序的装入和链接4.3 连续分配存储管理方式连续分配存储管理方式4.4 基本分页存储管理方式基本分页存储管理方式4.5 基本分段存储管理方式基本分段存储管理方式第第4 4章章 存储器管理存储器管理4.6 虚拟存储器的基本概念虚拟存储器的基本概念4.7 请求分页存储管理方式请求分页存储管理方式4.8 页面置换算法页面置换算法4.9 请求分段存储管理方式请求分段存储管理方式UNIX

3、系统中存储器管理系统中存储器管理本章作业本章作业74.1-4.3 教学目标和重点难点教学目标和重点难点目标：目标：1、了解一个程序从编译、链接到被装入执行的过、了解一个程序从编译、链接到被装入执行的过程，理解逻辑地址和物理地址的含义；程，理解逻辑地址和物理地址的含义；2、了解静态链接和动态链接，绝对装入和可重定、了解静态链接和动态链接，绝对装入和可重定位装入；位装入；3、理解几种基本的连续分配方式，能区分是否有、理解几种基本的连续分配方式，能区分是否有内部碎片和外部碎片；内部碎片和外部碎片；重点重点/难点：难点：1、内部碎片和外部碎片（可命制单选题）、内部碎片和外部碎片（可命制单选题）2、逻辑

4、地址和物理地址（可命制综合应用题）、逻辑地址和物理地址（可命制综合应用题）3、内存分配策略（可命制单选题）、内存分配策略（可命制单选题）84.1 存储器的层次结构存储器的层次结构(了解了解)n4.1.1 多级存储器结构多级存储器结构 寄存器寄存器高速缓存高速缓存主存主存磁盘缓存磁盘缓存磁盘磁盘可移动存储介质可移动存储介质CPU寄存器寄存器主存主存辅存辅存速度越快，价格越高，容量越小速度越快，价格越高，容量越小9n4.1.2 主存储器与寄存器主存储器与寄存器1、主存储器：、主存储器：用于保存进程运行时的程序和用于保存进程运行时的程序和数据，也称可执行存储器。速度远低于数据，也称可执行存储器。速度

5、远低于CPU执行指令的速度。执行指令的速度。2、寄存器：、寄存器：访问速度最快，完全能与访问速度最快，完全能与CPU协调工作。以字为单位。用于加速存储器协调工作。以字为单位。用于加速存储器的访问速度。的访问速度。4.1 存储器的层次结构存储器的层次结构10n4.1.3 高速缓存和磁盘缓存高速缓存和磁盘缓存1、高速缓存：、高速缓存：容量大于或远大于寄存器，访问容量大于或远大于寄存器，访问速度快于主存储器。根据程序执行的局部性原理，速度快于主存储器。根据程序执行的局部性原理，将主存中一些经常访问的信息存放着高速缓存中，将主存中一些经常访问的信息存放着高速缓存中，减少访问主存储器的次数，提高程序的执

6、行速度。减少访问主存储器的次数，提高程序的执行速度。2、磁盘缓存：、磁盘缓存：将频繁使用的一部分磁盘数据和将频繁使用的一部分磁盘数据和信息，暂时存放在磁盘缓存中，可减少访问磁盘信息，暂时存放在磁盘缓存中，可减少访问磁盘的次数。的次数。4.1 存储器的层次结构存储器的层次结构114.2 4.2 程序的装入和链接程序的装入和链接 一个用户源程序要变一个用户源程序要变为在内存中可执行的程为在内存中可执行的程序，通常要进行以下处序，通常要进行以下处理理：（1）编译：编译：由编译程序由编译程序将用户源程序编译成若将用户源程序编译成若干个目标模块。干个目标模块。（2）链接链接：由链接程序：由链接程序将目标

7、模块和相应的库将目标模块和相应的库函数链接成装入模块。函数链接成装入模块。 （3）装入装入：由装入程序：由装入程序将装入模块装入内存。将装入模块装入内存。库库目标程序块目标程序块1 1目标程序块目标程序块2 2第一步第一步链接程序链接程序装入模块装入模块第二步第二步装入程序装入程序第三步第三步用户源程序用户源程序编译程序编译程序在外存在外存在内存在内存12n4.2.1 程序的装入程序的装入v绝对装入方式绝对装入方式v可重定位装入方式可重定位装入方式v动态运行时装入方式动态运行时装入方式n4.2.2 程序的链接程序的链接 根据链接时间的不同，可将链接分成三种：根据链接时间的不同，可将链接分成三种

8、：v静态链接静态链接v装入时动态链接装入时动态链接v运行时动态链接运行时动态链接4.2 4.2 程序的装入和链接程序的装入和链接返回目录131 1、绝对装入方式、绝对装入方式n在编译时，如果知道程序将驻留在内存的什么位置，在编译时，如果知道程序将驻留在内存的什么位置，那么，编译程序将产生那么，编译程序将产生绝对地址的目标代码绝对地址的目标代码。绝对。绝对装入程序按照装入模块中的地址，将程序和数据装装入程序按照装入模块中的地址，将程序和数据装入内存。装入模块被装入内存后，由于程序中的逻入内存。装入模块被装入内存后，由于程序中的逻辑地址与实际内存中的地址完全相同，故辑地址与实际内存中的地址完全相同

9、，故不需对程不需对程序和数据的地址进行修改序和数据的地址进行修改。 n该装入方式只适用于该装入方式只适用于单道程序环境单道程序环境。14n重定位：重定位：由于一个作业装入到与其地址空间不一致由于一个作业装入到与其地址空间不一致的存储空间所引起的，需对其有关地址部分进行的存储空间所引起的，需对其有关地址部分进行调调整整的过程就称为重定位（实质是一个地址变换过程的过程就称为重定位（实质是一个地址变换过程/地址映射）。根据地址变换进行的地址映射）。根据地址变换进行的时间及采用技术手段不同手段不同，可分为，可分为静态重定位静态重定位和和动态重定位动态重定位两类。两类。2、可重定位装入方式、可重定位装入

10、方式基本概念基本概念n逻辑地址（相对地址，虚地址）逻辑地址（相对地址，虚地址）v用户的程序经过汇编或编译后形成目标代码，目标用户的程序经过汇编或编译后形成目标代码，目标代码通常采用相对地址的形式，其代码通常采用相对地址的形式，其首地址为首地址为0，其余，其余指令中的地址都指令中的地址都相对于首地址而编址相对于首地址而编址。v不能不能用逻辑地址在内存中读取信息。用逻辑地址在内存中读取信息。n物理地址（绝对地址，实地址）物理地址（绝对地址，实地址）v 内存中存储单元的地址，内存中存储单元的地址，可直接寻址可直接寻址。n地址转换地址转换v为了保证为了保证CPU执行指令时可正确访问存储单元，需执行指令

11、时可正确访问存储单元，需将用户程序中的将用户程序中的逻辑地址转换逻辑地址转换为运行时由机器直接为运行时由机器直接寻址的寻址的物理地址物理地址，这一过程称为地址映射。，这一过程称为地址映射。03456.LOAD A 200.0100200300.LOAD A 2003456逻辑地址空间逻辑地址空间110012001300物理地址空间物理地址空间200VR+1000BR原因原因:当程序装入内存时当程序装入内存时, 操作系统要为该程序分配一个合适的内操作系统要为该程序分配一个合适的内存空间，由于程序的逻辑地址与分配到内存物理地址不一致存空间，由于程序的逻辑地址与分配到内存物理地址不一致, 而而CPU

12、执行指令时是按物理地址进行的，所以要进行地址转换。执行指令时是按物理地址进行的，所以要进行地址转换。17基本概念基本概念n静态地址转换（静态重定位）静态地址转换（静态重定位）v当用户程序被当用户程序被装入装入内存时，一次性实现逻辑地内存时，一次性实现逻辑地址到物理地址的转换，以后不再转换。址到物理地址的转换，以后不再转换。v一般在装入内存时由软件完成。一般在装入内存时由软件完成。n动态地址转换（动态重定位）动态地址转换（动态重定位）v在程序在程序运行运行过程中要访问数据时再进行程序和过程中要访问数据时再进行程序和数据的地址变换（即在逐条指令执行时完成地数据的地址变换（即在逐条指令执行时完成地址

13、映射。一般为了提高效率，此工作由硬件地址映射。一般为了提高效率，此工作由硬件地址映射机制来完成。硬件支持，软硬件结合完址映射机制来完成。硬件支持，软硬件结合完成）。成）。v硬件上需要一对寄存器的支持。硬件上需要一对寄存器的支持。182、可重定位装入方式、可重定位装入方式n可重定位装入方式可重定位装入方式：事先不知事先不知用户程序在内存的驻留位置，用户程序在内存的驻留位置，装入程序在装入时根据内存的装入程序在装入时根据内存的实际情况把相对地址（逻辑地实际情况把相对地址（逻辑地址）转换为绝对地址，装入到址）转换为绝对地址，装入到适当的位置。（适当的位置。（在装入时在装入时进行地址转换进行地址转换）

14、n用于多道程序环境用于多道程序环境1，12500193、动态运行装入方式、动态运行装入方式n如果事先不知用户程序在内存的驻留位置，程如果事先不知用户程序在内存的驻留位置，程序在运行过程中，它在内存中的位置序在运行过程中，它在内存中的位置可经常改可经常改变变。装入程序把装入模块装入内存后，并不立。装入程序把装入模块装入内存后，并不立即把装入模块中相对地址转换为绝对地址，而即把装入模块中相对地址转换为绝对地址，而是在是在程序运行程序运行时才进行。这种方式需一个重定时才进行。这种方式需一个重定位寄存器来支持。（位寄存器来支持。（在程序运行过程中进行地在程序运行过程中进行地址转换址转换）返回装入内存后

15、的所有地址都仍然是相对地址。装入内存后的所有地址都仍然是相对地址。20二、程序的链接二、程序的链接1 1、静态链接方式、静态链接方式v是一种事先链接方式，即在程序运行之前，先将各是一种事先链接方式，即在程序运行之前，先将各目标模块及它们所需的库函数，链接成一个完整的目标模块及它们所需的库函数，链接成一个完整的装入模块装入模块( (执行文件执行文件) )，以后不再拆开。，以后不再拆开。v实现静态链接应解决的问题：实现静态链接应解决的问题： （1 1）相对地址的修改）相对地址的修改 （2 2）变换外部调用符号）变换外部调用符号v存在问题：存在问题： （1 1）不便于对目标模块的修改和更新）不便于对

16、目标模块的修改和更新 （2 2）无法实现对目标模块的共享）无法实现对目标模块的共享21静态链接方式静态链接方式图图 4-3 程序链接示意图程序链接示意图22二、程序的链接二、程序的链接2、装入时动态链接方式、装入时动态链接方式v指将一组目标模块在装入内存时边装入边链接的方式指将一组目标模块在装入内存时边装入边链接的方式,具有便于修改和更新、便于实现对目标模块的共享。具有便于修改和更新、便于实现对目标模块的共享。v存在问题：存在问题：由于程序运行所有可能用的目标模块在装由于程序运行所有可能用的目标模块在装入时均全部链接在一起，所以将会把一些不会运行的入时均全部链接在一起，所以将会把一些不会运行的

17、目标模块也链接进去。如程序中的错误处理模块。目标模块也链接进去。如程序中的错误处理模块。3、运行时动态链接方式、运行时动态链接方式v在程序运行中需要某些目标模块时，才对它们进行链在程序运行中需要某些目标模块时，才对它们进行链接的方式。具有高效且节省内存空间的优点。接的方式。具有高效且节省内存空间的优点。返回234.3 连续分配存储管理方式连续分配存储管理方式q连续分配方式：连续分配方式：指为一个用户程序分配一片连续的内存空指为一个用户程序分配一片连续的内存空间。间。v4.3.1 单一连续分配方式单一连续分配方式v4.3.2 固定分区分配方式固定分区分配方式v4.3.3 动态分区分配方式动态分区

18、分配方式v4.3.6 动态重定位分区分配方式动态重定位分区分配方式v4.3.4 伙伴系统伙伴系统v分区的存储保护分区的存储保护v4.3.7覆盖与交换覆盖与交换返回目录244.3.1 单一连续分配方式（单独分区分配）单一连续分配方式（单独分区分配）n存储管理方法存储管理方法：将内存分为：将内存分为系统区系统区（内存低端，分（内存低端，分配给配给OS用）和用）和用户区用户区（内存高端，分配给用户用）。（内存高端，分配给用户用）。采用静态分配方式，即作业一旦进入内存，就要等采用静态分配方式，即作业一旦进入内存，就要等待它运行结束后才能释放内存。待它运行结束后才能释放内存。n最简单的一种存储管理方式，

19、但只能用于最简单的一种存储管理方式，但只能用于单用户、单用户、单任务的单任务的OS中。中。25单一连续分配方式单一连续分配方式n主要特点主要特点：管理简单，：管理简单，只需小量的软件和硬件只需小量的软件和硬件支持，便于用户了解和支持，便于用户了解和使用。但因内存中只装使用。但因内存中只装入一道作业运行，内存入一道作业运行，内存空间浪费大，各类资源空间浪费大，各类资源的利用率也不高。的利用率也不高。系统区系统区-os用户区用户区用户程序用户程序26例子例子n一个容量为一个容量为256KB的内存，操作系统占用的内存，操作系统占用32KB，剩下，剩下224KB全部分配给用户作业，如果一个作业仅需全部

20、分配给用户作业，如果一个作业仅需64KB，那，那么就有么就有160KB的存储空间被浪费。的存储空间被浪费。操作系统操作系统作业作业0KB32KB96KB256KB-1分配给用分配给用户的空间户的空间返回274.3.2 固定分区分配方式固定分区分配方式n是最早使用的一种可运行多道程序的存储管理方法。是最早使用的一种可运行多道程序的存储管理方法。n存储管理方法存储管理方法v内存空间的划分内存空间的划分：将内存空间划分为若干个固定大：将内存空间划分为若干个固定大小的分区，除小的分区，除OS占一区外，其余的一个分区装入一占一区外，其余的一个分区装入一道程序。分区的大小可以相等，也可以不等，但道程序。分

21、区的大小可以相等，也可以不等，但事事先必须确定，在运行时不能改变先必须确定，在运行时不能改变。即分区大小及边。即分区大小及边界在运行时不能改变。界在运行时不能改变。v系统需建立一张系统需建立一张分区说明表或使用表分区说明表或使用表，以记录分区，以记录分区号、分区大小、分区的起始地址及状态（已分配或号、分区大小、分区的起始地址及状态（已分配或未分配）。未分配）。28固定分区分配方式示意图固定分区分配方式示意图图图 4-4 固定分区使用表固定分区使用表20K20K未未n内存分配内存分配v当某个用户程序要装入内存时，由当某个用户程序要装入内存时，由内存分配程序检索内存分配程序检索分区说明表分区说明表

22、，从表中找出一个满足要求的尚未分配的，从表中找出一个满足要求的尚未分配的分区分配该程序，同时修改说明表中相应分区的状态；分区分配该程序，同时修改说明表中相应分区的状态；若找不到大小足够的分区，则拒绝为该程序分配内存。若找不到大小足够的分区，则拒绝为该程序分配内存。v当程序执行完毕，当程序执行完毕，释放占用的分区释放占用的分区，管理程序将修改，管理程序将修改说明表中相应分区的状态为未分配，说明表中相应分区的状态为未分配，实现内存资源的实现内存资源的回收回收。n主要特点主要特点v管理简单，但因作业的大小并不一定与某个分区大小管理简单，但因作业的大小并不一定与某个分区大小相等，从而使一部分存储空间被

23、浪费。所以主存的利相等，从而使一部分存储空间被浪费。所以主存的利用率不高。用率不高。 例：在某系统中，采用固定分区分配管理方式，内存分区例：在某系统中，采用固定分区分配管理方式，内存分区（单位：字节）情况如图所示，现有大小为（单位：字节）情况如图所示，现有大小为1K、9K、33K、121K的多个作业要求进入内存，试画出它们进入内存后的的多个作业要求进入内存，试画出它们进入内存后的空间分配情况，并说明主存浪费多大？空间分配情况，并说明主存浪费多大？ 0k 20k 28k 60k 180k 511k1234（1）内存分区图）内存分区图os区号区号大小大小起址起址状态状态18k20k未分配未分配23

24、2k28k未分配未分配3120k60k未分配未分配4331k180k未分配未分配（2）分区说明表）分区说明表区号区号大小大小起址起址状态状态18k20k已分配已分配232k28k已分配已分配3120k60k已分配已分配4331k180k已分配已分配（2）分区说明表）分区说明表(3)主存浪费空间主存浪费空间=(8-1)+(32-9)+(120-33)+(331-121)=327(k)解：解：根据分区说明表，将根据分区说明表，将4个分区依次分配给个分区依次分配给4个作业，同个作业，同时修改分区说明表，其内存分配和分区说明表如下所示：时修改分区说明表，其内存分配和分区说明表如下所示： 0k 20k

25、28k 60k180k511k23(1)内存分配图内存分配图1K9K33K121K返回324.3.3 动态分区分配方式动态分区分配方式n动态分区分配又称为可变式分区分配，是一种动动态分区分配又称为可变式分区分配，是一种动态划分存储器的分区方法。态划分存储器的分区方法。n存储管理方法存储管理方法v内存不是预先划分好的；内存不是预先划分好的；v作业装入时，根据作业的需求和内存空间的使作业装入时，根据作业的需求和内存空间的使用情况来决定是否分配；用情况来决定是否分配；v若有足够的空间，则按需要分割一部分分区给若有足够的空间，则按需要分割一部分分区给该进程；否则令其等待内存空间。该进程；否则令其等待内

26、存空间。33动态分区分配动态分区分配n主要特点主要特点 管理简单，只需少量的软件和硬件支持，便于管理简单，只需少量的软件和硬件支持，便于用户了解和使用。进程的大小与某个分区大小相用户了解和使用。进程的大小与某个分区大小相等，从而主存的利用率有所提高。等，从而主存的利用率有所提高。341、分区分配中的数据结构、分区分配中的数据结构n空闲分区表空闲分区表v用来登记系统中的空闲分区用来登记系统中的空闲分区(分区号、分区起始地址、分分区号、分区起始地址、分区大小及状态区大小及状态)。n空闲分区链空闲分区链v用链头指针将系统中的空闲分区链接起来，构成空闲分用链头指针将系统中的空闲分区链接起来，构成空闲分

27、区链。每个空闲分区的起始部分存放相应的控制信息区链。每个空闲分区的起始部分存放相应的控制信息(如如大小、指向下一空闲分区的指针等大小、指向下一空闲分区的指针等)。353、分区分配操作、分区分配操作_分配内存和回收内存分配内存和回收内存（1）分配内存）分配内存v系统利用某种分配算法，从空闲分区表系统利用某种分配算法，从空闲分区表/链中找到所需大小链中找到所需大小的分区。的分区。v分区的切割：分区的切割： 设请求的分区大小为设请求的分区大小为u.size，空闲分区的大小为，空闲分区的大小为m.size。若。若m.size-u.size size(size是事先规定的不再切是事先规定的不再切割的剩余

28、分区的大小割的剩余分区的大小)，说明多余部分大小可不再切割，将，说明多余部分大小可不再切割，将整个分区分配给请求者；否则，从该分区中按请求的大小整个分区分配给请求者；否则，从该分区中按请求的大小划分出一块内存空间分配出去，余下的部分仍留在空闲分划分出一块内存空间分配出去，余下的部分仍留在空闲分区表区表/链中，然后将分配区的首址返回给调用者。链中，然后将分配区的首址返回给调用者。36从头开始查表从头开始查表从该分区中划出从该分区中划出u.size大小的分区大小的分区检索完否检索完否？返回返回m.sizeu.sizem.size-u.size size将该分区分配给请求者，修改有关数据结构将该分区

29、分配给请求者，修改有关数据结构返回返回将该分区从分区表将该分区从分区表/链中移出链中移出继续检索下一个表项继续检索下一个表项YYYNNN内存分配流程图内存分配流程图37（2）回收内存）回收内存n回收分区与已有空闲分区的相邻情况有以下四种回收分区与已有空闲分区的相邻情况有以下四种： 1）回收分区上邻接一个空闲分区）回收分区上邻接一个空闲分区,合并后首地址为空闲分区的首地址合并后首地址为空闲分区的首地址,大大小为二者之和。小为二者之和。 2）回收分区下邻接一个空闲分区）回收分区下邻接一个空闲分区,合并后首地址为回收分区的首地址合并后首地址为回收分区的首地址,大小为二者之和。大小为二者之和。 3）回

30、收分区上下邻接空闲分区）回收分区上下邻接空闲分区,合并后首地址为上空闲分区的首地址合并后首地址为上空闲分区的首地址,大小为三者之和。大小为三者之和。 4）回收分区不邻接空闲分区，这时在空闲分区表中新建一表项，并填）回收分区不邻接空闲分区，这时在空闲分区表中新建一表项，并填写分区大小等信息。写分区大小等信息。回收分区回收分区空闲分区空闲分区(a)空闲分区空闲分区回收分区回收分区(b)空闲分区空闲分区回收分区回收分区空闲分区空闲分区(c)内存回收情况内存回收情况返回384.3.4 基于顺序搜索的动态分区分配算法基于顺序搜索的动态分区分配算法n为了将一个作业装入内存，应按照一定的分配算法从空闲为了将

31、一个作业装入内存，应按照一定的分配算法从空闲分区表（链）中选分区表（链）中选 出一个满足作业需求的分区分配给作业，出一个满足作业需求的分区分配给作业，如果这个空闲分区的容量比作业申请的空间要大，则将该如果这个空闲分区的容量比作业申请的空间要大，则将该分区一分为二，一部分分配给作业，剩下的部分仍然留在分区一分为二，一部分分配给作业，剩下的部分仍然留在空闲分区表（链）中，同时修改空闲分区表（链）中相应空闲分区表（链）中，同时修改空闲分区表（链）中相应的信息。目前常用分配算法有：的信息。目前常用分配算法有：首次适应算法（首次适应算法（First-Fit） 循环首次适应算法（循环首次适应算法（Next

32、-Fit） 最佳适应算法（最佳适应算法（Best-Fit） 最坏适应算法（最坏适应算法（Worst-Fit） 前进39首次适应算法（最先适应算法）首次适应算法（最先适应算法）n算法：空闲分区（链）按算法：空闲分区（链）按地址递增地址递增的次序排列。的次序排列。在进行内存分配时，在进行内存分配时，从空闲分区表从空闲分区表/链首开始顺序链首开始顺序查找查找，直到找到第一个满足其大小要求的空闲分，直到找到第一个满足其大小要求的空闲分区为止。然后再按照作业大小，从该分区中划出区为止。然后再按照作业大小，从该分区中划出一块内存空间分配给请求者，余下的空闲分区仍一块内存空间分配给请求者，余下的空闲分区仍留

33、在空闲分区表（链）中。留在空闲分区表（链）中。区号区号大小大小起址起址132k20k28k52k3120k60k4331k180k空闲分区表空闲分区表解：解：按首次适应算法，按首次适应算法，申请作业申请作业100k，分配，分配3号分区，剩下号分区，剩下分区为分区为20k，起始地址，起始地址160K ；申请作业申请作业30k，分配，分配1号分区，号分区，剩下分区为剩下分区为2k，起始地址，起始地址50K ；申请作业申请作业7k，分配，分配2号分区，号分区，剩下分区为剩下分区为1k，起始地址，起始地址59K。其内存分配图及分配后空闲。其内存分配图及分配后空闲分区表如下：分区表如下：例例 ：系统中的

34、空闲分区表如下表示，现有三个作业分配申请内系统中的空闲分区表如下表示，现有三个作业分配申请内存空间存空间100K、30K及及7K，给出按首次适应算法的内存分配情，给出按首次适应算法的内存分配情况及分配后空闲分区表。况及分配后空闲分区表。区号区号大小大小起址起址12k50k21k59k320k160k4331k180k(2)该算法分配后的空闲分区表该算法分配后的空闲分区表0k20k52k60k180k511k(1)内存分配图内存分配图50K59K160K180Kv首次适应算法的特点首次适应算法的特点 优先利用内存优先利用内存低地址部分低地址部分的空闲分区，从而保留了高地址的空闲分区，从而保留了高

35、地址部分的大空闲区。但由于低地址部分不断被划分，致使低地址部分的大空闲区。但由于低地址部分不断被划分，致使低地址端留下许多难以利用的很小的空闲分区端留下许多难以利用的很小的空闲分区(碎片或零头碎片或零头)，而每次，而每次查找又都是从低地址部分开始，这无疑增加了查找可用空闲分查找又都是从低地址部分开始，这无疑增加了查找可用空闲分区的开销。区的开销。返回42循环首次适应算法循环首次适应算法n算法要求算法要求 又称为下次适应算法，又称为下次适应算法，由首次适应算法演变而来由首次适应算法演变而来。在为作业分配内存空间时，不再每次从空闲分区表在为作业分配内存空间时，不再每次从空闲分区表/链首开始查找，而

36、是链首开始查找，而是从上次找到的空闲分区的下一个从上次找到的空闲分区的下一个空闲分区开始查找，空闲分区开始查找，直到找到第一个能满足其大小要直到找到第一个能满足其大小要求的空闲分区为止。然后，再按照作业大小，从该分求的空闲分区为止。然后，再按照作业大小，从该分区中划出一块内存空间分配给请求者，余下的空闲分区中划出一块内存空间分配给请求者，余下的空闲分区仍留在空闲分区表区仍留在空闲分区表/链中。链中。区号区号大小大小起址起址132k20k28k52k3120k60k4331k180k空闲分区表空闲分区表解：解：按循环首次适应算法，按循环首次适应算法，申请作业申请作业100k，分配，分配3号分区，

37、剩号分区，剩下分区为下分区为20k，起始地址，起始地址160K；申请作业申请作业30k，分配，分配4号分区，号分区，剩下分区为剩下分区为301k，起始地址，起始地址210K ；申请作业申请作业7k，分配，分配1号分号分区，剩下分区为区，剩下分区为25k，起始地址，起始地址27K 。其内存分配图及分配后。其内存分配图及分配后空闲分区表如下：空闲分区表如下：例例 ：系统中的空闲分区表如下，现有三个作业分配申请内系统中的空闲分区表如下，现有三个作业分配申请内存空间存空间100K、30K及及7K。给出按循环首次适应算法的内存。给出按循环首次适应算法的内存分配情况及分配后空闲分区表。分配情况及分配后空闲

38、分区表。区号区号大小大小起址起址125k27k28k52k320k160k4301k210k(2)该算法分配后的空闲分区表该算法分配后的空闲分区表返回v算法特点：算法特点：使存储空间的利用更加均衡，不致使小的空闲使存储空间的利用更加均衡，不致使小的空闲区集中在存储区的一端，但这会导致缺乏大的空闲分区。区集中在存储区的一端，但这会导致缺乏大的空闲分区。 0k 20k 52k 60k180k511k(1)内存分配图内存分配图27K52K160K210K45最佳适应算法最佳适应算法n算法要求：算法要求： 空闲分区表空闲分区表/链按链按容量大小递增容量大小递增的次序排列。的次序排列。在进行内存分配时，

39、从空闲分区表在进行内存分配时，从空闲分区表/链的链的首开始首开始顺顺序查找，直到找到第一个满足其大小要求的空闲序查找，直到找到第一个满足其大小要求的空闲分区为止。分区为止。 按这种方式为作业分配内存，就能把既满足按这种方式为作业分配内存，就能把既满足作业要求又与作业大小最接近的空闲分区分配给作业要求又与作业大小最接近的空闲分区分配给作业。如果该空闲分区大于作业的大小，则与首作业。如果该空闲分区大于作业的大小，则与首次适应算法相同，将剩余空闲分区仍留在空闲分次适应算法相同，将剩余空闲分区仍留在空闲分区表区表/链中。链中。例例 ：系统中的空闲分区表如下，现有三个作业分配申请系统中的空闲分区表如下，

40、现有三个作业分配申请内存空间内存空间100K、30K及及7K。给出按最佳适应算法的内存。给出按最佳适应算法的内存分配情况及分配后空闲分区表。分配情况及分配后空闲分区表。区号区号大小大小起址起址18k52k232k20k3120k60k4331k180k分配前的空闲分区表分配前的空闲分区表 0k 20k 52k 60k180k511k2134内存分区内存分区解：解：按最佳适应算法，分配前的空闲分区表如上表。按最佳适应算法，分配前的空闲分区表如上表。申请作业申请作业100k，分配，分配3号分区，剩下分区为号分区，剩下分区为20k,起始地址起始地址160K；申请作申请作业业30k，分配，分配2号分区

41、，剩下分区为号分区，剩下分区为2k，起始地址，起始地址50K ；申请作申请作业业7k，分配，分配1号分区，剩下分区为号分区，剩下分区为1k，起始地址，起始地址59K 。其内存。其内存分配图及分配后空闲分区表如下：分配图及分配后空闲分区表如下：区号区号大小大小起址起址18k52k320k160k232k20k4331k180k1)作业作业100K分配后的空闲分区表分配后的空闲分区表区号区号大小大小起址起址12k50k28k52k320k160k4331k180k2)作业作业30K分配后的空闲分区表分配后的空闲分区表区号区号大小大小起址起址11k59k22k50k320k160k4331k180k

42、3)作业作业7K分配后的空闲分区表分配后的空闲分区表(2) 分配后的空闲分区表分配后的空闲分区表返回 0k 20k 52k 60k180k511k(1)内存分配图内存分配图50K59K160K180K区号区号大小大小起址起址11k59k22k50k320k160k4331k180kv算法特点算法特点 若存在与作业大小一致的空闲分区若存在与作业大小一致的空闲分区,则它必然被选中，若则它必然被选中，若不存在与作业大小一致的空闲分区，则只划分比作业稍大的空不存在与作业大小一致的空闲分区，则只划分比作业稍大的空闲分区，从而保留了大的空闲分区闲分区，从而保留了大的空闲分区。但空闲区一般不可能正好但空闲区

43、一般不可能正好和它申请的内存空间大小一样，因而将其分割成两部分时，往和它申请的内存空间大小一样，因而将其分割成两部分时，往往使剩下的空闲区非常小，从而在存储器中留下许多难以利用往使剩下的空闲区非常小，从而在存储器中留下许多难以利用的小空闲区（碎片或零头）。的小空闲区（碎片或零头）。49最坏适应算法最坏适应算法n算法要求算法要求 空闲分区表空闲分区表/链链按容量大小递减按容量大小递减的次序排列。的次序排列。在进行内存分配时，从空闲分区表在进行内存分配时，从空闲分区表/链的链的首开始首开始顺顺序查找，直到找到第一个比之大的空闲分区为止，序查找，直到找到第一个比之大的空闲分区为止，剩下的空闲仍留在空

44、闲分区表剩下的空闲仍留在空闲分区表/链中。链中。区号区号大小大小起址起址1331k180k2120k60k332k20k48k52k空闲分区表空闲分区表例例 ：系统中的空闲分区表如下，现有三个作业分配申请内存系统中的空闲分区表如下，现有三个作业分配申请内存空间空间100K、30K及及7K。给出按最坏适应算法的内存分配情况。给出按最坏适应算法的内存分配情况及分配后空闲分区表。及分配后空闲分区表。解：解：按最坏适应算法，分配前的空闲分区表如上表。按最坏适应算法，分配前的空闲分区表如上表。申请作业申请作业100k，分配，分配1号分区，剩下分区为号分区，剩下分区为231k，起始地址，起始地址280K；

45、申请申请作业作业30k，分配，分配1号分区，剩下分区为号分区，剩下分区为201k，起始地址，起始地址310K ；申申请作业请作业7k，分配，分配1号分区，剩下分区为号分区，剩下分区为194k，起始地址，起始地址317K 。其内存分配图及分配后空闲分区表如下：其内存分配图及分配后空闲分区表如下：区号区号大小大小起址起址1231k280k2120k60k332k20k48k52k1)作业作业100K分配后的空闲分区表分配后的空闲分区表区号区号大小大小起址起址1201k310k2120k60k332k20k48k52k2)作业作业30K分配后的空闲分区表分配后的空闲分区表区号区号大小大小起址起址11

46、94k317k2120k60k332k20k48k52k3)作业作业7K分配后的空闲分区表分配后的空闲分区表区号区号大小大小起址起址1194k317k2120k60k332k20k48k52k(2) 分配后的空闲分区表分配后的空闲分区表3 0k 20k 52k 60k180k511k(1)内存分配图内存分配图20K52K60K280K310K317K返回v算法特点算法特点 总是挑选满足作业要求的最大的分区分配给作业。这样使总是挑选满足作业要求的最大的分区分配给作业。这样使分给作业后剩下的空闲分区也较大，可装下其它作业。但由于分给作业后剩下的空闲分区也较大，可装下其它作业。但由于最大的空闲分区总

47、是因首先分配而划分，当有大作业到来时，最大的空闲分区总是因首先分配而划分，当有大作业到来时，其存储空间的申请往往会得不到满足。其存储空间的申请往往会得不到满足。534.3.5 基于索引搜索的动态分区分配算法基于索引搜索的动态分区分配算法n固定划分方案限制了系统中活跃进程的数目。并固定划分方案限制了系统中活跃进程的数目。并且，只能运行不超过分区大小的进程，如果进程且，只能运行不超过分区大小的进程，如果进程远远小于分区大小，则内存空间的利用率非常低。远远小于分区大小，则内存空间的利用率非常低。n动态划分方案使存储管理复杂化，并且需要系统动态划分方案使存储管理复杂化，并且需要系统付出紧凑零头的额外开

48、销。付出紧凑零头的额外开销。54n将空闲分区根据容量大小进行分类，具有相同容将空闲分区根据容量大小进行分类，具有相同容量的空闲分区单独设立一个空闲分区链表，同时量的空闲分区单独设立一个空闲分区链表，同时在内存中设立一张管理索引表。在内存中设立一张管理索引表。n第一步：根据进程的大小，从索引表中去寻找能第一步：根据进程的大小，从索引表中去寻找能容纳它的最小空闲区链表；容纳它的最小空闲区链表；n第二步：从链表中取下第一块进行分配，不对任第二步：从链表中取下第一块进行分配，不对任何分区产生分割。能保留大的分区。何分区产生分割。能保留大的分区。1、快速适应算法（、快速适应算法（quick fit）55

49、2、伙伴系统、伙伴系统n伙伴系统内存的用户可用空间为伙伴系统内存的用户可用空间为2u。n系统总是为进程分配大小为系统总是为进程分配大小为2i的一个空闲分区。的一个空闲分区。其中其中mi U,2m是系统允许的最小分区尺寸。是系统允许的最小分区尺寸。n伙伴系统：综合固定划分技术和动态划分技术的伙伴系统：综合固定划分技术和动态划分技术的优点。优点。562、伙伴系统、伙伴系统存储分配存储分配n进程申请大小为进程申请大小为k的空间，系统为之分配一个的空间，系统为之分配一个2i的空闲分的空闲分区，其中，区，其中，2i-12u,即进程即进程内存空间，失败；内存空间，失败；n若找到，即把该空闲分区分配给进程。

50、若找到，即把该空闲分区分配给进程。n若当前无尺寸为若当前无尺寸为2i的空闲分区，则：的空闲分区，则： （1）将）将i变成变成i+1,查找一个尺寸为查找一个尺寸为2i+1的空闲分区。若存在，的空闲分区。若存在，转（转（2）执行；否则，继续执行（）执行；否则，继续执行（1） （2）等分）等分2i+1空闲分区：产生两个空闲分区：产生两个2i的伙伴分区；的伙伴分区； （3）把其中一个）把其中一个2i的伙伴分区作为空闲分区；的伙伴分区作为空闲分区； （4）另一个）另一个2i空闲分区分配给进程，结束。空闲分区分配给进程，结束。572、伙伴系统、伙伴系统回收回收n当系统执行完毕，释放一个尺寸为当系统执行完毕

51、，释放一个尺寸为2i的分区时，的分区时，系统用下面的算法回收该分区：系统用下面的算法回收该分区：n如果被回收分区的伙伴分区非空闲，那么保留该如果被回收分区的伙伴分区非空闲，那么保留该分区为一个独立的空闲分区，否则分区为一个独立的空闲分区，否则 （1）合并回收分区及其伙伴分区，从而得到一个）合并回收分区及其伙伴分区，从而得到一个尺寸为尺寸为2i+1的空闲分区；的空闲分区； （2）系统再次调用本算法回收上一步得到的尺寸）系统再次调用本算法回收上一步得到的尺寸为为2i+1的空闲分区。的空闲分区。583、哈希算法、哈希算法n利用哈希快速查找的优点，以及空闲分区在可利利用哈希快速查找的优点，以及空闲分区

52、在可利用空闲区表中的分布规律，建立哈希函数，构造用空闲区表中的分布规律，建立哈希函数，构造一张以空闲分区大小为关键字的哈希表，该表的一张以空闲分区大小为关键字的哈希表，该表的每一个表项记录了一个对应的空闲分区链表头指每一个表项记录了一个对应的空闲分区链表头指针。针。594.3.6 动态可重定位分区分配方式动态可重定位分区分配方式1、碎片问题、碎片问题 在分区存储管理方式中，必须把作业装入在分区存储管理方式中，必须把作业装入到一片到一片连续的内存空间连续的内存空间。如果系统中有若干个。如果系统中有若干个小的分区，其总容量大于要装入的作业，但由小的分区，其总容量大于要装入的作业，但由于它们不相邻接

53、，也将致使作业不能装入内存。于它们不相邻接，也将致使作业不能装入内存。例例 ：如图所示系统中有四个小空闲分区，并不相如图所示系统中有四个小空闲分区，并不相邻，但总容量为邻，但总容量为90KB，如果现有一作业要求分，如果现有一作业要求分配配40KB的内存空间，由于系统中所有空闲分区的内存空间，由于系统中所有空闲分区的容量均小于的容量均小于40KB，故此作业无法装入内存。，故此作业无法装入内存。 这种内存中无法被利用的存储空间称为这种内存中无法被利用的存储空间称为“零头零头”或或“碎片碎片”.根据碎片出现的情况分为根据碎片出现的情况分为以下两种：以下两种：操作系统作业A20KB20KB作业B30K

54、B30KB作业C15KB15KB作业D25KB25KB60系统中的碎片系统中的碎片n内部碎片内部碎片：指分配给作业的存储空间中未被利用的部分。如：指分配给作业的存储空间中未被利用的部分。如固定分区中存在的碎片。固定分区中存在的碎片。n外部碎片外部碎片：指系统中无法利用的小的空闲分区。如动态分区：指系统中无法利用的小的空闲分区。如动态分区中存在的碎片。中存在的碎片。25KB作业作业D15KB作业作业C30KB作业作业B20KB作业作业A操作系统操作系统外外部部碎碎片片外部碎片外部碎片os用用户户程程序序p4p1p20k20k56k65k125k135k内部碎片内部碎片内内部部碎碎片片612 2、

55、碎片问题的解决方法、碎片问题的解决方法n拼接或紧凑或紧缩技术拼接或紧凑或紧缩技术v将内存中所有作业移到内存一端（作业在将内存中所有作业移到内存一端（作业在内存中的位置发生了变化，这就必须对其内存中的位置发生了变化，这就必须对其地址加以修改或变换即称为重定位），使地址加以修改或变换即称为重定位），使本来分散的多个小空闲分区连成一个大的本来分散的多个小空闲分区连成一个大的空闲区。如图所示。空闲区。如图所示。v这种通过移动作业从把多个分散的小分区这种通过移动作业从把多个分散的小分区拼接成一个大分区的方法称为拼接或紧凑拼接成一个大分区的方法称为拼接或紧凑或紧缩或紧缩。v拼接时机：分区回收时；当找不到足

56、够大拼接时机：分区回收时；当找不到足够大的空闲分区且总空闲分区容量可以满足作的空闲分区且总空闲分区容量可以满足作业要求时。业要求时。操作系统作业A作业B作业C作业D20KB20KB30KB 90KB30KB 90KB15KB15KB25KB25KB623 3、动态重定位、动态重定位n拼接或紧凑，都会对程序或数据的地址产生移位拼接或紧凑，都会对程序或数据的地址产生移位影响，必须进行重定位。而为了使地址的转换不影响，必须进行重定位。而为了使地址的转换不会影响到指令的执行速度，必须有硬件地址变换会影响到指令的执行速度，必须有硬件地址变换机构的支持。机构的支持。n重定位寄存器：重定位寄存器：存放程序（

57、数据）在内存中的起存放程序（数据）在内存中的起始地址。程序在执行时，真正访问的内存地址是始地址。程序在执行时，真正访问的内存地址是相对地址与重定位寄存器中的地址相加而形成的。相对地址与重定位寄存器中的地址相加而形成的。n动态重定位：动态重定位：地址变换是在程序执行期间，随着地址变换是在程序执行期间，随着对每条指令或数据的访问自动进行的。对每条指令或数据的访问自动进行的。v动态重定位分区分配技术动态重定位分区分配技术 在动态分区分配算法中增加拼接功能，在找不到足够大的空在动态分区分配算法中增加拼接功能，在找不到足够大的空闲分区来满足作业要求，而系统中总空闲分区容量可以满足作业闲分区来满足作业要求

58、，而系统中总空闲分区容量可以满足作业要求时，进行拼接。要求时，进行拼接。动态重定位分区分配算法流程图动态重定位分区分配算法流程图有大于有大于x的的空闲分区吗？空闲分区吗？返回分区号返回分区号空闲分区空闲分区总和大于总和大于x吗？吗？拼接拼接并修改相应数据结构并修改相应数据结构返回返回修改有关数据结构修改有关数据结构按按动态分区分配动态分区分配方式方式进行分配进行分配YYNN无法分配，返回无法分配，返回请求分配一个大小为请求分配一个大小为x的分区的分区64n动态重定位分区分配方式主要特点动态重定位分区分配方式主要特点v可以充分利用存储区中的可以充分利用存储区中的“零头零头/碎片碎片”，提高，提高

59、主存的利用率。主存的利用率。 v若若 “零头零头/碎片碎片”大多，则拼接频率过高会使大多，则拼接频率过高会使系统开销加大。系统开销加大。返回分配分配方式方式有无内有无内部碎片部碎片有无外有无外部碎片部碎片优点优点缺点缺点单一连单一连续分配续分配有有无无简单简单只能用在单用户、单任务只能用在单用户、单任务的的OS固定分固定分区分配区分配有有无无可用于多道程序系统的最可用于多道程序系统的最简单的分配方案简单的分配方案存储空间浪费存储空间浪费首次适首次适应算法应算法无无有有动态分区分配中最简单的动态分区分配中最简单的方案方案低地址部分用得太多，高低地址部分用得太多，高地址部分相对空闲，导致地址部分相

60、对空闲，导致查找效率低查找效率低循环首循环首次适应次适应无无有有查找时间很少，内存空间查找时间很少，内存空间分布均匀分布均匀会导致缺乏大的空闲分区会导致缺乏大的空闲分区最佳适最佳适应算法应算法无无有有使得外部碎片都很小，对使得外部碎片都很小，对于一次分配来说是最佳的于一次分配来说是最佳的需要查找整个内存空间，需要查找整个内存空间，费时，长期来看留下了很费时，长期来看留下了很多难以利用的小空闲区多难以利用的小空闲区最差适最差适应算法应算法无无有有使得留下来的空闲区较大，使得留下来的空闲区较大，便于下次利用便于下次利用需要查找整个内存空间，需要查找整个内存空间，费时，过早用掉大的空闲费时，过早用掉