illegalCreed

中文

English

中文

English

Appearance

伙伴系统与 Slab 分配 ​

基于通用操作系统概念 · 核于 2026-08

速查 ​

  • 伙伴系统（Buddy System）：把空闲内存按 2 的幂次组织成多个大小档（1, 2, 4, 8, ... 页）。分配 17KB → 找最近的 2 的幂 = 32KB；释放时若伙伴块（同大小、相邻）也空闲则合并成上一档，递归向上。
  • 伙伴（Buddy）：每个块都有一个同大小且相邻的"伙伴"。两个伙伴都空闲时合并成 2 倍的大块。伙伴关系由地址确定（块地址 XOR 块大小）。
  • 分配/释放复杂度 O(log n)：从某档找不到就分裂上一档（最多分裂 log n 次），释放合并也最多 log n 次——比首次适应 O(n) 快。
  • 代价：内部碎片。要 17KB 给 32KB，浪费约 47%（向上取整到 2 的幂）。最坏接近 50%。
  • slab 分配（Slab Allocator）：Linux 内核为频繁创建/销毁的同类型小对象（inode、task_struct、sk_buff、file）维护预构造好的对象池，分配时直接从池里取一个已初始化的对象，O(1)。
  • slab 三态：满（全在使用）、半满（部分空闲）、空（全空闲，可释放回伙伴系统）。每个 slab 是连续的一页或几页。
  • slab 解决的痛点：①小对象反复构造/析构开销大（初始化比分配本身还贵）；②伙伴系统对小对象内碎片严重（要 64B 给 4KB）。slab 池化复用消除两者。
  • 缓存着色（Cache Coloring）：slab/伙伴系统会让 slab 起始地址错开 L1 缓存行偏移，避免同类对象总落在同一缓存行造成冲突缺失。
  • Linux 三层分配：物理页（伙伴系统，alloc_pages）→ 大块（kmalloc/vmalloc）→ 小对象（slab/slob/slub）。kmalloc 小块走 slab，整页走伙伴。
  • slub/slob：slab 的现代变体——slub（默认，更简单更省元数据）、slob（极小嵌入式，给 tiny 系统）。
  • 非连续分配引入：连续分配（含伙伴/slab）都在分配连续物理内存；要支持换页/大于物理内存的地址空间，需把进程打散到不连续页框（分页/分段），靠页表翻译——这是下一叶主题。

一、伙伴系统：2 的幂次的优雅 ​

伙伴系统（Buddy System）是物理页框分配的经典算法，思想是所有块大小都是 2 的幂，用分裂与合并维持：

分配 17KB（要 32KB = 2^5）：

  初始空闲档：           分裂过程：
  64KB ──[整块]          64KB
                              └─分裂→ 两个 32KB 伙伴
                                        ├── 32KB(A) ← 分配给请求
                                        └── 32KB(B) 留作空闲
  • 分配：请求 size 向上取整到 2 的幂 = k。若第 k 档有空闲块，直接取；否则找上一档（k+1），分裂成两个 k（互为伙伴），取一个，另一个挂回第 k 档；若 k+1 也没有就再往上一档找……最多走 log n 档。
  • 释放：释放块 A（大小 k）。查它的伙伴 B（地址 = A 地址 XOR k）。若 B 空闲 → 合并成大小 2k 的大块，递归向上继续与伙伴合并；若 B 被占用 → A 挂回第 k 档，结束。
  • 伙伴怎么找：地址按块大小对齐，伙伴地址 = 块地址 XOR 块大小。例如大小 32KB 的块，地址 0x10000 的伙伴是 0x10000 XOR 0x8000 = 0x18000。
  • 复杂度：分配/合并都是 O(log n)（最多分裂/合并 log n 次），远快于首次适应的 O(n) 扫描。
  • 优点：①快（O(log n)）；②合并高效（伙伴关系确定，不用扫链表找邻居）；③外碎片可控（能合并的就合并）。
  • 缺点：内部碎片。向上取整到 2 的幂，请求 17KB 给 32KB（浪费 15KB ≈ 47%）；请求 33KB 给 64KB（浪费 31KB ≈ 48%）。最坏近 50%。所以伙伴系统适合分配较大的块（页框级别），不适合零碎小对象——那是 slab 的舞台。

二、slab 分配：内核对象池 ​

