Linux 内核的物理内存管理是经典的两级架构：伙伴系统（Buddy System）以页为单位管理大块连续内存，Slab 分配器在其之上为内核小对象提供缓存。本文用一个 160 行的 Python 模拟器完整复现两者的核心机制，用真实运行数据展示分裂、合并、外碎片与对象复用的全过程。

一、两级架构：为什么是伙伴 + Slab

内核面临两种截然不同的内存需求：

两级架构的分工逻辑是：伙伴系统解决『连续性』，Slab 解决『频率』。kmalloc 就是两者的粘合剂：大于约 8KB 的请求直接走伙伴系统，小请求走 Slab 的通用缓存（kmalloc-96、kmalloc-192 等 2 的幂次/常用尺寸阶梯）。

二、伙伴系统核心机制

伙伴系统把空闲页按 2^order 页的块组织，内核默认 order 范围 0~10（最大 4MB 连续块），每个 order 一条空闲链表：

伙伴系统的软肋是外碎片：空闲总页数充足、但没有足够大的连续块时，高阶分配照样失败。这是后面演示的重点。

三、Slab 分配器核心机制

Slab 在伙伴系统之上做对象级缓存：

四、完整可运行模拟器（Python 3，约 160 行）

下面的程序完整实现伙伴系统（分裂、异或找伙伴、级联合并、外碎片检测）和一个简化的 Slab 分配器（三态链表、对象复用、碎片统计）。场景设计为：1MB（256 页）内存上 6 次混合分配 → 释放两块 → 申请 64 页大块 → 演示合并受阻 → 触发级联合并 → 重试成功：

#!/usr/bin/env python3
"""伙伴系统 + Slab 分配器模拟：分裂、合并、外碎片与内碎片量化"""

PAGE = 4096
MAX_ORDER = 8          # 2^8 = 256 页 = 1MB

class Buddy:
    def __init__(self):
        self.free = {o: [] for o in range(MAX_ORDER + 1)}
        self.free[MAX_ORDER] = [0]   # 初始：一整块 256 页
        self.alloc_map = {}          # addr -> order

    def alloc(self, order):
        for o in range(order, MAX_ORDER + 1):
            if self.free[o]:
                addr = self.free[o].pop()
                while o > order:                    # 逐层分裂
                    o -= 1
                    self.free[o].append(addr + (1 << o))
                self.alloc_map[addr] = order
                return addr
        return None

    def free_blk(self, addr):
        order = self.alloc_map.pop(addr)
        while order < MAX_ORDER:
            buddy = addr ^ (1 << order)
            if buddy in self.free[order]:           # 伙伴空闲则合并
                self.free[order].remove(buddy)
                addr = min(addr, buddy)
                order += 1
            else:
                break
        self.free[order].append(addr)

    def stats(self):
        free_pages = sum(len(v) << o for o, v in self.free.items())
        big = [o for o in range(MAX_ORDER, -1, -1) if self.free[o]]
        largest_pages = (1 << big[0]) if big else 0
        return free_pages, largest_pages

    def dump(self):
        parts = []
        for o in range(MAX_ORDER + 1):
            if self.free[o]:
                parts.append('order%d:%d块' % (o, len(self.free[o])))
        return ' '.join(parts) if parts else '(无空闲块)'

print('=== 伙伴系统模拟（1MB = 256 页） ===')
b = Buddy()
seq = [('A', 4), ('B', 5), ('C', 3), ('D', 6), ('E', 2), ('F', 5)]
addrs = {}
for name, order in seq:
    a = b.alloc(order)
    addrs[name] = a
    print('alloc %s order%d (%d页) -> 起始页 %d'
          % (name, order, 1 << order, a))
fp, lp = b.stats()
print('6 次分配后: 空闲 %d 页, 最大连续 %d 页' % (fp, lp))
print('  空闲链表:', b.dump())

