操作系统第5章讲存储管理1连续分配

1、主要研究三方面的问题：主要研究三方面的问题： 放（放（PlacementPlacement） 取（取（FetchFetch） 换（换（ReplacementReplacement） 存储管理研究的内容存储管理研究的内容 l第一个问题：放（第一个问题：放（PlacementPlacement），如何），如何 放入内存？放入内存？ 存储管理研究的内容存储管理研究的内容 连续连续 不连续不连续 多道固定分区存放多道固定分区存放 多道可变分区存放多道可变分区存放 单道连续存放单道连续存放 分页存放分页存放 分段存放分段存放 段页式存放段页式存放 放放 l第二个问题是：第二个问题是： 取（取（Fetch

2、Fetch），即如），即如 何从外存调入内存。何从外存调入内存。 存储管理研究的内容存储管理研究的内容 预调：预调：访问前访问前 预先调入内存预先调入内存 请调：请调：因空间不因空间不 足，访问时请求足，访问时请求 调入内存调入内存 单道连续一次调入单道连续一次调入 分页式请求调入分页式请求调入 分段式分段式请求调入请求调入 段页式段页式请求调入请求调入 取取 多道固定分区一次调入多道固定分区一次调入 多道可变分区一次调入多道可变分区一次调入 l第三个的问题：换（第三个的问题：换（ReplacementReplacement），即），即 请求从外存调入的页或段与内存中的哪些请求从外存调入的页或

3、段与内存中的哪些 块或哪个存储区对换？块或哪个存储区对换？ 存储管理研究的内容存储管理研究的内容 换换 先进先出算法先进先出算法FIFO 时钟算法时钟算法CLOCK 最优算法最优算法OPT 最近最少使用算法最近最少使用算法LRU 页式策略页式策略 5.15.1程序的装入和链接程序的装入和链接 一、源程序装入内存的三个步骤一、源程序装入内存的三个步骤 l编译编译 l链接链接 l装入装入 一、源程序装入内存的三个步骤一、源程序装入内存的三个步骤 如：有一作业如：有一作业A A，有，有4 4个程序段，装入过程如下：个程序段，装入过程如下： 主程主程 序段序段 子主程子主程 序段序段 数据段数据段 堆

4、栈段堆栈段 编译编译 主程主程 序段序段 子主程子主程 序段序段 数据段数据段 堆栈段堆栈段 0 40K 0 30K 0 20K 0 10K 链接链接 主程主程 序段序段 子主程子主程 序段序段 数据段数据段 堆栈段堆栈段 0 100K 装入装入 OS 用户用户 可用可用 空间空间 地址地址 重定重定 位位 0 800K 4096K 作业作业A的源的源 程序程序-名名 空间空间 作业作业A的目标的目标 模块模块-逻辑逻辑 地址空间地址空间 作业作业A重定位重定位 后的物理地址后的物理地址 空间空间 作业作业A的目标的目标 程序程序(可执行可执行 文件文件)-逻辑逻辑 地址空间地址空间 二、链接

5、方式二、链接方式 1 1、静态链接、静态链接-程序运行之前就事先程序运行之前就事先 将外部目标模块链接成可执行文件，称为静态将外部目标模块链接成可执行文件，称为静态 链接。例：如下作业链接。例：如下作业B B有三个目标程序模块。有三个目标程序模块。 链接链接 装入装入 OS 用户用户 可用可用 空间空间 地址地址 重定重定 位位 0 800K 4096K 模块模块A Call B Return 模块模块B Call C Return 模块模块C Return 0 L-1 0 M-1 0 N-1 模块模块A JSR “L” Return 模块模块B JSR “L+M” Return 模块模块C

6、Return 0 L-1 L L+M-1 L+M L+M+N-1 作业作业B的目标模块的目标模块- -逻辑地址空间逻辑地址空间 作业作业B的目标的目标 程序程序(可执行可执行 文件文件)-逻辑逻辑 地址空间地址空间 二、链接方式二、链接方式 2 2、装入时动态链接、装入时动态链接-程序在装入内程序在装入内 存时才将外部目标模块链接成完整的可执行的存时才将外部目标模块链接成完整的可执行的 目标模块。目标模块。 装入时链接装入时链接 地址地址 重定重定 位位 4096K 模块模块A Call B Return 模块模块B Call C Return 模块模块C Return 0 L-1 0 M-1

