当前位置：首页 > news >正文

FreeRTOS源码分析三：列表数据结构

news 2025/8/4 13:24:21

系列文章目录

FreeRTOS源码分析一：task创建（RISCV架构）
FreeRTOS源码分析二：task启动（RISCV架构）

文章目录

系列文章目录
前言
List_t 带哨兵双向链表
链表初始化之后的模样
使用 vListInsert 插入两个元素（会按照 xItemValue 升序）
使用 vListInsertEnd 插入元素（无序插入逻辑尾部）
pxIndex的核心作用：实现轮询调度
通过configUSE_MINI_LIST_ITEM减少xListEnd的内存占用
总结

前言

本文会通过一些图来解析 FreeRTOS 的列表数据结构 List_t。一个双向链表，但有一些加速访问的设计。

我们不关心 configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES 这个完整性检查的设置。

List_t 带哨兵双向链表

先简单看一下数据结构的定义部分：

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

主要有三个成员：

uxNumberOfItems: 列表中实际项目的数量（不包括结束标记）
pxIndex: 实际上，它是 “轮询的游标”，记录当前轮询到哪个任务，实现O(1)时间复杂度的任务选择。
xListEnd: 结束标记项，值为portMAX_DELAY，永远在列表末尾的哨兵。

注：xListEnd 本身类型为 MiniListItem_t，这个是出于优化考虑，我们后文讨论。目前，它的定义就是一个链表的表项。

实际上，上面已经构成了一个单独的链表。接下来看一下组成链表的单一的表项有什么成员：

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

xItemValue: 列表项的值，用于排序（升序）
pxNext: 指向下一个列表项的指针
pxPrevious: 指向前一个列表项的指针
pvOwner: 指向拥有此列表项的对象（通常是TCB）
pxContainer: 指向包含此列表项的列表

OK，链表就长这样，就这些内容。

链表初始化之后的模样

vListInitialise函数用于初始化一个链表

在这里插入图片描述
左侧蓝色就是我们的链表，右侧黄色代表的是链表成员 xListEnd。pxIndex 和 xListEnd 的两个指针指向 xListEnd自身。具体初始化函数如下：

void vListInitialise( List_t * const pxList )
{   /* ==== 初始化轮询索引指针 ==== *//* The list structure contains a list item which is used to mark the* end of the list.  To initialise the list the list end is inserted* as the only list entry. */pxList->pxIndex = ( ListItem_t * ) &( pxList->xListEnd );   /* ==== 设置哨兵节点的值为最大值 ==== *//* The list end value is the highest possible value in the list to* ensure it remains at the end of the list. */pxList->xListEnd.xItemValue = portMAX_DELAY;  /* ==== 建立xListEnd的自循环结构 ==== *//* The list end next and previous pointers point to itself so we know* when the list is empty. */pxList->xListEnd.pxNext = ( ListItem_t * ) &( pxList->xListEnd );pxList->xListEnd.pxPrevious = ( ListItem_t * ) &( pxList->xListEnd );/* ==== 条件初始化完整的ListItem_t字段 ==== *//* Initialize the remaining fields of xListEnd when it is a proper ListItem_t */#if ( configUSE_MINI_LIST_ITEM == 0 ){pxList->xListEnd.pvOwner = NULL;pxList->xListEnd.pxContainer = NULL;}#endif/* ==== 初始化列表项计数器 ==== */pxList->uxNumberOfItems = ( UBaseType_t ) 0U;
}

使用 vListInsert 插入两个元素（会按照 xItemValue 升序）

vListInsert会根据链表项的 xItemValue 进行升序插入

void vListInsert( List_t * const pxList,ListItem_t * const pxNewListItem )
{ListItem_t * pxIterator;const TickType_t xValueOfInsertion = pxNewListItem->xItemValue; // 获取待插入节点的排序值if( xValueOfInsertion == portMAX_DELAY ){// 特殊处理：如果插入值是最大值（哨兵值），直接插入到 xListEnd 的前面（末尾）pxIterator = pxList->xListEnd.pxPrevious;}else{// 从 xListEnd 开始往前遍历，寻找第一个 xItemValue 大于插入值的位置// 插入在该位置之前（即该节点之后）for( pxIterator = ( ListItem_t * ) &( pxList->xListEnd ); pxIterator->pxNext->xItemValue <= xValueOfInsertion; pxIterator = pxIterator->pxNext ){// 空循环，仅迭代直到找到合适插入点}}// 插入新节点：将其插入在 pxIterator 之后pxNewListItem->pxNext = pxIterator->pxNext;                // 新节点的下一项指向当前迭代项的下一项pxNewListItem->pxNext->pxPrevious = pxNewListItem;         // 当前迭代项的下一项的前驱改为新节点pxNewListItem->pxPrevious = pxIterator;                    // 新节点的前驱指向当前迭代项pxIterator->pxNext = pxNewListItem;                        // 当前迭代项的下一项改为新节点// 设置新节点的容器指针为当前链表pxNewListItem->pxContainer = pxList;// 链表元素数量加一( pxList->uxNumberOfItems ) = ( UBaseType_t ) ( pxList->uxNumberOfItems + 1U );
}

