轻松掌握操作系统概念之第五讲存储管理之一连续分配

主要研究三方面的问题：主要研究三方面的问题：放（放（PlacementPlacement）取（取（FetchFetch）换（换（ReplacementReplacement）存储管理研究的内容存储管理研究的内容第五讲第五讲 存储管理概述存储管理概述l第一个问题：放（第一个问题：放（PlacementPlacement），如何），如何放入内存？放入内存？存储管理研究的内容存储管理研究的内容连续连续不连续不连续多道固定分区存放多道固定分区存放多道可变分区存放多道可变分区存放单道连续存放单道连续存放分页存放分页存放分段存放分段存放段页式存放段页式存放放放l第二个问题是：第二个问题是：取（取（FetchFetch），即如何），即如何从外存调入内存。从外存调入内存。存储管理研究的内容存储管理研究的内容预调：预调：访问前访问前预先调入内存预先调入内存请调：请调：因空间不因空间不足，访问时请求足，访问时请求调入内存调入内存单道连续一次调入单道连续一次调入分页式请求调入分页式请求调入分段式分段式请求调入请求调入段页式段页式请求调入请求调入取取多道固定分区一次调入多道固定分区一次调入多道可变分区一次调入多道可变分区一次调入l第三个的问题：换（第三个的问题：换（ReplacementReplacement），即），即请求从外存调入的页或段与内存中的哪些请求从外存调入的页或段与内存中的哪些块或哪个存储区对换？块或哪个存储区对换？存储管理研究的内容存储管理研究的内容换换先进先出算法先进先出算法FIFO时钟算法时钟算法CLOCK最优算法最优算法OPT最近最少使用算法最近最少使用算法LRU页式策略页式策略5.15.1程序的装入和链接程序的装入和链接一、源程序装入内存的三个步骤一、源程序装入内存的三个步骤l编译编译l链接链接l装入装入第五讲存储管理之一第五讲存储管理之一-连续空间分配连续空间分配一、源程序装入内存的三个步骤一、源程序装入内存的三个步骤如：有一作业如：有一作业A A，有，有4 4个程序段，装入过程如下：个程序段，装入过程如下：主程主程序段序段子主程子主程序段序段数据段数据段堆栈段堆栈段编译编译主程主程序段序段子主程子主程序段序段数据段数据段堆栈段堆栈段040K030K020K010K链接链接主程主程序段序段子主程子主程序段序段数据段数据段堆栈段堆栈段0100K装入装入OS用户用户可用可用内存内存空间空间地址地址重定重定位位0800K4096K作业作业A的源的源程序程序-名名空间空间作业作业A的目标的目标模块模块-逻辑逻辑地址空间地址空间作业作业A重定位重定位后的物理地址后的物理地址空间空间作业作业A的目标的目标程序程序(可执行可执行文件文件)-逻逻辑地址空间辑地址空间二、链接方式二、链接方式 1 1、静态链接、静态链接-程序运行之前就事先程序运行之前就事先将外部目标模块链接成可执行文件，称为静态将外部目标模块链接成可执行文件，称为静态链接。例：如下作业链接。例：如下作业B B有三个目标程序模块。有三个目标程序模块。链接链接装入装入OS用户用户可用可用内存内存空间空间地址地址重定重定位位0800K4096K模块模块ACall BReturn模块模块BCall CReturn模块模块CReturn0L-10M-10N-1模块模块AJSR“L”Return模块模块BJSR“L+M”Return模块模块CReturn0L-1LL+M-1L+ML+M+N-1作业作业B的目标模块的目标模块-逻辑地址空间逻辑地址空间作业作业B的目标的目标程序程序(可执行可执行文件文件)-逻逻辑地址空间辑地址空间二、链接方式二、链接方式2 2、装入时动态链接、装入时动态链接-程序在装入内程序在装入内存时才将外部目标模块链接成完整的可执行的存时才将外部目标模块链接成完整的可执行的目标模块。目标模块。装入时链接装入时链接地址地址重定重定位位4096K模块模块ACall BReturn模块模块BCall CReturn模块模块CReturn0L-10M-10N-1OS用户用户可用可用内存内存空间空间0800K模块模块AJSR“L”Return模块模块BJSR“L+M”Return模块模块CReturn0L-1LL+M-1L+ML+M+N-1作业作业B的目标模块的目标模块-逻辑地址空间逻辑地址空间基址寄存器基址寄存器二、链接方式二、链接方式3 3、运行时动态链接、运行时动态链接-由于程序在每由于程序在每次运行时，可能运行的次运行时，可能运行的程序模块可能不同，在程序模块可能不同，在程序得到运行时才将用到的目标模块链接成完程序得到运行时才将用到的目标模块链接成完整的可执行的目标模块。整的可执行的目标模块。三、重定位三、重定位-完成相对（逻辑）地址转换成完成相对（逻辑）地址转换成内存物理（绝对）地址的工作。分为静态重定内存物理（绝对）地址的工作。分为静态重定位和动态重定位。位和动态重定位。如下图示：如下图示：相对地址相对地址操作系统操作系统-50KB-50KB050K80K130K190K256K作业作业1-20KB作业作业2-40KB作业作业3-50KB作业作业4-60KB作业作业1-20KB作业作业2-40KB作业作业3-50KB作业作业4-60KB020K40K050K60K00内存物理地址内存物理地址重重定定位位5.2 5.2 连续空间分配连续空间分配 方式：单道连续、多道固定、多道可变方式：单道连续、多道固定、多道可变5.2.1 5.2.1 单道连续分配单道连续分配单道单道:指指任一任一时刻内存只有一道作业，时刻内存只有一道作业，该作业连续存放于内存中。该作业连续存放于内存中。特点：易于理解，访问效率高、空间利特点：易于理解，访问效率高、空间利用率低。用率低。（1 1）内存空间安排：内存除存在）内存空间安排：内存除存在OSOS外，外，余下的空间只供一个用户程序使用。余下的空间只供一个用户程序使用。一、管理方法操作系统操作系统用户程序用户程序0a aa+1a+1n n界界地址寄存器地址寄存器（2）设置越界检查机构：用户程序每访用户程序每访问一次主存，越界检查机构将访问的地址问一次主存，越界检查机构将访问的地址与界地址寄存器中的值比较。若越界，则与界地址寄存器中的值比较。若越界，则终止其执行。终止其执行。falsefalse界地址寄存器界地址寄存器A Aa aCPUCPUtruetrue地址地址A A终止程序运行终止程序运行操作系统操作系统用户用户程序程序0ana a（3 3）覆盖（）覆盖（overlapoverlap）技术技术 引入原因：因内存小于作业的程序引入原因：因内存小于作业的程序空间而引入覆盖。空间而引入覆盖。方法：将用户空间划分成一个固定方法：将用户空间划分成一个固定区和多个覆盖区。主程序放固定区，区和多个覆盖区。主程序放固定区，依次调用的子程序则放在同一个覆盖依次调用的子程序则放在同一个覆盖区。操作系统提供覆盖系统调用函数，区。操作系统提供覆盖系统调用函数，由用户编程序时考虑调用。由用户编程序时考虑调用。操作系统操作系统固定区固定区(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(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）将用户将用户内存空间分成内存空间分成长度固定的若长度固定的若干块干块。每块分。每块分区的大小不一区的大小不一定相等。定相等。操作系统操作系统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分区分区4-66KB4-66KB050K80K130K分区分区3-60KB3-60KB190K256K 这样，内存就可这样，内存就可以同时装入四个作以同时装入四个作业，分区业，分区1 1可装入可装入小于小于30KB30KB的作业，的作业，分区分区2 2可装入小于可装入小于50KB50KB的作业，分区的作业，分区3 3可装入小于可装入小于60KB60KB的作业，分区的作业，分区4 4可可装入小于装入小于66KB66KB的作的作业。业。操作系统操作系统-50KB-50KB050K80K130K190K256K作业作业1-20KB作业作业2-40KB作业作业3-50KB作业作业4-60KB 1.1.上下界寄存器上下界寄存器的地址检查机构。的地址检查机构。当作业被调度运行当作业被调度运行时，作业在内存中时，作业在内存中的上下界地址送上的上下界地址送上下界寄存器，每次下界寄存器，每次内存访问时，地址内存访问时，地址检查机构作越界检检查机构作越界检查。查。（2 2）地址访问保护技术的第一种方式）地址访问保护技术的第一种方式操作系统操作系统-50KB-50KB050K80K130K190K256K作业作业1-20KB作业作业2-40KB作业作业3-50KB作业作业4-60KB（1 1）上下界寄存器和地址检查机构。）上下界寄存器和地址检查机构。CPUCPU下界寄存器下界寄存器上界寄存器上界寄存器 TrueTrueTrueTrue地址地址A A程序性中断程序性中断操作系统操作系统-50KB-50KB050K80K130K190K256K作业作业1-20KB作业作业2-40KB作业作业3-50KB作业作业4-60KB静态重定位：静态重定位：指用户代码中使用的相对指用户代码中使用的相对地址地址,连接程序连接程序将其装配成绝对地址。将其装配成绝对地址。（即：在装入一个作业时，把该作业中（即：在装入一个作业时，把该作业中的程序和数据地址一次全部转换成绝对的程序和数据地址一次全部转换成绝对地址。地址。)（2 2）上下界寄存器和地址检查机构要）上下界寄存器和地址检查机构要求作业采用静态重定位技术。求作业采用静态重定位技术。100500:MOV R1,(500)123450700例：程序例：程序A的逻辑地址空间如图，将其装的逻辑地址空间如图，将其装入内存。内存起始地址为入内存。内存起始地址为5000号单元。用号单元。用静态重定位法画出其装入内存后的情况。静态重定位法画出其装入内存后的情况。MOV R1，(500)表示：将表示：将500号单号单元（地址）的数据元（地址）的数据12345送入送入1号寄存器。号寄存器。静态重定位装入内静态重定位装入内存后的情况：存后的情况：100500:MOV R1,(500)1234507005100550057005000逻辑地址逻辑地址:MOV R1,5500123450内存物理地址内存物理地址2 2.基址寄存器、长基址寄存器、长度寄存器的动态地度寄存器的动态地址转换机构。址转换机构。当作当作业被调度运行时，将业被调度运行时，将作业所占内存基址及作业所占内存基址及长度送基址、长度寄长度送基址、长度寄存器，每次内存访问存器，每次内存访问时，先看访问地址是时，先看访问地址是否小于长度，然后否小于长度，然后+基基址进行访存。见下图。址进行访存。见下图。操作系统操作系统-50KB-50KB050K80K130K190K256K作业作业1-20KB作业作业2-40KB作业作业3-50KB作业作业4-60KB（2 2）地址访问保护技术的第二种方式）地址访问保护技术的第二种方式CPUCPU基地址寄存器基地址寄存器长度寄存器长度寄存器+TrueTrue地址地址A Afalse false 程序性中断程序性中断OSOS作业作业1 1作业作业2 2作业作业3 3作业作业4 4例：例：CPU要访问上例作业要访问上例作业2的的A地址时的检查过程地址时的检查过程CPUCPU基地址基地址80K80K限长限长40K40K+TrueTrue地址地址A Afalse false 程序性中断程序性中断操作系统操作系统-50KB-50KB050K80K130K190K256K作业作业1-20KB作业作业2-40KB作业作业3-50KB作业作业4-60KB动态重定位：动态重定位：指用户代码中的相对指用户代码中的相对地址先原封不动地装入内存指定地地址先原封不动地装入内存指定地址，在执行期间才被动态地转换成址，在执行期间才被动态地转换成绝对地址绝对地址.（2 2）基址寄存器、长度寄存器和）基址寄存器、长度寄存器和动态地址转换机构要求作业采用动动态地址转换机构要求作业采用动态重定位技术态重定位技术100500:MOV R1,(500)123450700:MOV R1,(500)123450 内存绝对地址内存绝对地址5000510055005700+5000 基址寄存器基址寄存器相对地此相对地此700?长度寄存器长度寄存器700YN程序性中断程序性中断又例动态重定位的实现过程。指令又例动态重定位的实现过程。指令MOV MOV R1,(3000)R1,(3000)（即把相对地址为（即把相对地址为30003000的单元的单元中的中的123123取到取到1 1号寄存器）号寄存器）（3 3）多道固定划分法的作业调度技术）多道固定划分法的作业调度技术OS4kB6kB12kB.3kB 4kB1kB2kB.5kB6kB.7kB 10kB 11kB8kB（1 1）多多队队列列法法OS4kB6kB12kB.7kB 3kB 4kB5kB（2 2）单单队队列列法法（4 4）固定分区法存在碎片问题）固定分区法存在碎片问题 内部碎片：内存某存储区间大于其存放作内部碎片：内存某存储区间大于其存放作 业空间的部分。如：作业只有业空间的部分。如：作业只有3KB3KB时，而某内存固定分区有时，而某内存固定分区有4KB4KB。有有1KB1KB内内部碎片。部碎片。OS12KB固定固定4KB3KB内部碎片内部碎片外部碎片：内存某存储区间容不下要运行外部碎片：内存某存储区间容不下要运行 的作业时。的作业时。如：作业长度为：如：作业长度为：5KB5KB，8KB8KB，12KB12KB时，若时，若内存固定分区只剩下内存固定分区只剩下4KB4KB，则存在外部碎片。则存在外部碎片。OSOS4KB4KB6KB6KB12KB12KB外部碎片外部碎片 一、管理方法5.2.3 多道连续可变划分法特点：多道、连续、但不固定划分内存。多道、连续、但不固定划分内存。系统设置一个空闲块队列，初始状态系统设置一个空闲块队列，初始状态时队列中只有一个连续的空闲块。作业时队列中只有一个连续的空闲块。作业到达后，作业有多大就分配多大的空间。到达后，作业有多大就分配多大的空间。作业撤离时，将释放的空间加入空闲队作业撤离时，将释放的空间加入空闲队列。列。例题例题1 1：有以下：有以下4 4个作业，采用多道连续分个作业，采用多道连续分配技术配技术作业作业1-20KB作业作业2-40KB作业作业3-50KB作业作业4-60KB020K40K050K60K00操作系统操作系统-50KB-50KB空闲区空闲区050K70K110K160K256K作业作业1-20KB作业作业2-40KB作业作业3-50KB作业作业4-60KB220K例题例题2 2：有以下：有以下5 5个作业，假设任一时间段内，个作业，假设任一时间段内，内存中每一作业的运行时间相等，采用内存中每一作业的运行时间相等，采用FCFSFCFS作业调度方法。作业调度方法。作业到来次序作业到来次序 所需存储量所需存储量 运行时间运行时间J1 60KB 10sJ2 100KB 5sJ3 30KB 20sJ4 70KB 8sJ5 50KB 15sOS0 40K 256KJ1J2J3J4J5共190K二、可变分区中的数据结构二、可变分区中的数据结构 常用的数据结构有两种：空闲分区表和常用的数据结构有两种：空闲分区表和空闲分区链。空闲分区链。(1)(1)空闲分区表。为内存中每个尚未分配空闲分区表。为内存中每个尚未分配出去的分区设置一个表项，每个表项包含分出去的分区设置一个表项，每个表项包含分区序号、分区起始地址和分区的大小。区序号、分区起始地址和分区的大小。例：根据右图的内存使用情况填写空闲分区例：根据右图的内存使用情况填写空闲分区表。表。操作系统操作系统空闲区空闲区1(26KB)已使用已使用空闲区空闲区2(14KB)已使用已使用空闲区空闲区3(5KB)已使用已使用空闲区空闲区4(30KB)已使用已使用0k40k66k70k84k100k105k150k180k256k空闲分区表空闲分区表分区分区序号序号分区起分区起始地址始地址分区分区大小大小140k26kB270k14kB3100k5kB4150k30kB (2)(2)空闲分区链。在每个空闲分区中设置空闲分区链。在每个空闲分区中设置用于控制分区分配的信息及用于链接各个分用于控制分区分配的信息及用于链接各个分区的指针，将内存中的空闲分区链接成一个区的指针，将内存中的空闲分区链接成一个链表。不同的分配算法链表的组织方式不同。链表。不同的分配算法链表的组织方式不同。三、可变分区分配算法三、可变分区分配算法 (一一)首次适应首次适应(First Fit)(First Fit)算法算法。该算法要求空闲分区以地址递增的次序该算法要求空闲分区以地址递增的次序排序排序。如果采用的是链表结构，分配时则从链如果采用的是链表结构，分配时则从链表的开始顺序进行查找，直到找到一个能够表的开始顺序进行查找，直到找到一个能够满足进程大小要求的空闲分区为止。然后，满足进程大小要求的空闲分区为止。然后，按进程的大小，从分区中按进程的大小，从分区中“切出切出”一块内存一块内存空间分配给请求者，余下的空闲分区仍然留空间分配给请求者，余下的空闲分区仍然留在链表中在链表中。例例1 1：根据右图的内存使用：根据右图的内存使用情况画出首次适应算法的链情况画出首次适应算法的链表组织形式及分配一个表组织形式及分配一个10KB10KB的作业后的情况。的作业后的情况。操作系统操作系统空闲区空闲区1(26KB)已使用已使用空闲区空闲区2(14KB)已使用已使用空闲区空闲区3(5KB)已使用已使用空闲区空闲区4(30KB)已使用已使用0k40k66k70k84k100k105k150k180k256k1 1解：解：（1 1）分配一个分配一个10KB10KB的的作业前的链表组织形式。作业前的链表组织形式。40k26kB70k14kB100k5kB150k30kB70k100k150k（2 2）分配一个）分配一个10KB10KB的作业后的的作业后的链表组织形式。链表组织形式。50k16kB70k14kB100k5kB150k30kB70k100k150k操作系统操作系统空闲区空闲区1(26kB)已使用已使用空闲区空闲区2(14kB)已使用已使用空闲区空闲区3(5kB)已使用已使用空闲区空闲区4(30kB)已使用已使用0k40k66k70k84k100k105k150k180k256k表头指针表头指针表头指针表头指针三、可变分区分配算法三、可变分区分配算法 (二二)下次适应下次适应(Next Fit)(Next Fit)算法。算法。该算法从首次适应算法演变而来。为了避该算法从首次适应算法演变而来。为了避免低地址部分小空闲分区的不断增加，在给进免低地址部分小空闲分区的不断增加，在给进程分配内存空间时，不再每次从链首开始查找，程分配内存空间时，不再每次从链首开始查找，而是从上次找到的空闲分区的下一个空闲分区而是从上次找到的空闲分区的下一个空闲分区开始查找，直到找到一个能满足要求的空闲分开始查找，直到找到一个能满足要求的空闲分区，并从中区，并从中“切出切出”一块与请求的大小相等的一块与请求的大小相等的内存空间分配出去。内存空间分配出去。例例2 2：根据右图的内存使用：根据右图的内存使用情况画出下次适应算法的链情况画出下次适应算法的链表组织形式及分配一个表组织形式及分配一个10KB10KB的作业后的情况。假设上次的作业后的情况。假设上次找到的空闲分区是空闲区找到的空闲分区是空闲区1 1。操作系统操作系统空闲区空闲区1(16kB)已使用已使用空闲区空闲区2(14KB)已使用已使用空闲区空闲区3(5KB)已使用已使用空闲区空闲区4(30KB)已使用已使用0k40k66k70k84k100k105k150k180k256k50k已使用已使用2 2解：解：（1 1）分配一个分配一个10KB10KB的的作业前的链表组织形式。作业前的链表组织形式。（2 2）分配一个）分配一个10KB10KB的作业后的的作业后的链表组织形式。链表组织形式。50k16kB70k14KB100k5KB150k30kB70k100k150k50k16KB80k4KB100k5KB150k30KB80k100k150k操作系统操作系统空闲区空闲区1(16kB)已使用已使用空闲区空闲区2(14kB)已使用已使用空闲区空闲区3(5kB)已使用已使用空闲区空闲区4(30kB)已使用已使用0k40k66k70k84k100k105k150k180k256k50k已使用已使用表头指针表头指针表头指针表头指针三、可变分区分配算法三、可变分区分配算法 (三三)最佳适应最佳适应(Best Fit)算法。算法。最佳的含义是指每次为进程分配内存最佳的含义是指每次为进程分配内存时，总是把与进程大小最匹配的空闲分区时，总是把与进程大小最匹配的空闲分区分配出去。分配出去。该算法若采用的数据结构是空闲分区该算法若采用的数据结构是空闲分区链，首先要求将空闲分区，按分区大小递链，首先要求将空闲分区，按分区大小递增的顺序形成一空闲分区链。当进程要求增的顺序形成一空闲分区链。当进程要求分配内存时，第一次找到的满足要求的空分配内存时，第一次找到的满足要求的空闲区，必然是最优的。闲区，必然是最优的。例例3 3：根据右图的内存使用：根据右图的内存使用情况画出最佳适应算法的链情况画出最佳适应算法的链表组织形式及分配一个表组织形式及分配一个10KB10KB的作业后的情况。的作业后的情况。操作系统操作系统空闲区空闲区1(26KB)已使用已使用空闲区空闲区2(14KB)已使用已使用空闲区空闲区3(5KB)已使用已使用空闲区空闲区4(30KB)已使用已使用0k40k66k70k84k100k105k150k180k256k3 3解：解：（1 1）分配一个分配一个10KB10KB的的作业前的链表组织形式。作业前的链表组织形式。100k5KB70k14KB40k26KB150k30KB70k40k150k（2 2）分配一个）分配一个10KB10KB的作业后的的作业后的链表组织形式。链表组织形式。80k4KB100k5KB40k26KB150k30KB100k40k150k操作系统操作系统空闲区空闲区1(26KB)已使用已使用空闲区空闲区2(14KB)已使用已使用空闲区空闲区3(5KB)已使用已使用空闲区空闲区4(30KB)已使用已使用0k40k66k70k84k100k105k150k180k256k表头指针表头指针表头指针表头指针三、可变分区分配算法三、可变分区分配算法 (四四)最坏适应最坏适应(Worst Fit)算法。算法。该算法与最佳适应算法相反，要求空该算法与最佳适应算法相反，要求空闲分区按分区大小递减的顺序排序，每次闲分区按分区大小递减的顺序排序，每次分配时，从链首找到最大的空闲分区分配时，从链首找到最大的空闲分区“切切出出”一块进行分配。一块进行分配。该算法的特点是基本上不会留下小空该算法的特点是基本上不会留下小空闲分区，不易形成碎片。缺点是大的空闲闲分区，不易形成碎片。缺点是大的空闲分区被切割，当有较大的进程需要运行时，分区被切割，当有较大的进程需要运行时，系统往往不能满足要求。系统往往不能满足要求。例例4 4：根据右图的内存使用：根据右图的内存使用情况画出最坏适应算法的链情况画出最坏适应算法的链表组织形式及分配一个表组织形式及分配一个10KB10KB的作业后的情况。的作业后的情况。操作系统操作系统空闲区空闲区1(26KB)已使用已使用空闲区空闲区2(14KB)已使用已使用空闲区空闲区3(5KB)已使用已使用空闲区空闲区4(30KB)已使用已使用0k40k66k70k84k100k105k150k180k256k4 4解：解：（1 1）分配一个分配一个10KB10KB的的作业前的链表组织形式。作业前的链表组织形式。150k30KB40k26KB70k14KB100k5KB40k70k100k（2 2）分配一个）分配一个10KB10KB的作业后的的作业后的链表组织形式。链表组织形式。40k26KB160k20KB70k14KB100k5KB160k70k100k操作系统操作系统空闲区空闲区1(26KB)已使用已使用空闲区空闲区2(14KB)已使用已使用空闲区空闲区3(5KB)已使用已使用空闲区空闲区4(30KB)已使用已使用0k40k66k70k84k100k105k150k180k256k表头指针表头指针表头指针表头指针四、可变分区的作业分配过程四、可变分区的作业分配过程在找到合适的空闲块后，从其中将在找到合适的空闲块后，从其中将作业大小的空间分给作业，而剩余部分作业大小的空间分给作业，而剩余部分挂入空闲队列。挂入空闲队列。下面下面F F 是空闲块集合是空闲块集合;size(;size(k k)为块为块k k 的大小的大小;size(usize(u)为用户所需空间。分配为用户所需空间。分配共需共需5 5步：步：（1 1）如果所有属于）如果所有属于F F 的的k k，均有，均有size(size(k k)size(size(u u)（3 3）F F=F F k k;（4 4）如果如果size(size(k k)-size()-size(u u)基基本单位，则将本单位，则将k k分给用户。分给用户。（5 5）否则将）否则将k k分成分成k k1,1,k k2 2，其中，其中 size(size(k k1)=1)=size(size(u u)，F F=F F+k k222、空间回收过程：当作业结束时，收回作业所占空间，当作业结束时，收回作业所占空间，将此块链入空闲队列。将此块链入空闲队列。若空闲队列中原来有与此块的相邻块，若空闲队列中原来有与此块的相邻块，则把这些块合并成一个大连续块。则把这些块合并成一个大连续块。五、紧致技术通过移动作业位置可以将零散的空闲通过移动作业位置可以将零散的空闲块连接成大块。要求作业动态可浮动。如块连接成大块。要求作业动态可浮动。如下列：下列：操作系统操作系统空闲区空闲区作业作业2空闲区空闲区作业作业3空闲区空闲区作业作业1操作系统操作系统作业作业1操作系统操作系统作业作业2空闲区空闲区作业作业3作业作业1作业作业2空闲区空闲区作业作业3作业作业4（a）紧致前主存分紧致前主存分配情况，无法装入作配情况，无法装入作业业4（b）紧致后紧致后内存分配情况内存分配情况（c）紧致后紧致后内存空间可以内存空间可以装入作业装入作业4作业作业4例：例：一个应用紧致（紧缩）技术的例子。一个应用紧致（紧缩）技术的例子。连续空间分配法小结：连续空间分配法小结：作业作业道数道数内内部部碎碎片片外外部部碎碎片片硬件支持硬件支持可用空可用空间管理间管理解决解决碎片碎片方法方法解决空解决空间不足间不足提高作提高作业道数业道数单单道连续道连续分配分配1有有无无界地址寄存器界地址寄存器越界检查机构越界检查机构/覆盖覆盖交换交换多多道固定道固定连续分配连续分配=N（用用户空户空间划间划成成N块）块）有有有有1.上下界寄存上下界寄存器、越界检查器、越界检查机构机构2、基地址寄存、基地址寄存器、长度寄存器、长度寄存器、动态地址器、动态地址转换机构转换机构/多多道可变道可变连续分配连续分配不定不定无无有有1、数组、数组2、链表、链表紧致紧致