7、 0 N-1 OS 用户用户 可用可用 内存内存 空间空间 0 800K 模块模块A JSR “L” Return 模块模块B JSR “L+M” Return 模块模块C Return 0 L-1 L L+M-1 L+M L+M+N-1 作业作业B的目标模块的目标模块- -逻辑地址空间逻辑地址空间 基址寄存器基址寄存器 二、链接方式二、链接方式 3 3、运行时动态链接、运行时动态链接-由于程序在每由于程序在每 次运行时，可能运行的次运行时，可能运行的程序模块可能不同，在程序模块可能不同，在 程序得到运行时才将用到的目标模块链接成完程序得到运行时才将用到的目标模块链接成完 整的可执行的目标模块

8、。整的可执行的目标模块。 三、重定位三、重定位-完成相对（逻辑）地址转换完成相对（逻辑）地址转换 成内存物理（绝对）地址的工作。分为静态重成内存物理（绝对）地址的工作。分为静态重 定位和动态重定位。定位和动态重定位。 如下图示：如下图示： 相对地址相对地址 操作系统操作系统-50KB-50KB 0 50K 80K 130K 190K 256K 作业作业1-20KB 作业作业2-40KB 作业作业3-50KB 作业作业4-60KB 作业作业1-20KB 作业作业2-40KB 作业作业3-50KB 作业作业4-60KB 0 20K 40K 0 50K 60K 0 0 内存物理地址内存物理地址 重定

9、位重定位 5.2 5.2 连续空间分配连续空间分配 方式：单道连续、多道固定、多道可变方式：单道连续、多道固定、多道可变 5.2.1 5.2.1 单道连续分配单道连续分配 单道单道: :指指任一时刻内存只有一道作业，任一时刻内存只有一道作业， 该作业连续存放于内存中。该作业连续存放于内存中。 特点：易于理解，访问效率高、空间利特点：易于理解，访问效率高、空间利 用率低。用率低。 （1 1）内存空间安排：内存除存在）内存空间安排：内存除存在OSOS外，外， 余下的空间只供一个用户程序使用。余下的空间只供一个用户程序使用。 一、管理方法 操作系统操作系统 用户程序用户程序 0 a a a+1a+1

10、 n n 界地址寄存器界地址寄存器 （2）设置越界检查机构：用户程序每访用户程序每访 问一次主存，越界检查机构将访问的地址问一次主存，越界检查机构将访问的地址 与界地址寄存器中的值比较。若越界，则与界地址寄存器中的值比较。若越界，则 终止其执行。终止其执行。 falsefalse 界地址寄存器界地址寄存器 A Aa a CPUCPU truetrue 地址地址A A 终止程序运行终止程序运行 操作系统操作系统 用户用户 程序程序 0 a n a a （3 3）覆盖（）覆盖（overlapoverlap）技术）技术 引入原因：因内存小于作业的程序引入原因：因内存小于作业的程序 空间而引入覆盖。空

11、间而引入覆盖。 方法：将用户空间划分成一个固定方法：将用户空间划分成一个固定 区和多个覆盖区。主程序放固定区，区和多个覆盖区。主程序放固定区， 依次调用的子程序则放在同一个覆盖依次调用的子程序则放在同一个覆盖 区。操作系统提供覆盖系统调用函数，区。操作系统提供覆盖系统调用函数， 由用户编程序时考虑调用。由用户编程序时考虑调用。 操作系统操作系统 固定区固定区(4kB)(4kB) 覆盖区覆盖区(6kB)(6kB) 覆盖区覆盖区(10kB)(10kB) A(4kB)A(4kB) E(10kB)E(10kB)D(6kB)D(6kB) C(4kB)C(4kB)B(6kB)B(6kB) F(8kB)F(

12、8kB) 例例: :下图的调用关系中下图的调用关系中,B,B不会调用不会调用 C,CC,C也不会调用也不会调用B,B,所以过程所以过程B,CB,C不必不必 同时调入主存同时调入主存, , 同样同样D D、E E之间，之间，D D、 E E与与F F之间也有同样的关系。之间也有同样的关系。 多道：多道：任一时刻内存可有多道作业，每道任一时刻内存可有多道作业，每道 作业连续存放于内存作业连续存放于内存. . 5.2.2 5.2.2 多道固定划分法多道固定划分法 一、固定划分管理方法一、固定划分管理方法 （1 1）将用户）将用户 内存空间分成内存空间分成 长度固定的若长度固定的若 干块。每块分干块。