Linux 内核运行时频繁创建/销毁大量同类型小对象——打开一个文件就创建 inode、file、dentry；收一个网络包就分配 sk_buff；起一个进程就 task_struct。这些对象：①小（几十到几百字节）；②构造/析构开销大（要初始化一堆字段、加锁、链表）；③生命周期短。直接用伙伴系统分配有两个灾难：①内碎片（要 64B 给 4096B 一页）；②反复初始化（每次新分配都要构造，比分配本身还贵）。

slab 分配器的解法是池化复用：

   slab 缓存（如 inode_cache）
  ┌─────────────────────────────────┐
  │ slab1（满）  slab2（半满）  slab3（空）│
  │ ┌──┬──┬──┐ ┌──┬  ┬  ┐ ┌  ┬  ┬  ┐│
  │ │i1│i2│i3│ │i4│空│空│ │空│空│空││  ← 每个"空"是一个已析构的可用对象
  │ └──┴──┴──┘ └──┴  ┴  ┘ └  ┴  ┴  ┘│
  └─────────────────────────────────┘
   分配 inode：从 slab2 取一个"空"，O(1)（无需重新构造，复用已初始化结构）
   释放 inode：归还回 slab，标记可用（不真析构，下次直接用）
  • 预构造：slab 缓存建立时，预先构造好一批对象（初始化字段、建链表），存进 slab。分配时直接取一个已构造好的——省掉初始化开销。
  • 复用：释放时不真析构，标记为可用，下次分配直接复用——构造/析构开销分摊到多次复用上。
  • slab 三态：满（对象全占用）、半满（部分空闲，分配/释放的主战场）、空（全空闲，可整块释放回伙伴系统省内存）。
  • 复杂度：分配/释放 O(1)（从池里取/放回，无搜索、无构造）。
  • kmalloc：Linux 通用内核内存分配接口，小块走 slab（按大小分档的通用缓存 kmalloc-32/64/128...），大块走伙伴系统。
  • slub / slob：slab 的演进。slub（Linux 2.6.23 起默认）更简单、元数据更省、多核扩展性更好；slob 给极小嵌入式系统（省代码体积）。三者 API 一致（kmalloc/kfree），内核配置选一。

三、伙伴系统与 slab 协同 ​

Linux 内存分配是分层的，伙伴系统与 slab 各管一摊：

   请求大小
     │
     ├─ 大块（整页/几页） ──> 伙伴系统 alloc_pages（O(log n)，连续物理页）
     │
     ├─ 小对象（已知类型，如 inode） ──> 专用 slab 缓存（O(1)，池化复用）
     │
     └─ 小块（通用，如临时 100B） ──> kmalloc → 通用 slab 缓存（O(1)）
  • 伙伴系统管物理页框（4KB 起），是物理内存的最终分配者；slab 缓存本身也是向伙伴系统要页来建池。
  • slab 管页内小对象，把一页或几页切成定长对象槽，池化复用。
  • vmalloc：要一大段虚拟连续但物理不连续的内存（用于大缓冲区），用页表把散页映射成连续虚拟地址——这是非连续分配在内核的应用。

四、从连续到非连续：下一叶引子 ​

到这里，本叶讲的所有方案（固定/动态分区、伙伴系统、slab）分配的都是连续物理内存。但连续分配有根本限制：①进程必须连续驻留才能运行（外碎片难治）；②进程地址空间受限于物理内存大小（无法换页）。

非连续分配打破这个限制——把进程的逻辑地址空间打散映射到不连续的物理页框：

  • 分页（Paging）：逻辑空间切成固定大小的页，物理内存切成同样大小的页框，靠页表映射。进程无需连续，外碎片归零；支持换页（虚拟内存）。代价是页表存储与 TLB。
  • 分段（Segmentation）：按程序的逻辑段（代码/数据/栈）切成大小可变的段，分别映射。反映程序结构，但仍有外碎片。
  • 段页式：先分段再分页，兼得两者。

分页/分段/虚拟内存/缺页/页面置换是下一叶的主题——本叶的连续分配与伙伴/slab 是它们的物理层基础。

下一步 ​

掌握了连续分配、伙伴系统与 slab 后，下一站进入非连续分配——分页、分段与虚拟内存讲透页表机制、TLB、缺页中断、页面置换算法，理解进程如何突破物理内存限制。