什么是伙伴系统？

内存管理是操作系统 (OS) 的核心功能，它确保系统物理内存（RAM）高效地分配给进程。其中一种内存分配技术是伙伴系统，旨在平衡速度、效率和碎片控制。

伙伴系统因其以结构化且相对高效的方式管理连续内存的能力，常用于现代操作系统和内核级内存分配器。

块的两个较小部分大小相等，称为“伙伴”。伙伴系统是一种过程，其中两个单独的伙伴作为一个单元协同操作，以便它们可以相互监控和帮助。同样，两个伙伴中的一个将进一步分成更小的部分，直到请求得到满足。

Merriam-Webster 在1942年首次使用了“伙伴系统”一词。根据韦氏词典，伙伴系统是一种安排，其中两个人配对（例如，在危险情况下相互安全）。

伙伴系统基本上是在一个大组或独自一人时成对协作。两个人必须完成工作。工作可以是确保工作安全完成或有效地从一个人转移到另一个人。

操作系统中伙伴系统的定义

操作系统中的伙伴系统是一种内存分配算法，通过将空闲内存分成2的幂次方（例如，2、4、8、16… KB）大小的块来管理内存。当发出内存请求时，系统会找到足够大的最小可用块，如果需要，会将较大的块分成两个相等的“伙伴”，直到达到适当的大小。

当内存被释放时，系统会检查其对应的伙伴（即它被分割出来的块）是否也空闲。如果是，这两个伙伴将被合并（合并）回一个更大的块。这个过程减少了外部碎片，并支持高效的内存分配和回收。

操作系统中伙伴系统的核心概念

伙伴系统通过将内存分成大小为2的幂次方（如2⁰、2¹、2²等）的块来管理内存。核心思想是利用内存块的递归分裂和合并的结构化方法来简化分配和回收。

最初，系统将整个可用内存视为一个大的空闲块。当收到内存请求时，系统将请求大小向上取整到下一个2的幂次方。然后它定位一个该大小的空闲块。如果只有更大的块可用，系统会反复将其对半分裂，直到获得适当大小的块。每次块被分裂时，产生的两个半部分被称为伙伴。

一旦分配了一个块，相应的伙伴（分裂块的另一半）仍保留在空闲内存池中，并可用于将来的请求。当进程释放一个块时，系统会检查该块的伙伴是否也空闲。如果是，这两个伙伴将被合并（或聚合）回一个更大的块。这个过程递归地继续，允许系统从较小的块重建更大的块，保持内存效率。

这种方法减少了外部碎片，并实现了快速分配和回收，因为由于常规的2的幂次方结构，查找合适块和合并都非常简单。但是，它可能仍然存在内部碎片，因为分配的块可能大于请求的内存。

伙伴系统在操作系统中如何工作

1. 内存初始化

伙伴系统首先将所有可用的物理内存视为一个单一的、大的空闲内存块。这个块由操作系统管理，通常放置在一个名为“空闲列表”的数据结构中，该结构为每个允许的块大小维护单独的列表。块大小都是2的幂次方——例如，2 KB、4 KB、8 KB、16 KB等等。每个空闲列表条目对应这些大小之一，并包含该大小当前所有未分配的块。

2. 内存分配

当进程请求内存时，操作系统将请求向上取整到最接近的2的幂次方。这确保了内存块保持对齐并与伙伴系统结构兼容。然后系统搜索空闲列表以找到该确切大小的块。如果这样的块可用，它将直接分配给请求进程。如果所需大小的块不可用，系统会搜索更大的块。一旦找到更大的块，它会反复将其分成两个相等的部分——称为伙伴——直到创建所需大小的块。这些伙伴中的一个被分配，其他的返回到空闲列表以备将来使用。

3. 内存回收

当进程不再需要内存块并将其返回给系统时，伙伴系统会尝试将该块与其对应的伙伴合并。伙伴是该块上次分裂的另一半。如果该伙伴也空闲且大小相同，则两者将合并形成一个更大的块。这种合并过程称为“聚合”。它可以递归地继续：一旦两个伙伴合并，它们的新的伙伴就会被检查，依此类推。这种合并有助于防止内存过度碎片化，并使将来满足大型内存请求变得更容易。

4. 识别伙伴

伙伴系统的一个关键特性是可以使用简单的算术方法快速识别伙伴。给定一个已知起始地址和大小的内存块，系统可以通过翻转地址中的特定位来计算其伙伴的地址——具体来说，是与块大小对应的位。这种位操作允许系统非常高效地定位和合并伙伴，而无需搜索内存。