13、每块分 区的大小不一区的大小不一 定相等。定相等。 操作系统操作系统 U1U1 . U Un n 用户空间用户空间 例如例如: :某存储系统共某存储系统共 256KB256KB采用固定分区采用固定分区 法，法，0-50K0-50K为为OSOS使用。使用。 50K-80K50K-80K为分区为分区1 1， 80K-130K80K-130K为分区为分区2 2， 130K-190K130K-190K为分区为分区3 3， 190K-256K190K-256K为分区为分区4 4。 见图示见图示 操作系统操作系统-50KB-50KB 分区分区1-30KB1-30KB 分区分区2-50KB2-50KB 分区

14、分区4-66KB4-66KB 0 50K 80K 130K 分区分区3-60KB3-60KB 190K 256K 这样，内存就可这样，内存就可 以同时装入四个作以同时装入四个作 业，分区业，分区1 1可装入可装入 小于小于30KB30KB的作业，的作业， 分区分区2 2可装入小于可装入小于 50KB50KB的作业，分区的作业，分区 3 3可装入小于可装入小于60KB60KB 的作业，分区的作业，分区4 4可可 装入小于装入小于66KB66KB的作的作 业。业。 操作系统操作系统-50KB-50KB 0 50K 80K 130K 190K 256K 作业作业1-20KB 作业作业2-40KB 作

15、业作业3-50KB 作业作业4-60KB 1.1.上下界寄存器上下界寄存器 的地址检查机构。的地址检查机构。 当作业被调度运行当作业被调度运行 时，作业在内存中时，作业在内存中 的上下界地址送上的上下界地址送上 下界寄存器，每次下界寄存器，每次 内存访问时，地址内存访问时，地址 检查机构作越界检检查机构作越界检 查。查。 （2 2）地址访问保护技术的第一种方式）地址访问保护技术的第一种方式 操作系统操作系统-50KB-50KB 0 50K 80K 130K 190K 256K 作业作业1-20KB 作业作业2-40KB 作业作业3-50KB 作业作业4-60KB （1 1）上下界寄存器和地址检

16、查机构。）上下界寄存器和地址检查机构。 CPUCPU 下界寄存器下界寄存器上界寄存器上界寄存器 TrueTrue TrueTrue 地址地址A A 程序性中断程序性中断 操作系统操作系统-50KB-50KB 0 50K 80K 130K 190K 256K 作业作业1-20KB 作业作业2-40KB 作业作业3-50KB 作业作业4-60KB 静态重定位：静态重定位：指用户代码中使用的相对指用户代码中使用的相对 地址地址, ,连接程序连接程序将其装配成绝对地址。将其装配成绝对地址。 （即：在装入一个作业时，把该作业中（即：在装入一个作业时，把该作业中 的程序和数据地址一次全部转换成绝对的程序和

17、数据地址一次全部转换成绝对 地址。地址。) ) （2 2）上下界寄存器和地址检查机构要）上下界寄存器和地址检查机构要 求作业采用静态重定位技术。求作业采用静态重定位技术。 100 500 : : MOV R1,(500) 123 0 700 例：程序例：程序A的逻辑地址空间如图，将其装的逻辑地址空间如图，将其装 入内存。内存起始地址为入内存。内存起始地址为5000号单元。用号单元。用 静态重定位法画出其装入内存后的情况。静态重定位法画出其装入内存后的情况。 MOV R1，(500) 表示：将表示：将500号单元号单元 （地址）的数据（地址）的数据123送入送入1号寄存器。号寄存器。 静态重定位

