目录

首先，FreeRTOS 规定的一些列表主要分为以下几大类（如下面图中所示）：

接下来我详细说一下 FreeRTOS 是如何通过链表来管理任务的。

下面是list.c文件的注释和理解

今天看了 FreeRTOS 的 list.c 源码，对它里面实现的功能有了初步的了解。

首先，FreeRTOS 规定的一些列表主要分为以下几大类（如下面图中所示）：

1. 就绪列表：
   即已经准备好的任务列表。

2. 延时阻塞列表（DelayTaskList）：
   这个列表比较特殊，设计思路如下：
   (a) 原理：滴答计时器（Tick Timer）会根据用户设定的延时时间增加相应的数值。如果你延时了一段时间，它就会在当前计数值的基础上增加。
   (b) 溢出处理：假设以 8 位为例（最大值 255），如果当前计数值是 250 且延时 10，结果 260 会导致溢出变为 4。
   (c) 双列表机制：为了处理溢出，FreeRTOS 规定了两个 DelayTaskList：
      - List 1：存放没有溢出的正常任务。系统在每次中断时检查计数值是否到达设定值，若到达则释放任务。
      - List 2：存放发生溢出的任务。
   (d) 指针交替：系统定义了两个指针，分别是 pxDelayedTaskList（正常指针）和 pxOverflowDelayedTaskList（溢出指针）。当计时器溢出并重新计数时，这两个指针会交替指向这两个链表。这样可以确保滴答计时器始终能获取到当前活跃的延时任务。

3. PendingReadyList：
   这应该是一个已经挂在就绪态上但尚未运行的列表，本质是就绪态，但暂时不能被调度。

4. 暂停态（Suspended State）：
   暂停态没有专门的列表。它通常是外部调用函数让任务脱离暂停态。其设计思路应该是在任务控制块（TCB）里的某个关键字设置一下，以此标识当前任务是否活跃。

接下来我详细说一下 FreeRTOS 是如何通过链表来管理任务的。

首先，FreeRTOS 会把不同的任务分配到不同的区域，每个任务都会分配一定的栈空间，并在自己的栈空间内运行。当任务切换时，系统会将当前的栈地址保存在任务控制块（TCB）中，上下文则保存在任务所属的栈空间内。