5. 碎片和效率

伙伴系统旨在通过始终以固定大小的块分配内存来减少外部碎片，这些块可以可预测地组合和分裂。但是，它可能存在内部碎片，因为系统总是将内存请求向上取整到下一个2的幂次方。这意味着如果进程请求70 KB，它将收到一个128 KB的块，浪费58 KB的未使用内存。尽管如此，该系统在速度、简单性和内存管理方面是高效的，尤其是在操作系统内核和实时系统中，其中分配性能至关重要。

操作系统中伙伴系统的目的

1. 高效的动态内存分配

伙伴系统提供了一种在运行时分配内存的结构化方式。它通过根据需要划分和组合块来处理各种大小的内存请求。这种动态处理对于进程频繁请求和释放内存的多任务环境至关重要。

2. 减少外部碎片

外部碎片发生在空闲内存被分割成小的、不连续的块时。伙伴系统通过以固定块大小（2的幂次方）分配内存来减少这种情况。当识别出两个相邻的空闲块（伙伴）时，它们可以合并回一个更大的块，从而保留大的连续内存区域。

3. 快速分配和回收

由于系统为每个块大小维护单独的空闲列表，并使用可预测的分割和合并，因此它可以非常快速地分配和释放内存。通过简单的算术或位操作（通过翻转特定位）计算块伙伴的能力，可以实现快速聚合和内存重用。

4. 简化内存管理

伙伴系统的结构易于实现和维护。与必须跟踪各种任意块大小的通用分配器不同，伙伴系统使用有限的、可预测的大小集。这降低了内存管理器的复杂性并避免了碎片管理开销。

5. 可扩展性和适应性

块的递归分裂和合并特性使伙伴系统能够以最小的开销处理小内存和大内存请求。它在内存使用模式不可预测或随时间变化的环境中（例如操作系统、服务器或嵌入式系统）具有良好的可扩展性。

6. 提高内存重用性

由于系统定期尝试将空闲块合并回更大的块，因此它提高了满足未来大型内存请求的机会。这种持续的聚合确保内存保持可用，并且不会因碎片化而随时间退化。

伙伴系统的类型

伙伴系统有以下四种类型。

1. 二进制伙伴系统

伙伴系统维护每个大小的空闲块列表（称为空闲列表），以便如果有一个所需大小的块可用，则很容易找到它。如果没有请求大小的块可用，分配器会搜索第一个非空列表，查找至少请求大小的块。在这两种情况下，块都会从空闲列表中删除。

例如，假设内存段的初始大小为256kb，内核请求25kb内存。该段最初被分成两个伙伴。比如说A1和A2，每个大小为128kb。其中一个伙伴进一步分成两个64kb的伙伴，B1和B2。但是25kb的下一个最高2的幂是32kb，所以B1或B2之一进一步分成两个32kb的伙伴（C1和C2），最后，其中一个伙伴用于满足25kb的请求。一个分裂的块只能与它唯一的伙伴块合并，然后重新形成它们从中分裂出来的较大块。

2. 斐波那契伙伴系统

斐波那契伙伴系统是一种将块分成斐波那契数大小的系统。它满足以下关系：

斐波那契伙伴系统的原始过程要么仅限于少量固定块大小，要么计算耗时。

3. 加权伙伴系统

加权伙伴系统类似于原始伙伴系统。在该系统中，大块被迭代地分裂以提供所需的较小块。当块被释放时，如果其伙伴可用，则它们与伙伴合并；如果失败，则附加到可用空间列表。二进制和加权伙伴系统具有以下相似之处。

• 给定块的地址，计算其伙伴地址的便利性。二进制和加权伙伴系统的地址计算是直接的。
• 以及从可用空间列表中分配块。

4. 三元伙伴系统

三元伙伴系统允许块大小为2k和3.2k，而原始二进制伙伴系统只允许块大小为2k。这种扩展是以每块额外两个位的代价实现的。所提出的算法的模拟已用C编程语言实现。

本文对三元伙伴系统与其他现有方案（如二进制伙伴系统、斐波那契伙伴系统和加权伙伴系统）的内部碎片性能分析进行了说明。此外，还讨论了上述系统几次分裂和平均合并次数的模拟结果比较。

操作系统中的伙伴关系

