FreeRTOS 链表源码深度解析：从数据结构到调度内核的基石-拓冰建站

本篇文章所有代码基于 FreeRTOS Kernel V10.3.1，配套完整可运行的示例位于项目中 projects/02_list，使用 QEMU + STM32L475 平台仿真运行，基于VS Code的可视化在线调试方法可参考上篇文章告别硬件开发板，手把手教你零成本学习 FreeRTOS
本项目源码开源地址：https://gitcode.com/qingshan1206/easy-freertos

一、引言：为什么链表是 RTOS 的命脉？

当你调用xTaskCreate()创建任务，调用vTaskDelay()让任务等待，或者调度器在 tick 中断中切换任务时——所有这些操作的背后，都离不开同一个基础数据结构：双向循环链表。

在 FreeRTOS 中，链表被用来管理：

用途	对应列表
就绪任务	`pxReadyTasksLists[优先级]`
阻塞/延时任务	`xDelayedTaskList1`/`xDelayedTaskList2`
挂起任务	`xSuspendedTaskList`
空闲任务	`xTasksWaitingTermination`
软件定时器	`pxTimerList`

可以说，理解了 FreeRTOS 的链表，就掌握了理解调度内核的入口。

本文围绕projects/02_list中的 7 个演示，逐一拆解 FreeRTOS 链表的全部核心 API，并配合运行输出验证。

二、核心数据结构

2.1 链表节点：`ListItem_t`