typedef struct tskTaskControlBlock       /* The old naming convention is used to prevent breaking kernel aware debuggers. */
{
    volatile StackType_t * pxTopOfStack; /**< Points to the location of the last item placed on the tasks stack.  THIS MUST BE THE FIRST MEMBER OF THE TCB STRUCT. */

    #if ( portUSING_MPU_WRAPPERS == 1 )
        xMPU_SETTINGS xMPUSettings; /**< The MPU settings are defined as part of the port layer.  THIS MUST BE THE SECOND MEMBER OF THE TCB STRUCT. */
    #endif

    #if ( configUSE_CORE_AFFINITY == 1 ) && ( configNUMBER_OF_CORES > 1 )
        UBaseType_t uxCoreAffinityMask; /**< Used to link the task to certain cores.  UBaseType_t must have greater than or equal to the number of bits as configNUMBER_OF_CORES. */
    #endif

    ListItem_t xStateListItem;                  /**< The list that the state list item of a task is reference from denotes the state of that task (Ready, Blocked, Suspended ). */
    ListItem_t xEventListItem;                  /**< Used to reference a task from an event list. */
    UBaseType_t uxPriority;                     /**< The priority of the task.  0 is the lowest priority. */
    StackType_t * pxStack;                      /**< Points to the start of the stack. */
    #if ( configNUMBER_OF_CORES > 1 )
        volatile BaseType_t xTaskRunState;      /**< Used to identify the core the task is running on, if the task is running. Otherwise, identifies the task's state - not running or yielding. */
        UBaseType_t uxTaskAttributes;           /**< Task's attributes - currently used to identify the idle tasks. */
    #endif
    char pcTaskName[ configMAX_TASK_NAME_LEN ]; /**< Descriptive name given to the task when created.  Facilitates debugging only. */

    #if ( configUSE_TASK_PREEMPTION_DISABLE == 1 )
        BaseType_t xPreemptionDisable; /**< Used to prevent the task from being preempted. */
    #endif

    #if ( ( portSTACK_GROWTH > 0 ) || ( configRECORD_STACK_HIGH_ADDRESS == 1 ) )
        StackType_t * pxEndOfStack; /**< Points to the highest valid address for the stack. */
    #endif

    #if ( portCRITICAL_NESTING_IN_TCB == 1 )
        UBaseType_t uxCriticalNesting; /**< Holds the critical section nesting depth for ports that do not maintain their own count in the port layer. */
    #endif

    #if ( configUSE_TRACE_FACILITY == 1 )
        UBaseType_t uxTCBNumber;  /**< Stores a number that increments each time a TCB is created.  It allows debuggers to determine when a task has been deleted and then recreated. */
        UBaseType_t uxTaskNumber; /**< Stores a number specifically for use by third party trace code. */
    #endif

    #if ( configUSE_MUTEXES == 1 )
        UBaseType_t uxBasePriority; /**< The priority last assigned to the task - used by the priority inheritance mechanism. */
        UBaseType_t uxMutexesHeld;
    #endif

    #if ( configUSE_APPLICATION_TASK_TAG == 1 )
        TaskHookFunction_t pxTaskTag;
    #endif

    #if ( configNUM_THREAD_LOCAL_STORAGE_POINTERS > 0 )
        void * pvThreadLocalStoragePointers[ configNUM_THREAD_LOCAL_STORAGE_POINTERS ];
    #endif

    #if ( configGENERATE_RUN_TIME_STATS == 1 )
        configRUN_TIME_COUNTER_TYPE ulRunTimeCounter; /**< Stores the amount of time the task has spent in the Running state. */
    #endif

    #if ( configUSE_C_RUNTIME_TLS_SUPPORT == 1 )
        configTLS_BLOCK_TYPE xTLSBlock; /**< Memory block used as Thread Local Storage (TLS) Block for the task. */
    #endif

    #if ( configUSE_TASK_NOTIFICATIONS == 1 )
        volatile uint32_t ulNotifiedValue[ configTASK_NOTIFICATION_ARRAY_ENTRIES ];
        volatile uint8_t ucNotifyState[ configTASK_NOTIFICATION_ARRAY_ENTRIES ];
    #endif

    /* See the comments in FreeRTOS.h with the definition of
     * tskSTATIC_AND_DYNAMIC_ALLOCATION_POSSIBLE. */
    #if ( tskSTATIC_AND_DYNAMIC_ALLOCATION_POSSIBLE != 0 )
        uint8_t ucStaticallyAllocated; /**< Set to pdTRUE if the task is a statically allocated to ensure no attempt is made to free the memory. */
    #endif

    #if ( INCLUDE_xTaskAbortDelay == 1 )
        uint8_t ucDelayAborted;
    #endif

    #if ( configUSE_POSIX_ERRNO == 1 )
        int iTaskErrno;
    #endif
} tskTCB;

TCB 中主要是这几个变量：

volatile StackType_t * pxTopOfStack：
ListItem_t xStateListItem：任务状态链表节点（接入就绪 / 阻塞 / 延迟等状态链表）
ListItem_t xEventListItem：任务事件链表节点（接入队列 / 信号量等事件的等待链表） UBaseType_t uxPriority：任务当前优先级（0 最低，configMAX_PRIORITIES-1 最高）
StackType_t * pxStack：栈起始地址（指向任务栈的起始位置）
char pcTaskName[ configMAX_TASK_NAME_LEN ]：任务名称（调试用，不影响运行）
 

而列表项中（ListItem），有一个关键变量pvonwer用于指向其所属的TCB，通过这个指针，系统就可以追踪到对应的 TCB。列表项->TCB->栈

