内存碎片整理算法全景解析

从碎片成因到整理原理，一次性掌握操作系统、JVM、Linux 内核中的关键算法

目录

  1. 什么是内存碎片？
  2. 内存碎片导致的真实问题
  3. 核心整理算法
    1. 内存紧缩 (Compaction)
    2. 伙伴系统 (Buddy System)
    3. Slab 分配器
    4. 标记-整理 (Mark-Compact)
    5. 复制式 GC (Copying GC)
    6. 内存池 (Memory Pool)
    7. Linux 页面迁移 / 内存规整
  4. 分配策略与碎片
  5. 各算法对比总览
  6. 实际场景应用
  7. 总结

1. 什么是内存碎片？

内存碎片是指内存中存在大量不连续的小空闲块，导致无法满足大块连续内存的分配请求——即便空闲内存总量足够。碎片分为两种：

外部碎片 (External Fragmentation)

空闲内存被已分配块切割成多个不连续的小块。总空闲量够，但没有一块足够大的连续区域。

最常见 危害最大

内部碎片 (Internal Fragmentation)

分配器给出的内存块大于实际请求大小，多出的部分在块内部被浪费。常见于固定大小分配。

分配器设计问题

用一个直观例子说明外部碎片：

总内存 = 100 MB ┌──────┬──────┬──────┬──────┬──────┐ │ 已用 │ 空闲 │ 已用 │ 空闲 │ 已用 │ │ 20MB │ 15MB │ 30MB │ 10MB │ 25MB │ └──────┴──────┴──────┴──────┴──────┘ 空闲总量 = 15 + 10 = 25 MB ⭢ 够用！ 但申请 20 MB 连续内存 ⭢ ❌ 失败！因为没有一块 ≥ 20MB 的连续空闲区域。

2. 内存碎片导致的真实问题

问题场景一览

场景表现根因
服务器 OOM 内存明明 80% 使用率，却分配大页 (2MB/1GB) 失败触发 OOM Killer 外部碎片，没有连续物理内存
Java Full GC 频繁 老年代没有大块连续空间，频繁触发 Full GC 仍无法满足分配 老年代碎片化，Mark-Compact 开销大
Redis 内存用满 mem_fragmentation_ratio > 1.5，实际数据只用了一半内存 jemalloc 分配器碎片
DMA / 网卡驱动失败 DMA 需要物理连续内存 (>4KB)，长时间运行后分配失败 物理内存碎片
数据库缓冲池抖动 Buffer Pool 频繁换入换出，吞吐骤降 无法分配大块共享内存

这些问题的核心矛盾："空闲总量"不等于"可用连续性"。碎片整理算法就是来解决这个矛盾的。

3. 核心整理算法

3.1 内存紧缩 (Memory Compaction)

经典算法 OS 内核

将所有已分配块向一端移动，使空闲空间汇聚成一块连续大区域。

整理前：┌──┬──┬──┬──┬──┬──┬──┐ │A │空│B │空│C │空│D │ └──┴──┴──┴──┴──┴──┴──┘ 整理后：┌──┬──┬──┬──┬──────────┐ │A │B │C │D │ 空闲区域 │ └──┴──┴──┴──┴──────────┘ （所有已分配块左移，空闲合并到右边）

原理：遍历所有已分配块，将它们向低地址移动，同时更新所有引用（指针）。整理后空闲区域在高端地址连续分布。

优点
  • 彻底消除外部碎片
  • 不改变对象数量
缺点
  • 需要移动数据，开销大
  • 必须更新所有指针引用
  • 移动期间需暂停业务

适用：嵌入式实时系统、早期操作系统、JVM Serial/Parallel Old GC 的 Mark-Compact 阶段。

3.2 伙伴系统 (Buddy System)

经典算法 Linux Kernel

以 2 的幂次为单位管理内存，分配时向上取整到最近的 2^k，释放时尝试与相邻"伙伴"合并还原成大块。

释放过程（假设总 16 页）： 释放块 A（4 页，地址 0~3） → 检查伙伴 B（4 页，地址 4~7）是否空闲 → 若空闲，合并为 8 页块（地址 0~7） → 继续检查更大的伙伴 … 分配过程： 申请 3 页 → 向上取整到 4 页 → 从 4 页空闲链表中取 若无 4 页块 → 分裂 8 页块 → 一半分出去，一半加入 4 页链表

Linux 中的实现：alloc_pages() / __free_pages() 使用 buddy system 管理物理页框。每个 zone 维护 free_area[] 数组，对应 order 0~10 的空闲链表。

优点
  • 分配/释放 O(log N)，非常快
  • 自动合并碎片
  • 最小内部碎片（最多浪费 50%）
缺点
  • 内部碎片：分配 65 页也要拿 128 页
  • 外部碎片仍然存在（小块无法合并）
  • 迁移类型分离只能缓解不能根治

适用：Linux 内核物理页框管理、用户态内存分配器（jemalloc、tcmalloc 的底层）。

3.3 Slab 分配器

Linux Kernel 缓存优化

