三、FreeRTOS 内核数据结构：列表与列表项详解

在 FreeRTOS 内核中任务调度、延时管理、事件等待、软件定时器等功能都离不开一个基础数据结构链表。FreeRTOS 并不是简单地使用普通单向链表而是实现了一套适合内核调度使用的双向循环链表。理解List_t、ListItem_t和MiniListItem_t对于后续学习任务控制块、就绪列表、延时列表和事件列表非常重要。本文主要从链表的基本思想、FreeRTOS 列表结构、列表项初始化、链表初始化、节点插入、节点删除和实际使用场景几个方面进行整理。一、为什么 FreeRTOS 需要链表在裸机程序中通常是一个while(1)主循环顺序执行各个功能函数。而在 RTOS 中系统中可能同时存在多个任务每个任务又会处于不同状态例如任务状态说明就绪态任务已经具备运行条件等待调度器分配 CPU运行态当前正在占用 CPU 执行阻塞态正在等待延时结束、队列数据、信号量或事件挂起态被主动挂起暂时不参与调度内核需要把这些任务按照状态组织起来。比如就绪任务放在就绪列表中延时任务放在延时列表中等待队列的任务放在事件等待列表中。如果使用数组管理这些任务删除和插入都不够灵活。任务状态经常变化如果每次状态切换都移动数组元素效率并不理想。链表更适合这种频繁插入、删除、迁移节点的场景。例如一个任务调用延时函数后需要从就绪列表移除再插入延时列表延时时间到达后又需要从延时列表移除再插回就绪列表。这个过程本质上就是链表节点的移动。二、普通链表与 FreeRTOS 链表的区别普通单向链表一般只包含一个指向下一个节点的指针/* * 一、普通单向链表节点对比用 * */ typedef struct Node { int data; /* 节点存储的数据 */ struct Node *next; /* 指向下一个节点的指针单向 */ } Node_t;这种结构适合简单数据管理但删除某个节点时如果不知道前一个节点就需要从头遍历查找。FreeRTOS 使用的是双向循环链表。每个节点不仅知道后一个节点也知道前一个节点/* * 二、双向链表节点对比用 * */ typedef struct Node { int data; /* 节点存储的数据 */ struct Node *next; /* 指向后一个节点的指针 */ struct Node *prev; /* 指向前一个节点的指针双向核心 */ } Node_t;这样删除节点时不需要从头查找前驱节点直接通过prev和next就可以把当前节点摘下来。FreeRTOS 的链表还有一个特点它带有一个固定存在的结束标记节点也就是常说的“哨兵节点”。这个节点不是任务也不是普通数据只是用来标记链表边界简化插入和删除逻辑。三、FreeRTOS 中的三个核心结构FreeRTOS 链表主要由三个结构组成结构含义作用List_t链表结构管理整个链表ListItem_t列表项作为普通节点插入链表MiniListItem_t迷你列表项作为链表结束标记节点在较新的 FreeRTOS 版本中结构体名称通常通过typedef变成List_t、ListItem_t、MiniListItem_t。在一些旧资料中也会看到xLIST、xLIST_ITEM、xMINI_LIST_ITEM这样的写法。本质上是同一类结构只是命名和配置细节有所变化。四、ListItem_t真正挂入链表的节点ListItem_t是链表中的普通节点。简化后的结构如下/* * 三、ListItem_t真正挂入链表的节点 * */ typedef struct ListItem { uint32_t itemValue; /* 排序辅助值用于延时列表等有序链表 */ struct ListItem *next; /* 指向链表中后一个节点 */ struct ListItem *prev; /* 指向链表中前一个节点双向便于删除 */ void *owner; /* 指向拥有该节点的对象通常指向任务控制块 TCB */ void *container; /* 指向该节点当前所在的链表为 NULL 表示未插入任何链表 */ } ListItem_t;每个成员都有明确作用。itemValue用于排序。比如在延时列表中它可以表示任务应该在什么 tick 时刻被唤醒。数值越小说明越早被处理。next和prev用于连接前后节点这是双向链表的基础。owner表示这个列表项属于哪个对象。在任务调度中它通常指向任务控制块 TCB。container表示这个列表项当前位于哪个链表中。如果一个节点已经插入某个链表container就指向该链表如果没有插入任何链表container通常为NULL。这个设计非常关键。FreeRTOS 并不是把任务控制块本身直接放进链表而是把任务控制块内部的列表项挂到链表上。可以用一个简化的任务控制块表示/* * 四、任务控制块 TCB 简化示例 * 说明FreeRTOS 将列表项内嵌在 TCB 中 * 通过列表项挂入不同链表而非直接移动 TCB * */ typedef struct TaskControlBlock { char taskName[16]; /* 任务名称 */ uint32_t priority; /* 任务优先级 */ ListItem_t stateListItem; /* 用于挂入就绪列表、延时列表等状态链表 */ ListItem_t eventListItem; /* 用于挂入队列、信号量等事件等待链表 */ } TCB_t;这样做的好处是同一个任务可以根据不同用途挂入不同链表。例如stateListItem用于表示任务状态eventListItem用于表示任务等待某个事件。五、List_t管理整个链表List_t是链表的管理结构。简化后的定义如下/* * 五、List_t链表管理结构链表头 * */ typedef struct List { uint32_t numberOfItems; /* 链表中有效节点数量不包含哨兵节点 */ ListItem_t *index; /* 遍历游标调度器用它指向当前任务实现轮转调度 */ ListItem_t end; /* 哨兵节点结束标记始终存在不属于任何任务 */ } List_t;numberOfItems记录链表中真实节点的数量不包含哨兵节点。index是遍历链表时使用的指针。FreeRTOS 调度器在同优先级任务之间轮转时会用类似游标的方式找到下一个任务。end是链表结束标记节点。它始终存在不代表任何任务。很多资料中把它理解成“根节点”从学习角度看可以这么记但更准确的叫法是“哨兵节点”或“结束标记节点”。六、MiniListItem_t为什么需要迷你节点MiniListItem_t是精简版列表项。它一般只保留排序值和前后指针/* * 六、MiniListItem_t精简版列表项哨兵专用 * 说明哨兵节点不需要 owner 和 container * 因此可用更小的结构节省内存 * */ typedef struct MiniListItem { uint32_t itemValue; /* 排序值哨兵节点设为最大值确保位于链表末尾 */ struct ListItem *next; /* 指向后一个节点 */ struct ListItem *prev; /* 指向前一个节点 */ } MiniListItem_t;它没有owner和container因为哨兵节点不属于任何任务也不需要反向找到任务控制块。它只是链表的边界标记。在一些新版本配置中MiniListItem_t也可能直接等同于ListItem_t。这是 FreeRTOS 为了兼容性和配置灵活性做的处理。学习时只需要记住xListEnd是链表内部自带的结束标记不是普通任务节点。七、链表初始化链表在使用前必须初始化。初始化后的链表是一个空的双向循环链表。简化代码如下/* * 七、链表初始化函数 * 作用将链表初始化为空的双向循环链表 * */ #define MAX_DELAY 0xffffffffUL /* 32 位无符号最大值作为哨兵节点的 itemValue */ void List_Init(List_t *list) { /* 初始化时链表中没有任何有效节点 */ list-numberOfItems 0; /* 遍历游标初始指向哨兵节点表示从头开始 */ list-index list-end; /* 哨兵节点排序值设为最大确保在有序链表中永远位于最后 */ list-end.itemValue MAX_DELAY; /* 哨兵节点的前后指针都指向自己形成闭环 */ /* 这是空双向循环链表的标志 */ list-end.next list-end; list-end.prev list-end; /* 哨兵节点不属于任何任务也不属于任何外部链表 */ list-end.owner NULL; list-end.container NULL; }初始化后链表中没有普通节点但哨兵节点已经存在end.next end; end.prev end; numberOfItems 0;这表示链表为空。由于end的前后指针都指向自己所以整个链表形成了一个闭环。这种设计可以减少很多边界判断。普通链表在插入第一个节点、删除最后一个节点时经常需要单独处理而带哨兵节点的循环链表可以把空链表、单节点链表、多节点链表统一处理。八、为什么 end 的 itemValue 是最大值FreeRTOS 的很多链表需要按照itemValue升序排列。比如延时列表中itemValue可能表示任务解除阻塞的 tick 值。end.itemValue被设置为最大值是为了让哨兵节点永远位于排序链表的末尾。普通节点的值一般不会超过它所以插入时总能在到达哨兵节点之前找到合适位置。例如链表中有三个节点10 - 20 - 30 - endend的值是最大值因此它自然位于最后。九、列表项初始化列表项初始化主要是把container设置为空表示当前节点没有插入任何链表。/* * 八、列表项初始化 * */ void ListItem_Init(ListItem_t *item) { /* 将 container 置空表示当前节点未插入任何链表 */ /* 这是判断节点是否在链表中的重要标志 */ item-container NULL; }实际使用时还需要设置itemValue和owner/* 设置列表项的排序值 */ void ListItem_SetValue(ListItem_t *item, uint32_t value) { item-itemValue value; } /* 设置列表项的拥有者通常传入 TCB 指针 */ void ListItem_SetOwner(ListItem_t *item, void *owner) { item-owner owner; }组合起来可以这样使用TCB_t task; ListItem_Init(task.stateListItem); ListItem_SetValue(task.stateListItem, task.priority); ListItem_SetOwner(task.stateListItem, task);这样链表节点和任务控制块之间就建立了关系ListItem_t.owner - TCB_t TCB_t.stateListItem - ListItem_t通过列表项可以找到任务通过任务也可以找到自己的列表项。十、插入到链表尾部尾插操作常用于就绪列表。比如相同优先级下有多个任务时可以把新任务插到链表尾部后续调度时实现时间片轮转。简化代码如下/* * 九、插入到链表尾部常用于就绪列表 * 说明在 index 指向的位置之前插入新节点 * 若 index 指向哨兵 end则插入到链表尾部 * */ void List_InsertEnd(List_t *list, ListItem_t *newItem) { /* 获取当前遍历游标位置作为插入的参考点 */ ListItem_t *index list-index; /* 新节点的 next 指向 index即插入到 index 前面 */ newItem-next index; /* 新节点的 prev 指向 index 原来的前一个节点 */ newItem-prev index-prev; /* 将原前一个节点的 next 指向新节点完成前向链接 */ index-prev-next newItem; /* 将 index 的 prev 指向新节点完成后向链接 */ index-prev newItem; /* 记录新节点所属的链表便于后续删除时直接定位 */ newItem-container list; /* 有效节点数加一 */ list-numberOfItems; }这段代码可以分成四步理解newItem-next index;新节点的下一个节点指向index。newItem-prev index-prev;新节点的前一个节点指向index原来的前一个节点。index-prev-next newItem;原来的尾节点的下一个节点改成新节点。index-prev newItem;index的前一个节点改成新节点。如果index指向哨兵节点end那么这次插入就相当于把新节点插到了end前面也就是链表尾部。十一、按照 itemValue 升序插入FreeRTOS 中还有一种常见插入方式按照itemValue从小到大插入。延时列表就需要这种方式。简化代码如下/* * 十、按 itemValue 升序插入常用于延时列表 * 说明从哨兵开始向后遍历找到第一个大于 * newItem-itemValue 的节点插入其前面 * */ void List_InsertSorted(List_t *list, ListItem_t *newItem) { /* 从哨兵节点开始遍历哨兵在有序链表中位于末尾 */ ListItem_t *iterator list-end; /* 向后遍历直到找到 itemValue 大于新节点的位置 */ /* 循环结束时iterator 指向新节点应该插入位置的前一个节点 */ while (iterator-next-itemValue newItem-itemValue) { iterator iterator-next; } /* 新节点的 next 指向 iterator 原来的下一个节点 */ newItem-next iterator-next; /* 新节点的 prev 指向 iterator */ newItem-prev iterator; /* 将原下一个节点的 prev 指向新节点 */ iterator-next-prev newItem; /* 将 iterator 的 next 指向新节点完成插入 */ iterator-next newItem; /* 标记新节点已插入该链表 */ newItem-container list; /* 有效节点数加一 */ list-numberOfItems; }假设已有链表如下10 - 30 - end现在插入一个itemValue 20的节点。遍历时会发现 20 应该插入 10 和 30 之间插入后变为10 - 20 - 30 - end如果用于延时列表数值越小的任务越早被唤醒调度器检查链表头部即可快速判断是否有任务到期。十二、从链表中删除节点删除节点时只需要传入列表项本身。因为container已经记录了它属于哪个链表。/* * 十一、从链表中删除节点 * 说明通过 container 字段直接定位所属链表 * 无需从头遍历查找 * */ uint32_t List_Remove(ListItem_t *item) { /* 通过 container 反向找到该节点所属的链表头 */ List_t *list (List_t *)item-container; /* 核心删除操作让后一个节点的 prev 跳过当前节点 */ item-next-prev item-prev; /* 核心删除操作让前一个节点的 next 跳过当前节点 */ /* 这两步执行后当前节点从链表中脱离 */ item-prev-next item-next; /* 如果删除的节点正好是游标指向的节点将游标回退到前一个节点 */ /* 防止游标悬空保证后续遍历正常 */ if (list-index item) { list-index item-prev; } /* 清除 container 标记表示该节点已不在任何链表中 */ item-container NULL; /* 有效节点数减一 */ list-numberOfItems--; /* 返回删除后链表的剩余节点数 */ return list-numberOfItems; }删除过程的核心是两行item-next-prev item-prev; item-prev-next item-next;第一行让后一个节点的prev跳过当前节点指向当前节点的前一个节点。第二行让前一个节点的next跳过当前节点指向当前节点的后一个节点。这样当前节点就从链表中脱离出来了。删除后需要把container设置为NULL表示该节点已经不属于任何链表。十三、遍历链表FreeRTOS 中遍历链表时经常通过index游标获取下一个节点对应的 owner。简化示例如下/* * 十二、遍历链表获取下一个节点的 owner * 说明常用于任务调度返回下一个要运行的任务 TCB * */ void *List_GetNextOwner(List_t *list) { /* 游标向后移动一个节点 */ list-index list-index-next; /* 如果移动后指向哨兵节点说明已经到达链表末尾 */ /* 跳过哨兵回到链表头部循环链表特性 */ if (list-index list-end) { list-index list-index-next; } /* 返回当前游标指向节点的拥有者即任务控制块 */ return list-index-owner; }这段逻辑表示先移动到下一个节点如果遇到哨兵节点就跳过哨兵节点继续移动到真正的第一个节点。在任务调度中owner通常是任务控制块因此这个函数可以返回下一个要调度的任务。十四、一个完整的小例子下面用一个简化例子模拟任务挂入链表的过程。/* * 十三、完整示例模拟任务挂入就绪链表 * */ #include stdio.h #include stdint.h #include string.h #define MAX_DELAY 0xffffffffUL /* 列表项结构 */ typedef struct ListItem { uint32_t itemValue; struct ListItem *next; struct ListItem *prev; void *owner; void *container; } ListItem_t; /* 链表管理结构 */ typedef struct List { uint32_t numberOfItems; ListItem_t *index; ListItem_t end; } List_t; /* 简化任务控制块 */ typedef struct TaskControlBlock { char name[16]; uint32_t priority; ListItem_t stateItem; /* 内嵌列表项用于挂入就绪链表 */ } TCB_t; /* 链表初始化构造空双向循环链表 */ void List_Init(List_t *list) { list-numberOfItems 0; list-index list-end; /* 游标初始指向哨兵 */ list-end.itemValue MAX_DELAY; /* 哨兵值最大确保位于有序链表末尾 */ list-end.next list-end; /* 空表哨兵自己指向自己 */ list-end.prev list-end; list-end.owner NULL; list-end.container NULL; } /* 列表项初始化标记为未插入任何链表 */ void ListItem_Init(ListItem_t *item) { item-container NULL; } /* 尾插法在 index 之前插入新节点 */ void List_InsertEnd(List_t *list, ListItem_t *item) { ListItem_t *index list-index; /* 新节点插入到 index 和 index-prev 之间 */ item-next index; item-prev index-prev; index-prev-next item; /* 原尾节点的 next 指向新节点 */ index-prev item; /* index 的 prev 指向新节点 */ item-container list; /* 标记所属链表 */ list-numberOfItems; /* 节点计数加一 */ } /* 任务初始化设置任务名、优先级并初始化其列表项 */ void Task_Init(TCB_t *task, const char *name, uint32_t priority) { /* 拷贝任务名并确保字符串以 \0 结尾防止越界 */ strncpy(task-name, name, sizeof(task-name) - 1); task-name[sizeof(task-name) - 1] \0; task-priority priority; /* 初始化列表项此时未插入任何链表 */ ListItem_Init(task-stateItem); /* 在就绪链表中通常用优先级作为排序值 */ task-stateItem.itemValue priority; /* 列表项的 owner 指向任务本身便于从链表节点找回 TCB */ task-stateItem.owner task; } /* 打印链表遍历除哨兵外的所有节点输出任务信息 */ void Print_List(List_t *list) { /* 从哨兵的下一个节点开始遍历即链表第一个有效节点 */ ListItem_t *item list-end.next; /* 当遍历回到哨兵时说明链表已遍历完毕 */ while (item ! list-end) { /* 通过 owner 指针获取对应的任务控制块 */ TCB_t *task (TCB_t *)item-owner; printf(task name: %s, priority: %lu\r\n, task-name, (unsigned long)task-priority); /* 移动到下一个节点 */ item item-next; } } /* 主函数演示链表初始化、任务创建和插入过程 */ int main(void) { List_t readyList; /* 定义就绪链表 */ TCB_t task1; /* 定义三个任务控制块 */ TCB_t task2; TCB_t task3; /* 步骤 1初始化链表构造空表 */ List_Init(readyList); /* 步骤 2初始化三个任务分别设置名称和优先级 */ Task_Init(task1, LED, 1); /* 任务 LED优先级 1 */ Task_Init(task2, UART, 2); /* 任务 UART优先级 2 */ Task_Init(task3, KEY, 1); /* 任务 KEY优先级 1 */ /* 步骤 3将三个任务的 stateItem 依次挂入就绪链表尾部 */ /* 插入顺序LED - UART - KEY */ List_InsertEnd(readyList, task1.stateItem); List_InsertEnd(readyList, task2.stateItem); List_InsertEnd(readyList, task3.stateItem); /* 步骤 4遍历并打印链表内容验证插入结果 */ Print_List(readyList); return 0; }这个例子体现了 FreeRTOS 链表设计的核心思想链表中挂入的是ListItem_t但通过owner可以找到真正的任务控制块。十五、FreeRTOS 链表与任务调度的关系FreeRTOS 中常见的任务列表包括列表作用就绪列表保存已经准备好运行的任务延时列表保存正在延时或等待超时的任务挂起列表保存被挂起的任务事件等待列表保存等待队列、信号量、事件组的任务例如一个任务创建成功后会被插入就绪列表。任务调用vTaskDelay()后会从就绪列表移除再插入延时列表。系统 tick 中断到来时内核会检查延时列表中是否有任务到期。如果到期就把任务从延时列表移除再放回就绪列表。这个过程可以概括为任务运行 - 调用延时函数 - 从就绪列表删除 - 插入延时列表 - tick 到期 - 从延时列表删除 - 插入就绪列表 - 等待调度器再次运行所以任务状态切换的底层本质上就是列表项在不同链表之间移动。十六、学习这部分时容易混淆的点List_t不是普通节点而是链表管理结构。ListItem_t才是真正挂入链表的普通节点。xListEnd不是任务节点而是哨兵节点。pvOwner指向拥有该列表项的对象通常是 TCB。pxContainer指向该列表项当前所在的链表。vListInitialise()初始化链表。vListInitialiseItem()初始化列表项。vListInsertEnd()通常用于尾插。vListInsert()通常用于按xItemValue升序插入。uxListRemove()用于把节点从所在链表中移除。