【FreeRTOS源码学习笔记】链表的实现

前言

链表是 FreeRTOS 内核的核心数据结构。任务调度、延时、阻塞、事件等待等操作，本质上都是通过对不同链表进行插入、删除和遍历来完成的。list.c 与 list.h 提供的是一套为调度器高度定制的环形双向链表

一、核心数据结构

1.1 ListItem_t 链表节点

1structxLIST_ITEM2{3TickType_t xItemValue;/* 辅助值，用于帮助节点进行顺序排列 */4structxLIST_ITEM*pxNext;/* 指向链表下一个节点 */5structxLIST_ITEM*pxPrevious;/* 指向链表上一个节点 */6void*pvOwner;/* 指向拥有该节点的内核对象，通常是 TCB */7void*pvContainer;/* 指向该节点所在的链表 */8};9typedefstructxLIST_ITEMListItem_t;/* 节点数据类型重定义 */

• xItemValue：排序依据。在就绪列表中存放任务优先级；在延时列表/事件列表中存放唤醒时刻或超时值，用于升序排列。

pvOwner
含义：链表节点的归属对象，标记这个节点是用来代表哪一个实体。

• 常规场景：存放任务TCB指针；
• 用途：遍历链表拿到ListItem后，通过 pvOwner 反向取出对应的任务控制块，进而调度、处理任务；
• 特点：节点依附于TCB，节点属于TCB，所以owner固定是这个任务，节点挪到别的链表，owner不变。

pvContainer
含义：节点当前所在的宿主链表（xLIST），记录节点挂载在哪一张链表上。

• 节点未入链： pvContainer = NULL ；
• 节点插入链表时赋值，移除链表时置空；
• 用途：

1. 检测节点是否已经挂载，避免重复插入；
2. 移除节点时，直接找到所属链表，修改链表成员计数 uxNumberOfItems ；
3. 校验节点合法性；

• 特点：节点移动到不同链表， pvContainer 会跟着变；一个节点同一时刻只能属于一个链表。

1.2 MiniListItem_t 迷你节点（哨兵位）

1structxMINI_LIST_ITEM2{3TickType_t xItemValue;/* 辅助值，用于帮助节点进行升序排列 */4structxLIST_ITEM*pxNext;/* 指向链表下一个节点 */5structxLIST_ITEM*pxPrevious;/* 指向链表上一个节点 */6};7typedefstructxMINI_LIST_ITEMMiniListItem_t;/* 精简节点数据类型重定义 */

• 与完整 ListItem_t 相比，MiniListItem_t 去掉了 pvOwner 和 pvContainer。它只用于 List_t 内部的 xListEnd 哨兵，不需要“拥有者”和“所属链表”信息，从而节省 RAM。
• 在链表结构体里会包含有这个哨兵位。

1.3 List_t 链表

1typedefstructxLIST2{3UBaseType_t uxNumberOfItems;/* 链表节点计数器 */4ListItem_t*pxIndex;/* 链表节点索引指针 */5MiniListItem_t xListEnd;/* 链表最后一个节点 */6}List_t;

• uxNumberOfItems 当前链表中有效列表项的数量
• pxIndex 遍历/轮转指针，vListInsertEnd 和轮转调度依赖它
• xListEnd 迷你列表项，作为环形链表的“哨兵位”，其 xItemValue 被设为最大值，永远位于有序插入的末尾

二、链表的基本形态

• FreeRTOS 链表是环形双向链表，xListEnd 同时充当“头”和“尾”的锚点：

• 空链表：pxIndex 指向 xListEnd，xListEnd.pxNext = xListEnd.pxPrevious = &xListEnd。

• 非空链表：xListEnd.pxNext 指向第一个实际节点，xListEnd.pxPrevious 指向最后一个实际节点，形成闭环。

• 这种设计使得插入和删除操作不需要处理 NULL 边界，哨兵永远存在，操作逻辑统一。

三、核心操作函数

3.1 初始化链表节点

1voidvListInitialiseItem(ListItem_t*constpxItem)2{3/* 初始化该节点所在的链表为空，表示节点还没有插入任何链表 */4pxItem->pvContainer=NULL;5}

• 链表节点 ListItem_t 总共有 5 个成员，但是初始化时只需要将 pvContainer 初始化为空即可，表示该节点还没有插入任何链表。
• 一个初始化好的节点示意图如图：

