《操作系统 - 清华大学》3 -3：连续内存分配：内存碎片与分区的动态分配

0. 概述

内存分配是操作系统管理过程中很重要的环节，首先需要考虑的是一块连续区域分配的过程，这个过程中会有很多问题，首先比较关注的一个问题是内存碎片问题。

1. 内存碎片问题

什么碎片问题？
实际上就可以理解为当给一个运行程序分配空间之后，会出现一些无法进一步利用的空闲空间，这就是碎片，因为它已经没法被使用了。

但是碎片又分两种:
外碎片: 就是说在分配单元之间的这个没法去使用的内存。
内碎片: 所谓内碎片就是已经分配给了这个应用程序，但应用程序没法去进一步使用在这个分配的内存。
这两者都是希望尽量避免，希望能够有一种有效的内存分配方法，能够有效地减少内碎片和外碎片。

2. 动态分配

另一个问题在于，首先站在操作系统角度，它要在什么时候提供连续空间的分配？

1. 很显然操作系统需要把应用程序从硬盘加载到内存中去，需要在内存中分配出一块连续的区域，那程序可以正常地跑起来，那么这时候需要去分配内存，分配连续空间。
2. 应用程序在运行的时候，它需要去访问数据，这时候需要给数据分配块空间，这也是操作系统来完成，它希望能够给应用程序提供它所需要的内存空间，当然这个空间也需要是连续的。

为此操作系统需要管理整个空闲的和非空闲的内存空间，它需要知道哪些空间是已经被占用了，哪些空间还是空闲的，这实际上是有一些数据结构和算法来有效地进行管理。

为此在这里面首先介绍三个简单的内存分配算法，包括首次适配、最佳适配、还有最差适配。这三种内存分配算法。

3. 首次适配算法

什么叫首次适配算法？

字面意思还是比较好理解，首先看看上述例子，这例子有三块空闲空间，1K、2K 和500B，地址也是由 0 地址开始到最后的 Max最大地址空间。在整个存储里面存在了三块空间空间。
  ~  
那如果应用程序提出一个需求，要分配 n 个 BYTE，首先需要找到第一个能够满足这个需求的空闲块。把这个块就分配给应用程序。

那基于这个原则，看一看刚才说到的1K、2K、 500 byte 按照这个地址顺序来找，如果从低地址和高地址找，如果采用 First-fit 分配策略的话，那么应该是选择哪空闲块分配出去？

其实就是第一个空间块，因为它从0 地址开始往下找，第一个碰到的就是1K，而这个1K 空间块能够满足应用程序发出400 BYTE 的应用需求，所以说这就是 First-fit 分配算法的执行过程。

这个算法看起来是挺简单，也便于实现，但其实它有一定需求，还有它的特点，那么它需求什么呢？

首先，需要把空闲的内存块按照地址排序，从0地址开始找，一个一个空闲块开始找，按照地址顺序，那么第一个满足内存请求大小的空间块就能够就是分配出去了。

但是也需要注意这个分配过程中还存在另一过程回收，那在回收过程中需要考虑，是否能够把空闲的块合并一下，合并就可以使我们有更大的空间块。为什么这么说呢？

因为一旦能够形成更大空间块之后，其实可以满足更多的应用需求，特别是这种大的内存应用需求。这是First-fit 分配策略的时候需要考虑的问题。

那么这种方法的优点是什么？

1. 它的优点其实也很直接，第一个简单。可以看出来，确实找到第一个，不管后面，第一个能够满足需求就马上返回了。
2. 它能够产生更多更大的空闲块。因为找到第一个之后，可能后面还有很多大的空间块，就不需要去破坏，把这个大空闲块变得更小，这也是它的好处。

那它不好的在什么地方呢？
容易产生外碎片。因为它把第一个块找到之后，下一次再找可能又找到下一个空闲块，那么这两个空闲块之间的那个空间可能就不太容易被使用到，因为它已经比较小了。外碎片问题会随动态分配和释放，持续加剧，从而使得这个算法在某些情况下就不太适用了。

4. 最优适配算法

第二个为 Best-fit——最优适配算法，相对于首次适配算法而言，它有新的特点，它寻找整个适配块中最适合的空闲块，最适合满足分配请求的空闲块。什么叫最适合，实际就是说它的力度会比分配请求的那个力度要大，但是它们的差值是最小的，这是最匹配最贴近，这就为 best-fit 的含义。

看看这幅图，如果采取最优适配算法的话，那么到底应选择哪一个空间块分配出去呢？

也是一样分配 400 byte，那可以看出来最匹配 400 byte 的空闲块是 500 byte 空闲块，所以说会把最后一个500 byte 空闲块给分配出去，可以看到会产生一个 100 byte 的空闲块，那么这100 byte空闲空间将来很难被使用到，因为将来的需求可能都大于100，那空闲的100 就不太好用。

那它的要求是什么呢？

避免把大的空间块拆散，找的空间块一定是最适合这个分配请求的 size ，所以可避免对大空闲块拆分。另一方面，外碎片的产生可达到最小化。
  ~  
为了完成这个算法，要把空闲内存块排好序，最好是能够按照 size 来排序。这样的话就可以比较容易在链表中找到满足最贴近分配请求 size 的空间块的位置，同时在做回收的时候也需要考虑怎么能够把它合并，这一点也是跟前面一样是比较困难。

它的好处什么呢？

对于大多数小内存分配的情况比较合适，相对而言也比较简单。

不好的地方在哪呢？

它把外碎片拆得比较细，使得将来进一步使用外碎片的可能性比较小，使得将来整个空间中很碎的、很小的空闲块到处都存在，不利于后续空间的分配和管理。

5. 最差适配算法

它的特点是找到一个空闲的内存块，它与内存分配请求的 size 差距是最大的，把这种块作为分配的对象分配出去。

以刚才例子为例，如果是1K 2K 500 byte 空闲块，如果采取最坏适配算法的话，那么其实可以看到应该选择2K byte 空闲块，因为它和分配请求400 byte 的差距是最大的。

算法的特点是可以首先把大的空间块给拆分了，可以理解为好，也可以理解为不好的地方，那么它可以把大块变成小块，小块还继续保留，这是它的一个特点。尽量拆分大块的方法使得避免产生大量的、琐碎的、小的碎片，这是它的特点。

如果为能够实现这种算法，也需要对空闲的块做排序，根据它的 size 来排序，这样可以更好地选择到底哪一个块是与分配请求的 size 是差距最大的。

第二个也需要考虑怎么去合并，它的分配效率相对来说是比较快的，它的好处是说如果分配请求尽量是比较大的、中大型的 size 的话，那么采取最坏适配算法是比较合适的。

但是不好的地方在哪呢？

它一开始就要去拆那个大块，带来的问题就是将来再去分配这种大块就可能分配不到了，这是它的问题，大块的这种处理使得对这种大块的请求会带来一定影响。

再看看前面讲了三种首次适配、最优适配和最坏适配算法，这三者到底哪个是最好的一个算法吗？

其实这里面没有最好算法的说法，为什么这么说呢？因为应用程序的请求是随机产生的，或者说根据特定的应用场景，有各自的特点，有可能应用程序一会是需要大的空闲块，一会需要小的空闲块，有时候它可能一直需要小的，或者一直需要大的，而这个需求是随机的、可变的。

那么这几种算法，没有一种是能够满足所有的需求，所以这些算法可以理解为是一种简单的内存管理算法，实际应用中有一些更复杂的算法，后续做进一讲解。