4. RTOS内存管理机制
内存碎片化，是RTOS里最让人头疼的问题之一。你想想看，系统跑着跑着，明明剩余内存总量还够，但就是分配不出一个连续的大块——这就是外部碎片在作祟。伙伴算法（Buddy System），正是为了解决这个问题而生的。
我个人习惯把伙伴算法看作一种「以空间换时间」的经典策略。它不像动态分区那样需要复杂的内存整理，也不像固定分区那样死板。它的核心思想很简单：把内存按2的幂次方切块，合并时也只跟大小相同的邻居合并。
4.1 伙伴算法的基本原理
说白了，伙伴算法维护了一个空闲块链表数组，每个链表对应一种大小的块。比如2^0、2^1、2^2……一直到2^n。分配时，从刚好能满足需求的块开始找；找不到就向上找更大的块，然后一分为二。释放时，检查它的「伙伴」是否空闲，如果是，就合并成一个更大的块。
这里有个关键问题：什么是「伙伴」？
两个块互为伙伴，必须满足三个条件：
- 大小相同
- 物理地址连续
- 由同一个大块分裂而来
举个例子。假设内存基址是0，一个大小为64KB的块。它分裂成两个32KB的块，地址分别是[0, 32KB)和[32KB, 64KB)。这两个块就是伙伴。再往下，[0, 16KB)和[16KB, 32KB)也是伙伴。但[0, 16KB)和[32KB, 48KB)就不是——它们虽然大小相同、地址连续，但不是从同一个父块分裂出来的。
核心公式：给定一个大小为2^k的块，起始地址为addr，它的伙伴地址为：
buddy_addr = addr ^ (1 << k)这个异或操作，是伙伴算法最精妙的地方。一行代码就能找到伙伴，效率极高。
4.2 伙伴算法的数据结构
我见过不少RTOS内核的实现，数据结构大同小异。核心就两个东西：空闲链表数组和分配信息位图。
| 数据结构 | 作用 | 典型实现 |
|---|---|---|
| free_area[k] | 管理大小为2^k的空闲块链表 | 双向链表头节点数组 |
| map[k] | 记录每个大小为2^k的块是否被分配 | 位图，每一位对应一个块 |
| page_owner | 记录每个最小块的分配信息 | 数组或结构体指针 |
嗯，这里要注意。位图的大小取决于内存总量和最小块大小。如果总内存是1MB，最小块是1KB，那位图就需要1024位，也就是128字节。这点开销在RTOS里完全可以接受。
4.3 分配与释放的完整流程
咱们直接看代码。这是一个简化版的伙伴算法分配函数：
// 分配大小为 size 的内存块，返回起始地址
void *buddy_alloc(size_t size) {
int order = get_order(size); // 计算需要的阶数
int current = order;
// 从当前阶数开始，向上查找空闲块
while (current <= MAX_ORDER) {
if (!list_empty(&free_area[current])) {
// 找到空闲块，取出一个
struct buddy_block *block =
list_first_entry(&free_area[current],
struct buddy_block, list);
list_del(&block->list);
// 如果当前阶数大于需要的阶数，不断分裂
while (current > order) {
current--;
// 将块一分为二
struct buddy_block *buddy =
(struct buddy_block *)((uint8_t *)block + (1 << current));
// 把另一半加入空闲链表
list_add(&buddy->list, &free_area[current]);
// 更新位图
set_bit(current, block_index(block, current));
}
// 标记已分配
clear_bit(order, block_index(block, order));
return block;
}
current++;
}
return NULL; // 没有足够的内存
}释放的逻辑是对称的：
void buddy_free(void *addr, size_t size) {
int order = get_order(size);
struct buddy_block *block = (struct buddy_block *)addr;
// 尝试向上合并
while (order < MAX_ORDER) {
// 计算伙伴地址
struct buddy_block *buddy =
(struct buddy_block *)((uintptr_t)addr ^ (1 << order));
// 检查伙伴是否空闲且可合并
if (!buddy_is_free(buddy, order)) {
break; // 伙伴不空闲，停止合并
}
// 从空闲链表中移除伙伴
list_del(&buddy->list);
clear_bit(order, block_index(buddy, order));
// 合并：取两个块中地址较小的作为新块
if (buddy < block) {
block = buddy;
}
order++;
}
// 将合并后的块加入空闲链表
list_add(&block->list, &free_area[order]);
set_bit(order, block_index(block, order));
}避坑指南：我曾经在一个项目中，因为伙伴地址计算错误，导致释放时合并了不该合并的块，内存被踩得乱七八糟。排查了两天才发现，问题出在地址对齐上——伙伴算法要求所有块的起始地址必须是它大小的整数倍。如果你的内存池基址不是2的幂次对齐，那伙伴地址公式就不成立。
4.4 伙伴算法的优缺点分析
没有银弹。伙伴算法虽然经典，但也有它的短板。咱们客观地分析一下。
| 维度 | 评价 | 说明 |
|---|---|---|
| 分配速度 | O(log N) | 最多遍历MAX_ORDER次，通常MAX_ORDER=10~20 |
| 释放速度 | O(log N) | 合并操作最多向上递归MAX_ORDER次 |
| 内部碎片 | 最多50% | 分配513字节，实际占用1024字节，浪费近一半 |
| 外部碎片 | 几乎为零 | 合并机制保证了不会产生不可用的小碎片 |
| 内存开销 | 约1%~3% | 位图和链表节点开销，随内存增大比例降低 |
优点很明显：
- 分配和释放的时间确定性好，适合实时系统
- 外部碎片被彻底消除，不会出现「内存够但分不出」的情况
- 实现相对简单，代码量小，适合嵌入式环境
缺点也不容忽视：
- 内部碎片严重。这是最让人头疼的。你申请70字节，它给你128字节的块，浪费了58字节。如果系统里大量存在这种「小请求」，内存利用率会很低。
- 只能分配2的幂次大小。不能分配任意大小的块，灵活性受限。
- 合并延迟。释放时如果伙伴还没释放，就不能立即合并。这可能导致内存「看起来」很碎，虽然实际上可以合并。
注意：在实时性要求极高的场景下（比如中断处理函数中），伙伴算法的O(log N)复杂度可能还是偏高。我见过一些极端优化，把MAX_ORDER限制在8以内，这样最坏情况只有8次循环，但代价是最大可分配块变小了。
4.5 伙伴算法的可视化流程
光说理论不够直观。我画了一张图，展示一个64KB内存块从分配到释放的完整过程。
从这张图可以看得很清楚：伙伴算法的核心在于「分裂」和「合并」的对称性。分配时分裂，释放时合并。只要伙伴空闲，就不断向上合并，直到遇到已分配的块或达到最大阶数。
4.6 实际项目中的取舍
我在一个物联网网关项目里用过伙伴算法。当时设备只有256KB RAM，要同时跑TCP/IP协议栈、MQTT客户端和几个传感器驱动。一开始用伙伴算法，发现内部碎片太严重了——协议栈经常申请几十字节的缓冲区，但每次都拿到128字节的块，浪费率超过50%。
后来我做了个改进：在伙伴算法上层加了一个slab分配器，专门处理小对象（16字节、32字节、64字节）。大块内存（超过1KB）才走伙伴算法。这样既保证了外部碎片不增长，又把内部碎片降到了可接受的范围。
经验总结：伙伴算法最适合管理「大块内存」和「大小变化频繁」的场景。如果系统里小对象居多，建议配合slab或块分配器使用。别指望一个算法解决所有问题——好的架构师懂得组合使用。
4.7 伙伴算法的适用场景
说了这么多，到底什么时候该用伙伴算法？我列个清单：
- RTOS内核堆管理：FreeRTOS的heap_4.c用的就是伙伴算法的变体
- 连续内存分配器：比如DMA缓冲区、帧缓冲区的管理
- 虚拟内存管理：Linux内核的物理内存管理就基于伙伴算法
- 需要抗碎片的场景：系统长时间运行，不能重启，内存碎片必须可控
不适合的场景：
- 大量小对象分配（建议用slab或对象池）
- 内存极度紧张（内部碎片太奢侈）
- 需要分配任意大小（比如513字节这种）
嗯，最后说一句。伙伴算法虽然经典，但别把它神化。它只是一个工具，用对地方是利器，用错地方是累赘。理解它的原理和局限，比背下代码更重要。