动态内存分配之伙伴算法

伙伴算法

伙伴算法是一种在计算机内存管理中使用的算法，用于分配和释放内存。它是一种基于二叉树的动态内存分配算法，可以高效地分配和合并内存块。伙伴算法是一种按照固定大小分配内存的算法，例如，每个内存块的大小为2的n次幂，即1、2、4、8、16、32等等。

伙伴算法的主要思想是将可用内存划分成多个大小相等的内存块，每个内存块大小为2的n次幂。对于每个内存块，都有一个伙伴内存块，它的大小是相等的，但是地址不同。例如，如果有一个大小为4个字节的内存块，它的伙伴内存块大小也为4个字节，但是它的地址不同。

当需要分配内存时，伙伴算法将查找大小最接近请求大小的可用内存块。如果找到的内存块大小正好匹配请求大小，则将其标记为已用，并返回指向该内存块的指针。如果找到的内存块比请求大小大，则将其拆分成两个相等的伙伴内存块，并将其中一个标记为已用，另一个标记为可用。然后，继续在较小的伙伴块中查找可用内存块，直到找到大小匹配的块或搜索完整个内存区域。

当需要释放内存时，伙伴算法将标记为已用的内存块标记为可用，并将其与其伙伴内存块合并。如果伙伴内存块也是可用的，则将它们合并成一个更大的内存块，直到合并到最大的内存块为止。在合并时，伙伴算法通过一个二叉树来管理内存块，每个节点表示一个内存块，节点的左子节点是伙伴内存块。

伙伴算法的优点是分配和释放内存的效率比较高，合并内存块的操作也比较简单。但是，由于它只能分配大小相等的内存块，因此可能会导致内存浪费。此外，它也可能导致内存碎片的问题。

能否避免内存碎片？

伙伴算法无法完全避免内存碎片，但可以减少碎片的数量和大小。

伙伴算法通过将可用内存空间划分为二的指数次幂大小的块，然后以块为单位分配和释放内存。分配请求按指数次幂进行舍入，以便可以分配给与请求大小最接近但不小于请求大小的可用块。如果没有完全匹配，就将块拆分为更小的块，然后继续寻找匹配项。当释放内存时，会找到相邻的空闲块并合并它们，以创建更大的空闲块。

尽管伙伴算法减少了碎片的数量和大小，但仍可能发生内存碎片。例如，如果有大量小型内存请求，可能会导致大量小块的分配和释放，这些小块可能无法合并成更大的块。此外，如果存在大小不一的块，则无法在它们之间进行合并。因此，伙伴算法无法消除所有内存碎片，但可以降低其影响。

内部碎片与外部碎片

内部碎片指的是已分配的内存空间中，未被使用的小块内存。这些内存块的大小小于分配的内存大小。例如，如果分配了一个 10MB 的空间来存储 1MB 的数据，则剩余的 9MB 就是内部碎片。

外部碎片指的是已分配的内存空间中，由于分配和释放的顺序不同导致的空隙，这些空隙可能很小，但无法被利用。例如，如果分配了两个 5MB 的内存块，但它们之间有一个 1MB 的空隙，这个空隙就是外部碎片。

【最后一个bug】多平台都有更新和发布，大家可以一键三连，关注+星标，不错过精彩内容~