314_连续分配管理方式
# 3.1_4_连续分配管理方式
在这个小节中我们会学习连续分配管理方式相关的知识点，在之前的学习中我们知道操作系统对内存进行管理需要实现这样 4 个事情，那么内存空间的扩充，地址转换和存储保护，这是之前的小节介绍过的内容。
从本小节开始我们会介绍内存空间的分配与回收应该怎么实现。我们在这个小节中会先介绍连续分配管理方式，分别是单一连续分配，固定分区分配和动态分区分配，我们会按从上至下的顺序依次讲解，那么这儿需要注意的是，所谓的连续分配和非连续分配的区别在于连续分配是指系统为用户进程分配的，必须是一个连续的内存空间，而非连续分配管理方式是指系统为用户分配的那些内存空间不一定是连续的，可以是离散的。
# 单一连续分配方式
那么我们先来看单一连续分配方式，采用单一连续分配方式的系统当中，会把内存分为一个系统区和一个用户区，那系统区就是用于存放操作系统相关的一些数据，用户区就是用于存放用户进程或者说用户程序相关的一些数据。
不过需要注意的是采用单一连续分配方式的这种系统当中，内存当中，同一时刻只能有一道用户程序，也就是说它并不支持多道程序并发运行，所以用户程序是独占整个用户区的，不管这个用户区有多大
比如说一个用户进程或者说用户程序，它本来只需要这么大的内存空间，当它放到内存的用户区之后，用户区当中其他这些空闲的区间，其实也不会被分配给别的用户程序，所以说是整个用户程序独占整个用户区的这种存储空间的。所以这种方式其实优点很明显，就是实现起来很简单，并且没有外部碎片，外部碎片概念，我们在讲到动态分区分配的时候，再补充这儿先有个印象
由于整个系统当中同一时刻只会有一个用户程序在运行，所以采用这种分配方式的系统当中，不一定需要采用内存保护，注意只是不一定。有的系统当中，它也会设置那种越界检查的一些机制，但是像早期的个人操作系统，微软的 DOS 系统就没有采用这种内存保护的机制，因为系统中只会运行一个用户程序，那么即使用户程序出问题了，也只会影响用户程序本身，或者说即使这个用户程序越界，把操作系统的数据损坏了，这个数据一般来说也可以通过重启计算机就可以很方便的就进行修复。
所以说采用单一连续分配的系统当中，不一定采取内存保护，这也是它的优点。另一方面这种方式的缺点也很明显，就是只适用于单用户单任务的操作系统，它并不支持多道程序并发运行，并且这种方式会产生内部碎片，所谓的内部碎片就是指我们分配给某一个进程，或者说程序的内存区间当中，如果有某一个部分没有被用上，这就是所谓的内部碎片。像这个例子当中，本来整个用户区都是分配给用户进程 a 的，但是有这么大一块它是空闲的，暂时没有利用起来，本来给进程分配了，但是进程没有用上的这一部分内存区域就是所谓的内部碎片，所以这种方式也会导致存储器的利用率很低，这是单一连续分配方式。
# 固定分区分配方式
接下来来看固定分区分配方式，随着计算机的发展出现，慢慢的开始出现了多道程序技术，可以让各个程序同时装入内存，并且这些程序之间不能互相干扰。所以人们就想到了把用户区划分成了若干个固定大小的分区，并且在每一个分区内只能装入一道作业，也就是说每一道作业或者说每一道程序，它是独享其中的某一个固定大小的分区的，这样的话就形形成了，最早的可以支持多道程序的内存管理方式
固定分区分配可以分为两种，一种是分区大小相等，另外一种是分区大小不等。如果说采用的是分区大小相等的策略的话，系统会把用户区的这一整片的内存区间分割为若干个固定大小并且大小相等的区域，比如说每一个区 10 兆字节，如果说采用的是分区大小不相等的这种策略的话，系统会把用户区分割为若干个大小固定，但是大小又不相等的分区
这两种方式各有各的特点，如果说采用的是分区大小相等的这种策略的话，很显然会缺乏灵活性。比如说一些小的进程，它可能只需要占用很小的一部分内存空间，但是由于每个分区只能装入一道作业，所以一个很小的进程又会占用一个比较大的很多余的分区。如果说有一个比较大的进程进入的话，那么如果这些分区的大小都不能满足大进程的需求，那么大进程就不能被装入这个系统，或者说只能采用覆盖技术，在逻辑上来拓展各个分区的大小，但这个显然又会增加一些系统开销。所以说分区大小相等的这种情况是比较缺乏灵活性的
不过这种策略即使在现代也是有很广泛的用途的，比如说我们钢铁厂里有 n 个相同的炼钢炉，那么可以把内存当中分为 n 个大小相同的区域，并且在这 n 个区域当中放入 n 个一模一样的炼钢炉的控制程序。由于这 n 个炼钢炉本来就是相同的对象，所以对这些相同的对象进行控制的程序当然也是相同的程序。所以如果采用这种把它分割为 n 个大小相等的区域，来分别存放 n 个控制程序，让这 n 个控制程序并发执行并发的控制各个炼钢炉的话，在这种场景下的应用就是很适合的
如果分区大小不等的话，灵活性会有所增加。比如说小的进程，我们可以给它分配一个小的分区，而大的进程可以给它分配一个大的分区。一般来说可以先估计一下系统当中会出现的大作业小作业分别到底有多少，然后再根据大小作业的比例来对这些大小分区的数量进行一个划分。比如说可以划分多个小分区，适量的中等分区，然后少量的大分区。
接下来我们再考虑下一个问题，操作系统应该怎么记录内存当中各个分区的空闲或者分配的这些情况。一般来说我们可以建立一个叫做分区说明表的一个数据结构，用这个数据结构对各个分区进行管理。
比如说如果系统当中内存的情况是这个样子，那么我们可以给它建立一个对应的分区说明表，每一个表项会对应其中的某一个分区，每一个表项需要包含当前分区的大小，还有分区的起始地址，还有分区是否已经被分配的这种状态。
像这样一张表，其实我们可以建立一个数据结构当中有这样一些属性，然后把用这个数据结构组成一个数组或者组成一个链表来。如果学过数据结构的同学，这应该不难理解。
操作系统根据这个数据结构就可以知道各个分区的使用情况，如果说一个用户程序想要装入内存的话，操作系统就可以来检索这个表，然后找到一个大小能够满足并且没有被分配出去的分区，然后把分区分配给用户程序之后，再把这个分区对应的状态成已分配的状态就可以了。那么固定分区分配实现起来其实也不算复杂，并且使用这种方式也不会产生外部碎片，那么外部碎片这个概念，咱们再往后拖一拖，下一个分配方式当中会进行讲解
但是这种方式也有很明显的缺点，如果说一个用户程序太大，到没有任何一个分区可以直接满足它的大小的话，那么我们只能通过覆盖技术来解决分区大小不够的问题。但是如果采用了覆盖技术，那就意味着需要付出一定的代价，会降低整个系统的性能。
另外这种分配方式很显然也会产生内部碎片，比如说有一个用户程序，它所需要的内存空间是 10 兆，那么扫描了这个表之后，会发现只有分区 6 可以满足 10 兆这么大的需求，所以用户程序就会被装到分区 6 里，但是由于用户程序会独占整个分区 6，所以分区 6 总共有 12 兆，那么就有两兆字节的空间是分配了给这个程序，但是这个程序又用不到的，这一部分就是所谓的内部碎片，所以固定分区分配是会产生内部碎片的，因此它的内存利用率也不是特别高。
# 动态分区分配
那么为了解决这个问题，人们又提出了动态分区分配的策略，动态分区分配又可以称作可变分区分配，这种分配方式并不会像之前固定分区分配那样预先划分内存区域，而是在进程装入内存的时候，才会根据进程的大小动态的建立分区，而每一个分区的大小会正好适合进程所需要的大小，所以和固定分区分配不同，如果采用动态分区分配的话，系统当中内存分区的大小和数目是可以改变的。
我们来看一个例子，比如说一个计算机的内存大小总共是 64 兆字节，然后系统区会占 8 兆字节，用户区就是 56 兆字节。刚开始一个用户进程一到达，他总共占用了 20M 字节的分区，之后一个用户进程二到达占用了 14 兆字节的分区。用户进程三到达占用了 18 兆字节的分区，那么 56 兆的用户区总共只会剩 4 兆字节的空闲分区
那么系统中这些分区的大小和数量是可变的，并且有些分区是已经被分出去的，有些分区又是没有被分出去的，操作系统应该用什么样的数据结构来记录内存的使用情况，这是我们之后要探讨的第一个问题。
再来看第二个问题，如果此时占有 14 兆字节的进程二已经运行结束了，并且被移出了内存，那么内存当中就会有这样一片 14 兆字节的空闲区间，此时如果有一个新进程到达，并且进程需要 4 兆字节的内存空间，这一片空闲区间是 14 兆，那么有多个空闲分区的话，到底应该放这一片还是放下面这一片？也就是说当我们的内存当中有很多个空闲分区都可以满足进程的需求的时候，应该把哪个空闲分区分配给进程，这是第二个问题。
第三个问题，假设此时占 18 兆字节的进程三运行结束，并且被撤离了内存，那么内存当中就会出现 18 兆字节的一个新的空闲分区，空闲分区应该怎么处理？是否应该和它与它相邻的这些分区进行合并，这就是第三个问题，我们应该如何进行分区的分配和回收的操作。
接下来我们依次对这三个问题进行探讨。先来看第一个问题，操作系统应该用什么样的数据结构记录内存的使用情况，一般来说会采用两种常用的数据结构，要么是空闲分区表或者采用空闲分区链，比如某一个时刻系统当中内存的使用情况是这个样子，总共有三个空闲分区，那么如果采用空闲分区表的话，这个表就会有三个对应的表项，每个表项会对应一个空闲分区，并且每一个表项都需要记录与表项相对应的空闲分区的大小是多少，起始地址是多少等等一系列的信息。如果说没有在空闲分区表当中记录的那些分区，当然就是已经被分配出去了。
再看第二种数据结构，空闲分区链，如果采用这种方式的话，那么每一个分区的起始部分和末尾部分都会分别设置一个指向，前面一个空闲分区和指向后面一个空闲分区的指针，就像这个样子，所以就会把这些空闲分区用一个类似于链表的方式把它们连接起来，每一个空闲分区的大小，还有空闲分区的起始地址、结尾地址等等，这些信息可以统一的把它们放在各个空闲分区的起始部分，所以这是我们可以采用的两种数据结构，空闲分区表和空闲分区链。
再来看第二个问题，当有很多空闲分区都可以满足需求的时候，到底应该选择哪个空闲分区进行分配呢？假如此时有一个进程 5，它只需要 4 兆字节的空间，那么如果有 3 个空闲分区都可以满足他这个需求，我们应该用哪个分区进行分配呢
由这个问题我们可以引出动态分区分配算法相关的问题。所谓的动态分区分配算法就是要从空闲分区表或者空闲分区链当中，按照某一种规则选择出一个合适的分区，把它分配给此时请求的进程或者说作业，由于分配算法对系统性能造成的影响是很大的，所以人们对这个问题进行了很多的研究，这个问题我们现在暂时不展开处理，会在下一个小节进行详细的介绍。
接下来我们再来看第三个问题，如何进行分区的分配与回收？假设我们采用的是空闲分区表的这种数据结构的话，进行分配的时候需要做一些什么操作？这个地方我们只以空闲分区表为例，其实空闲分区链的操作也是大同小异的。
假如说此时系统当中有这样 3 块空闲的分区，如果此时有一个进程需要申请 4 兆字节的内存空间，假设我们采用了某一种算法，最后决定从这 20 兆的空闲分区当中摘出 4 兆分配给进程 5，就像这样。
那么我们需要对空闲分区表进行一定的处理。由于空闲分区的大小，本来就是比此次申请的这块内存区域的大小要更大的，所以即使我们从分区当中摘出一部分进行了分配，那么分区的数量依然是不会改变的。所以我们只需要在分区对应的表项当中修改一下它的分区大小，还有起始地址就可以了。这是第一种情况。
再来看第二种情况还是相同的例子，有一个进程 5 需要 4M 字节，如果说我们采用了某种分配算法，最后决定把这 4M 字节的空闲分区分配给进程 5，那么本来空闲分区的大小就和此次申请的内存空间大小是相同的，所以如果把分区空闲分区全部分配给进程的话，那么显然空闲分区的数量会减一，所以我们需要把分区对应的表项给删除，如果说我们采用的是空闲分区链的话，我们需要把其中的某一个空闲分区链的节点给删掉，这是分配的时候可能会遇到的两种情况。
接下来我们再来看进行回收的时候可能会需要做一些什么样的处理。假设此时系统内存中的情况是这样的，如果采用空闲分区表这种数据结构的话，这个表应该是有两个表项，分别对应一个 10 兆的空闲分区和一个 4 兆的空闲分区。假设此时进程 4 已经运行结束了，我们可以把进程 4 占用的这 4 兆字节的空间给回收，
那么此时这一块回收的区域的后面有一个相邻的空闲分区，也就是 10 兆的这块分区，因此我们把这块内存分区回收之后，我们需要把空闲分区表当中对应的表项的分区大小和起始地址也进行一个更新。所以可以看到如果两个空闲分区相邻的话，那么我们需要把这两个空闲分区进行合二为一的操作。
再看第二种情况，假设此时进程三已经运行结束了，那么当进程三占用的这一块分区被回收之后，在它的前面也有一个相邻的空闲分区，所以参照刚才的那种思路，我们也需要把这两块相邻的空闲分区进行合二为一的操作，这和之前的那种情况其实是很类似的。
再看第三种情况，假设此时进程 4 已经运行结束，需要把这 4 兆字节给回收，
那么进程 4 的前面和后面都会有一个相邻的空闲分区，所以本来我们的空闲分区表有三个表项，也就是有三个空闲分区，但是当进程 4 的这块空间被回收之后，需要把这一整块的空间都进行一个合并，所以本来系统中有三个空闲分区，但如果把进程 4 回收之后就会合并为两个空闲分区，当然我们也需要修改相应表项的这些分区大小、起始地址等等这一系列的信息，这是第三种情况，需要把三个相邻的空闲分区合并为一个。
再看第四种情况，假如回收区的前后都没有相应的空闲分区的话，应该怎么处理？假设此时进程二已经运行结束
那么当进程二的这块内存区间被回收之后，系统当中就出现了两块空闲分区，所以相应的我们当然也需要增加一个空闲分区表的表项。
通过刚才的这一系列讲解，大家可能会发现我们对空闲分区表的这种顺序，一般来说是采用这种按照起始地址的先后顺序来进行排列的，但是这个并不一定各个表项的排序，我们一般来说需要根据我们采用哪种动态分区分配算法来确定，比如说有的时候我们按照分区从大到小的顺序排列会比较方便，有的时候我们按照分区大小，从小到大进行排列会比较方便，当然也有的时候就像现在这样，按照起始地址的先后顺序来进行排列会比较方便，这个地方会在下一个小节进行进一步的解释。到这个地方我们就回答了之前提出的三个问题，
第一个问题，我们需要用什么样的数据结构来记录内存的使用情况：一般来说会使用两种数据结构，空闲分区表或者空闲分区链。
第二个问题涉及到动态分区分配算法：这会在下一个小结中进行进一步的解释。
第三个问题，我们讨论了怎么对内存的空间进行分配与回收：进行分配与回收的时候，需要对这些数据结构进行什么处理。特别需要注意的是在回收的过程中，我们有可能会遇到 4 种情况，不过本质上我们可以用一句话来进行总结，在进行内存分区回收的时候，如果说回收了之后，发现有一些空闲分区是相邻的，那么我们就需要把这些相邻的空闲分区全部给合并。
接下来我们再来讨论一下动态分区分配，关于内部碎片和外部碎片的问题，我们给出了内部碎片和外部碎片的完整的定义
内部碎片是指分配给某个进程的内存区域当中，如果说有些部分没有用上，那么这些部分就是所谓的内部碎片，注意是分配给进程，但是进程没有用上的那些部分。而外部碎片是指内存当中的某些空闲分区，由于太小而难以利用，因为各个进程需要的都是一整片连续的内存区域，所以如果这些空闲的分区太小的话，那么任何一个空闲分区都不能满足进程的需求。这种空闲分区就是所谓的外部碎片
比如说我们系统当中依次进入了进程一、进程二、进程三，它们的大小分别是这样，然后这个时候内存当中只剩下一片空闲的内存区域，就是 4 兆字节这么大，那么此时如果进程二暂时不能运行，我们可以暂时把它换出到外存当中
于是这块就有 14 兆字节的空闲区域。接下来进程 4 到达占用 4 兆字节，这一块就应该是 10 兆字节的大小。
之后如果进程一也暂时不能运行，那么我们可以把进程一暂时换出外存，于是这个地方可以空出 20 兆字节的连续的空闲区间。
接下来如果进程二又可以恢复运行了，他再回到内存当中，他又占用了其中的 14 兆字节，于是这块就只剩下 6 兆字节。
接下来如果说进程一也就是 20 兆字节的进程又可以执行了，又想回到内存的话，那么此时会发现内存当中的任何一个区域都已经不能满足进程一的需求了，所以这就产生了所谓的外部碎片，这些空闲区间是暂时没有分配给任何一个进程的，但是由于他们都太小了太零碎了，所以没办法满足这种大进程的需求。
像这种情况下，其实内存当中总共剩余的空闲区间应该是 6+10+4，也就是总共有 20 兆字节，也就是说内存当中的空闲区间的总和，其实应该是可以满足进程与一的需求的。所以在这种情况下，我们可以采用紧凑技术或者叫拼凑技术来解决外部碎片的问题。紧凑技术很简单，其实就是把各个进程挪位，把它们全部攒到一起，然后挪出一个更大的空闲连续的空闲区间出来，这样的话这块空闲区间就可以满足进程一的需求了。
这个地方大家也可以停下来回忆一下，咱们刚才提到的换入换出技术和中级调度相关的一些概念，这是咱们之前讲过的内容。显然咱们之前介绍的三种装入方式当中，动态重定位的方式，其实是最方便实现这些程序或者说进程在内存当中移动位置这件事情的，所以我们采用的应该是动态重定位的方式。
另外紧凑之后，我们需要把各个进程的起始地址给修改掉，进程的起始地址，这个信息一般来说是存放在进程对应的 PCB 当中，当进程要上 CPU 运行之前，会把进程的起始地址那个信息放到重定位寄存器里，或者叫基址寄存器里。大家对这些概念还有没有印象？
# 小结
这个小节我们介绍了三种连续分配管理的分配方式，连续分配的特点就是为用户进程分配的必须是一个连续的内存空间，那么我们分别介绍了单一连续分配、固定分区分配和动态分区分配这三种分配方式。
咱们之前留下了一个问题，单一连续分配和固定分区分配都不会产生外部碎片。由于采用这两种分配方式的情况下，不会出现那种暂时没有被分配出去，但是又由于空闲区间太小而没有办法利用的这种情况，所以这两种分配方式是不会产生外部碎片的。
对于是否有外部碎片还是内部碎片，这个知识点经常在选择题当中进行考察，大家千万不能死记硬背，一定要在理解了各种分配方式的规则的这种情况下，能够自己分析到底有没有外部碎片，有没有内部碎片。
另外动态分区分配方式当中对外部碎片的处理紧凑技术也是曾经作为选择题的选项进行考察过，这个地方也需要有一些印象，在回收内存分区的时候，我们可能会遇到的这 4 种情况也是曾经在真题当中考察过，所以这个点也也需要注意，不过只需要抓住一个它的本质，相邻的空闲区间是需要合并的，我们只要知道这一点就可以了。另外我们也需要对空闲分区表和空闲分区链这两种数据结构相关的概念，还有它们的原理要有一个印象。