18、装入内静态重定位装入内 存后的情况：存后的情况： 100 500 : : MOV R1,(500) 123 0 700 5100 5500 5700 5000 逻辑地址逻辑地址 : : MOV R1,(5500) 123 0 内存物理地址内存物理地址 2 2. .基址寄存器、长基址寄存器、长 度寄存器的动态地度寄存器的动态地 址转换机构。址转换机构。当作当作 业被调度运行时，将业被调度运行时，将 作业所占内存基址及作业所占内存基址及 长度送基址、长度寄长度送基址、长度寄 存器，每次内存访问存器，每次内存访问 时，先看访问地址是时，先看访问地址是 否小于长度，然后否小于长度，然后+ +基基 址进

19、行访存。见下图。址进行访存。见下图。 操作系统操作系统-50KB-50KB 0 50K 80K 130K 190K 256K 作业作业1-20KB 作业作业2-40KB 作业作业3-50KB 作业作业4-60KB （2 2）地址访问保护技术的第二种方式）地址访问保护技术的第二种方式 CPUCPU 基地址寄存器基地址寄存器长度寄存器长度寄存器 + + TrueTrue地址地址A A false false 程序性中断程序性中断 OSOS 作业作业1 1 作业作业2 2 作业作业3 3 作业作业4 4 例：例：CPU要访问上例作业要访问上例作业2的的 A地址时的检查过程地址时的检查过程 CPUCP

20、U 基地址基地址80K80K限长限长40K40K + + TrueTrue地址地址A A false false 程序性中断程序性中断 操作系统操作系统-50KB-50KB 0 50K 80K 130K 190K 256K 作业作业1-20KB 作业作业2-40KB 作业作业3-50KB 作业作业4-60KB 动态重定位：动态重定位：指用户代码中的相对指用户代码中的相对 地址先原封不动地装入内存指定地地址先原封不动地装入内存指定地 址，在执行期间才被动态地转换成址，在执行期间才被动态地转换成 绝对地址绝对地址. . （2 2）基址寄存器、长度寄存器和）基址寄存器、长度寄存器和 动态地址转换机构

21、要求作业采用动动态地址转换机构要求作业采用动 态重定位技术态重定位技术 100 500 : : MOV R1,(500) 123 0 700 : : MOV R1,(500) 123 0 内存绝对地址内存绝对地址 5000 5100 5500 5700 + 5000 基址寄存器基址寄存器 相对地此相对地此 700? 长度寄存器长度寄存器 700 Y N 程序性中断程序性中断 又例动态重定位的实现过程。指令又例动态重定位的实现过程。指令MOV MOV R1,(3000)R1,(3000)（即把相对地址为（即把相对地址为30003000的单元的单元 中的中的123123取到取到1 1号寄存器）号寄

22、存器） （3 3）多道固定划分法的作业调度技术）多道固定划分法的作业调度技术 OS 4kB 6kB 12kB .3kB 4kB1kB2kB .5kB6kB .7kB 10kB 11kB8kB （1 1）多队列法）多队列法 OS 4kB 6kB 12kB .7kB 3kB 4kB5kB （2 2）单队列）单队列法法 （4 4）固定分区法存在碎片问题）固定分区法存在碎片问题 内部碎片：内存某存储区间大于其存放作内部碎片：内存某存储区间大于其存放作 业空间的部分。如：作业只有业空间的部分。如：作业只有 3KB3KB时，而某内存固定分区有时，而某内存固定分区有4KB4KB。有。有1KB1KB内内 部碎

