FreeRTOS 源码学习：彻底吃透 list.h 与 list.c

前言

学习 FreeRTOS 内核源码时，list.h和list.c是绕不开的基础。

FreeRTOS 中的就绪链表、延时链表、挂起链表，以及队列、信号量的任务等待链表，底层都使用同一套链表实现。

理解这部分代码后，很多调度器相关问题都会变得清晰：

• 任务如何进入就绪链表？
• 延时任务为什么按照唤醒 Tick 排序？
• 队列和信号量为什么优先唤醒高优先级任务？
• 一个 TCB 为什么需要两个链表节点？
• pxIndex为什么不是简单的头指针？
• portMAX_DELAY为什么需要特殊处理？

本文基于 FreeRTOS Kernel V10.3.1

一、先建立一个核心认识

FreeRTOS 链表中存放的并不是 TCB 本身，而是嵌入 TCB 内部的链表节点。

一个任务控制块中包含两个节点：

typedef struct tskTaskControlBlock { volatile StackType_t *pxTopOfStack; ListItem_t xStateListItem; ListItem_t xEventListItem; UBaseType_t uxPriority; /* 其他成员省略 */ } TCB_t;

它们的职责不同：

可以把它们理解为 TCB 上的两个“挂钩”。

• xStateListItem表示任务当前处于什么状态。
• xEventListItem表示任务正在等待什么事件。

二、三个核心数据结构

1. ListItem_t：完整链表节点

ListItem_t定义如下：

struct xLIST_ITEM { TickType_t xItemValue; struct xLIST_ITEM *pxNext; struct xLIST_ITEM *pxPrevious; void *pvOwner; struct xLIST *pxContainer; }; typedef struct xLIST_ITEM ListItem_t;

各成员作用如下。

pvOwner 有什么作用？

链表中保存的是ListItem_t，但调度器最终需要得到任务的 TCB。

因此，任务创建时会建立节点到 TCB 的反向关系：

listSET_LIST_ITEM_OWNER( &(pxNewTCB->xStateListItem), pxNewTCB ); listSET_LIST_ITEM_OWNER( &(pxNewTCB->xEventListItem), pxNewTCB );

这样，从链表节点就可以快速找到对应的任务：

pxTCB = listGET_LIST_ITEM_OWNER(pxListItem);

pxContainer 有什么作用？

pxContainer记录节点当前位于哪个链表。

因此删除节点时，只需要传入节点本身：

uxListRemove(&pxTCB->xStateListItem);

uxListRemove()可以通过：

pxItemToRemove->pxContainer

直接找到所属链表，不需要额外遍历。

2. MiniListItem_t：精简版链表节点

MiniListItem_t定义如下：

struct xMINI_LIST_ITEM { TickType_t xItemValue; struct xLIST_ITEM *pxNext; struct xLIST_ITEM *pxPrevious; }; typedef struct xMINI_LIST_ITEM MiniListItem_t;

它只保留了：

• xItemValue
• pxNext
• pxPrevious

而没有：

• pvOwner
• pxContainer

因为它不代表真实任务，只用作链表的结束标记。

MiniListItem_t的前三个成员与ListItem_t保持相同布局，因此内核可以在只访问这三个字段时，将它转换为ListItem_t使用。

这样既实现了统一操作，又节省了 RAM。

3. List_t：链表管理结构

List_t定义如下：

typedef struct xLIST { volatile UBaseType_t uxNumberOfItems; ListItem_t *pxIndex; MiniListItem_t xListEnd; } List_t;

三个成员的作用如下。

需要特别注意：

pxIndex不是链表头指针。

真正的头节点是：

pxList->xListEnd.pxNext

真正的尾节点是：

pxList->xListEnd.pxPrevious

三、vListInitialise：初始化链表

函数实现如下：