在伙伴系统内存分配技术中，伙伴关系指的是将一个较大的块分成两个等大小的半部分后形成的内存块的特殊配对。这两个半部分被称为伙伴，理解它们之间的关系对于系统高效合并和管理内存的能力至关重要。

1. 伙伴的形成

当一个内存块被分割时，它被分成两个大小相等的部分。这两个新块被称为伙伴。例如，如果一个256 KB的块被分割，它会创建两个128 KB的块。这两个128 KB的块是彼此的伙伴。

伙伴关系很重要，因为只有伙伴才能在回收过程中合并回其原始的较大块。非伙伴块，即使它们大小相同且在内存中相邻，也无法合并。

2. 伙伴块的条件

如果满足以下条件，则两个块被认为是伙伴：

• 它们大小相同。
• 它们在内存中相邻。
• 它们是由同一个原始父块通过分割创建的。

这些条件确保合并块不会损坏内存或使未来的分配错位。

3. 伙伴的地址计算

伙伴块的地址可以使用位操作来计算。假设一个块的大小为2^k，起始地址为A。要找到它的伙伴，系统翻转地址A的第k位。这种翻转会得到伙伴块的精确地址。

这种计算速度快，不需要搜索内存。这是伙伴系统高效的原因之一。

4. 合并伙伴

当一个块被回收时，系统会检查其伙伴是否也空闲。如果是，两者将合并成一个更大的块。这个合并过程可以递归地向上链条继续，允许系统从较小的、先前分配的块中重新创建非常大的块。这有助于减少碎片并提高内存重用。

5. 伙伴对的例子

想象一个起始地址为0，总大小为512 KB的内存区域。如果请求需要128 KB，系统可能会将512 KB的块分割成：

• 两个256 KB的块
• 然后将其中一个256 KB的块分割成两个128 KB的块

这两个128 KB的块现在是伙伴。如果一个被分配并随后释放，而另一个也空闲，它们可以合并回一个256 KB的块。

伙伴系统内存分配技术

伙伴系统内存分配技术是一种将内存划分为分区以尽可能合适地满足内存请求的算法。该系统通过将内存一分为二来提供最佳匹配。伙伴内存分配相对容易实现。它支持有限但高效的内存块分割和合并。

伙伴内存分配算法

伙伴系统有各种形式，其中每个块被细分为两个较小的块是最简单和最常见的变体。该系统中的每个内存块都有一个顺序，其中顺序是一个整数，范围从0到一个指定的上限。n阶块的大小与2ⁿ成比例，因此这些块的大小恰好是比它们低一阶的块的两倍。2的幂次方块大小使地址计算变得简单，因为所有伙伴都对齐在2的幂次方内存地址边界上。

• 当一个较大的块被分割时，它被分成两个较小的块，每个较小的块成为彼此唯一的伙伴。一个分裂的块只能与它唯一的伙伴块合并，然后重新形成它们从中分裂出来的较大块。
• 确定最小可能块的大小，即可以分配的最小内存块。如果不存在下限（例如，可以进行位大小的分配），那么系统将需要大量的内存和计算开销来跟踪内存的哪些部分已分配和未分配。
• 然而，较低的限制可能是可取的，以便最小化每次分配的平均内存浪费（相对于大小不是最小块倍数的分配）。
• 通常，下限应足够小以最小化每次分配的平均浪费空间，但足够大以避免过多的开销。然后，最小块大小被视为0阶块的大小，以便所有更高阶的块都表示为该大小的2的幂次方倍数。
• 然后，程序员必须决定或编写代码以适应剩余的可用内存空间，以获得尽可能高的阶。由于给定计算机系统中的总可用内存可能不是最小块大小的2的幂次方倍数，因此最大块大小可能无法跨越系统的整个内存。

例如，如果系统有2000K的物理内存，0阶块大小为4K，那么阶的上限将是8，因为8阶块（256个0阶块，1024K）是内存中能容纳的最大块。因此，不可能将整个物理内存一次性分配；剩余的976K内存将不得不以较小的块分配。

优点

伙伴系统分配具有以下优点，例如：

• 与其他更简单的技术相比，伙伴内存系统具有较少的外部碎片。
• 伙伴内存分配系统使用二叉树实现，以表示已使用或未使用的分裂内存块。
• 分配正确大小的块。
• 伙伴系统分配或释放内存的速度非常快。
• 在伙伴系统中，分配和释放内存块的成本低于最佳适应或首次适应算法。
• 合并相邻空洞很容易。
• 另一个主要优点是聚合。它定义为相邻伙伴可以多快地组合形成更大的段。这就是聚合。