23、片。部碎片。 OS 12KB 固定固定 4KB 3KB 内部碎片内部碎片 外部碎片：内存某存储区间容不下要运行外部碎片：内存某存储区间容不下要运行 的作业时。的作业时。 如：作业长度为：如：作业长度为：5KB5KB，8KB8KB，12KB12KB时，若时，若 内存固定分区只剩下内存固定分区只剩下4KB4KB，则存在外部碎片。，则存在外部碎片。 OSOS 4KB4KB 6KB6KB 12KB12KB 外部碎片外部碎片 一、管理方法 5.2.3 多道连续可变划分法 特点：多道、连续、但不固定划分内存。多道、连续、但不固定划分内存。 系统设置一个空闲块队列，初始状态系统设置一个空闲块队列，初始状态

24、时队列中只有一个连续的空闲块。作业时队列中只有一个连续的空闲块。作业 到达后，作业有多大就分配多大的空间。到达后，作业有多大就分配多大的空间。 作业撤离时，将释放的空间加入空闲队作业撤离时，将释放的空间加入空闲队 列。列。 例题例题1 1：有以下：有以下4 4个作业，采用多道连续分个作业，采用多道连续分 配技术配技术 作业作业1-20KB 作业作业2-40KB 作业作业3-50KB 作业作业4-60KB 0 20K 40K 0 50K 60K 0 0 操作系统操作系统-50KB-50KB 空闲区空闲区 0 50K 70K 110K 160K 256K 作业作业1-20KB 作业作业2-40KB

25、 作业作业3-50KB 作业作业4-60KB 220K 例题例题2 2：有以下：有以下5 5个作业，假设任一时间段个作业，假设任一时间段 内，内存中每一作业的运行时间相等，采内，内存中每一作业的运行时间相等，采 用用FCFSFCFS作业调度方法。作业调度方法。 作业到来次序作业到来次序 所需存储量所需存储量 运行时间运行时间 J1 60KB 10s J2 100KB 5s J3 30KB 20s J4 70KB 8s J5 50KB 15s OS 0 40K 256K J1J2J3J4J5 共190K 二、可变分区中的数据结构二、可变分区中的数据结构 常用的数据结构有两种：空闲分区表和常用的数

26、据结构有两种：空闲分区表和 空闲分区链。空闲分区链。 (1)(1)空闲分区表。为内存中每个尚未分配空闲分区表。为内存中每个尚未分配 出去的分区设置一个表项，每个表项包含分出去的分区设置一个表项，每个表项包含分 区序号、分区起始地址和分区的大小。区序号、分区起始地址和分区的大小。 例：根据右图的内存使用情况填写空闲分区例：根据右图的内存使用情况填写空闲分区 表。表。 操作系统操作系统 空闲区空闲区1(26KB) 已使用已使用 空闲区空闲区2(14KB) 已使用已使用 空闲区空闲区3(5KB) 已使用已使用 空闲区空闲区4(30KB) 已使用已使用 0k 40k 66k 70k 84k 100k

27、105k 150k 180k 256k 空闲分区表空闲分区表 分区分区 序号序号 分区起分区起 始地址始地址 分区分区 大小大小 140k26kB 270k14kB 3100k5kB 4150k30kB (2) (2)空闲分区链。在每个空闲分区中设置空闲分区链。在每个空闲分区中设置 用于控制分区分配的信息及用于链接各个分用于控制分区分配的信息及用于链接各个分 区的指针，将内存中的空闲分区链接成一个区的指针，将内存中的空闲分区链接成一个 链表。不同的分配算法链表的组织方式不同。链表。不同的分配算法链表的组织方式不同。 三、可变分区分配算法三、可变分区分配算法 ( (一一) )首次适应首次适应(F

28、irst Fit)(First Fit)算法。算法。 该算法要求空闲分区以地址递增的次序该算法要求空闲分区以地址递增的次序 排序。排序。 如果采用的是链表结构，分配时则从链如果采用的是链表结构，分配时则从链 表的开始顺序进行查找，直到找到一个能够表的开始顺序进行查找，直到找到一个能够 满足进程大小要求的空闲分区为止。然后，满足进程大小要求的空闲分区为止。然后， 按进程的大小，从分区中按进程的大小，从分区中“切出切出”一块内存一块内存 空间分配给请求者，余下的空闲分区仍然留空间分配给请求者，余下的空闲分区仍然留 在链表中。在链表中。 例例1 1：根据右图的内存使用：根据右图的内存使用 情况画出首

