Linux 伙伴系统与 Slab 分配器：内存管理的内核实现与调优实践

Linux 伙伴系统与 Slab 分配器：内存管理的内核实现与调优实践

一、内存分配的碎片化困境：外部碎片与内部碎片的物理根源

Linux 内核面临的核心内存管理矛盾是：应用程序请求的内存大小千差万别（从几个字节到几兆字节），而物理内存的管理单元必须高效且可预测。如果按字节分配，元数据开销和碎片化将使系统不可用；如果只按大块分配，内部碎片将浪费大量内存。

外部碎片是指内存中存在足够的空闲总量，但无法找到连续的空闲块满足分配请求。内部碎片是指分配的块大于请求的大小，多余部分无法使用。伙伴系统通过 2 的幂次方对齐解决了外部碎片问题——任何大小的空闲块都可以快速拆分和合并——但引入了内部碎片（最坏情况下浪费接近 50%）。Slab 分配器在伙伴系统之上构建了对象级缓存，解决了小对象的内部碎片问题，是两者协同工作的典型范例。

二、伙伴系统的底层机制：分裂、合并与迁移类型

2.1 伙伴系统的核心算法

伙伴系统将物理内存按 2 的幂次方划分为不同阶（order）的块。每个阶维护一个空闲链表。分配时，从满足请求的最小阶开始查找；若该阶无空闲块，则从更高阶分裂。释放时，检查"伙伴块"是否空闲，若空闲则合并为更高阶的块。

flowchart TD A[分配请求: 2^k 页] --> B{order=k 空闲链表非空?} B -->|是| C[从链表取出空闲块返回] B -->|否| D{更高阶 order 有空闲块?} D -->|否| E[分配失败: ENOMEM] D -->|是| F[从高阶取出空闲块] F --> G[递归分裂直到 order=k] G --> H[返回目标块<br/>其余块挂入对应阶链表] I[释放请求: 2^k 页] --> J[计算伙伴块地址] J --> K{伙伴块是否空闲且同阶?} K -->|否| L[将块挂入 order=k 空闲链表] K -->|是| M[合并为 order=k+1 块] M --> N[递归检查更高阶合并]

伙伴块的计算方式是：块地址的第 k 位取反。例如，order=2（4 页）的块地址为 0x1000，其伙伴块地址为 0x1000 XOR 0x4000 = 0x5000。这种位运算保证了 O(1) 时间找到伙伴块。

2.2 迁移类型与反碎片策略

Linux 2.6.24 引入了迁移类型（migrate type）机制，将空闲页分为不可移动（UNMOVABLE）、可回收（RECLAIMABLE）、可移动（MOVABLE）三类。分配时优先从同类型空闲页中分配，避免不可移动页分散在可移动页之间，导致内存迁移失败。

三、Slab 分配器的对象缓存机制

3.1 Slab 三级结构

Slab 分配器在伙伴系统之上构建了三层缓存结构：缓存（Cache）→ Slab → 对象（Object）。每个 Cache 管理一种固定大小的对象，每个 Slab 从伙伴系统申请连续物理页，内部划分为多个等大对象。

