315_动态分区分配算法
# 3.1_5_动态分区分配算法
在小节中我们会学习动态分区分配算法相关的知识点，这是我们上小节遗留下来的问题。在动态分区分配方式当中，如果有很多个空闲分区都能够满足进程的需求，那么我们应该选择哪个分区进行分配，这是动态分区分配算法需要解决的问题
考试当中要求我们掌握的有这样 4 种算法，首次适应，最佳适应，最坏适应，临近适应这 4 种，我们会按从上至下的顺序依次讲解。
# 首次适应
首先来看首次适应算法，这种算法的思想很简单，每次从低地址部分开始查找，找到第一个能够满足大小的空闲分区，所以按照这种思想，我们可以把空闲分区按照地址递增的次序进行排列，而每一次分配内存的时候，我们就可以顺序的查找空闲分区链或者空闲分区表，找到第一个能够大小能够满足要求的空闲分区进行分配。
这个地方提到了空闲分区链和空闲分区表，这是两种常用于表示动态分区分配算法当中内存分配情况的数据结构。如果我们此时系统当中内存的使用情况是这样的，采用空闲分区表的话，我们就可以得到一个这样的表
每一个空闲分区块都会对应一个空闲分区表的表项，这些空闲分区块是按地址从低到高的顺序依次进行排列的，如果采用空闲分区链的话，其实也类似也是按照地址从低到高的顺序，把这些空闲分区块依次的连接起来。这个算法对这两种数据结构的操作其实是很类似的，无非就是从头到尾依次检索，然后找到第一个能够满足要求的分区。
所以这个地方我们就以空闲分区链为例子，空闲分区表的操作其实也类似，那按照首次适应算法的规则，如果说此时有一个进程要求 15 兆字节的空闲分区，那么我们会从空闲分区链的链头开始依次查找，找到第一个能够满足大小的分区。经过检查发现第一个 20 兆字节的空隙分区已经可以满足这个要求，所以我们会从 20 兆字节的空闲分区当中摘出 15 兆分配给进程 5，于是这个地方会剩余 5 兆字节的空闲分区，相应的我们需要把空闲分区链的对应节点的这些数据，包括分区的大小，还有分区的起始地址等等这一系列的数据都进行修改。
那么此时如果还有一个进程，到来他需要 8 兆字节的内存空间，我们依然还是会从空闲分区链的链头开始依次检索。经过一系列的检索会发现第二个空闲分区的大小是足够的，于是我们会从第二个空闲分区 10 兆字节当中择出 8 兆分配给进程 6，这个地方会剩余两兆字节的空闲分区，所以我们和刚才一样也需要修改空闲分区链当中相应的分区大小，还有分区的起始地址，这一系列的信息，这个地方就不再展开赘述。
所以这就是首次适应算法的一个规则，我们按照地空闲分区以地址递增的次序进行排列，并且每一次分配内存的时候，我们都会从链头开始依次往后寻找，找到第一个能够满足要求的空闲分区进行分配。
# 最佳适应
接下来来看最佳适应算法，这种算法的思想其实也很好理解，由于动态分区分配算法是一种连续分配的方式，既然是连续分配，就意味着我们系统为各个进程分配的空间必须是连续的一整片区域。所以我们为了保证大进程到来的时候，有大片的连续空间可以供大进程使用，所以我们可以尝试尽可能多的留下大片的空闲区间，那也就是说我们可以优先的使用更小的那些空闲区间，所以最佳适应算法会把空闲分区按照容量递增的次序依次连接，每次分配内存的时候会从头开始，依次查找空闲分区链或者空闲分区表，找到大小能够满足要求的第一个空闲分区。
由于这个空闲分区是按容量递增的次序排序排列的，所以我们找到的第一个能够满足的空闲分区一定是能够满足，但是大小又是最小的空闲分区，这样的话我们就可以尽可能多的留下大片的空闲分区了。
这个地方还是一样，我们就以空闲分区链作为例子，空闲分区表的操作其实也类似，如果说系统当中的内存使用情况是这个样子，那么我们按照空闲分区块的大小，从小到大也就是递增的次序链接的话，应该是 4，10， 20 这样的顺序链接
如果说此时有一个新的进程到达进程需要 9 兆字节的内存空间的话，按照最佳适应算法的规则，我们会从链头开始依次往后检索，找到第一个能够满足要求的空闲分区也就 10 兆字节，于是我们会从这 10 兆字节当中摘出其中的 9 兆分配给进程，这个地方就只剩下一兆字节的大小。
但是由于最佳适应算法要求，我们空闲分区必须按照容量递增的次序进行链接，所以这个地方变成了 1M 之后，我们就需要对整个空闲分区链进行重新排序，最后会更新为这个样子。也就是把更小的空闲分区挪到链头的位置。
那之后如果还有另外一个进程需要到达，它需要三兆字节的空闲分区的话，同样的我们也需要从链头开始依次查找，于是发现这个分区是可以满足的。那么第二个进程 3 兆字节，我们就可以从 4 兆当中摘出 3 兆给它分配，这个地方也会变成只有一兆字节的空闲分区，我们之后就需要把节点对应的那些空闲分区大小空闲分区的起始地址这些信息进行更新，这个地方进行更新之后，整个空闲分区链依然是按照容量递增的次序进行链接的，所以我们就不需要再像刚才那样进行重新排列，这个地方就不再展开细聊了。
从刚才的这个例子当中，我们会发现最佳适应算法有一个很明显的缺点，由于我们每一次选择的都是最小的能够满足要求的空闲分区进行分配，所以我们会留下越来越多很小的很难以利用的内存块。比如说这个地方有一兆字节，这个地方又一兆字节，假如我们所有的进程都是两兆字节以上，这两个地方的碎片就是我们难以利用的，所以采用这种算法的话，其实是会产生很多外部碎片的，这是最佳适应算法的一个缺点。
# 最坏适应算法
于是为了解决这个问题，人们又提出了最坏适应算法，他的算法思想和最佳适应刚好相反，由于最佳适应算法留下了太多难以利用的小碎片，所以我们可以考虑在每次分配的时候优先使用最大的那些连续空闲区，这样的话我们进行分配之后，剩余的那些空闲区就不会太小
所以如果采用最坏适应算法的话，我们可以把空闲分区按照容量递减的次序进行排列，而每一次分配内存的时候，就顺序的查找空闲分区链，找出大小能够满足要求的第一个空闲分区。由于这个地方空闲分区是按容量递减的次序进行排列的，所以链头第一个位置的空闲分区肯定是能够满足要求的。如果第一个都满足不了要求，剩下的后面的那些空闲分区肯定都比第一个空闲分区更小，别的那些空闲分区肯定也不会满足。
还是来看一个具体的例子。假设此时系统当中内存的使用情况是这样，我们采用空闲分区表和空闲分区链，可以表示出此时的这些空闲分区的情况。按照最坏适应算法的规则，我们需要按照容量递减的次序，依次把这些空闲分区进行排列，也就是 20，10，4。
此时假如有一个进程，它需要三兆大小的内存空间，由于链头的第一个空闲分区就可以满足，所以我们会从其中摘出三兆进行分配，这个地方就变成了还剩 17 兆。
接下来如果还有一个进程也到达，它需要 9 兆内存，同样的我们也是从这 10 念头的 17 兆当中摘出其中的 9 兆分配给进程 6，于是进行数据的更新。那更新了之后我们会发现此时空闲分区链已经不是按照容量递减的次序进行排列的，所以我们需要把空闲分区链进行重新排序，也就变成这个样子，10,8,4 依然保持按容量递减的次序进行链接，如果有下一个进程到达的话，我们第一个需要检查的就是 10 空间分区。
从这个例子当中可以看到，最坏适应算法确实解决了刚才最大适应算法，留下了太多难以利用的碎片的问题，但是最坏适应算法又造成了一个新的问题，由于我们每次都是选择最大的分区进行分配，所以这就会导致我们的那些大分区会不断的被分割为一个小分区。如果之后有一个大进程到达的话，就没有连续的大分区可用了。比如说此时来了一个 20 兆的大进程就无处安放，所以这是最坏适应算法的一个明显的缺点。
# 临近适应算法
接下来我们再来看第四种临近适应算法，这种算法的思想其实为是为了解决首次适应算法当中存在的一个问题，首次适应算法每次都会从链头开始查找，这有可能会导致低地址部分出现很多很小的难以利用的空闲分区，也就是碎片。
但是由于首次适应算法，又必须按照地址从低到高的次序来排列这些空闲分区，所以我们在每次分配查找的时候，都需要经过低地址部分那些很小的分区，这样的话就有可能会增加查找的一个开销。所以如果我们能够从每次都从上一次查找结束的位置开始往后结检索的话，是不是就可以解决之前所说的这个问题了？
所以临近适应算法其实和首次适应算法很像，它也是把空闲分区按照地址递增的顺序进行排列，当然我们可以把它排成一个循环链表，这样的话比较方便我们检索。每一次分配内存的时候，都是从上次结束的位置开始往后查找，找到大小能够满足的第一个空闲分区。
假如说此时系统当中的内存使用情况是这样，我们可以把这些空闲分区按照地址递增的次序依次进行排列，排成一个循环链表。
刚开始如果说有一个进程到达，它需要 5 兆字节的内存空间，刚开始我们会从链头的位置开始查找，第一个不满足，第二个 6 找是满足的。于是我们会从 6 兆当中择出 5 兆分配给他，这个地方就还剩余一兆字节，于是我们需要更新链当中对应的节点，包括分区的大小，还要分区的起始地址
但是有没有发现采用临近适应算法还有首次适应算法，我们只需要按照地址递增的次序进行排列，所以即使这个地方内存分区的大小发生了一个比较大的变化，但是我们依然不需要对整个列表进行重新排列，所以这也是临近适应算法，还有首次适应算法，比最佳适应算法和最坏适应算法更好的一个地方。算法的开销会比较小，不需要我们再花额外的时间对这个列表进行重新排列。
假如此时有一个新的进程到达，它需要 5 兆字节的空间，按照临近适应算法的规则，我们只需要从上一次查找到的位置一次再往后查找就可以了。所以这个不满足，我们看下一个 10 兆是满足的，于是会从 10 兆当中择出 5 兆进行分配，然后更新相应的这些数据结构。
这个地方大家有没有发现，如果此时我们采用的是首次适应算法的话，如果此时需要分配 5 兆的内存空间，那么我们依然会从链头的位置开始往后查找，所以第一个 4M 不满足，第二个一兆不满足，第三个 10 兆才能满足，这会有三次查找。如果说我们采用的是临近适应算法的话，我们只需要从这个位置开始往后查找，也就是查两次就可以了，所以这是临近适应算法比首次适应算法更优秀的一个地方。首次适应算法会导致低地址部分留下一些比较小的碎片，但是我们每一次开始检索，都需要从低地址部分的这些小碎片开始往后检索，所以这就会导致首次适应算法在查找的时候可能会多花一些时间
不过这并不意味着临近适应算法就比首次适应算法更优秀很多，其实临近适应算法又造成了一个新的问题。在首次适应算法当中，我们每次都需要从低地址部分的那些小分区开始一次往后检索，但是这种规则也决定了，如果说在低地址部分有更小的分区可以满足我们的需求的时候，我们就会优先的使用低地址部分的那些小分区，这样的话就意味着高地址部分的那些大分区就有更大的可能性被保留下来。所以其实首次适应算法当中也隐含了一点最佳适应算法的优点。
如果我们采用的是临近适应算法的话，由于我们每次都是从上一次检查的位置开始往后检查，所以我们无论是低地址部分还是高地址部分的空闲分区，其实都是有相同的概率被使用到的，所以这就导致了和首次适应算法相比，高地址部分的那些大分区，更有可能被使用被划分成小分区。这样的话高地址部分的那些大分区也很有可能被我们用完，那之后如果有大进程到达的话，就没有那种连续的空闲分区可以进行分配了。所以其实临近适应算法的这种策略也隐含了一点最大适应算法的缺点。所以综合来看，其实刚才介绍的这 4 种算法当中，反而首次适应算法的效果是最好的。
# 小结
那么这个小节我们介绍了 4 种动态分区分配算法，分别是首次适应、最佳适应、最坏适应和临近适应，这个小节的内容，很容易作为选择题进行考察，甚至也有可能作为大题进行考察。
其实我们只需要理解各个算法的算法核心思想，就可以分析出个这些算法的这些空闲分区应该怎么排列，它们的优点是什么，缺点是什么。这几个算法当中比较不容易理解的其实是临近适应算法的优点和缺点，但是刚才咱们也进行了详细的分析，这就不再重复了。
这个地方大家会发现各个算法提到算法开销的大小问题，这个地方的算法开销指的是为了保证我们的空闲分区，是按照我们规定的这种次序排列的，在最佳适应和最坏适应这两种算法当中，我们可能需要经常对整个空闲分区链进行重新排序，所以这就导致了算法开销更大的问题。
而首次适应和临近适应，我们并不需要对整个空闲分区链进行顺序的检查和排序，所以这两种算法的开销是要更小的。那么这些算法大家还需要通过课后习题的动手实践来进行进一步的巩固