29、次适应算法的链情况画出首次适应算法的链 表组织形式及分配一个表组织形式及分配一个10KB10KB 的作业后的情况。的作业后的情况。 操作系统操作系统 空闲区空闲区1(26KB) 已使用已使用 空闲区空闲区2(14KB) 已使用已使用 空闲区空闲区3(5KB) 已使用已使用 空闲区空闲区4(30KB) 已使用已使用 0k 40k 66k 70k 84k 100k 105k 150k 180k 256k 1 1解：解：（1 1）分配一个分配一个10KB10KB 的作业前的链表组织形式。的作业前的链表组织形式。 40k 26kB 70k 14kB 100k 5kB 150k 30kB 70k100k

30、150k （2 2）分配一个）分配一个10KB10KB的作业后的的作业后的 链表组织形式。链表组织形式。 50k 16kB 70k 14kB 100k 5kB 150k 30kB 70k100k150k 操作系统操作系统 空闲区空闲区1(26kB) 已使用已使用 空闲区空闲区2(14kB) 已使用已使用 空闲区空闲区3(5kB) 已使用已使用 空闲区空闲区4(30kB) 已使用已使用 0k 40k 66k 70k 84k 100k 105k 150k 180k 256k 表头指针表头指针 表头指针表头指针 三、可变分区分配算法三、可变分区分配算法 ( (二二) )下次适应下次适应(Next F

31、it)(Next Fit)算法。算法。 该算法从首次适应算法演变而来。为了避该算法从首次适应算法演变而来。为了避 免低地址部分小空闲分区的不断增加，在给进免低地址部分小空闲分区的不断增加，在给进 程分配内存空间时，不再每次从链首开始查找，程分配内存空间时，不再每次从链首开始查找， 而是从上次找到的空闲分区的下一个空闲分区而是从上次找到的空闲分区的下一个空闲分区 开始查找，直到找到一个能满足要求的空闲分开始查找，直到找到一个能满足要求的空闲分 区，并从中区，并从中“切出切出”一块与请求的大小相等的一块与请求的大小相等的 内存空间分配出去。内存空间分配出去。 例例2 2：根据右图的内存使用：根据右

32、图的内存使用 情况画出下次适应算法的链情况画出下次适应算法的链 表组织形式及分配一个表组织形式及分配一个10KB10KB 的作业后的情况。假设上次的作业后的情况。假设上次 找到的空闲分区是空闲区找到的空闲分区是空闲区1 1。 操作系统操作系统 空闲区空闲区1(16kB) 已使用已使用 空闲区空闲区2(14KB) 已使用已使用 空闲区空闲区3(5KB) 已使用已使用 空闲区空闲区4(30KB) 已使用已使用 0k 40k 66k 70k 84k 100k 105k 150k 180k 256k 50k 已使用已使用 2 2解：解：（1 1）分配一个分配一个10KB10KB 的作业前的链表组织形式

33、。的作业前的链表组织形式。 （2 2）分配一个）分配一个10KB10KB的作业后的的作业后的 链表组织形式。链表组织形式。 50k 16kB 70k 14KB 100k 5KB 150k 30kB 70k100k150k 50k 16KB 80k 4KB 100k 5KB 150k 30KB 80k100k150k 操作系统操作系统 空闲区空闲区1(16kB) 已使用已使用 空闲区空闲区2(14kB) 已使用已使用 空闲区空闲区3(5kB) 已使用已使用 空闲区空闲区4(30kB) 已使用已使用 0k 40k 66k 70k 84k 100k 105k 150k 180k 256k 50k 已