void vListInitialise(List_t * const pxList) { 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.pxNext == &xListEnd xListEnd.pxPrevious == &xListEnd pxIndex == &xListEnd uxNumberOfItems == 0

虽然链表中已经存在xListEnd，但它只是哨兵，不属于真实节点，所以：

uxNumberOfItems == 0

四、xListEnd 的作用

xListEnd是一个嵌入List_t内部的哨兵节点。

它主要有四个作用。

1. 统一空链表和非空链表操作

空链表也是一个完整的双向循环结构：

xListEnd ⇄ xListEnd

插入和删除时不需要反复判断：

if (head == NULL)

也不需要单独处理头节点或尾节点。

2. 标记链表末尾

初始化时：

xListEnd.xItemValue = portMAX_DELAY;

portMAX_DELAY是TickType_t能表示的最大值。

由于普通节点按照xItemValue升序排列，xListEnd会自然位于最后。

3. 保存真实头尾指针

xListEnd.pxNext // 真实头节点 xListEnd.pxPrevious // 真实尾节点

4. 判断链表是否初始化

FreeRTOS 可以通过下面的条件进行简单判断：

pxList->xListEnd.xItemValue == portMAX_DELAY

五、vListInitialiseItem：初始化链表节点

函数实现很简单：

void vListInitialiseItem(ListItem_t * const pxItem) { pxItem->pxContainer = NULL; }

它只保证：

pxContainer == NULL

表示该节点当前不属于任何链表。

需要注意，它不会初始化：

xItemValue pxNext pxPrevious pvOwner

这些成员会在任务初始化或节点插入时设置。

因此，判断一个节点是否位于链表中，应该检查：

pxItem->pxContainer

而不是检查pxNext或pxPrevious。

六、vListInsertEnd：插入到轮转末尾

函数的核心代码如下：

void vListInsertEnd( List_t * const pxList, ListItem_t * const pxNewListItem) { ListItem_t * const pxIndex = pxList->pxIndex; pxNewListItem->pxNext = pxIndex; pxNewListItem->pxPrevious = pxIndex->pxPrevious; pxIndex->pxPrevious->pxNext = pxNewListItem; pxIndex->pxPrevious = pxNewListItem; pxNewListItem->pxContainer = pxList; pxList->uxNumberOfItems++; }

这里的“End”并不一定是物理链表尾部。

它实际上把新节点插入到：

pxIndex->pxPrevious 和 pxIndex 之间

即：

Previous ⇄ New ⇄ pxIndex

为什么要这样设计？

因为pxIndex是任务轮转游标，把新任务插到pxIndex前面，可以保证当前链表中的其他任务先获得执行机会。

FreeRTOS 的同优先级就绪任务正是通过这个函数加入就绪链表：

vListInsertEnd(&(pxReadyTasksLists[pxTCB->uxPriority]), &(pxTCB->xStateListItem));

七、pxIndex 为什么不是链表头？

pxIndex是链表遍历游标，而不是头节点指针。

相关宏如下：

#define listGET_OWNER_OF_NEXT_ENTRY(pxTCB, pxList) \ { \ pxList->pxIndex = pxList->pxIndex->pxNext; \ \ if (pxList->pxIndex == \ (ListItem_t *)&pxList->xListEnd) \ { \ pxList->pxIndex = \ pxList->pxIndex->pxNext; \ } \ \ pxTCB = pxList->pxIndex->pvOwner; \ }

每调用一次：

1. pxIndex移动到下一个节点。
2. 如果遇到xListEnd，就跳过哨兵。
3. 返回该节点的pvOwner。

假设某优先级就绪链表中有三个任务：

TaskA ⇄ TaskB ⇄ TaskC

连续调用后得到：

TaskA → TaskB → TaskC → TaskA → TaskB → TaskC

这就是同优先级时间片轮转的基础。

如果调度器每次都简单选择链表头，那么头节点对应的任务可能反复运行，其他同优先级任务得不到公平调度。

八、vListInsert：按照 xItemValue 排序插入

vListInsert()是链表中最值得深入分析的函数。

其核心查找代码如下：

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;

即在pxIterator和它的后继之间插入新节点：

插入前： Iterator ⇄ Next 插入后： Iterator ⇄ New ⇄ Next

实际是升序排列

循环条件是：

next->xItemValue <= new->xItemValue

只要下一个节点的值小于或等于新节点，就继续向后走。

最终结果是：

小值 → 大值 → xListEnd

也就是升序排列。

相同值如何处理？

因为条件中使用了<=，而不是<，所以遇到相同值时会继续向后遍历。

因此，新节点会插在已有同值节点之后，这会保留相同值节点的插入顺序，相当于同值节点之间保持 FIFO。

九、uxListRemove：从链表中删除节点

核心代码如下：

UBaseType_t uxListRemove( ListItem_t * const pxItemToRemove) { List_t * const pxList = 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--; return pxList->uxNumberOfItems; }

假设删除 B：

删除前： A ⇄ B ⇄ C

执行：

B->pxNext->pxPrevious = B->pxPrevious; B->pxPrevious->pxNext = B->pxNext;

得到：

删除后： A ⇄ C

如果pxIndex正好指向 B，则让它退回 B 的前驱：

pxIndex = B->pxPrevious;

这样下一次遍历时再执行：

pxIndex = pxIndex->pxNext;

就会正确移动到 B 原来的后继节点。

删除完成后：

pxItemToRemove->pxContainer = NULL; uxNumberOfItems--;

由于节点保存了pxPrevious、pxNext和pxContainer，整个删除过程不需要遍历链表，时间复杂度为 O(1)。

十、一个任务如何进入就绪链表？

FreeRTOS 为每个任务优先级维护一条独立的就绪链表：

List_t pxReadyTasksLists[configMAX_PRIORITIES];

本工程配置：

configMAX_PRIORITIES = 56

因此共有 56 条就绪链表：

pxReadyTasksLists[0] pxReadyTasksLists[1] ... pxReadyTasksLists[55]

其中优先级 0 最低，55 最高。

任务进入就绪态时：

vListInsertEnd( &(pxReadyTasksLists[pxTCB->uxPriority]), &(pxTCB->xStateListItem) );

因此：

• 任务优先级由进入哪条链表决定。
• 同一条就绪链表中的任务优先级相同。
• 就绪链表不需要按照xItemValue排序。
• 同优先级任务通过pxIndex实现轮转调度。

调度器先找到最高的非空就绪优先级，然后调用：

listGET_OWNER_OF_NEXT_ENTRY( pxCurrentTCB, &pxReadyTasksLists[uxTopPriority] );

从该优先级链表中轮流选择任务。

十一、延时任务为什么按照唤醒 Tick 排序？

任务调用延时或阻塞 API 后，内核计算它的绝对唤醒时间：

xTimeToWake = xTickCount + xTicksToWait;

随后将唤醒时间保存到：

pxCurrentTCB->xStateListItem.xItemValue

即：

listSET_LIST_ITEM_VALUE( &(pxCurrentTCB->xStateListItem), xTimeToWake );

再调用：

vListInsert( pxDelayedTaskList, &(pxCurrentTCB->xStateListItem) );

因为vListInsert()按升序排列，所以延时链表形成：

最早唤醒 → 较晚唤醒 → 最晚唤醒

例如：

TaskB：110 Tick TaskA：130 Tick TaskC：150 Tick

链表顺序为：

xListEnd ↓ TaskB(110) ↓ TaskA(130) ↓ TaskC(150) ↓ xListEnd

Tick 中断只需要检查链表头：

pxTCB = listGET_OWNER_OF_HEAD_ENTRY(pxDelayedTaskList);

如果头节点还没有到达唤醒时间，那么后面的任务必然也没有到期，可以立即停止检查。

这样就不需要每个 Tick 都扫描所有阻塞任务。

十二、为什么需要两条延时链表？

TickType_t会发生溢出。

本工程使用 32 位 Tick，最大值为：

0xFFFFFFFF

假设当前 Tick 已接近最大值：

xTickCount = 0xFFFFFFF0

任务延时 32 Tick：

xTimeToWake = 0xFFFFFFF0 + 32 = 0x00000010

唤醒时间发生了回绕。

如果所有任务都放在同一条升序链表中，0x00000010会排在普通任务前面，但它实际上属于下一轮 Tick 周期。

所以 FreeRTOS 使用两条延时链表：

xDelayedTaskList1; xDelayedTaskList2; pxDelayedTaskList; pxOverflowDelayedTaskList;

• 没有发生 Tick 回绕：进入当前延时链表。
• 唤醒时间发生回绕：进入溢出延时链表。
• xTickCount溢出后，交换两条链表。

这样，每条链表内部仍然可以使用简单的升序排序。

十三、为什么事件等待链表与任务优先级有关？

任务创建时，FreeRTOS 会设置：

xEventListItem.xItemValue = configMAX_PRIORITIES - uxPriority;

本工程最大优先级数量为 56。

例如：

任务优先级越高，事件节点值越小。

而事件链表使用vListInsert()升序排列，因此：

高优先级任务 → 低优先级任务

当队列、信号量等事件发生时，内核直接取事件等待链表的头节点：

pxUnblockedTCB = listGET_OWNER_OF_HEAD_ENTRY(pxEventList);

头节点就是等待该事件的最高优先级任务。

因此，队列或信号量可用时，FreeRTOS 会优先唤醒高优先级等待任务，而不是简单地按照任务进入等待状态的先后顺序唤醒。

如果多个等待任务优先级相同，它们的xItemValue也相同。由于vListInsert()会把新节点插在已有同值节点之后，所以相同优先级之间仍保持先来先服务。

十四、一个 TCB 为什么需要两个链表节点？

假设一个任务从空队列中接收数据，并设置了 100 Tick 超时。

这时，它需要同时表达两种关系：

关系一：我正在等待这个队列 关系二：我最迟在某个 Tick 超时

FreeRTOS 会执行：

vListInsert( &pxQueue->xTasksWaitingToReceive, &pxCurrentTCB->xEventListItem ); prvAddCurrentTaskToDelayedList( xTicksToWait, pdTRUE );

于是任务同时位于两条链表中：

xEventListItem └── 队列的 xTasksWaitingToReceive xStateListItem └── 延时链表

如果队列先收到数据：

1. 删除xEventListItem。
2. 删除延时链表中的xStateListItem。
3. 将xStateListItem加入就绪链表。

如果等待超时：

1. Tick 中断删除延时链表中的xStateListItem。
2. 检查xEventListItem是否仍在事件链表。
3. 如果仍在，则将其删除。
4. 将任务重新加入就绪链表。

由于一个ListItem_t只有一个pxContainer，它不可能同时属于两条链表。

因此，一个 TCB 必须有两个链表节点。

十五、三个节点插入顺序推演

假设三个节点的值为：

A.xItemValue = 30; B.xItemValue = 10; C.xItemValue = 30;

按下面的顺序插入：

vListInsert(&list, &A); vListInsert(&list, &B); vListInsert(&list, &C);

使用S表示xListEnd。

1. 初始状态

S ⇄ S uxNumberOfItems = 0 pxIndex = S

2. 插入 A(30)

S ⇄ A(30) ⇄ S

指针变化：

A.pxNext = S; S.pxPrevious = A; A.pxPrevious = S; S.pxNext = A;

数量变化：

uxNumberOfItems：0 → 1

pxIndex不变，仍然指向 S。

3. 插入 B(10)

由于：

10 < 30

B 插入 A 前面：

S ⇄ B(10) ⇄ A(30) ⇄ S

指针变化：

B.pxNext = A; A.pxPrevious = B; B.pxPrevious = S; S.pxNext = B;

数量变化：

uxNumberOfItems：1 → 2

pxIndex仍然不变。

4. 插入 C(30)

遍历过程：

B.xItemValue <= 30 成立 A.xItemValue <= 30 成立 S.xItemValue <= 30 不成立

因此 C 插在已有的 A 后面：

S ⇄ B(10) ⇄ A(30) ⇄ C(30) ⇄ S

指针变化：

C.pxNext = S; S.pxPrevious = C; C.pxPrevious = A; A.pxNext = C;

最终结果：

正向： S → B(10) → A(30) → C(30) → S 反向： S → C(30) → A(30) → B(10) → S

数量为：

uxNumberOfItems = 3

pxIndex仍然指向原来的节点 S。

十六、vListInsert 是否会改变 pxIndex？

不会。

vListInsert()只负责：

• 查找排序位置。
• 修改新节点和相邻节点的前后指针。
• 设置pxContainer。
• 增加uxNumberOfItems。

它不会修改：

pxList->pxIndex

因此，无论新节点插到头部、中间还是尾部，pxIndex都不会跟随插入位置移动。

vListInsertEnd()同样不会直接修改pxIndex，它只是读取pxIndex，然后把新节点插到pxIndex前面。

只有在删除节点时，如果被删除节点正好是pxIndex，uxListRemove()才会将pxIndex调整到被删除节点的前驱。

十七、portMAX_DELAY 为什么需要特殊处理？

vListInsert()中存在明确的特殊分支：

if (xValueOfInsertion == portMAX_DELAY) { pxIterator = pxList->xListEnd.pxPrevious; }

原因是：

xListEnd.xItemValue == portMAX_DELAY

如果新节点的值也是portMAX_DELAY，普通循环条件会变成：

xListEnd.xItemValue <= portMAX_DELAY

也就是：

portMAX_DELAY <= portMAX_DELAY

该条件永远成立。

由于链表是循环链表，遍历会越过xListEnd后继续循环，最终无法退出。

因此，当新节点值为portMAX_DELAY时，内核不再执行普通遍历，而是直接令：

pxIterator = xListEnd.pxPrevious;

把新节点插入到当前尾节点与xListEnd之间：

原尾节点 ⇄ New(portMAX_DELAY) ⇄ xListEnd

如果已经存在多个值为portMAX_DELAY的节点，新节点仍会插到它们后面，保持插入顺序。

还需要区分链表层和调度层的语义。

当任务允许无限期阻塞，并且等待时间为：

portMAX_DELAY

调度器通常不会把任务加入延时链表，而会将它加入挂起链表：

vListInsertEnd( &xSuspendedTaskList, &pxCurrentTCB->xStateListItem );

这样任务不会因为 Tick 到期而被唤醒，只能由事件、通知或恢复操作解除阻塞。

十八、五个核心函数总结

总结

理解 FreeRTOS 链表时，可以记住下面几句话：

1. List_t是一个带哨兵的双向循环链表。
2. xListEnd.pxNext才是真正的链表头。
3. pxIndex是轮转游标，不是头指针。
4. vListInsertEnd()主要服务于同优先级任务的公平轮转。
5. vListInsert()按xItemValue升序排列。
6. 相同xItemValue的新节点插在已有同值节点之后。
7. 延时链表将绝对唤醒 Tick 作为xItemValue。
8. 事件链表将configMAX_PRIORITIES - uxPriority作为排序值。
9. xStateListItem表示任务状态，xEventListItem表示等待事件。
10. 两个节点使一个任务能够同时等待事件和等待超时。
11. xListEnd是不计入节点数量的尾哨兵。
12. portMAX_DELAY必须特殊处理，否则循环链表遍历无法结束。