3.2 链表初始化

1voidvListInitialise(List_t*constpxList)2{3/* 将链表索引指针指向最后一个节点 */(1)4pxList->pxIndex=(ListItem_t*)&(pxList->xListEnd);56/* 将链表最后一个节点的辅助排序的值设置为最大，确保该节点就是链表的最后节点 */(2)7pxList->xListEnd.xItemValue=portMAX_DELAY;89/* 将最后一个节点的pxNext和pxPrevious指针均指向节点自身，表示链表为空 */(3)10pxList->xListEnd.pxNext=(ListItem_t*)&(pxList->xListEnd);11pxList->xListEnd.pxPrevious=(ListItem_t*)&(pxList->xListEnd);1213/* 初始化链表节点计数器的值为0，表示链表为空 */(4)14pxList->uxNumberOfItems=(UBaseType_t)0U;15}

• (1) 将链表索引指针指向最后一个节点，即第 1 个节点，或者第 0 个节点更准确，因为这个节点不会计入节点计数器。

• (2) 将链表最后一个（也可以理解为第一个）节点的辅助排序的值设置为最大，确保该节点就是链表的最后节点（也可以理解为第一个节点）。

• (3) 将最后一个（也可以理解为第一个）节点的 pxNext 和 pxPrevious 指针均指向节点自身，表示链表为空。

• (4) 初始化链表节点计数器的值为 0，表示链表为空。

• 初始化好的链表如图：
  

3.3 插入：vListInsert 与 vListInsertEnd

1. 将节点插入链表尾部
vListInsertEnd：插入到 pxIndex 所指节点的前面（即逻辑“尾部”）。它不排序，插入位置完全由 pxIndex 决定

1voidvListInsertEnd(List_t*constpxList,ListItem_t*constpxNewListItem)2{3ListItem_t*constpxIndex=pxList->pxIndex;45pxNewListItem->pxNext=pxIndex;6pxNewListItem->pxPrevious=pxIndex->pxPrevious;7pxIndex->pxPrevious->pxNext=pxNewListItem;8pxIndex->pxPrevious=pxNewListItem;910/* 记住该节点所在的链表 */11pxNewListItem->pvContainer=(void*)pxList;1213/* 链表节点计数器 ++ */14(pxList->uxNumberOfItems)++;15}

• 为什么叫尾插？因为插入点在遍历指针pxlndex前面，链表按顺序往后遍历，链表是一个环，新插入的节点在从当前pxlndex节点开始遍历的一轮里算是最后一个节点。

2.将节点按照升序排列插入链表
vListInsert：按 xItemValue 升序有序插入。
遍历链表，找到第一个 xItemValue 大于待插入值的节点，插入其前面。若待插入值等于已有值，则排在已有相等值之后。xListEnd.xItemValue 为最大值，因此插入值即使很大也永远会在 xListEnd 之前终止。

1voidvListInsert(List_t*constpxList,ListItem_t*constpxNewListItem)2{3ListItem_t*pxIterator;45/* 获取节点的排序辅助值 */6constTickType_t xValueOfInsertion=pxNewListItem->xItemValue;(1)78/* 寻找节点要插入的位置 */(2)9if(xValueOfInsertion==portMAX_DELAY)10{11pxIterator=pxList->xListEnd.pxPrevious;12}13else14{15for(pxIterator=(ListItem_t*)&(pxList->xListEnd);16pxIterator->pxNext->xItemValue<=xValueOfInsertion;17pxIterator=pxIterator->pxNext)18{19/* 没有事情可做，不断迭代只为了找到节点要插入的位置 */20}21}22/* 根据升序排列，将节点插入 */(3)23pxNewListItem->pxNext=pxIterator->pxNext;24pxNewListItem->pxNext->pxPrevious=pxNewListItem;25pxNewListItem->pxPrevious=pxIterator;26pxIterator->pxNext=pxNewListItem;2728/* 记住该节点所在的链表 */29pxNewListItem->pvContainer=(void*)pxList;3031/* 链表节点计数器 ++ */32(pxList->uxNumberOfItems)++;33}

• ( 1 )：获取节点的排序辅助值。
• ( 2 )：根据节点的排序辅助值，找到节点要插入的位置，按照升序排列。
• ( 3 )：按照升序排列，将节点插入链表。假设将一个节点排序辅助值是 2 的节点插入有两个节点的链表中，这两个现有的节点的排序辅助值分别是 1 和 3

