操作系统中的内存管理：伙伴系统（Buddy System） 描述 伙伴系统是一种动态内存管理算法，主要用于分配连续物理页框，能有效减少外部碎片。其核心思想是将内存划分为大小不同的块（通常是2的幂次方），每次分配时找到最接近需求大小的块，若没有合适块则对半分裂更大块，并在释放时检查相邻"伙伴"块是否空闲以合并。适用于页式内存分配或内核对象管理。 知识要点 块大小规则 ：所有块大小均为2^k（如4KB、8KB）。 伙伴块定义 ：大小相同、地址连续且低k+1位中仅第k位不同的两个块互为伙伴（例如地址0x1000与0x1400的8KB块在16KB块中互为伙伴）。 分配与合并 ：通过分裂满足分配，利用伙伴关系合并减少碎片。 解题过程 假设系统初始有16KB连续内存，最小分配单元1KB（即块大小范围为1KB~16KB），需分配3KB内存： 步骤1：初始化空闲链表 创建5个空闲链表（对应大小1KB、2KB、4KB、8KB、16KB）。 初始时16KB块加入最大链表： free_list[4] → [16KB块] （索引0~4分别对应1KB~16KB）。 步骤2：分配3KB内存 计算最小满足块：找大于等于3KB的2^k最小块，即4KB（2^2 KB）。 检查4KB链表（free_ list[ 2 ]）是否空闲：若空，则向上查找更大块。 分裂过程： 16KB块分裂为两个8KB伙伴块（free_ list[ 3 ]加入两个8KB块）。 取一个8KB块继续分裂为两个4KB伙伴块（free_ list[ 2 ]加入两个4KB块）。 分配一个4KB块给请求，返回其地址，剩余块更新链表： free_list[2] → [剩余4KB块] 。 步骤3：释放已分配块 释放刚才分配的4KB块时，检查其伙伴块（相邻4KB块）状态： 若伙伴块空闲，合并为8KB块，递归检查8KB块的伙伴是否可继续合并。 若伙伴块被占用，仅将当前块加入4KB空闲链表。 合并示例：若释放后两个4KB伙伴均空闲，合并为8KB块加入free_ list[ 3 ]。 关键机制 快速定位伙伴 ：通过地址异或块大小计算伙伴地址（如4KB块地址0x2000，伙伴地址为0x2000 XOR 0x1000 = 0x3000）。 碎片控制 ：合并机制有效减少外部碎片，但可能因强制2^k大小产生内部碎片（如申请3KB实际分配4KB）。 应用场景 Linux内核的页分配器、早期用户态内存管理（如libc的malloc实现）均曾使用伙伴系统变种，适合对分配速度要求高、允许少量内部碎片的场景。