# slab_allocator_sim.py # Slab 分配器模拟：对象级缓存的分配与回收 from dataclasses import dataclass, field from typing import Optional @dataclass class SlabObject: """Slab 中的对象槽位""" index: int is_allocated: bool = False next_free: Optional[int] = None # 空闲链表指针 @dataclass class Slab: """Slab：从伙伴系统申请的连续页，划分为等大对象""" slab_order: int # 伙伴系统的阶（2^order 页） object_size: int # 单个对象大小（字节） objects: list[SlabObject] = field(default_factory=list) free_list_head: int = 0 # 空闲链表头索引 inuse_count: int = 0 # 已分配对象数 def __post_init__(self): # 计算可容纳的对象数量 slab_size = 4096 * (2 ** self.slab_order) usable = slab_size - 16 # 预留 Slab 管理元数据 obj_count = usable // self.object_size # 初始化空闲链表 self.objects = [] for i in range(obj_count): next_idx = i + 1 if i + 1 < obj_count else None self.objects.append(SlabObject(index=i, next_free=next_idx)) self.free_list_head = 0 if obj_count > 0 else -1 @property def is_full(self) -> bool: return self.free_list_head == -1 or self.free_list_head is None @property def is_empty(self) -> bool: return self.inuse_count == 0 def alloc(self) -> Optional[int]: """从空闲链表分配一个对象""" if self.is_full: return None idx = self.free_list_head obj = self.objects[idx] obj.is_allocated = True self.free_list_head = obj.next_free obj.next_free = None self.inuse_count += 1 return idx def free(self, idx: int): """释放对象，挂回空闲链表头部""" obj = self.objects[idx] if not obj.is_allocated: return obj.is_allocated = False obj.next_free = self.free_list_head self.free_list_head = idx self.inuse_count -= 1 @dataclass class SlabCache: """Slab 缓存：管理同类型对象的 Slab 集合""" name: str object_size: int slab_order: int = 0 # 默认 1 页（order=0） partial_slabs: list[Slab] = field(default_factory=list) # 部分满 full_slabs: list[Slab] = field(default_factory=list) # 全满 empty_slabs: list[Slab] = field(default_factory=list) # 全空 def alloc(self) -> Optional[tuple[Slab, int]]: """分配对象：优先从 partial slab 分配""" # 优先级：partial > empty > 新建 target_slab = None if self.partial_slabs: target_slab = self.partial_slabs[0] elif self.empty_slabs: target_slab = self.empty_slabs.pop(0) else: # 从伙伴系统申请新 Slab target_slab = Slab( slab_order=self.slab_order, object_size=self.object_size, ) idx = target_slab.alloc() if idx is None: return None # 更新 Slab 所在列表 if target_slab.is_full: if target_slab in self.partial_slabs: self.partial_slabs.remove(target_slab) self.full_slabs.append(target_slab) elif target_slab not in self.partial_slabs: self.partial_slabs.append(target_slab) return target_slab, idx def free(self, slab: Slab, idx: int): """释放对象：处理 Slab 状态迁移""" was_full = slab.is_full slab.free(idx) if was_full: self.full_slabs.remove(slab) self.partial_slabs.append(slab) elif slab.is_empty: # 空 Slab 保留在 empty 列表中，避免频繁申请释放 self.partial_slabs.remove(slab) self.empty_slabs.append(slab) # 限制空 Slab 数量，防止内存浪费 if len(self.empty_slabs) > 2: self.empty_slabs.pop(0)

四、伙伴系统与 Slab 的协作权衡

4.1 分配延迟与内存利用率的矛盾

伙伴系统的分配延迟取决于分裂深度。最坏情况下，一个 order=10（4MB）的块需要分裂 10 次才能满足 order=0（4KB）的请求。Slab 分配器通过预分配对象缓存，将小对象的分配延迟从 O(log N) 降至 O(1)，但代价是预分配的内存可能长时间不被使用。

4.2 调优参数与生产实践

禁用场景：在内存极度受限的嵌入式设备（< 64MB）上，Slab 预分配可能导致内存不足。此时应使用 SLOB 分配器（线性分配器），牺牲性能换取更低的内存开销。

五、总结

伙伴系统通过 2 的幂次方分裂合并解决了外部碎片问题，Slab 分配器通过对象级缓存解决了小对象的内部碎片和分配延迟问题。两者协同构成了 Linux 内存管理的核心分配链路。调优时需关注 min_free_kbytes 和水位线参数，确保原子分配不会因内存不足而失败。在内存受限场景下，SLOB 是更合适的选择。理解伙伴系统与 Slab 的协作机制，是诊断内存分配延迟和碎片化问题的前提。