4. 堆(Heap)管理算法详解：静态分配 vs 动态分配，实现一个简单的固定大小块分配器，分析碎片化问题
说到内存管理，很多嵌入式工程师第一反应就是「别用 malloc」。这个观点我理解，但不完全认同。我做过不少物联网终端和工业控制器项目，堆管理用得好，系统灵活度能上一个台阶；用得不好，三天两头死机。关键不在于用不用，而在于怎么用。
这一章，我们就把堆管理这件事彻底讲透。从静态分配和动态分配的本质区别，到亲手实现一个固定大小块分配器，再到碎片化问题的根源分析。嗯，内容不少，但都是硬货。
4.1 静态分配 vs 动态分配：到底差在哪？
先看一个最直观的对比。静态分配，说白了就是编译时就定死了。你写 int buffer[1024]，那 4KB 空间在链接阶段就锁死了。动态分配呢？运行时才决定要多大，用完了还能还回去。
| 对比维度 | 静态分配 | 动态分配 |
|---|---|---|
| 分配时机 | 编译/链接时 | 运行时 |
| 内存位置 | 全局区/栈 | 堆区 |
| 大小灵活性 | 固定，不可变 | 可变，按需分配 |
| 释放方式 | 自动（生命周期结束） | 手动（free） |
| 碎片化风险 | 无 | 有（尤其频繁分配释放时） |
| 确定性 | 高（执行时间可预测） | 低（分配时间不确定） |
| 适用场景 | 大小已知、生命周期明确 | 大小未知、需要灵活复用 |
我个人习惯是：能静态分配就静态分配。但有些场景你绕不开动态分配。比如通信协议栈里，报文长度是运行时才知道的；再比如多任务系统里，任务栈大小需要根据负载动态调整。这时候，你就得跟堆管理打交道了。
4.2 固定大小块分配器：从零开始实现
标准库的 malloc/free 为什么在嵌入式里不好用？原因很多：实现复杂、执行时间不确定、容易产生外部碎片。我早期一个项目就吃过这个亏——一个跑 Modbus 协议的网关，跑了两周后突然分配失败，查了半天是碎片把堆搞碎了。
从那以后，我倾向于用固定大小块分配器。思路很简单：把堆区预先切成若干个大小相同的块，分配时拿一块，释放时还回去。没有合并、没有分裂，时间复杂度 O(1)。
来看一个具体实现。我用的是空闲链表法：
/* 固定大小块分配器 */
#define BLOCK_SIZE 64 /* 每个块 64 字节 */
#define BLOCK_COUNT 32 /* 总共 32 个块 */
#define HEAP_SIZE (BLOCK_SIZE * BLOCK_COUNT)
static uint8_t heap[HEAP_SIZE];
static uint8_t free_list[BLOCK_COUNT];
static uint8_t next_free;
void block_alloc_init(void)
{
int i;
for (i = 0; i < BLOCK_COUNT - 1; i++) {
free_list[i] = i + 1;
}
free_list[BLOCK_COUNT - 1] = 0xFF; /* 链表结束标记 */
next_free = 0;
}
void *block_alloc(void)
{
void *ptr = NULL;
if (next_free != 0xFF) {
ptr = &heap[next_free * BLOCK_SIZE];
next_free = free_list[next_free];
}
return ptr;
}
void block_free(void *ptr)
{
uint8_t index;
if (ptr == NULL) return;
index = ((uint8_t *)ptr - heap) / BLOCK_SIZE;
free_list[index] = next_free;
next_free = index;
}
这段代码的核心逻辑就三件事：
- 初始化：把所有块串成一条空闲链表
- 分配：从链表头部取一个块，返回地址
- 释放：把块放回链表头部
你想想看，这个分配器没有遍历、没有排序、没有合并。每次分配和释放都是常数时间。对于实时系统来说，这个特性太重要了。
4.3 碎片化问题：为什么固定大小块也有坑？
你可能会问：固定大小块没有外部碎片，是不是就完美了？不是的。它会产生内部碎片。
内部碎片是什么？就是分配给你的块你没用完的那部分。比如块大小是 64 字节，你只存了 30 字节的数据，那剩下的 34 字节就浪费了。所有块加起来，浪费的总量就是内部碎片。
外部碎片呢？标准 malloc 那种才会产生。频繁分配释放不同大小的块，堆里会出现很多小空隙，每个空隙都不够用，但总和却很大。这就是外部碎片。
我画了一张图，把这两种碎片的关系说清楚：
核心结论：固定大小块分配器用「内部碎片」换「确定性」和「无外部碎片」。在实时嵌入式系统中，这个交换通常是值得的。
4.4 如何评估你的堆分配器？
选型的时候，我一般看四个指标：
- 分配/释放时间复杂度：是不是 O(1)？最坏情况会不会退化？
- 碎片化上限：最坏情况下会浪费多少内存？能不能算出来？
- 内存利用率：有效载荷占总堆大小的比例。
- 确定性：每次分配的时间是否可预测？
标准 malloc 在指标 1 和 4 上表现很差。固定大小块分配器在 1、2、4 上都很优秀，但指标 3 可能不高。如果你对内存利用率要求极高，可以考虑伙伴分配器（Buddy Allocator）或 slab 分配器，但实现复杂度会上升。
4.5 什么时候该用动态分配？
说了这么多动态分配的坑，那到底什么时候该用？我总结三个场景：
- 协议栈接收缓冲：报文长度不确定，用固定大小块池按需分配
- 任务/线程栈：RTOS 中任务栈大小需要动态创建时
- 配置数据存储：系统启动时从外部加载配置，大小不固定
但记住一条铁律：不要在中断里做动态分配。中断上下文要求极短执行时间，而任何分配器都可能触发内存整理或等待锁。我见过不止一个工程师在中断里调 malloc，然后系统随机死机——查都查不出来。
好了，这一章的内容就到这里。固定大小块分配器虽然简单，但它是理解更复杂分配器的基础。你把这个吃透了，后面讲伙伴分配器和 slab 分配器时，上手会快很多。