前言学习 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;各成员作用如下。成员作用xItemValue节点的排序值pxNext指向下一个节点pxPrevious指向上一个节点pvOwner指向拥有该节点的对象通常是 TCBpxContainer指向该节点当前所在的链表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;它只保留了xItemValuepxNextpxPrevious而没有pvOwnerpxContainer因为它不代表真实任务只用作链表的结束标记。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;三个成员的作用如下。成员作用uxNumberOfItems链表中真实节点的数量pxIndex遍历和任务轮转游标xListEnd链表结束哨兵需要特别注意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; \ }每调用一次pxIndex移动到下一个节点。如果遇到xListEnd就跳过哨兵。返回该节点的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()按升序排列所以延时链表形成最早唤醒 → 较晚唤醒 → 最晚唤醒例如TaskB110 Tick TaskA130 Tick TaskC150 Tick链表顺序为xListEnd ↓ TaskB(110) ↓ TaskA(130) ↓ TaskC(150) ↓ xListEndTick 中断只需要检查链表头pxTCB listGET_OWNER_OF_HEAD_ENTRY(pxDelayedTaskList);如果头节点还没有到达唤醒时间那么后面的任务必然也没有到期可以立即停止检查。这样就不需要每个 Tick 都扫描所有阻塞任务。十二、为什么需要两条延时链表TickType_t会发生溢出。本工程使用 32 位 Tick最大值为0xFFFFFFFF假设当前 Tick 已接近最大值xTickCount 0xFFFFFFF0任务延时 32 TickxTimeToWake 0xFFFFFFF0 32 0x00000010唤醒时间发生了回绕。如果所有任务都放在同一条升序链表中0x00000010会排在普通任务前面但它实际上属于下一轮 Tick 周期。所以 FreeRTOS 使用两条延时链表xDelayedTaskList1; xDelayedTaskList2; pxDelayedTaskList; pxOverflowDelayedTaskList;没有发生 Tick 回绕进入当前延时链表。唤醒时间发生回绕进入溢出延时链表。xTickCount溢出后交换两条链表。这样每条链表内部仍然可以使用简单的升序排序。十三、为什么事件等待链表与任务优先级有关任务创建时FreeRTOS 会设置xEventListItem.xItemValue configMAX_PRIORITIES - uxPriority;本工程最大优先级数量为 56。例如任务优先级xEventListItem.xItemValue55最高1401620360最低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 └── 延时链表如果队列先收到数据删除xEventListItem。删除延时链表中的xStateListItem。将xStateListItem加入就绪链表。如果等待超时Tick 中断删除延时链表中的xStateListItem。检查xEventListItem是否仍在事件链表。如果仍在则将其删除。将任务重新加入就绪链表。由于一个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 S2. 插入 A(30)S ⇄ A(30) ⇄ S指针变化A.pxNext S; S.pxPrevious A; A.pxPrevious S; S.pxNext A;数量变化uxNumberOfItems0 → 1pxIndex不变仍然指向 S。3. 插入 B(10)由于10 30B 插入 A 前面S ⇄ B(10) ⇄ A(30) ⇄ S指针变化B.pxNext A; A.pxPrevious B; B.pxPrevious S; S.pxNext B;数量变化uxNumberOfItems1 → 2pxIndex仍然不变。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 3pxIndex仍然指向原来的节点 S。十六、vListInsert 是否会改变 pxIndex不会。vListInsert()只负责查找排序位置。修改新节点和相邻节点的前后指针。设置pxContainer。增加uxNumberOfItems。它不会修改pxList-pxIndex因此无论新节点插到头部、中间还是尾部pxIndex都不会跟随插入位置移动。vListInsertEnd()同样不会直接修改pxIndex它只是读取pxIndex然后把新节点插到pxIndex前面。只有在删除节点时如果被删除节点正好是pxIndexuxListRemove()才会将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 到期而被唤醒只能由事件、通知或恢复操作解除阻塞。十八、五个核心函数总结函数核心作用是否排序是否修改pxIndexvListInitialise()初始化链表和哨兵否初始化为xListEndvListInitialiseItem()将节点标记为未挂链否否vListInsertEnd()插入到pxIndex前否否vListInsert()按xItemValue升序插入是否uxListRemove()O(1) 摘除节点否删除游标节点时调整总结理解 FreeRTOS 链表时可以记住下面几句话List_t是一个带哨兵的双向循环链表。xListEnd.pxNext才是真正的链表头。pxIndex是轮转游标不是头指针。vListInsertEnd()主要服务于同优先级任务的公平轮转。vListInsert()按xItemValue升序排列。相同xItemValue的新节点插在已有同值节点之后。延时链表将绝对唤醒 Tick 作为xItemValue。事件链表将configMAX_PRIORITIES - uxPriority作为排序值。xStateListItem表示任务状态xEventListItem表示等待事件。两个节点使一个任务能够同时等待事件和等待超时。xListEnd是不计入节点数量的尾哨兵。portMAX_DELAY必须特殊处理否则循环链表遍历无法结束。