为固定大小的内核对象（如 inode、dentry、task_struct）预分配缓存，按对象大小分类管理，从根本上避免外部碎片。

Slab 层次结构： Cache（如 inode_cache） ├─ Slab 1（1 个连续物理页，切分为 N 个 inode 槽位） │ 槽位：[used][used][free][used]… ├─ Slab 2 │ 槽位：[used][free][free][used]… └─ Slab 3 … 申请 inode → 从 partial/free slab 取第一个空闲槽位 释放 inode → 槽位标记为空闲，若整个 slab 全空则释放回 buddy

原理：大块内存（slab）被切成等大小槽位，分配只取一个槽位，释放只还一个槽位。slab 内部不存在外部碎片，因为所有槽位大小相同。slab 之间通过 buddy 分配——这也是 buddy 的典型使用场景。

Linux 三态：full（全部使用）→ partial（部分空闲）→ empty（全部空闲，可回收）。

优点
  • 零外部碎片（固定大小）
  • 极快 O(1) 分配/释放
  • CPU 缓存友好（对象聚集）
缺点
  • 只适用于固定大小对象
  • 内部碎片（64 字节对象浪费在 128 槽位）

3.4 标记-整理 (Mark-Compact)

GC 算法 JVM Serial/Parallel Old

先标记存活对象，再将其向一端移动，最后更新指针引用——是 Compact 思想在 GC 中的经典应用。

阶段 1 — 标记 (Mark)： 从 GC Roots 出发，标记所有可达对象。 [A✓][B][C✓][D][E✓]（✓ = 存活） 阶段 2 — 计算新地址 (Compute Forwarding)： 存活对象依次排列：A→0, C→1, E→2 阶段 3 — 移动 + 修引用 (Compact + Adjust)： [A][C][E][ 空闲区域… ]

JVM 中的体现：Serial Old GC 和 Parallel Old GC 都使用 Mark-Compact 回收老年代。CMS 在并发标记失败后也会退化为 Serial Old 做一次单线程 Compact——这是 CMS 的痛点之一。

优点
  • 消除碎片，老年代利用率高
  • 无内存浪费（不像 Copying 要一半预留）
缺点
  • 需要多次遍历堆，STW 时间长
  • 移动大对象开销高

3.5 复制式 GC (Copying / Semi-space GC)

GC 算法 JVM Young Gen

将堆等分为 From 和 To 两半，只在 From 中分配。GC 时把存活对象复制到 To 空间，然后交换角色。

GC 前： From ┌─A─┬───┬─B─┬─C─┬───┐（有碎片） └───┴───┴───┴───┴───┘ To ┌─────────────────────┐（全空） └─────────────────────┘ GC 后（复制 A、B、C 到 To）： From → 全清空（新 To） To ┌─A─┬─B─┬─C─┬─────────┐（紧凑排列，无碎片） └───┴───┴───┴─────────┘

JVM 中的应用：新生代（Young Generation）采用此算法。Eden + Survivor0 → Survivor1，每次 Minor GC 后存活对象被紧凑复制到 Survivor 区，天然无碎片。

优点
  • 天然消除碎片（复制即紧凑）
  • 分配极简单（bump pointer）
  • 回收时间 ∝ 存活对象数量
缺点
  • 浪费一半内存（或更多）
  • 存活对象多时复制成本高
  • 大对象不友好

3.6 内存池 (Memory Pool)

工程设计 应用层

预分配固定大小的大块内存，自行管理分配和回收。通过隔离不同大小的分配域来避免跨域碎片。

不同请求大小走不同池： Pool 32B ┌──┬──┬──┬──… (只分 32 字节对象) Pool 128B ┌──────┬──────┬──… Pool 512B ┌──────────────┬──… Pool 4KB ┌──────────────────────┬──… 释放回原池，不跨池，天然不产生碎片。

实际案例：Nginx 的连接池、MySQL 的 Query Cache、DPDK 的 mbuf pool、Redis 的 jemalloc（内部多个 size class 就是内存池）。

优点
  • 零外部碎片（同类大小）
  • 极快分配（freelist 头取）
  • 无系统调用开销
缺点
  • 需预估用量，预分配浪费
  • 不适合大小差异大的场景

3.7 Linux 页面迁移 / 内存规整 (Page Migration & Compaction)

Linux Kernel 高级特性

Linux 2.6.35+ 引入的原生内存规整机制，在线（不停止系统）地把可移动页面集中到一起，腾出连续大块物理内存。

规整过程： 1. 扫描 zone，标记两个扫描指针 migratescanner → 扫描可移动页 freescanner ← 扫描空闲页 2. 当两者相遇 → 触发页面迁移 可移动页 → 复制到空闲页区域 → 更新页表 3. 结果：可移动页集中到一边，形成连续大空闲块 ┌──────────────────┬──────────────────────┐ │ 可移动页面区域 │ 连续大块空闲（可做大页分配） │ └──────────────────┴──────────────────────┘

触发方式：

  • /proc/sys/vm/compact_memory → 手动触发全系统规整
  • 分配高阶页面（order ≥ 2）失败时，内核自动尝试规整
  • 透明大页 (THP) 的 khugepaged 后台线程持续规整