链表插入就不详细叙述。插入一个xItemValue 为 100 的数据之后如下所示：
在这里插入图片描述
再插入一个xItemValue 为 200 的数据之后如下所示：

使用 vListInsertEnd 插入元素（无序插入逻辑尾部）

void vListInsertEnd( List_t * const pxList,ListItem_t * const pxNewListItem )
{// 获取当前链表的 pxIndex 指针，默认初始时是指向 xListEnd 的ListItem_t * const pxIndex = pxList->pxIndex;/* Insert a new list item into pxList, but rather than sort the list,* makes the new list item the last item to be removed by a call to* listGET_OWNER_OF_NEXT_ENTRY(). */// 设置新节点的下一个节点为 pxIndex（通常是 xListEnd）pxNewListItem->pxNext = pxIndex;// 设置新节点的前一个节点为 pxIndex 的前驱pxNewListItem->pxPrevious = pxIndex->pxPrevious;// 将前一个节点的下一个指针指向新节点（把新节点插入链表中）pxIndex->pxPrevious->pxNext = pxNewListItem;// 将 pxIndex 的前驱改为新节点，完成双向链接pxIndex->pxPrevious = pxNewListItem;// 设置新节点的所属链表指针pxNewListItem->pxContainer = pxList;// 链表元素数加 1( pxList->uxNumberOfItems ) = ( UBaseType_t ) ( pxList->uxNumberOfItems + 1U );
}

这里我们注意到，每次插入都是插入到指针 pxIndex 的后面。这是因为 pxIndex 作为指示下一个将要调度的元素的指示器。下面我们详细看看。

pxIndex的核心作用：实现轮询调度

list提供了宏listGET_OWNER_OF_NEXT_ENTRY来获取轮询的下一个元素。逻辑很简单，移动 pxIndex 到下一个位置，遇到哨兵 xListEnd 则跳过它

#define listGET_OWNER_OF_NEXT_ENTRY( pxTCB, pxList )                             \do {                                                                         \/* 创建一个常量指针指向传入的链表 pxList */                              \List_t * const pxConstList = ( pxList );                                 \\/* 将链表的 pxIndex 移动到下一个节点 */                                 \( pxConstList )->pxIndex = ( pxConstList )->pxIndex->pxNext;            \\/* 如果 pxIndex 指向了 xListEnd（哨兵节点），则跳过它，回到第一个有效节点 */ \if( ( void * ) ( pxConstList )->pxIndex ==                               \( void * ) &( ( pxConstList )->xListEnd ) )                          \{                                                                        \( pxConstList )->pxIndex = ( pxConstList )->xListEnd.pxNext;        \}                                                                        \\/* 获取当前 pxIndex 所指节点的 pvOwner，即这个 ListItem 所属对象（如 TCB） */ \( pxTCB ) = ( pxConstList )->pxIndex->pvOwner;                           \} while( 0)

假设三个同等优先级任务在 list 中等待调度，则顺序如下：
在这里插入图片描述
实际上，在获取最高优先级任务时，确实用到了该接口来拿到当前最高优先级队列中的下一个待调度任务：

    #define taskSELECT_HIGHEST_PRIORITY_TASK()                                                  \do {                                                                                        \UBaseType_t uxTopPriority;                                                              \\/* Find the highest priority list that contains ready tasks. */                         \portGET_HIGHEST_PRIORITY( uxTopPriority, uxTopReadyPriority );                          \configASSERT( listCURRENT_LIST_LENGTH( &( pxReadyTasksLists[ uxTopPriority ] ) ) > 0 ); \listGET_OWNER_OF_NEXT_ENTRY( pxCurrentTCB, &( pxReadyTasksLists[ uxTopPriority ] ) );   \} while( 0 )

通过configUSE_MINI_LIST_ITEM减少xListEnd的内存占用

当启动宏 configUSE_MINI_LIST_ITEM 之后，xListEnd 的类型 struct xMINI_LIST_ITEM 定义如下所示：

struct xMINI_LIST_ITEM
{TickType_t xItemValue;          // 列表项的值struct xLIST_ITEM * pxNext;     // 指向下一个项struct xLIST_ITEM * pxPrevious; // 指向前一个项// 缺少 pvOwner 和 pxContainer 字段
};