b.free_blk(addrs['B']); print('free B(32页) 后:', b.dump())
b.free_blk(addrs['E']); print('free E(4页)  后:', b.dump())
fp, lp = b.stats()
print('此时空闲 %d 页, 最大连续块 %d 页' % (fp, lp))
g = b.alloc(6)
print('alloc G order6(64页):',
      ('成功@页%d' % g) if g is not None else '失败')

b.free_blk(addrs['A'])
print('free A(16页) 后（伙伴被C占用，无法合并）:', b.dump())
fp, lp = b.stats()
print('空闲 %d 页, 最大连续块 %d 页' % (fp, lp))
g2 = b.alloc(6)
print('再申请 order6(64页):',
      ('成功@页%d' % g2) if g2 is not None
      else '失败 <-- 外碎片: 总空闲88页足够, 但无连续64页')

b.free_blk(addrs['C'])
print('free C(8页) 触发三级级联合并(8+8->16->32->64):',
      b.dump())
fp, lp = b.stats()
print('合并后空闲 %d 页, 最大连续块恢复为 %d 页' % (fp, lp))
g3 = b.alloc(6)
print('重试 order6(64页):',
      ('成功@页%d' % g3) if g3 is not None else '失败')

print()
print('=== Slab 分配器模拟（kmalloc-96, 每 slab 占 1 页） ===')
OBJ = 96
PER_SLAB = PAGE // OBJ
print('对象大小 %dB, 每 slab 容纳 %d 个对象, '
      '单 slab 内碎片 %dB (%.1f%%)'
      % (OBJ, PER_SLAB, PAGE - PER_SLAB * OBJ,
         (PAGE - PER_SLAB * OBJ) / PAGE * 100))

class Slab:
    def __init__(self):
        self.free_objs = list(range(PER_SLAB))

class Cache:
    def __init__(self):
        self.partial, self.full, self.empty = [], [], []
        self.ptr2slab = {}
        self.n = 0
    def alloc(self):
        if not self.partial:
            if self.empty:
                s = self.empty.pop()
            else:
                s = Slab(); self.n += 1
            self.partial.append(s)
        s = self.partial[0]
        obj = s.free_objs.pop()
        ref = id(s) * 1000 + obj
        self.ptr2slab[ref] = s
        if not s.free_objs:
            self.partial.remove(s)
            self.full.append(s)
        return ref
    def free_obj(self, ref):
        s = self.ptr2slab.pop(ref, None)
        if s is None:
            return
        was_full = not s.free_objs
        s.free_objs.append(-1)
        if was_full:
            self.full.remove(s)
            self.partial.append(s)
        if len(s.free_objs) == PER_SLAB:
            if s in self.partial:
                self.partial.remove(s)
            self.empty.append(s)

c = Cache()
refs = [c.alloc() for _ in range(100)]
print('分配 100 对象后: slab 总数=%d, full=%d, partial=%d, empty=%d'
      % (c.n, len(c.full), len(c.partial), len(c.empty)))
for r in refs[::2]:
    c.free_obj(r)
print('释放一半(50 个)后: full=%d, partial=%d, empty=%d'
      % (len(c.full), len(c.partial), len(c.empty)))
before = c.n
refs2 = [c.alloc() for _ in range(50)]
print('再分配 50 个: 新增 slab=%d（优先复用 partial/empty 链表）'
      % (c.n - before))
used = c.n * PAGE
live = 100 * OBJ
print('内存占用: slab 总内存=%dB, 有效载荷=%dB, 综合开销=%.1f%%'
      % (used, live, (used - live) / live * 100))

五、真实运行输出与解读

以上代码在 Python 3 下原样运行（无任何依赖），输出如下：

=== 伙伴系统模拟（1MB = 256 页） ===
alloc A order4 (16页) -> 起始页 0
alloc B order5 (32页) -> 起始页 32
alloc C order3 (8页) -> 起始页 16
alloc D order6 (64页) -> 起始页 64
alloc E order2 (4页) -> 起始页 24
alloc F order5 (32页) -> 起始页 128
6 次分配后: 空闲 100 页, 最大连续 64 页
  空闲链表: order2:1块 order5:1块 order6:1块
