1、第三章第三章 存储管理存储管理 (Memory Management)存储器是计算机系统的重要组成部分，所以存储器的管存储器是计算机系统的重要组成部分，所以存储器的管理是操作系统最主要的功能之一。理是操作系统最主要的功能之一。当程序的指令和数据当当程序的指令和数据当以文件的形式存放在磁盘上时，是不能被以文件的形式存放在磁盘上时，是不能被CPU访问的，只访问的，只有当被调入内存（有当被调入内存（RAM）里才能被里才能被CPU直接访问，程序才直接访问，程序才能够被执行。虽然目前的能够被执行。虽然目前的RAM芯片的集成度在不断地提高，芯片的集成度在不断地提高，从原来的几百到现在的几百兆甚至上千兆，价
2、格也在不从原来的几百到现在的几百兆甚至上千兆，价格也在不断地降低，但是软件系统需要的内存容量也在不断地增加，断地降低，但是软件系统需要的内存容量也在不断地增加，所以内存的容量仍然是计算机硬件中最关键的、且又是最所以内存的容量仍然是计算机硬件中最关键的、且又是最紧张的紧张的“瓶颈瓶颈”资源。如何对存储器进行有效的管理，不资源。如何对存储器进行有效的管理，不仅直接影响到它的利用率，而且还对系统的性能有重大影仅直接影响到它的利用率，而且还对系统的性能有重大影响。响。存储管理的主要对象是存储管理的主要对象是内存。内存。教学要求教学要求z熟悉熟悉存储管理目的和存储管理目的和功能，功能，掌握掌握地址重定位
3、地址重定位的概念。的概念。z熟悉熟悉单一连续分配、单一连续分配、固定分区分配、固定分区分配、动态分区分配动态分区分配实现实现原理；原理；掌握掌握可变分区分配的可变分区分配的数据结构和数据结构和分配分配回回收算法，收算法，熟悉熟悉可变分区零头和拼接技术可变分区零头和拼接技术。z熟练熟练掌握掌握分页存储管理分页存储管理原理，原理，熟练熟练掌握掌握分页存储管分页存储管理基本的地址变换机构和具有快表的地址变换机构理基本的地址变换机构和具有快表的地址变换机构。z掌握掌握分段存储管理分段存储管理原理和原理和分段地址变换机构，分段地址变换机构，掌握掌握分页和分段比较，熟分页和分段比较，熟悉悉分页和分段的共享
4、，分页和分段的共享，掌握掌握段段页页式式存储管理存储管理原理和原理和地址变换机构。地址变换机构。教学要求教学要求-1-1z掌握掌握虚拟存储器的虚拟存储器的理论基础和定义，理论基础和定义，熟悉虚拟存储熟悉虚拟存储器器实现方式和实现方式和特征。特征。z掌握请求分页的页表机制、缺页中断机构和地址变掌握请求分页的页表机制、缺页中断机构和地址变换机构，换机构，熟悉熟悉页面的分配和置换策略、页面的分配页面的分配和置换策略、页面的分配的算法。的算法。z熟练掌握最佳置换算法、先进先出（熟练掌握最佳置换算法、先进先出（FIFOFIFO）置换算置换算法、最近最久未使用置换算法法、最近最久未使用置换算法LRULRU
5、，熟悉熟悉ClockClock置换置换算法和算法和页面缓冲算法；熟悉页面缓冲算法；熟悉有效访问时间计算，了有效访问时间计算，了解工作集概念。解工作集概念。z掌握请求分段的段表机制、缺段中断机构和地址变掌握请求分段的段表机制、缺段中断机构和地址变换机构，换机构，熟悉熟悉分段的共享和保护。分段的共享和保护。存储管理存储管理目录目录z31 存储管理概述z311存储层次结构z312存储管理的功能z313 地址重定位z32 存储器的连续分配z321单一连续分配z322固定分区分配z323可变（动态）分区分配z33存储器的离散分配z331纯分页存储管理z332 分段存储管理z333 段页式存储管理存储管理
6、存储管理目录目录-1z34虚拟存储器管理技术z341虚拟存储器的基本概念z342请求分页存储管理z343请求分段存储管理z35 Windows2000内存的管理z351Intel x86/Pentium系列CPU对内存管理的硬件支持机制z352 Windows2000地址空间的划分z353 Windows2000用户空间内存分配和使用z354页面调度策略z355物理内存管理z35.6 Windows 2000高速缓冲管理存储管理存储管理目录目录-2z36 实验与习题z361实验一：在Windows2000下评价内存和缓存使用z362 实验2：Windows 2000 内存管理API函数的使用z
7、363 选择题z364 问答题31 存储管理概述存储管理概述3 31 11 1存储层次结构存储层次结构 存储器是处理器处理的信息的来源与归宿，占据着重要地位。存储器是处理器处理的信息的来源与归宿，占据着重要地位。但任何一种存储设备都无法在速度与容量两个方面同时满足但任何一种存储设备都无法在速度与容量两个方面同时满足用户的需求。为解决速度和容量之间的矛盾，冯用户的需求。为解决速度和容量之间的矛盾，冯诺依曼计诺依曼计算机系统中，采用了三级或更多级的存储器来组成存储层次算机系统中，采用了三级或更多级的存储器来组成存储层次结构，高一级为结构，高一级为CPUCPU寄存器和寄存器和高速缓存高速缓存器，中间
8、是主存器，中间是主存(可执可执行的存储器行的存储器)，最低一级为辅存。通过采用特殊的存储技术，最低一级为辅存。通过采用特殊的存储技术，主存与辅存两级可以进一步优化成多级。在存储层次结构中，主存与辅存两级可以进一步优化成多级。在存储层次结构中，高层的存储器往往是速度很快、但成本高使容量有限，而接高层的存储器往往是速度很快、但成本高使容量有限，而接近底部的存储器容量很大、成本低，相对访问速度则慢。各近底部的存储器容量很大、成本低，相对访问速度则慢。各种存储设备组成存储层次结构，如图种存储设备组成存储层次结构，如图5 51 1所示。所示。存储层次结构图存储层次结构图高速缓存器高速缓存器主主存存辅辅存
9、存10MB12时钟时钟1GB14时钟时钟绝对地址绝对地址2150(=2000+150)y内容修改：内容内容修改：内容100变成变成2100(=100+2000)。动态重定位动态重定位z 动态重定位动态重定位是指在程序执行过程中进行地址重定是指在程序执行过程中进行地址重定位，即在每次访问内存单元前才进行地址变换。动位，即在每次访问内存单元前才进行地址变换。动态重定位可使装配模块不加任何修改就装入内存，态重定位可使装配模块不加任何修改就装入内存，但是它需要硬件但是它需要硬件重定位寄存器的支持。下图给出重定位寄存器的支持。下图给出了了动态重定位的示意图。动态重定位的示意图。程序的目标模块在装入内存时
10、，与地址有关的指令程序的目标模块在装入内存时，与地址有关的指令都无须进行修改，如在图都无须进行修改，如在图3-4中中LOADLOAD 1，2500这条指这条指令中仍保持相对地址令中仍保持相对地址25002500。当该指令被操作系统取。当该指令被操作系统取到中央处理器到中央处理器指令寄存器指令寄存器上执行时，操作系统首先上执行时，操作系统首先把该模块装入的实际起始地址减去目标模块的相对把该模块装入的实际起始地址减去目标模块的相对基地址（图基地址（图3-4中该模块的基地址为中该模块的基地址为0），然后将其差），然后将其差值值10000装入重定位寄存器。装入重定位寄存器。动态重定位的示意图动态重定位
11、的示意图LOAD 1，25003650：10025002600程序的地址空间程序的地址空间LOAD 1，2500365100001010012500物 理 地址内存的地址空间重定位寄存重定位寄存器重定位寄存器中央处理器中央处理器CPUCPU指令寄存器指令寄存器LOAD 1,2500LOAD 1,25002500(2500(逻辑地址逻辑地址)MMU(存储管理部件存储管理部件)CPU芯片+10000动态重定位动态重定位-1当当CPU执行该指令时，地址变换硬件逻辑自动将指令执行该指令时，地址变换硬件逻辑自动将指令中的逻辑地址中的逻辑地址2500与重定位寄存器中的值相加，再与重定位寄存器中的值相加，再
12、根据和值作为内存的绝对地址去访问该单元的数据，根据和值作为内存的绝对地址去访问该单元的数据，读入的数据送到读入的数据送到寄存器寄存器1 1。完成地址变换硬件是属于。完成地址变换硬件是属于存储管理部件存储管理部件 MMUMMU，目前它已集成到目前它已集成到中央处理器中央处理器CPUCPU中。中。由此可见，动态重定位是在指令执行过程中动态由此可见，动态重定位是在指令执行过程中动态进行，它由进行，它由硬件完成，硬件完成，这样可以带来两个好处：这样可以带来两个好处：目标程序装入内存时无需任何修改，所以装入之后目标程序装入内存时无需任何修改，所以装入之后再移动也不会影响其正确运行，这便于存储器用紧再移动
13、也不会影响其正确运行，这便于存储器用紧缩来解决存储器的碎片问题。一个程序由若干个缩来解决存储器的碎片问题。一个程序由若干个相对独立的目标模块组成时，每个目标模块各装入相对独立的目标模块组成时，每个目标模块各装入一个存储区域，这些存储区域可以不相领接，只要一个存储区域，这些存储区域可以不相领接，只要各个模块有自己对应的重定位寄存器就可以了。各个模块有自己对应的重定位寄存器就可以了。3.3.链接链接 静态链接静态链接(static-linking)static-linking)是在生成可执行文件时进是在生成可执行文件时进行的。在目标模块中记录符号地址行的。在目标模块中记录符号地址(symbolic
14、 address)symbolic address)，而在可执行文件中改写为指令直接使用的数字地址。而在可执行文件中改写为指令直接使用的数字地址。Module AModule Acall function10L-1Module BModule B0M-1function1().function1FModule AModule Acall L+F0L-1Module BModule BLL+M-1function1().function1L+F 有一个程序P（如图所示），它既可以被其它程序调用（通过用符号定义的入口点如P,e,d），也可以调用别的程序模块。前一种情况称为内部定义符号，后者称为外部
15、调用符号。一个源程序经编译或汇编后生成的可重定位目标模块必须明显地给出这些内部符号和外部符号，以供连接装入程序使用。每个可重定位目标段相关联的除重定位表（又称重定位词典）或指示字外，还应有一张内部定义符号表和外部调用符号表。链接链接例例-1-1链接链接例例-2 CALL SUB1ADD TIME内部定义符号：P,e,d。外部调用符号：SUB1,TIME。Ped内部定义符号表符号名地址PedSUB1TIMEPeCALL*ADD*d.外部调用符号表重定位词典.代码和数据区链接链接例例-3-3动态链接动态链接动态链接(dynamic-linking)在装入或运行时进行链接。通常被链接的共享代码称为动
16、态链接库(DLL,Dynamic-Link Library)或共享库(shared library)。优点：共享：多个进程可以共用一个DLL，节省内存，减少文件交换。y部分装入：一个进程可以将多种操作分散在不同的DLL中实现，而只将当前操作相应的DLL装入内存。y便于局部代码修改：即便于代码升级和代码重用；只要函数的接口参数（输入和输出）不变，则修改函数及其DLL，无需对可执行文件重新编译或链接。y便于运行环境适应：调用不同的DLL，就可以适应多种使用环境和提供不同功能。如：不同的显示卡只需厂商为其提供特定的DLL，而OS和应用程序不必修改。缺点：链接开销：增加了程序执行时的链接开销；y管理开
17、销：程序由多个文件组成，增加管理复杂度。32 存储器的连续分配存储器的连续分配 321单一连续分配单一连续分配 这是一种最简单的存储管理方式，但只能用于单用户、这是一种最简单的存储管理方式，但只能用于单用户、单任务的操作系统，如在单任务的操作系统，如在8位和位和16位微机上位微机上CP/M和和MS-DOS操作系统。它将内存分为两个区：操作系统。它将内存分为两个区：系统区：仅供操作系统使用，通常设置在内存的低段；系统区：仅供操作系统使用，通常设置在内存的低段；用户区：指除系统区以外的全部内存空间，提供给用用户区：指除系统区以外的全部内存空间，提供给用户使用。户使用。这种存储分配方式由于用在单用户
18、、单任务的操作系统这种存储分配方式由于用在单用户、单任务的操作系统中。中。单一连续分配单一连续分配-1系统区系统区操作系统操作系统用户区用户区用户程序用户程序 0下限下限上限上限基址基址长度长度用户程序用户程序位于位于RAM中的中的操作系统操作系统0 xFFF.0位于位于RAM中的中的操作系统操作系统用户程序用户程序0ROM中的中的设备驱动程序设备驱动程序用户程序用户程序位于位于RAM中的中的操作系统操作系统0单一连续区存储管理单一连续区存储管理3 32 22 2固定分区固定分区(Fixed Partitioning)分配分配 分区存储管理是能够满足多道程序运行的最简单的存储器分区存储管理是能
19、够满足多道程序运行的最简单的存储器管理方案，其基本思想是将内存划分成若干个连续的区域，管理方案，其基本思想是将内存划分成若干个连续的区域，称为分区。每个分区只能储存一个程序，而且程序也只能在称为分区。每个分区只能储存一个程序，而且程序也只能在它所驻留的分区中运行。分区存储管理根据分区个数及分区它所驻留的分区中运行。分区存储管理根据分区个数及分区大小的可变性分为固定式分区和可变式分区两种。大小的可变性分为固定式分区和可变式分区两种。固定分区是在作业装入之前，内存就被划分成若干个分区。固定分区是在作业装入之前，内存就被划分成若干个分区。划分工作可以由系统管理员完成，也可以由操作系统实现。划分工作可
20、以由系统管理员完成，也可以由操作系统实现。然而一旦划分完成，在系统运行期间不再重新划分，即分区然而一旦划分完成，在系统运行期间不再重新划分，即分区的个数不可变，分区的大小不可变，所以，固定式分区又称的个数不可变，分区的大小不可变，所以，固定式分区又称为静态分区。为静态分区。这种分区方式一般将内存的用户区域划分成大小不等的分这种分区方式一般将内存的用户区域划分成大小不等的分区，以适应不同大小的作业的需要。系统有一张分区说明表，区，以适应不同大小的作业的需要。系统有一张分区说明表，每个表目说明一个分区的大小、起始地址和是否已分配的使每个表目说明一个分区的大小、起始地址和是否已分配的使用标志。分区说
21、明表和用标志。分区说明表和内存分配图内存分配图如下所示。如下所示。固定分区分配固定分区分配-1-1区号区号 大小大小 起址起址 标志标志 1 16KB 20K 已分配已分配 2 32KB 36K 已分配已分配 3 64KB 68K 已分配已分配 4 124KB 132K 未分配未分配 (a)分区说明表分区说明表 固定式分区实现技术简单固定式分区实现技术简单，但是内存的利用率不高，但是内存的利用率不高，适用于作业的大小和多少事适用于作业的大小和多少事先都比较清楚的系统中。它先都比较清楚的系统中。它用于用于6060年代的年代的IBM-360IBM-360的的MFTMFT操作系统中。操作系统中。0k
22、：20k：36k：68k：132k：256k：内存分配图内存分配图 操作系统作业A（16k）作业B（26k）作业C（56k）第第1分区（分区（16kb）第第2分区（分区（32kb）（已分配）（已分配）第第3分区（分区（64kb）（已分配）已分配）4分区（分区（124kb）（未分配）未分配）固定分区分配固定分区分配-2-2z由于每个分区的大小是固定的，所以每个提出运行的作业必须说明所需的最大内存容量。在调度作业时，存储管理程序根据作业所需的内存容量，在分区说明表中找出一个足够大的空闲分区分配给它，然后用重定位装入程序将此作业装入。如果找不到，则通知作业调度模块，选择另外一个作业。图3-6（b）说
23、明了某一时刻，作业A、B、C分别被分配到1，2，3三个分区中，第四个分区尚未分配，操作系统则永久占据内存低地址区20KB的空间。当一个作业结束时，系统又调用存储管理程序查到分区说明表，把所占分区的使用标志修改为未分配状态即可。固定分区分配固定分区分配-3-3z采用这种技术，虽然可以使多个作业共驻内存，但是一个作业的大小不可能正好等于某个分区的大小，所以每个被分配的分区总有一部分被浪费，我们把这部分被浪费的存储区称为内零头或内碎片。有时这种分配方式浪费相当严重，如图3-6（b）中第3分区未分配的部分还有8KB，加上第4分区的124KB共计132KB，而且这132KB的内存空间在物理上是一个连续的
24、区域，这时如果有一个大小为130KB的作业申请内存，却被拒绝，因为分区的大小是预先划分好的，分区说明表中指出只有第4分区未分配（大小为124K），且不能改变分区的大小。Multiprogramming with Fixed Partitionsz Fixed memory partitionsyseparate input queues for each partitionysingle input queue323可变（动态）可变（动态）(Dynamic Partitioning)分区分配分区分配 1.1.可变分区概述可变分区概述可变分区是指在作业装入内存时，从可用的内存中划出一块连可变分区
25、是指在作业装入内存时，从可用的内存中划出一块连续的区域分配给它，且分区大小正好等于该作业的大小。可续的区域分配给它，且分区大小正好等于该作业的大小。可变分区中分区的大小和分区的个数都是可变的，而且是根据变分区中分区的大小和分区的个数都是可变的，而且是根据作业的大小和多少动态地划分，因此又称为动态分区。这种作业的大小和多少动态地划分，因此又称为动态分区。这种存储管理技术是固定式分区的改进，既可以获得较大的灵活存储管理技术是固定式分区的改进，既可以获得较大的灵活性，又能提高内存的利用率。性，又能提高内存的利用率。系统初始化后，内存被划分成两块，一块用于常驻的操作系统，系统初始化后，内存被划分成两块
26、，一块用于常驻的操作系统，另一块则是完整的空闲区（用户区）。对于调入的若干个作另一块则是完整的空闲区（用户区）。对于调入的若干个作业，划分几个大小不等的分区给它们，随着作业的调入和撤业，划分几个大小不等的分区给它们，随着作业的调入和撤除，相应的分区被划分和释放，原来整块的存储区形成空闲除，相应的分区被划分和释放，原来整块的存储区形成空闲区和已分配区相间的局面。图区和已分配区相间的局面。图3-7（c）给出了可变式分区的给出了可变式分区的示例，示例，512512KBKB内存中除内存中除20KB操作系统外，装入作业操作系统外，装入作业2、3、4、6四个，有空闲区四个，有空闲区1、2、3三个。三个。可
27、变式分区数据结构图表可变式分区数据结构图表 序号序号P P大小大小起址起址状态状态 1 13232k k20k20k空闲空闲 2 25656k k260k260k空闲空闲 3 116 3 116k k396k396k空闲空闲 4 4空表目空表目 5 5空表目空表目 （a）空闲分区表前向指针前向指针 N+2 00后向指针后向指针 N+2 00N个字可用 （b）空闲链结构空闲区（空闲区（56k）作业作业6（80k）空闲区（空闲区（116k）空闲区（空闲区（32k）作业作业2（64k）作业作业3（48k）作业作业4（96k）操作系统操作系统(20K)0 02020K K52K52K116K116K1
28、64K164K260K260K316K316K396K396K512K512K返回可变分区概述可变分区概述-1-1z可变式分区的分配和释放的基本思想是：在分配时，首先找到一个足够大的空闲分区，即这个空闲区的大小比作业要求的要大，系统则将这个空闲分区分成两部分：一部分成为已分配的分区，剩余的部分仍作为空闲区。在回收撤除作业所占领的分区时，要检查回收的分区是否与前后空闲的分区相领接，若是，则加以合并，使之成为一个连续的大空间。Example Dynamic PartitioningOperating SystemProcess 1320 KProcess 2Process 3224 K288 K6
29、4 KOperating SystemProcess 1320 KProcess 3224 K288 K64 KOperating SystemProcess 1320 KProcess 3288 K64 KProcess 4128 K96 KExample Dynamic Partitioning-1Operating System320 KProcess 3288 K64 KProcess 4128 K96 KOperating SystemProcess 3288 K64 KProcess 4128 K96 KProcess 2224 k96 K动态动态/可变式分区分配可变式分区分配-1
30、-12.2.可变式分区的可变式分区的数据结构数据结构 空闲区表空闲区表形式形式 空闲分区表为每个尚未分配的分区设置一个表项，包括分空闲分区表为每个尚未分配的分区设置一个表项，包括分区的序号、大小、始址和状态。区的序号、大小、始址和状态。空闲区链空闲区链形式形式 为了实现对空闲分区的分配和链接，在每个分区的起始部为了实现对空闲分区的分配和链接，在每个分区的起始部分，设置一些用于控制分区分配的信息（如分区的大小和分，设置一些用于控制分区分配的信息（如分区的大小和状态位），以及用于链接其它分区的前向指针；在分区尾状态位），以及用于链接其它分区的前向指针；在分区尾部，则设置了一个后向指针，为了检索方便
31、也设置了控制部，则设置了一个后向指针，为了检索方便也设置了控制分区分配的信息。然后，通过前、后向指针将所有的分区分区分配的信息。然后，通过前、后向指针将所有的分区链接成一个双向链表。链接成一个双向链表。3.3.可变分区分配算法可变分区分配算法(Partitioning Placement Algorithm)(1)(1)最佳适应算法最佳适应算法BFBF（Best FitBest Fit）：）：它从全部空闲区中找出能它从全部空闲区中找出能满足作业要求的、且大小最小的空闲分区，这种方法能使满足作业要求的、且大小最小的空闲分区，这种方法能使碎片尽量小。为适应这种算法，空闲分区表（空闲区链）碎片尽量小
32、。为适应这种算法，空闲分区表（空闲区链）中的空闲分区要中的空闲分区要按大小按大小从小到大进行排序，从小到大进行排序，自表头开始查自表头开始查找到第一个满足要求的自由分区分配。找到第一个满足要求的自由分区分配。该算法该算法保留大的空保留大的空闲区，但造成许多小的空闲区。闲区，但造成许多小的空闲区。(2)(2)首次适应算法首次适应算法FFFF（First FitFirst Fit）：）：从从空闲分区表空闲分区表的第一个的第一个表目起查找该表表目起查找该表，把最先能够满足要求的空闲区分配给作，把最先能够满足要求的空闲区分配给作业，这种方法目的在于减少查找时间。为适应这种算法，业，这种方法目的在于减少
33、查找时间。为适应这种算法，空闲分区表（空闲区链）中的空闲分区要按地址由低到高空闲分区表（空闲区链）中的空闲分区要按地址由低到高进行排序。进行排序。该算法该算法优先使用低址部分空闲区，在低址空间优先使用低址部分空闲区，在低址空间造成许多小的空闲区，在高地址空间保留大的空闲区。造成许多小的空闲区，在高地址空间保留大的空闲区。可变分区分配算法可变分区分配算法-1(3)循环首次适应算法循环首次适应算法NF(Next Fit)：该算法是首次适应算法该算法是首次适应算法的变种，它把的变种，它把空闲分区表（空闲区链）中的空闲分区按地空闲分区表（空闲区链）中的空闲分区按地址递增构成一个址递增构成一个循环链。在
34、分配内存空间时，不再每次从循环链。在分配内存空间时，不再每次从表头（链首）开始查找，而是从上次找到的空闲区的下一表头（链首）开始查找，而是从上次找到的空闲区的下一个空闲区开始查找，直到找到第一个能满足要求的的空闲个空闲区开始查找，直到找到第一个能满足要求的的空闲区为止，并从中划出一块与请求大小相等的内存空间分配区为止，并从中划出一块与请求大小相等的内存空间分配给作业。该算法能使内存中的空闲区分布得比较均匀。给作业。该算法能使内存中的空闲区分布得比较均匀。(4)最坏适应法：最坏适应法：从所有未分配的分区中挑选最大的且大于和从所有未分配的分区中挑选最大的且大于和等于作业大小的分区分给要求的作业；等
35、于作业大小的分区分给要求的作业；空闲空闲分区按大小由分区按大小由大到小排序。大到小排序。该算法使该算法使小的空闲区减少，但造成大的空闲小的空闲区减少，但造成大的空闲区不够大。区不够大。Lastallocatedblock(14K)BeforeAfter8K8K12K12K22K18K6K6K8K8K14K14K6K2K36K20KNext FitFree blockAllocated blockBest FitFirst Fit例：分配一个例：分配一个16KB分区分区采用采用空闲分区表空闲分区表结构和结构和首次适应首次适应分配分配算法算法z 空闲分区表空闲分区表数据结构数据结构空闲分区表中的空
36、闲分区要空闲分区表中的空闲分区要按按地址从低地址从低到高连续排序，最后一个空闲分区中到高连续排序，最后一个空闲分区中 m_sizem_size为为0 0表示以上表目空白。空闲分区表示以上表目空白。空闲分区表起始地址为表起始地址为coremapcoremap分配和释放的基本思想是：在分配时，分配和释放的基本思想是：在分配时，首先找到一个足够大的空闲分区，即这首先找到一个足够大的空闲分区，即这个空闲区的大小比作业要求的要大，系个空闲区的大小比作业要求的要大，系统则将这个空闲分区分成两部分：一部统则将这个空闲分区分成两部分：一部分成为已分配的分区，剩余的部分仍作分成为已分配的分区，剩余的部分仍作为空
37、闲区。在回收撤除作业所占领的分为空闲区。在回收撤除作业所占领的分区时，要检查回收的分区是否与前后空区时，要检查回收的分区是否与前后空闲的分区相领接，若是，则加以合并，闲的分区相领接，若是，则加以合并，使之成为一个连续的大空间。使之成为一个连续的大空间。m_addrm_size.m_addrm_size=0.m_addrm_sizem_addrm_sizem_addrm_sizem_addrm_sizeCoremapCoremap采用首次适应算法的可变分区的分配流程图采用首次适应算法的可变分区的分配流程图 申请分配一个申请分配一个u.size大小的分区大小的分区从头开始查表从头开始查表是否检索完
38、毕？是否检索完毕？本次无法分配本次无法分配m.sizeu.size m.size-u.sizesize？从 该 分 区 中 划 出从 该 分 区 中 划 出u.size大小的分区大小的分区继续检索下一个表项继续检索下一个表项将该表目以上的所将该表目以上的所有表目下移一格有表目下移一格将该分区分配给申请者将该分区分配给申请者修改有关的数据结构修改有关的数据结构 返返 回回YNN4.4.可变分区回收算法可变分区回收算法 当一个作业运行完毕释放内存时，系统根据释放区的首地当一个作业运行完毕释放内存时，系统根据释放区的首地址，从空闲区说明表中找到相应的插入点，此时可能出址，从空闲区说明表中找到相应的插
39、入点，此时可能出现下列四种情况（如图现下列四种情况（如图3-93-9所示，其中所示，其中F1F1，F2F2表示回收区表示回收区的前、后空闲区）的前、后空闲区）：(1)(1)当回收区既不与当回收区既不与F1F1领接，又不与领接，又不与F2F2领接时（如图领接时（如图3-93-9（a a），应为回收区单独建立一项新表目，填写回收区应为回收区单独建立一项新表目，填写回收区的起址和大小，并根据其起址，插入到空闲区说明表的的起址和大小，并根据其起址，插入到空闲区说明表的适当位置。适当位置。(2)(2)当回收区只与插入点的前一个分区当回收区只与插入点的前一个分区F1F1相领接时（如图相领接时（如图3-3-
40、9 9（b b），），应将回收区与插入点的前一个分区合并，不应将回收区与插入点的前一个分区合并，不再为回收区分配新的表目，而只需修改再为回收区分配新的表目，而只需修改F1F1分区表目的大分区表目的大小即可。小即可。可变分区回收算法可变分区回收算法-1(3)(3)当回收区只与插入点的后一个分区当回收区只与插入点的后一个分区F2F2相领接时（如图相领接时（如图3-93-9（c c），），将把两个空闲区合并，修改将把两个空闲区合并，修改F2F2分区的表目，把回分区的表目，把回收区的起址作为新空闲区的起址，大小为两个分区之和。收区的起址作为新空闲区的起址，大小为两个分区之和。(4)(4)当回收区与插入
41、点的前、后两个分区（当回收区与插入点的前、后两个分区（F1F1和和F2F2）都相领都相领接时（如图接时（如图3-93-9（d d），），合并三个分区，用合并三个分区，用F1F1表目的起址表目的起址作为新空闲区的起址，修改其大小为三块分区之和，最后作为新空闲区的起址，修改其大小为三块分区之和，最后取消取消F2F2的表目。的表目。图图3-73-7（c c）内存分配图中作业内存分配图中作业3 3、2 2、4 4、6 6分别回收时相当于分别回收时相当于图图3-93-9（a a）、（）、（b b）、（）、（c c）、（）、（d d）内存回收时的情况。内存回收时的情况。可变分区回收算法可变分区回收算法-2
42、z 作业作业Y回收区 作业作业X F1F1 F1 回收区 作业作业Y F2F2 F1 回收区 F2 作业作业Y 回收区 F2 作业作业X 作业作业Y A A B B C C D D可变分区回收算法可变分区回收算法-3z对于前图所示的可变式分区内存分配图，下列四种情况分别如下图所示：作业作业4回收区 作业作业2空闲区空闲区1 1 空闲区空闲区1 1 回收区 作业作业3 空闲区空闲区2 2 回收区空闲区空闲区3 3 回收区 空闲区空闲区2 2 作业作业3 作业作业6 A A B B C C D D作业作业3回收回收 作业作业2回收回收 作业作业4回收回收 作业作业6回收回收可变分区回收算法可变分区
43、回收算法-4作业作业3回收前后回收前后序号序号P P大小大小起址起址状态状态 1 13232k k20k20k空闲空闲 2 25656k k260k260k空闲空闲 3 116 3 116k k396k396k空闲空闲 4 4空表目空表目 5 5空表目空表目 （a）空闲分区表序号序号P P 大小大小 起址起址 状态状态 1 1 32 32k 20k k 20k 空闲空闲 2 2 4848k 116k k 116k 空闲空闲 3 3 56 56k 260k k 260k 空闲空闲 4 4 116 116k 396k k 396k 空闲空闲 5 5 空表目空表目 空闲分区表空闲区空闲区2（56k）
44、作业作业6（80k）空闲区空闲区3（116k）空闲区空闲区1（32k）作业作业2（64k）作业作业3（48k）回收区回收区作业作业4（96k）操作系统操作系统(20K)0 02020K K52K52K116K116K164K164K260K260K316K316K396K396K512K512K空闲区空闲区3（56k）作业作业6（80k）空闲区空闲区4（116k）空闲区空闲区1（32k）作业作业2（64k）空闲区空闲区2（48k）作业作业4（96k）操作系统操作系统(20K)0 02020K K52K52K116K116K164K164K260K260K316K316K396K396K512K
45、512K 回收前回收前 回收后回收后空闲区空闲区2（56k）作业作业6（80k）空闲区空闲区3（116k）作业作业3（48k）作业作业4（96k）操作系统操作系统(20K)0 02020K K116K116K164K164K260K260K316K316K396K396K512K512K空闲区空闲区2（56k）作业作业6（80k）空闲区空闲区3（116k）空闲区空闲区1（32k）作业作业2（64k）回收区回收区作业作业3（48k）作业作业4（96k）操作系统操作系统(20K)0 02020K K52K52K116K116K164K164K260K260K316K316K396K396K512K
46、512K 回收前回收前 回收后回收后可变分区回收算法可变分区回收算法-5作业作业2回收前后回收前后序号序号P P大小大小起址起址状态状态 1 13232k k20k20k空闲空闲 2 25656k k260k260k空闲空闲 3 116 3 116k k396k396k空闲空闲 4 4空表目空表目 5 5空表目空表目 （a）空闲分区表序号序号P P 大小大小 起址起址 状态状态 1 1 96 96k k 20k 20k 空闲空闲 2 2 56 56k 260k k 260k 空闲空闲 3 3 116 116k 396k k 396k 空闲空闲 4 4 空表目空表目 5 5 空表目空表目 空闲分
47、区表空闲区空闲区1（96k）可变分区回收算法可变分区回收算法-6作业作业4回收前后回收前后序号序号P P大小大小起址起址状态状态 1 13232k k20k20k空闲空闲 2 25656k k260k260k空闲空闲 3 116 3 116k k396k396k空闲空闲 4 4空表目空表目 5 5空表目空表目 （a）空闲分区表序号序号P P 大小大小 起址起址 状态状态 1 1 32 32k 20k k 20k 空闲空闲 2 2 152152k 164kk 164k 空闲空闲 3 3 116 116k 396k k 396k 空闲空闲 4 4 空表目空表目 5 5 空表目空表目 空闲分区表空闲
48、区空闲区2（56k）作业作业6（80k）空闲区空闲区3（116k）空闲区空闲区1（32k）作业作业2（64k）作业作业3（48k）作业作业4（96k）回收区回收区操作系统操作系统(20K)0 02020K K52K52K116K116K164K164K260K260K316K316K396K396K512K512K空闲区空闲区2（152k）作业作业6（80k）空闲区空闲区3（116k）空闲区空闲区1（32k）作业作业2（64k）作业作业3（48k）操作系统操作系统(20K)0 02020K K52K52K116K116K164K164K316K316K396K396K512K512K 回收前回
49、收前 回收后回收后可变分区回收算法可变分区回收算法-7作业作业6回收前后回收前后序号序号P P大小大小起址起址状态状态 1 13232k k20k20k空闲空闲 2 25656k k260k260k空闲空闲 3 116 3 116k k396k396k空闲空闲 4 4空表目空表目 5 5空表目空表目 （a）空闲分区表序号序号P P 大小大小 起址起址 状态状态 1 1 32 32k 20k k 20k 空闲空闲 2 2 252252k k 260k 260k 空闲空闲 3 3 空表目空表目 4 4 空表目空表目 5 5 空表目空表目 空闲分区表作业作业6（80k）空闲区空闲区4（116k）空闲
50、区空闲区2（56k）作业作业6-80k回收区回收区空闲区空闲区3（116k）空闲区空闲区1（32k）作业作业2（64k）作业作业3（48k）作业作业4（96k）操作系统操作系统(20K)0 02020K K52K52K116K116K164K164K260K260K316K316K396K396K512K512K空闲区空闲区2（252k）空闲区空闲区1（32k）作业作业2（64k）作业作业3（48k）作业作业4（96k）操作系统操作系统(20K)0 02020K K52K52K116K116K164K164K260K260K512K512K 回收前回收前 回收后回收后可变分区回收算法可变分区回