注意：同一个 ListItem_t 不可重复插入到同一个链表中。节点的 pxNext/pxPrevious 会被覆写，重复插入会导致链表指针自指、链表断裂。

3.4 将节点从链表中删除

删除操作直接通过 pxItemToRemove->pxContainer 获取所属链表，然后修正前后节点的指针，将 uxNumberOfItems 减一，最后将节点的 pvContainer 置为 NULL，返回剩余节点数。

1UBaseType_tuxListRemove(ListItem_t*constpxItemToRemove)2{3/* 获取节点所在的链表 */4List_t*constpxList=(List_t*)pxItemToRemove->pvContainer;5/* 将指定的节点从链表删除 */6pxItemToRemove->pxNext->pxPrevious=pxItemToRemove->pxPrevious;7pxItemToRemove->pxPrevious->pxNext=pxItemToRemove->pxNext;89/* 调整链表的节点索引指针 */10if(pxList->pxIndex==pxItemToRemove)11{12pxList->pxIndex=pxItemToRemove->pxPrevious;13}1415/* 初始化该节点所在的链表为空，表示节点还没有插入任何链表 */16pxItemToRemove->pvContainer=NULL;1718/* 链表节点计数器 -- */19(pxList->uxNumberOfItems)--;2021/* 返回链表中剩余节点的个数 */22returnpxList->uxNumberOfItems;23}

• 返回值的关键用途：调度器在将任务从某个就绪优先级链表中移除后，如果返回值为 0，说明该优先级已无就绪任务，可以直接清除最高就绪优先级位（portRESET_READY_PRIORITY），而不需要再遍历检查。

四、关键设计要点与易错点

1. xListEnd 的 xItemValue 为最大值。 这使得 vListInsert 的有序遍历永远有终止条件：任何待插入项都会在到达 xListEnd 之前找到位置；插入值很大时直接落在 xListEnd 之前。

2. vListInsertEnd 的“末尾”不是 xListEnd，而是 pxIndex 的前方。 初始化后 pxIndex == &xListEnd，看起来像是“插到末尾”；但一旦调度器移动了 pxIndex，插入点就变成了当前轮转游标的前方。理解这一点是理解轮转调度的关键。

3. pvContainer 是 O(1) 删除的关键。 uxListRemove 不接收 List_t * 参数，完全依赖节点反查所属链表，减少了调用时的出错面，也使节点可以在不同链表之间安全迁移。

4. 环形 + 哨兵避免了 NULL 边界处理。 空链表和非空链表使用同一套指针操作，插入/删除不需要分支判断 pxNext == NULL 或 pxPrevious == NULL，代码更紧凑，也更适合在中断和调度器上下文中快速执行。

5. 同一节点不可重复插入。 节点的 pxNext/pxPrevious 会被新插入操作覆写；重复插入同一节点会导致自指或断链，这是使用 list.c 时必须遵守的约束。

6. 链表只是工具：FreeRTOS 之所以要手写一个如此精简的 list.c，是因为在资源受限的 MCU 上，需要极低的 RAM 占用和 O(1) 的插入/删除效率，来支撑整个实时操作系统的调度。

• 简单说说TCB是什么，后面会重点讲到:
  用通俗的话说：TCB 就是一个任务在操作系统里的“身份证”和“档案袋”。
  在 FreeRTOS 中，我们写代码时创建一个任务，本质上就是让操作系统在内存里分配了一个 TCB 结构体，把任务的所有重要信息都记在这个结构体里。
  在操作系统的眼里，一个任务就等于一个 TCB 结构体。链表管理的是 TCB 里面的节点，找到节点后，通过节点的 pvOwner 指针就能反向找到整个 TCB 结构体的首地址，从而获取这个任务的所有信息。
• freertos里面只有一个链表吗，链表里面具体装的是什么，任务吗?
  FreeRTOS 中不止一个链表，而是有一整套链表，由调度器在 tasks.c 中定义并管理。链表里装的不是任务本身，而是任务控制块（TCB，Task Control Block）中的链表节点，每个节点通过 pvOwner 指针反向指向所属的 TCB。
• 脑海中FreeRTOS 的链表:
  一个 List_t 带着一个环，任务 TCB 里的节点挂在环上，pxIndex 指针在环上不断转动切换任务