free B(32页) 后: order2:1块 order5:2块 order6:1块
free E(4页)  后: order3:1块 order5:2块 order6:1块
此时空闲 136 页, 最大连续块 64 页
alloc G order6(64页): 成功@页192
free A(16页) 后（伙伴被C占用，无法合并）: order3:1块 order4:1块 order5:2块
空闲 88 页, 最大连续块 32 页
再申请 order6(64页): 失败 <-- 外碎片: 总空闲88页足够, 但无连续64页
free C(8页) 触发三级级联合并(8+8->16->32->64): order5:1块 order6:1块
合并后空闲 96 页, 最大连续块恢复为 64 页
重试 order6(64页): 成功@页0

=== Slab 分配器模拟（kmalloc-96, 每 slab 占 1 页） ===
对象大小 96B, 每 slab 容纳 42 个对象, 单 slab 内碎片 64B (1.6%)
分配 100 对象后: slab 总数=3, full=2, partial=1, empty=0
释放一半(50 个)后: full=0, partial=3, empty=0
再分配 50 个: 新增 slab=0（优先复用 partial/empty 链表）
内存占用: slab 总内存=12288B, 有效载荷=9600B, 综合开销=28.0%

逐条解读这场演示：

六、理论分析

6.1 伙伴系统的复杂度与局限

分配与释放均为 O(MAX_ORDER)，即常数时间；异或定位伙伴避免了任何遍历。理论上伙伴系统的内碎片率上界为 50%（申请 2^k+1 页也分配 2^(k+1) 页），但页粒度分配下内碎片极少；真正的代价是外碎片。Knuth 在《计算机程序设计艺术》第一卷中证明：在随机分配/释放序列下，伙伴系统的内存利用率稳定在约 75% 左右——这与我们演示中『空闲 88/256 页却分配不出 64 页连续块』的现象相互印证。

6.2 Slab 的着色与对齐

真实内核的 Slab 还有一层本文模拟器未展开的优化：slab 着色（coloring）。不同 slab 内的对象故意错开起始偏移，让同一 cache 的不同对象落到不同的 CPU cache 组，降低冲突失效。着色消耗的就是内碎片的残余空间，是『废物利用』的经典设计。

6.3 从 SLAB 到 SLUB 再到 SLAB_TINY

原始 SLAB（Solaris 风格，Christopher 1988 设计）元数据复杂、每 CPU 队列层级深；SLUB（2008 年合入，2.6.24 起默认）砍掉了每 CPU 的 partial 队列和大量元数据，把 freelist 直接嵌在页内，锁竞争大幅下降；SLOB 面向嵌入式。5.x 之后内核持续推进 slab 元数据统一（struct slab），6.8 起 SLAB 已被移除，SLUB 成为唯一实现。理解本文的三态链表模型，再看 SLUB 源码只需补上 per-cpu 指针（c->page）和无锁 freelist（cmpxchg）两个概念。

七、工程应用

八、常见误区

九、参考文献

  1. D. Knuth (1997). The Art of Computer Programming, Vol. 1: Fundamental Algorithms (3rd ed.), §2.5 Dynamic Storage Allocation. Addison-Wesley.
  2. J. Bonwick (1994). The Slab Allocator: An Object-Caching Kernel Memory Allocator. USENIX Summer Technical Conference.
  3. C. Lameter (2007). SLUB: The unqueued slab allocator. Linux kernel documentation (Documentation/vm/slub.rst).
  4. M. Gorman (2004). Understanding the Linux Virtual Memory Manager. Prentice Hall. （开放电子版，伙伴系统章节为公认最佳阐释）
  5. W. Mauerer 著，郭旭译. 专业 Linux 内核架构（Professional Linux Kernel Architecture）第 3 章：内存管理。
← 返回文章列表