目录
- 1. 核心思想
- 2. 工作原理
- 数据结构
- 内存分配过程（以页为单位）
- 内存释放过程
- 3. 一个简单的例子
- 4. 优缺点
- 优点
- 缺点
- 5. 实际应用
- 总结
伙伴算法是一种经典的内存管理算法，主要用于分配和回收物理内存页（通常是连续的页框），其核心思想是将内存分割和合并，以尽可能减少外部碎片。
1. 核心思想
伙伴算法的核心在于两个操作：分割 和 合并。
- 分割：当请求内存时，如果没有合适大小的空闲块，就将一个大的空闲块对半分割成两个较小的块。这个过程可以递归进行，直到得到所需大小的块。
- 合并：当释放内存时，算法会检查其“伙伴”块是否也是空闲的。如果是，就将这两个伙伴块合并成一个更大的空闲块。这个过程也可以递归进行，以尽可能地减少碎片。
关键概念：什么是“伙伴”？
两个内存块被称为“伙伴”，当且仅当它们满足以下所有条件：
- 大小相同，记大小为 \(S\)。
- 物理地址是连续的。
- 它们是由同一个大小为 \(2 \times S\) 的块分裂而来。
- 其中较低地址的块的起始地址必须是 \(2 \times S\) 的整数倍。
简单来说，一个块的伙伴就是和它“同出一源、大小相等、地址相邻”的那个块。
2. 工作原理
数据结构
算法使用一个空闲链表数组。
- 数组的每一个元素（即每一条链表）都对应一种特定大小的空闲块。例如：
free_list[0]：链接所有大小为 \(2^0 = 1\) 个页的空闲块。free_list[1]：链接所有大小为 \(2^1 = 2\) 个页的空闲块。free_list[2]：链接所有大小为 \(2^2 = 4\) 个页的空闲块。- ...
free_list[n]：链接所有大小为 \(2^n\) 个页的空闲块（最大块）。
内存分配过程（以页为单位）
假设系统需要分配 \(k\) 个页。
- 确定阶数：找到满足 \(2^i \geq k\) 的最小 \(i\)。也就是说，找到能容纳 \(k\) 个页的最小 \(2\) 的幂次方块。
- 查找空闲链表：
- 检查
free_list[i]是否为空。 - 如果非空，直接从该链表头取出一个空闲块，分配出去，过程结束。
- 检查
- 分裂块：
- 如果
free_list[i]为空，则向上查找，例如检查free_list[i+1]。 - 如果
free_list[i+1]也为空，则继续向上查找free_list[i+2]，以此类推。 - 假设在
free_list[j](\(j > i\)) 找到了一个空闲块。 - 将这个大小为 \(2^j\) 的块分裂成两个大小为 \(2^{j-1}\) 的“伙伴”块。
- 将其中一个 \(2^{j-1}\) 的块放入
free_list[j-1]。 - 对另一个 \(2^{j-1}\) 的块重复此分裂过程，直到得到大小为 \(2^i\) 的块，然后将其分配给请求者。
- 如果
内存释放过程
- 回收块：当释放一个大小为 \(2^i\) 的块时，算法并不立即将其放回
free_list[i]。 - 查找伙伴：算法首先计算这个被释放块的伙伴块的地址。
- 检查合并条件：
- 检查该伙伴块是否存在于
free_list[i]中（即同样是空闲的）。 - 并且，确认它确实是当前释放块的伙伴（地址相邻且由同一大块分裂而来）。
- 检查该伙伴块是否存在于
- 合并：
- 如果伙伴块存在且空闲，则将这两个大小为 \(2^i\) 的伙伴块从
free_list[i]中移除。 - 将它们合并成一个大小为 \(2^{i+1}\) 的连续块。
- 然后，递归地对这个新合并的、大小为 \(2^{i+1}\) 的块执行释放过程（即尝试继续与它的伙伴合并）。
- 如果伙伴块存在且空闲，则将这两个大小为 \(2^i\) 的伙伴块从
- 终止条件：当无法再合并（伙伴块不空闲或不存在）时，将最终合并成的大块放入对应的空闲链表中。
3. 一个简单的例子
假设内存初始为一个连续的 \(16\) 页的块（\(2^4\)）。
-
请求分配 3 个页：
- 最小满足的 \(2^i\) 是 \(2^2 = 4\) 页。
free_list[2]为空，向上查找。在free_list[4]找到 \(16\) 页的块。- 分裂1：\(16\) -> 两个 \(8\) 页的块。一个放入
free_list[3]。 - 分裂2：\(8\) -> 两个 \(4\) 页的块。一个放入
free_list[2]。 - 将得到的这个 \(4\) 页块分配给请求者。
-
请求分配 2 个页：
- 最小满足的 \(2^i\) 是 \(2^1 = 2\) 页。
free_list[1]为空，向上查找。在free_list[2]找到刚才放入的 \(4\) 页块。- 分裂：\(4\) -> 两个 \(2\) 页的块（互为伙伴）。一个放入
free_list[1]。 - 将另一个 \(2\) 页块分配给请求者。
-
释放第一个 4 页块：
- 计算其伙伴地址。发现其伙伴（另一个 \(4\) 页块）正在被使用（被分裂成了两个 \(2\) 页块，其中一个已分配，一个在空闲链表），无法合并。
- 因此，直接将这个释放的 \(4\) 页块放入
free_list[2]。
-
释放第二个 2 页块：
- 计算其伙伴地址。发现其伙伴（另一个 \(2\) 页块）正好在
free_list[1]中，是空闲的。 - 合并1：将这两个 \(2\) 页块合并成一个 \(4\) 页块。
- 现在，这个新 \(4\) 页块，它的伙伴（我们之前在步骤3中释放的）正好在
free_list[2]中，是空闲的。 - 合并2：将这两个 \(4\) 页块合并成一个 \(8\) 页块，放入
free_list[3]。
- 计算其伙伴地址。发现其伙伴（另一个 \(2\) 页块）正好在
通过这个过程，内存碎片被有效地合并了。
4. 优缺点
优点
- 有效避免外部碎片：通过“伙伴”合并机制，能够快速地将小块合并成大块，极大地减少了外部碎片。
- 分配和释放速度快：由于搜索的空闲链表是固定的，算法效率是 \(O(\log n)\)，在内存块数量很大时依然表现良好。
- 实现相对简单：概念清晰，数据结构不复杂。
缺点
- 内部碎片问题：由于分配的内存块大小必须是 \(2\) 的幂次方，如果请求的内存大小刚好比某个 \(2^i\) 大一点，比如 \(129KB\)，但系统只能分配 \(256KB\) 的块，这就会导致严重的内部碎片。
- 空间浪费：为了满足 \(2\) 的幂次方要求，平均会有 \(25\%\) 的内存浪费。
- 拆分与合并开销：频繁的分割和合并操作会带来一定的计算开销。
5. 实际应用
伙伴算法最著名的应用是在 Linux 内核中，用于管理物理页框的分配，即所谓的 “页分配器”。
- Linux 对其进行了优化，形成了 伙伴系统。
- 为了解决内部碎片问题，Linux 在伙伴系统之上增加了 slab 分配器（或
slub/slob）。Slab 分配器从伙伴系统获取大块内存（通常是页的整数倍），然后自己管理，切割成一个个细小的对象（如task_struct,inode等）分配给内核使用，从而极大地减少了内核对象的分配和初始化开销，并解决了小内存分配的内部碎片问题。
总结
伙伴算法是一种以空间换时间和换规整性的算法。它通过强制使用 \(2\) 的幂次方大小的块，并利用“伙伴”关系进行高效的合并，成功地解决了外部碎片问题，成为许多现代操作系统内存管理的基石。尽管存在内部碎片的缺陷，但通过与其他分配器（如 Slab）协同工作，它在实践中取得了巨大的成功。