FreeRTOS 的列表是一个双向循环列表。在初始化阶段，哨兵列表的 pxNext（后向指针）和 pxPrevious（前向指针）都会指向它自己。

对于正常的列表项，主要包含以下五个变量：
1. xItemValue：在不同的列表中代表不同意义。
   - 在就绪列表中，它代表优先级，值越大优先级越高。
   - 在延迟列表（Delay List）中，它代表阻塞时间，阻塞时间越长，排列位置越靠后。
2. pxNext：指向下一个任务项。
3. pxPrevious：指向上一个任务项。
4. pvOwner：指向该列表项所属的 TCB。
5. pxContainer：记录该列表项当前所属的列表（例如是属于就绪列表还是阻塞列表）。


在链表结构中，我们首先定义了一个链表头（List Head），其主要包含以下内容：
1. number of items：记录当前任务的数量。
2. pxIndex：这是一个指针索引。在同优先级的任务循环中，调度器会不断轮询该索引，使其指向不同的任务。
3.哨兵节点（就是上图的minilistitem_t类型）
   - 在初始化时，pxIndex 会指向一个特殊的哨兵节点（xListEnd）。
   - 这个哨兵节点可以根据用户需求设置为一个完整的任务节点，或者仅作为一个虚拟的特殊节点。
   - 哨兵节点的主要特征是它的 xItemValue。在初始化时，该值会被赋值为 0xFFFFFFFF（32位系统中的最大值）。因为列表项是按 xItemValue 升序排列的，设置成最大值可以确保哨兵节点始终位于链表的末尾。

所以，任务调度的核心流程如下：
CPU 会根据头节点的 pxIndex 索引指针，在任务列表中通过调度算法依次选择任务。选定任务后，系统会通过该任务列表项的 pvOwner 指向其所在的 TCB，再根据 TCB 中的栈指针找到对应的栈空间，最终跳转到该栈去执行任务。可以参考下图：

下面是list.c文件的注释和理解

我详细看了一下 list.c 文件，对其中的五个函数都做了注释。其中有一些函数是用于校验和保证列表安全性的，这些对内核分析没有影响，所以就没有加注释。
这个 .c 文件主要包含五个函数：
1. 初始化：初始化链表（list）
2. 插入：将新的链表项插入到链表中的特定位置
3. 索引前插入：将链表项插入到索引前，也就是插入到循环链表的最后一个位置
4. 删除：把特定的链表项删掉
5. 链表项初始化：初始化链表项（其过程也非常简单）

我们主要关心列表是如何插入和删除的，实际上就是数据结构中双向链表的简单操作：

1. 插入操作：
   你需要依次设置好四个指针：
   - 当前列表项的前向指针和后向指针。
   - 插入位置前一个节点的后向指针。
   - 插入位置后一个节点的前向指针。

2. 删除操作：
   如果要删除一个列表项，直接调整指针指向即可：
   - 让该列表项前一个节点的后向指针，指向它的后一个节点。
   - 让该列表项后一个节点的前向指针，指向它的前一个节点。
   - 被删除项的前向和后向指针可以设为 NULL 或者直接忽略。

3. 初始化：
   - 列表项初始化：非常简单，只初始化了 container（所属列表），其他值在不同情况下需要不同的赋值，所以暂不处理。
   - 链表初始化：
     (a) 将链表头指针（如 pxIndex）指向 end 节点。
     (b) 将 end 哨兵节点的 xItemValue 设置为 0xFFFFFFFF（最大值）。
     (c) 让 end 节点的前向和后向指针都指向自己。

4. 插入到末尾：
    它是将列表项插入到 pxIndex 指针的前面。我们认为 pxIndex 这个循环遍历指针的前面就是“最后”的位置，所以直接把指针赋值给该位置即可。

注：循环切换任务时：通过一个函数不停地遍历并返回下一个要执行任务的 pxIndex 列表项，当遍历碰到哨兵节点（End 节点）时，它会自动跳过。

以上是核心逻辑，参考源码如下

#include <stdlib.h>

#define MPU_WRAPPERS_INCLUDED_FROM_API_FILE