迁移类型分类（Anti-fragmentation）：Linux 将页面按迁移能力分为 UNMOVABLE（内核关键数据）、RECLAIMABLE（可回收）、MOVABLE（用户进程页）三类，分别放到不同的页块组中，从源头减少碎片产生。

优点
  • 在线整理，不停止系统
  • 支持透明大页
  • 迁移类型分组预防碎片
缺点
  • 内存拷贝开销
  • 不可移动页无法整理
  • 碎片严重时效果有限

4. 分配策略与碎片的关系

分配策略不直接整理碎片，但决定了碎片产生的速度和模式。

策略做法碎片表现适用
First Fit 找到第一个足够大的空闲块就分配 前端碎片严重，大块消失快 实现简单，一般场景
Best Fit 找到最小的足够大的空闲块分配 留下大量极小碎片，很难再利用 追求利用率（慎用）
Worst Fit 找到最大的空闲块分配 大块被逐渐切小，长期同样碎片化 较少使用
Next Fit 从上次分配位置继续搜索 碎片分布更均匀，尾部有空闲 改进 First Fit
Segregated Fit 按大小分多个链表，各管各的 同类大小间零碎片，跨类有碎片 jemalloc / tcmalloc

实际上现代分配器（jemalloc、tcmalloc）的核心思路：

分配请求 → 查 Size Class 表 → 定位对应 bin → 从 run 中取槽位 → 无空闲？向 buddy 申请新 run

这套机制融合了 Slab（固定槽位）+ Buddy（run 管理）+ Segregated Fit（多链表），是现代内存分配器对抗碎片的标准范式。

5. 各算法对比总览

算法解决什么原理开销适用层级
Compaction 外部碎片 移动所有块到一端 高（移动+更新指针） OS / GC
Buddy System 外部碎片 2^k 分裂与合并 低（O(log N)） 物理页管理
Slab 外部碎片（固定大小对象） 预切等大槽位 极低（O(1)） 内核对象
Mark-Compact GC 后碎片 标记→移动→修引用 高（STW） JVM 老年代
Copying GC GC 后碎片 复制存活对象到新空间 中（浪费内存） JVM 新生代
Memory Pool 应用层碎片 按大小隔离分配域 低 应用层
Page Migration 物理内存碎片 扫描 + 迁移可移动页 中（拷贝+TLB flush） Linux 内核
Segregated Fit 分配器碎片 多大小链表 + Bin 低 用户态分配器

6. 实际场景应用

场景 A：Java 服务 Full GC 频繁

症状：老年代使用率 70%，却频繁 Full GC，每次 GC 后使用率降幅不大。

诊断：老年代碎片化——Mark-Compact 开销大，CMS 退化为 Serial Old。

方案：

  • 换 G1 或 ZGC，其 Region 化 + 并发 Compact 减少碎片
  • 调大 -XX:CMSInitiatingOccupancyFraction，给碎片留余量
  • 减少大对象直接进入老年代（调 PretenureSizeThreshold）

场景 B：Linux 透明大页 (THP) 分配失败

症状：/proc/meminfo 中 thp_fault_fallback 持续增长。

诊断：物理内存碎片严重，没有连续 2MB 空闲块。

方案：

  • echo 1 > /proc/sys/vm/compact_memory 手动触发规整
  • 开启 khugepaged 后台规整
  • 启动时尽早分配大页（避免运行时碎片）

场景 C：Redis 内存碎片率高

症状：INFO memory 中 mem_fragmentation_ratio > 1.5。

诊断：频繁的 key 增删导致 jemalloc 内部 run 碎片化。

方案：

  • Redis 4.0+ 开启 activedefrag yes 主动碎片整理
  • Redis 7.0+ 默认开启，可调 active-defrag-threshold-lower
  • 重启实例（碎片率过高时的终极方案）

7. 总结

内存碎片整理的本质是"用时间（整理开销）换空间（连续性）"的交易。没有银弹，只有根据场景选对工具：

碎片问题 ── 按层级选择方案 ──→ ┌─ 应用层碎片 ──→ Memory Pool / Segregated Fit 分配器 │ ┌─ 语言运行时 ─┬─ 新生代碎片 ──→ Copying GC │ └─ 老年代碎片 ──→ Mark-Compact / G1 Mix GC / ZGC │ ├─ 内核对象 ────→ Slab 分配器 │ └─ 物理页框 ──┬─ 分配/释放 ──→ Buddy System └─ 大块连续 ──→ Page Migration + 迁移类型分组

关键结论：

  1. 预防重于治疗：好的分配策略（Segregated Fit、迁移分组）比事后整理更有效
  2. 分层解耦：应用层、运行时、OS 各有各的算法，不能互相替代
  3. 理解你的 workload：短生命周期对象用 Copying、长生命周期用 Compact、固定大小对象用 Pool
  4. 碎片不可避免：只要有动态分配和释放，碎片就会出现——关键是控制它在可接受范围内