操作系统中的内存管理：伙伴系统（Buddy System）详解 伙伴系统是一种用于管理物理内存的算法，主要用于解决外部碎片问题。它通过将内存划分为大小相等的块，并按照2的幂次方进行分配和释放，能够高效地管理内存分配与回收。 1. 伙伴系统的基本思想 伙伴系统的核心思想是将可用内存空间视为一个大小为2^N的块。当需要分配内存时，系统会寻找一个足够大的块进行分配。如果找到的块过大，则将其对半分割成两个大小相等的"伙伴"块，直到得到合适大小的块。释放内存时，如果两个伙伴块都空闲，则合并它们成一个更大的块。 2. 伙伴系统的数据结构 系统维护一组链表（通常称为空闲链表），每个链表对应特定大小的内存块： 大小为2^0的块链表 大小为2^1的块链表 大小为2^2的块链表 ... 大小为2^N的块链表 3. 内存分配过程（以分配大小为k的内存为例） 步骤1：计算最小满足条件的块大小 找到最小的m使得2^m ≥ k 例如：需要分配10KB内存，2^3=8不够，2^4=16足够，所以m=4 步骤2：在对应大小的空闲链表中查找 检查大小为2^m的空闲链表 如果链表非空，直接分配第一个块 步骤3：如果当前链表为空，则向上查找 检查大小为2^(m+1)的空闲链表 如果非空，取出一个块并将其分割成两个2^m大小的伙伴块 一个用于分配，另一个加入2^m空闲链表 步骤4：递归向上查找 如果2^(m+1)也空，继续检查2^(m+2) 重复分割过程直到找到可用块 4. 内存释放过程 步骤1：释放内存块，将其标记为空闲 步骤2：检查伙伴块的状态 计算当前块的伙伴块地址：buddy_ addr = block_ addr XOR block_ size 例如：地址0x1000，大小16KB的块，其伙伴地址为0x1000 XOR 0x400 = 0x1400 步骤3：如果伙伴块也空闲，则合并 将两个伙伴块从当前链表中移除 合并成一个大一倍的块 将合并后的块加入更大尺寸的空闲链表 步骤4：递归合并 检查合并后块的伙伴是否空闲 如果可以继续合并，重复步骤3 直到无法合并或达到最大块大小 5. 伙伴系统的优势 有效减少外部碎片：通过合并机制保持大块内存可用 分配效率高：查找、分割、合并操作都是O(1)时间复杂度 实现相对简单：只需要维护一组空闲链表 6. 伙伴系统的局限性 内部碎片问题：如果申请大小不是2的幂次方，会产生浪费 合并条件严格：只能与特定地址的伙伴块合并 内存对齐要求：块地址必须是块大小的整数倍 7. 实际应用场景 伙伴系统在Linux内核的页面分配器中广泛使用，用于管理物理页面的分配。现代操作系统通常将伙伴系统与其他内存管理技术结合使用，以平衡碎片问题和分配效率。