structxLIST_ITEM{TickType_t xItemValue;// 节点的排序值structxLIST_ITEM*pxNext;// 指向下一个节点structxLIST_ITEM*pxPrevious;// 指向前一个节点void*pvOwner;// 指向"宿主"对象（如 TCB）structxLIST*pxContainer;// 指向所属的链表};typedefstructxLIST_ITEMListItem_t;

关键设计思想：

xItemValue—— 排序依据。就绪链表中用任务优先级，延时链表中用任务的唤醒时间点。
pvOwner 双向关联—— 节点知道自己属于哪个对象（Owner），Owner 反过来嵌入节点。TCB 结构体内部就嵌有一个ListItem_t。
pxContainer—— 节点知道自己在哪条链表里，这使得uxListRemove()可以不依赖链表指针，仅凭节点自身就能完成删除。

2.2 迷你节点：`MiniListItem_t`

structxMINI_LIST_ITEM{TickType_t xItemValue;structxLIST_ITEM*pxNext;structxLIST_ITEM*pxPrevious;};typedefstructxMINI_LIST_ITEMMiniListItem_t;

与ListItem_t相比去掉了pvOwner和pxContainer。仅用作链表的结尾标记，节省 RAM（不要小看节省的 8 字节，在 RAM 以 KB 计量的 MCU 上弥足珍贵）。

2.3 链表头：`List_t`

typedefstructxLIST{UBaseType_t uxNumberOfItems;// 节点计数ListItem_t*pxIndex;// 遍历游标MiniListItem_t xListEnd;// 结尾标记节点}List_t;

2.4 结构关系总览

用下图展示三个核心数据结构的关系：

初始化后，xListEnd.pxNext和xListEnd.pxPrevious都指向自身 —— 这是空链表的标志。

三、链表初始化：`vListInitialise`

voidvListInitialise(List_t*constpxList){pxList->pxIndex=(ListItem_t*)&(pxList->xListEnd);pxList->xListEnd.xItemValue=portMAX_DELAY;pxList->xListEnd.pxNext=(ListItem_t*)&(pxList->xListEnd);pxList->xListEnd.pxPrevious=(ListItem_t*)&(pxList->xListEnd);pxList->uxNumberOfItems=0;}

初始化后的状态：

三个重点：

xListEnd.xItemValue = portMAX_DELAY—— 赋值为最大值，确保它在排序时永远在链表末尾。
pxNext = pxPrevious = &xListEnd—— 自环结构，表示空链表。
pxIndex = &xListEnd—— 遍历游标初始指向结尾标记。

演示 1 运行输出：

--- 演示1: vListInitialise --- listLIST_IS_INITIALISED: 是 listLIST_IS_EMPTY: 是 listCURRENT_LIST_LENGTH: 0

四、排序插入：`vListInsert`

这是 FreeRTOS 链表最核心的操作。

voidvListInsert(List_t*constpxList,ListItem_t*constpxNewListItem){ListItem_t*pxIterator;constTickType_t xValueOfInsertion=pxNewListItem->xItemValue;if(xValueOfInsertion==portMAX_DELAY){pxIterator=pxList->xListEnd.pxPrevious;}else{for(pxIterator=(ListItem_t*)&(pxList->xListEnd);pxIterator->pxNext->xItemValue<=xValueOfInsertion;pxIterator=pxIterator->pxNext){/* 遍历找到合适的位置 */}}pxNewListItem->pxNext=pxIterator->pxNext;pxNewListItem->pxNext->pxPrevious=pxNewListItem;pxNewListItem->pxPrevious=pxIterator;pxIterator->pxNext=pxNewListItem;pxNewListItem->pxContainer=pxList;(pxList->uxNumberOfItems)++;}

插入逻辑图解

假设依次插入：A(30) → B(10) → C(50) → D(20) → E(40)

排序规则核心：遍历时，条件pxIterator->pxNext->xItemValue <= xValueOfInsertion表示"继续向前走，直到下一个节点的值大于新值"。这意味着：

按值升序排列（小值在前）。
相同值时，新节点插入到所有相同值节点之后 —— FIFO 行为。

演示 2 运行输出：

--- 演示2: vListInsert (排序插入) --- 插入顺序: A(30) B(10) C(50) D(20) E(40) 预期结果: B(10) D(20) A(30) E(40) C(50) -- vListInsert 结果 (共 5 项) [0] B value=10 [1] D value=20 [2] A value=30 [3] E value=40 [4] C value=50 => 验证: 按 xItemValue 升序排列正确

五、相同值处理：FIFO 行为

当多个节点具有相同的xItemValue时，vListInsert将它们按插入顺序排列，先入先出（FIFO）。

// 循环条件 <= 保证了新节点插在所有 <= 自身值的节点之后pxIterator->pxNext->xItemValue<=xValueOfInsertion

演示 6 运行输出：

--- 演示6: 相同 value 的 FIFO 插入行为 --- 插入: A(50) B(50) C(50) D(30) 预期: D(30) -> A(50) -> B(50) -> C(50) -- 相同 value 插入结果 (共 4 项) [0] D30 value=30 [1] A50 value=50 [2] B50 value=50 [3] C50 value=50 => 同 value 按插入顺序 FIFO，值小的在前

重要影响：在就绪链表中，同优先级的任务按 FIFO 顺序被调度，这正是 FreeRTOS 的同优先级时间片轮转的实现基础。

六、尾部插入：`vListInsertEnd`

与vListInsert不同，vListInsertEnd不按值排序，而是将节点插入到pxIndex游标的当前位置之前（逻辑尾部）。

voidvListInsertEnd(List_t*constpxList,ListItem_t*constpxNewListItem){ListItem_t*constpxIndex=pxList->pxIndex;pxNewListItem->pxNext=pxIndex;pxNewListItem->pxPrevious=pxIndex->pxPrevious;pxIndex->pxPrevious->pxNext=pxNewListItem;pxIndex->pxPrevious=pxNewListItem;pxNewListItem->pxContainer=pxList;(pxList->uxNumberOfItems)++;}

插入位置图解

注意：pxIndex的初值就是xListEnd，所以第一次插入时vListInsertEnd的效果实际上等同于在列表末尾追加。但pxIndex会随着listGET_OWNER_OF_NEXT_ENTRY的遍历而移动。

演示 3 运行输出：

--- 演示3: vListInsertEnd (尾部插入) --- vListInsertEnd 保留插入顺序，不按 value 排序 -- vListInsertEnd 结果 (共 3 项) [0] X value=300 [1] Y value=200 [2] Z value=100 => 顺序: X(300) Y(200) Z(100) 与插入顺序一致

注意：X(300) 在 Y(200) 之前，而 Z(100) 在最后，完全保留了插入顺序，无视 value 大小。

七、删除操作：`uxListRemove`

删除是最简单的操作——因为节点自身保存了pxContainer指针，只要传入节点即可完成删除。

UBaseType_tuxListRemove(ListItem_t*constpxItemToRemove){List_t*constpxList=pxItemToRemove->pxContainer;pxItemToRemove->pxNext->pxPrevious=pxItemToRemove->pxPrevious;pxItemToRemove->pxPrevious->pxNext=pxItemToRemove->pxNext;if(pxList->pxIndex==pxItemToRemove){pxList->pxIndex=pxItemToRemove->pxPrevious;}pxItemToRemove->pxContainer=NULL;(pxList->uxNumberOfItems)--;returnpxList->uxNumberOfItems;}

删除过程图解

三个关键细节：

pxContainer自动清零—— 删除后节点不再认为自己属于任何链表。
pxIndex保护—— 如果删除的刚好是游标指向的节点，游标自动回退到前一个节点，防止遍历指针悬空。
返回值是有用信息—— 返回删除后链表中剩余节点的数量。

演示 4 运行输出：

--- 演示4: uxListRemove (删除链表项) --- -- 插入 5 个元素 (共 5 项) [0] A value=10 [1] B value=20 [2] C value=30 [3] D value=40 [4] E value=50 删除C(中间) 后剩余: 4 -- 删除C后 (共 4 项) [0] A value=10 [1] B value=20 [2] D value=40 [3] E value=50 删除A(头部) 后剩余: 3 -- 删除A后 (共 3 项) [0] B value=20 [1] D value=40 [2] E value=50 删除E(尾部) 后剩余: 2 -- 删除E后 (共 2 项) [0] B value=20 [1] D value=40 全部删除后 listLIST_IS_EMPTY: 是

八、辅助宏与工具函数

以下宏虽短，但贯穿了整个 FreeRTOS 源码。

宏	功能	调度器中的典型用法
`listSET_LIST_ITEM_VALUE`	设置节点的排序值	将延时任务的唤醒 tick 写入节点
`listGET_LIST_ITEM_VALUE`	读取节点的排序值	比较任务优先级或唤醒时间
`listSET_LIST_ITEM_OWNER`	设置节点的宿主指针	将 TCB 指针赋给节点
`listGET_LIST_ITEM_OWNER`	获取节点的宿主指针	遍历就绪链表获取待运行任务
`listGET_HEAD_ENTRY`	获取链表的第一个节点	获取最高优先级的就绪任务
`listGET_END_MARKER`	获取链表的结尾标记	遍历时判断是否走到末尾
`listGET_NEXT`	获取当前节点的下一个节点	遍历链表
`listLIST_IS_EMPTY`	判断链表是否为空	检查就绪链表是否有任务
`listCURRENT_LIST_LENGTH`	获取链表长度	调试/统计
`listIS_CONTAINED_WITHIN`	判断节点是否在指定链表中	验证任务状态一致性

容器检查

listIS_CONTAINED_WITHIN利用了节点中的pxContainer指针：

#definelistIS_CONTAINED_WITHIN(pxList,pxListItem)\((pxListItem)->pxContainer==(pxList))?pdTRUE:pdFALSE

演示 5 运行输出：

--- 演示5: listIS_CONTAINED_WITHIN (容器检查) --- 插入 listA: in A=是 in B=否 移除后: in A=否 pxContainer=NULL 插入 listB: in B=是

九、综合实战：模拟调度器就绪链表

演示 7 模拟了 FreeRTOS 调度器的核心行为——从就绪链表中按优先级取任务执行。

场景

4 个任务，优先级分别为：1（低）、2（中）、3（高）、2（中优先级2）

vListInsert(&readyList,&tasks[0].listItem);// 优先级 1vListInsert(&readyList,&tasks[1].listItem);// 优先级 2vListInsert(&readyList,&tasks[2].listItem);// 优先级 3vListInsert(&readyList,&tasks[3].listItem);// 优先级 2

就绪链表结构

运行输出：

--- 演示7: 综合 -- 模拟调度器就绪链表 --- 4 个任务按优先级(1/2/3/2)插入就绪链表 vListInsert 按 value 升序排列 -- 就绪链表 (共 4 项) [0] 低优先级 value=1 [1] 中优先级 value=2 [2] 中优先级2 value=2 [3] 高优先级 value=3 出队顺序 (升序，value 小先出): 出队: 低优先级 (value=1) 出队: 中优先级 (value=2) 出队: 中优先级2 (value=2) 出队: 高优先级 (value=3) 全部出队完毕

与真实调度器的对应关系

演示中的元素	真实 FreeRTOS 调度器
`DemoItem_t`嵌入`ListItem_t`	`TCB_t`嵌入`ListItem_t`（通过`xStateListItem`、`xEventListItem`）
`xItemValue`存储优先级	就绪链表`pxReadyTasksLists[pri]`中所有 TCB 的`xItemValue`相同
`vListInsert`升序排列	同优先级任务按 FIFO 插入，实现时间片轮转
`listGET_HEAD_ENTRY`取队首	`selectHighestPriorityTask()`获取最高优先级队列的第一个 TCB
`uxListRemove`出队	任务被调度运行后从就绪链表移除

十、总结

FreeRTOS 的链表设计处处体现着嵌入式系统 RAM 极度受限下的工程智慧：

双向循环链表—— 任意节点插入/删除都是 O(1) 时间复杂度，确定性对 RTOS 至关重要。
MiniListItem_t作为结尾标记—— 省去 2 个指针（8 字节），避免为结尾标记分配完整的ListItem_t。
pvOwner双向关联—— 链表节点 ↔ 宿主对象的"双向指针"，遍历时能直接从节点拿到 TCB。
pxContainer自包含删除—— 节点保存所属链表信息，uxListRemove不需要外部传入链表指针。
排序插入 FIFO——<=比较条件保证同值节点的先入先出行为。

掌握 FreeRTOS 链表，就等于拿到了阅读整个 FreeRTOS 内核源码的钥匙。无论你是想理解任务调度、延时机制，还是软件定时器、事件组，底层的链表操作逻辑始终如一。

参考资料

FreeRTOS Kernel V10.3.1 官方源码：freertos/include/list.h、freertos/list.c
本演示项目完整代码：projects/02_list/app/main.c
构建方式：cmake -S . -B build -DCMAKE_TOOLCHAIN_FILE=cmake/arm-none-eabi.cmake -DBUILD_PROJECT=02_list && cmake --build build

如果你觉得这篇文章有帮助，欢迎转发分享。