#include "FreeRTOS.h"
#include "list.h"

#undef MPU_WRAPPERS_INCLUDED_FROM_API_FILE

/**
 * @brief 初始化一个FreeRTOS列表(List_t)结构
 *
 * 此函数创建一个新的空列表，设置所有必要的内部指针和值
 *
 * @param pxList 指向要初始化的列表结构的指针
 */
void vListInitialise(List_t *const pxList)
{
    traceENTER_vListInitialise(pxList);

    pxList->pxIndex = (ListItem_t *)&(pxList->xListEnd);

    listSET_FIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE(&(pxList->xListEnd));

    /* 设置列表结束标记项的值为最大可能值，确保它始终在列表末尾 */
    pxList->xListEnd.xItemValue = portMAX_DELAY; // 0xffff

    /* 列表结束标记的前后指针指向自身，这样可以判断列表是否为空 */
    pxList->xListEnd.pxNext = (ListItem_t *)&(pxList->xListEnd);
    pxList->xListEnd.pxPrevious = (ListItem_t *)&(pxList->xListEnd);

/* 当xListEnd是完整的ListItem_t时，初始化其余字段 */
#if (configUSE_MINI_LIST_ITEM == 0)
    {
        pxList->xListEnd.pvOwner = NULL;
        pxList->xListEnd.pxContainer = NULL;
        listSET_SECOND_LIST_ITEM_INTEGRITY_CHECK_VALUE(&(pxList->xListEnd));
    }
#endif

    pxList->uxNumberOfItems = (UBaseType_t)0U;

    listSET_LIST_INTEGRITY_CHECK_1_VALUE(pxList);
    listSET_LIST_INTEGRITY_CHECK_2_VALUE(pxList);

    traceRETURN_vListInitialise();
}
/*-----------------------------------------------------------*/

/**
 * @brief 初始化一个列表项(ListItem_t)结构
 *
 * 该函数初始化一个列表项，将其从任何列表中分离出来
 *
 * @param pxItem 指向要初始化的列表项结构的指针
 */
void vListInitialiseItem(ListItem_t *const pxItem)
{
    traceENTER_vListInitialiseItem(pxItem);

    /* 确保列表项不会被记录为在某个列表上 */
    pxItem->pxContainer = NULL;

    /* Write known values into the list item if
     * configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES is set to 1. */
    listSET_FIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE(pxItem);
    listSET_SECOND_LIST_ITEM_INTEGRITY_CHECK_VALUE(pxItem);

    traceRETURN_vListInitialiseItem();
}
/*-----------------------------------------------------------*/

/**
 * @brief 将列表项插入到列表末尾
 *
 * 将新列表项插入到列表中，使其成为最后一个被移除的项
 *
 * @param pxList 指向要插入到的列表的指针
 * @param pxNewListItem 指向要插入的新列表项的指针
 */
void vListInsertEnd(List_t *const pxList,
                    ListItem_t *const pxNewListItem)
{
    ListItem_t *const pxIndex = pxList->pxIndex;

    traceENTER_vListInsertEnd(pxList, pxNewListItem);

    listTEST_LIST_INTEGRITY(pxList);
    listTEST_LIST_ITEM_INTEGRITY(pxNewListItem);

    /* 将新的列表项插入到pxList中，但不是排序插入，
     * 而是使新列表项成为通过listGET_OWNER_OF_NEXT_ENTRY()调用
     * 移除的最后一项 */
    pxNewListItem->pxNext = pxIndex;
    pxNewListItem->pxPrevious = pxIndex->pxPrevious;

    mtCOVERAGE_TEST_DELAY();

    pxIndex->pxPrevious->pxNext = pxNewListItem;
    pxIndex->pxPrevious = pxNewListItem;

    /* 记住该项所在的列表 */
    pxNewListItem->pxContainer = pxList;

    (pxList->uxNumberOfItems) = (UBaseType_t)(pxList->uxNumberOfItems + 1U);

    traceRETURN_vListInsertEnd();
}
/*-----------------------------------------------------------*/