34、使用已使用 表头指针表头指针 表头指针表头指针 三、可变分区分配算法三、可变分区分配算法 ( (三三) )最佳适应最佳适应(Best Fit)算法。算法。 最佳的含义是指每次为进程分配内存最佳的含义是指每次为进程分配内存 时，总是把与进程大小最匹配的空闲分区时，总是把与进程大小最匹配的空闲分区 分配出去。分配出去。 该算法若采用的数据结构是空闲分区该算法若采用的数据结构是空闲分区 链，首先要求将空闲分区，按分区大小递链，首先要求将空闲分区，按分区大小递 增的顺序形成一空闲分区链。当进程要求增的顺序形成一空闲分区链。当进程要求 分配内存时，第一次找到的满足要求的空分配内存时，第一次找到的满足要求

35、的空 闲区，必然是最优的。闲区，必然是最优的。 例例3 3：根据右图的内存使用：根据右图的内存使用 情况画出最佳适应算法的链情况画出最佳适应算法的链 表组织形式及分配一个表组织形式及分配一个10KB10KB 的作业后的情况。的作业后的情况。 操作系统操作系统 空闲区空闲区1(26KB) 已使用已使用 空闲区空闲区2(14KB) 已使用已使用 空闲区空闲区3(5KB) 已使用已使用 空闲区空闲区4(30KB) 已使用已使用 0k 40k 66k 70k 84k 100k 105k 150k 180k 256k 3 3解：解：（1 1）分配一个分配一个10KB10KB 的作业前的链表组织形式。的作

36、业前的链表组织形式。 100k 5KB 70k 14KB 40k 26KB 150k 30KB 70k40k150k （2 2）分配一个）分配一个10KB10KB的作业后的的作业后的 链表组织形式。链表组织形式。 80k 4KB 100k 5KB 40k 26KB 150k 30KB 100k40k150k 操作系统操作系统 空闲区空闲区1(26KB) 已使用已使用 空闲区空闲区2(14KB) 已使用已使用 空闲区空闲区3(5KB) 已使用已使用 空闲区空闲区4(30KB) 已使用已使用 0k 40k 66k 70k 84k 100k 105k 150k 180k 256k 表头指针表头指针

37、表头指针表头指针 三、可变分区分配算法三、可变分区分配算法 ( (四四) )最坏适应最坏适应(Worst Fit)算法。算法。 该算法与最佳适应算法相反，要求空该算法与最佳适应算法相反，要求空 闲分区按分区大小递减的顺序排序，每次闲分区按分区大小递减的顺序排序，每次 分配时，从链首找到最大的空闲分区分配时，从链首找到最大的空闲分区“切切 出出”一块进行分配。一块进行分配。 该算法的特点是基本上不会留下小空该算法的特点是基本上不会留下小空 闲分区，不易形成碎片。缺点是大的空闲闲分区，不易形成碎片。缺点是大的空闲 分区被切割，当有较大的进程需要运行时，分区被切割，当有较大的进程需要运行时， 系统往

38、往不能满足要求。系统往往不能满足要求。 例例4 4：根据右图的内存使用：根据右图的内存使用 情况画出最坏适应算法的链情况画出最坏适应算法的链 表组织形式及分配一个表组织形式及分配一个10KB10KB 的作业后的情况。的作业后的情况。 操作系统操作系统 空闲区空闲区1(26KB) 已使用已使用 空闲区空闲区2(14KB) 已使用已使用 空闲区空闲区3(5KB) 已使用已使用 空闲区空闲区4(30KB) 已使用已使用 0k 40k 66k 70k 84k 100k 105k 150k 180k 256k 4 4解：解：（1 1）分配一个分配一个10KB10KB 的作业前的链表组织形式。的作业前的链

39、表组织形式。 150k 30KB 40k 26KB 70k 14KB 100k 5KB 40k70k100k （2 2）分配一个）分配一个10KB10KB的作业后的的作业后的 链表组织形式。链表组织形式。 40k 26KB 160k 20KB 70k 14KB 100k 5KB 160k70k100k 操作系统操作系统 空闲区空闲区1(26KB) 已使用已使用 空闲区空闲区2(14KB) 已使用已使用 空闲区空闲区3(5KB) 已使用已使用 空闲区空闲区4(30KB) 已使用已使用 0k 40k 66k 70k 84k 100k 105k 150k 180k 256k 表头指针表头指针 表头指针表头指针 四、可变分区的作业