缺点

它也有一些缺点，例如：

• 它要求所有分配单位都是2的幂次方。
• 它导致内部碎片。

伙伴系统内存分配示例

以下是程序发出内存请求时发生情况的示例。假设在此系统中，最小可能的块大小为64 KB，阶的上限为4，这导致最大可能的分配块大小为2⁴乘以64 K = 1024 K。下图显示了各种内存请求后系统可能的状态。

这种内存分配可能以以下方式发生。

步骤1： 这是初始情况。

步骤2： 程序A请求内存34 K，阶为0。

• 没有0阶块可用，因此一个4阶块被分割，创建了两个3阶块。
• 仍然没有0阶块可用，因此第一个3阶块被分割，创建了两个2阶块。
• 仍然没有0阶块可用，因此第一个2阶块被分割，创建了两个1阶块。
• 仍然没有0阶块可用，因此第一个1阶块被分割，创建了两个0阶块。
• 现在有一个0阶块可用，因此它被分配给A。

步骤3： 程序B请求内存66 K，阶为1。一个1阶块可用，因此它被分配给B。

步骤4： 程序C请求内存35 K，阶为0。一个0阶块可用，因此它被分配给C。

步骤5： 程序D请求内存67 K，阶为1。

• 没有1阶块可用，因此一个2阶块被分割，创建了两个1阶块。
• 现在有一个1阶块可用，因此它被分配给D。

步骤6： 程序B释放其内存，释放一个1阶块。

步骤7： 程序D释放其内存。

• 一个1阶块被释放。
• 由于新释放块的伙伴块也空闲，两者合并成一个2阶块。

步骤8： 程序A释放其内存，释放一个0阶块。

步骤9： 程序C释放其内存。

• 一个0阶块被释放。
• 由于新释放块的伙伴块也空闲，两者合并成一个1阶块。
• 由于新形成的1阶块的伙伴块也空闲，两者合并成一个2阶块。
• 由于新形成的2阶块的伙伴块也空闲，两者合并成一个3阶块。
• 由于新形成的3阶块的伙伴块也空闲，两者合并成一个4阶块。

如您在上述步骤中所见，当发出内存请求时会发生以下情况：

1. 如果要分配内存。
   1. 寻找一个大小合适的内存槽（大于或等于请求内存的最小2^k块）。
   2. 如果找到，则分配给程序。
   3. 如果未找到，它会尝试创建一个合适的内存槽。系统通过以下方式进行尝试：
      • 将大于请求内存大小的空闲内存槽一分为二。
      • 如果达到下限，则分配该数量的内存。
      • 返回寻找大小合适的内存槽（步骤I）。
      • 重复此过程，直到找到合适的内存槽。
2. 如果要释放内存。
   1. 释放内存块。
   2. 查看相邻块。
   3. 如果它空闲，则将两者合并，然后返回步骤II，并重复此过程，直到达到上限（所有内存都被释放）或遇到非空闲相邻块。

常见问题解答

Q1. 操作系统中的伙伴系统是什么？

伙伴系统是操作系统用于高效管理空闲内存的一种内存分配技术。它通过将内存分成2的幂次方大小的块，并将它们组织成称为“伙伴”的对，以实现快速合并和重用。

Q2. 为什么它被称为“伙伴”系统？

它被称为伙伴系统，因为每次内存块被分割时，它都会创建两个大小相等的“伙伴”块。这些块被视为伙伴，只有当两者都空闲时，伙伴才能合并回一起。

Q3. 系统如何知道哪些块是伙伴？

伙伴是根据块大小和地址确定的。可以通过翻转块地址中的特定位（与块大小对应的位）来找到块的伙伴。这种简单的算术使伙伴识别非常快。

Q4. 伙伴系统解决了什么问题？

伙伴系统通过以固定大小的块组织内存并允许相邻的空闲块合并来解决外部碎片问题。这有助于在内存中保持较大的块，并随着时间的推移提高内存可用性。

Q5. 伙伴系统中的外部碎片和内部碎片是什么？

• 外部碎片大部分被减少，因为系统会合并相邻的空闲块。
• 内部碎片仍然可能发生，因为内存请求会向上取整到下一个2的幂次方，这可能会在已分配的块内留下未使用的空间。