/**
 * @brief 将列表项按顺序插入到列表中
 *
 * 将新列表项按xItemValue值排序插入到列表中
 *
 * @param pxList 指向要插入到的列表的指针
 * @param pxNewListItem 指向要插入的新列表项的指针
 */
void vListInsert(List_t *const pxList,
                 ListItem_t *const pxNewListItem)
{
    ListItem_t *pxIterator;
    const TickType_t xValueOfInsertion = pxNewListItem->xItemValue;

    traceENTER_vListInsert(pxList, pxNewListItem);

    listTEST_LIST_INTEGRITY(pxList);
    listTEST_LIST_ITEM_INTEGRITY(pxNewListItem);

    /* 将新列表项按xItemValue值排序插入到列表中
     *
     * 如果列表已经包含具有相同项值的列表项，则新列表项应该放在它之后。
     * 这确保存储在就绪列表中的TCB（所有TCB都有相同的xItemValue值）能共享CPU。
     * 但是，如果xItemValue与后标记相同，则下面的迭代循环将不会结束。
     * 因此首先检查该值，并在必要时稍微修改算法。 */
    if (xValueOfInsertion == portMAX_DELAY)
    {
        pxIterator = pxList->xListEnd.pxPrevious;
    }
    else
    {
        /* 遍历列表找到正确的插入位置 */
        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;

    /* 记住该项所在的列表，这允许稍后快速移除该项 */
    pxNewListItem->pxContainer = pxList;

    (pxList->uxNumberOfItems) = (UBaseType_t)(pxList->uxNumberOfItems + 1U);

    traceRETURN_vListInsert();
}
/*-----------------------------------------------------------*/

/**
 * @brief 从列表中移除一个列表项
 *
 * 从其所在列表中移除指定的列表项
 *
 * @param pxItemToRemove 指向要移除的列表项的指针
 * @return 移除项后列表中的项数
 */
UBaseType_t uxListRemove(ListItem_t *const pxItemToRemove)
{
    /* 列表项知道它在哪个列表中。从列表项获取列表 */
    List_t *const pxList = pxItemToRemove->pxContainer;

    traceENTER_uxListRemove(pxItemToRemove);

    /* 更新相邻项的指针，跳过要移除的项 */
    pxItemToRemove->pxNext->pxPrevious = pxItemToRemove->pxPrevious;
    pxItemToRemove->pxPrevious->pxNext = pxItemToRemove->pxNext;

    /* Only used during decision coverage testing. */
    mtCOVERAGE_TEST_DELAY();

    /* 确保索引仍然指向有效项 */
    if (pxList->pxIndex == pxItemToRemove)
    {
        pxList->pxIndex = pxItemToRemove->pxPrevious;
    }
    else
    {
        mtCOVERAGE_TEST_MARKER();
    }

    /* 将项标记为不在任何列表中 */
    pxItemToRemove->pxContainer = NULL;

    /* 减少列表中的项数 */
    (pxList->uxNumberOfItems) = (UBaseType_t)(pxList->uxNumberOfItems - 1U);

    traceRETURN_uxListRemove(pxList->uxNumberOfItems);

    return pxList->uxNumberOfItems;
}
/*-----------------------------------------------------------*/

# list # c语言
Logo
openvela

openvela 操作系统专为 AIoT 领域量身定制，以轻量化、标准兼容、安全性和高度可扩展性为核心特点。openvela 以其卓越的技术优势，已成为众多物联网设备和 AI 硬件的技术首选，涵盖了智能手表、运动手环、智能音箱、耳机、智能家居设备以及机器人等多个领域。

更多推荐

cover

产教共蓉 开源无界：openvela产教生态峰会落地成都，剑指AIoT产业生态与人才双破局

avatar openvela
cover

生产级RAG Agent系统的标准架构

avatar openvela
cover

NovelAI 全攻略：文生图+图生图实操指南，新手也能轻松解锁二次元创作

avatar openvela