3. 内存分配算法

在RTOS中，动态内存分配并不只是“找一个空闲块”这么简单。任务栈、消息队列缓冲区、网络报文、DMA描述符、文件缓存等对象往往具有不同的大小分布、生命周期和实时性要求。分配算法决定了空闲块如何组织、如何查找、如何切分与合并，也直接决定了最坏分配时间、碎片形态和系统可预测性。本节围绕首次适应、最佳适应、伙伴系统和TLSF四类典型算法，分析其原理、数据结构、时间特性以及在RTOS中的适用边界。

一、核心原理：四种算法的空闲块组织方式

首次适应（First Fit）维护一条按地址排序的空闲链表。分配时从链表头开始扫描，找到第一个容量不小于请求大小的空闲块，若块较大则切分，剩余部分留在链表中。释放时按地址插入并尝试与前后相邻空闲块合并。它的优点是实现简单、释放合并直观；缺点是低地址区域容易被反复切分，形成大量小碎片，后续大请求可能长时间扫描仍无法满足。

最佳适应（Best Fit）同样使用空闲链表，但要求遍历整条链表，选择容量最接近请求大小的空闲块。理论上它能减少大块被切碎的概率，但代价是每次分配都要全表扫描，最坏时间随空闲块数量线性增长。更严重的是，它容易留下大量极小且难以再利用的“边角料”，在长期运行中反而加剧外部碎片。

伙伴系统（Buddy System）把内存按2的幂次划分。请求大小向上取整到2的幂，系统在对应阶的空闲链表中查找；若没有，则向更高阶申请并不断二分，直到得到合适块。释放时检查“伙伴块”是否空闲，若空闲则合并并继续向上递归。伙伴系统的分配与合并次数有明确上界，适合需要可预测性的场景，但内部碎片明显：请求65字节会占用128字节块，且只能按2的幂切分。

TLSF（Two-Level Segregated Fit）采用两级索引：第一级按2的幂划分大小区间，第二级在每个区间内再等分，用位图记录非空链表。分配时通过位图快速定位到满足请求的最小非空链表，通常只需常数级或接近常数级的查找；释放时同样按地址合并相邻空闲块。TLSF在分配速度、碎片控制和确定性之间取得较好平衡，因此被许多RTOS和嵌入式中间件采用。

二、方法流程：从请求到释放的关键步骤

无论采用哪种算法，一次完整分配通常包含以下阶段：请求大小对齐、查找可用块、切分或整块返回、更新元数据；释放则包含校验、标记空闲、合并相邻块、更新索引。差异主要体现在“查找”和“合并”两个环节。

• 首次适应：从链表头顺序扫描，命中即返回；释放时按地址插入并检查前后合并。
• 最佳适应：遍历全部空闲块，记录最小满足块；释放合并逻辑与首次适应类似，但查找代价更高。
• 伙伴系统：请求大小向上取整到2的幂，从对应阶查找；无可用块则向高阶申请并二分；释放时检查伙伴地址是否空闲，递归合并。
• TLSF：根据请求大小计算一级和二级索引，通过位图找到非空链表；释放时按物理地址合并相邻块，并更新两级位图。

三、案例场景：不同RTOS配置下的选择

假设一个Cortex-M4 RTOS系统，RAM为128KB，运行Modbus从站、CAN报文收发和日志缓存。若直接使用首次适应，长时间运行后可能出现大量16B、24B的小空闲块，而网络报文需要512B连续空间时分配失败。此时可改用TLSF：请求512B时，一级索引定位到512～1024B区间，二级索引快速找到最接近的可用块，分配时间稳定在微秒级。

若系统使用FreeRTOS的heap_4方案，其本质是首次适应加相邻合并，适合中小规模、分配模式较固定的场景。若使用heap_5或支持多内存区域的方案，则可在不同区域上应用类似伙伴或TLSF的策略。对于需要DMA连续缓冲区的场景，伙伴系统的2的幂对齐反而有利，因为DMA常要求地址和大小对齐；但若请求大小与2的幂差距大，内部碎片会浪费内存。

/* TLSF风格分配伪代码：两级索引定位 */
size_t req = 300;                     /* 请求300字节 */
int fl = tlsf_fls(req);               /* 一级：2的幂区间 */
int sl = (req >> (fl - SL_INDEX)) & SL_MASK; /* 二级：线性等分 */
uint32_t map = tlsf->sl_bitmap[fl] & (~0U << sl);
if (map == 0) {
    map = tlsf->fl_bitmap & (~0U << (fl + 1));
    fl = tlsf_ffs(map);
    map = tlsf->sl_bitmap[fl];
}
sl = tlsf_ffs(map);
block = tlsf->blocks[fl][sl];         /* 命中最小可用块 */

四、误区与复盘：算法选择中的常见问题

综合来看，首次适应适合资源受限、分配模式简单的轻量RTOS；最佳适应在通用系统中较少单独用于RTOS；伙伴系统适合对对齐和确定性有要求的场景；TLSF则在分配速度、碎片控制和实现复杂度之间取得了较好的工程平衡，是当前RTOS动态内存管理中值得优先评估的方案。实际选型时，应结合最坏分配时间、碎片容忍度、内存规模和验证成本综合判断，而不是仅看平均性能。