FreeRTOS 任务调度 List 组织

2016-10-03 本文已影响701人 orientlu

@(嵌入式)

Freertos
FreeRtos

简述

前面了解了 FreeRTOS 的内存管理，接下来看看任务调度，这也是一个操作系统中最重要的一部分，而其任务调度大量使用了链表（list.c 实现），调度器使用链表跟踪不同状态下的任务（就绪、挂起、延时的任务，都会被挂接到各自的链表中），所以这里用一定篇幅介绍下主要供调度使用的链表文件是如何组织的。

我目前使用的源码版本是 v9.0.0

数据结构

FreeRTOS 链表中主要的数据结构是链表(xLIST)和链表项(xLIST_ITEM)，以及一个低配的链表项(xMINI_LIST_ITEM)包含于链表中，具体定义和作用下面介绍。定义内容在 Source/include/list.h

xLIST_ITEM

链表项就是链表每个节点的数据结构，其每个成员的具体作用如注释所示。

其中开头和结尾两个宏的作用是检查数据是否完整，当设置 Source/include/projdefs.h configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES 为1的时候，以下结构体会在开始和结尾添加两个变量存储 Magic number(0x5a5a...)供校验。
（后面说明假设没有开启校验）

struct xLIST_ITEM
{
    listFIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE
    // 保存如任务优先级(任务切换)、阻塞时间(延时挂起时)等信息
    // 供列表排序用，递减
    configLIST_VOLATILE TickType_t xItemValue;
    // 指向下一个节点
    struct xLIST_ITEM * configLIST_VOLATILE pxNext;
    // 指向上一个节点
    struct xLIST_ITEM * configLIST_VOLATILE pxPrevious;
    // 指向对象，主要是 TCB
    void * pvOwner; 
    // 指向所属链表 xLIST
    void * configLIST_VOLATILE pvContainer;         
    listSECOND_LIST_ITEM_INTEGRITY_CHECK_VALUE      
};

xLIST

链表包含多个链表项（节点），链表数据结构中包含一个简单的列表项用于表示其尾部（前面提到的低配版列表项）用于标记链表的结束（包含指向第一个节点）

struct xMINI_LIST_ITEM
{
    listFIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE
    // =0xFFF... 判断链表结束时用
    configLIST_VOLATILE TickType_t xItemValue;
    // 指向链表第一个节点
    // 在 xLIST 中指向自身说明链表空
    struct xLIST_ITEM * configLIST_VOLATILE pxNext;
    // 指向链表的最后一个节点
    // 在 xLIST 中初始化指向自身
    struct xLIST_ITEM * configLIST_VOLATILE pxPrevious;
};
typedef struct xMINI_LIST_ITEM MiniListItem_t;

/*
 * Definition of the type of queue used by the scheduler.
 */
typedef struct xLIST
{
    listFIRST_LIST_INTEGRITY_CHECK_VALUE
    // 节点数统计
    configLIST_VOLATILE UBaseType_t uxNumberOfItems;
    // 用于遍历链表，默认指向 xListEnd
    ListItem_t * configLIST_VOLATILE pxIndex;
    MiniListItem_t xListEnd;                        
    listSECOND_LIST_INTEGRITY_CHECK_VALUE           
} List_t;

每个链表的结构如下所示，通过其成员 xListEnd 的指针指向其他链表项，组织成一个完整的链表。

xList.png

链表实现

结合 list.c, 看看 FreeRTOS 的链表是如何实现的。

初始化

在使用链表前，需要调用 FreeRTOS 提供的初始化函数进行初始化

void vListInitialise( List_t * const pxList )
{
    pxList->pxIndex = ( ListItem_t * ) &( pxList->xListEnd );           
    // xListEnd 标记链表
    // 设置最大值 作为判断链表结束
    pxList->xListEnd.xItemValue = portMAX_DELAY;
    // 链表入口，指向第一个节点；没有节点 则指向自己
    pxList->xListEnd.pxNext = 
        ( ListItem_t * ) &( pxList->xListEnd );
    // 链表结束，指向最后一个节点；没有节点，则指向自己 
    pxList->xListEnd.pxPrevious = 
        ( ListItem_t * ) &( pxList->xListEnd );
    
    // 初始化链表节点计数器 = 0
    pxList->uxNumberOfItems = ( UBaseType_t ) 0U;
    
    // 前面提到的检测 如果置 1
    listSET_LIST_INTEGRITY_CHECK_1_VALUE( pxList );
    listSET_LIST_INTEGRITY_CHECK_2_VALUE( pxList );
}

初始化结束后，链表组织如下图所示。

init.png

相应地准备插入新节点前，需要对新节点进行初始化，可以调用函数：
void vListInitialiseItem( ListItem_t * const pxItem )
主要功能是检测新节点是否可用(如果开启检测)

插入新节点

完成链表初始化后，在需要插入新节点的时候，可以调用插入函数完成，新节点按照其 xItemValue 的值逆序插入链表中。

void vListInsert( List_t * const pxList, 
        ListItem_t * const pxNewListItem )
{
    ListItem_t *pxIterator;
    // 取插入排序的依据值
    const TickType_t xValueOfInsertion = 
            pxNewListItem->xItemValue;
    
    // 检测， 如果开启了
    listTEST_LIST_INTEGRITY( pxList );
    listTEST_LIST_ITEM_INTEGRITY( pxNewListItem );

    if( xValueOfInsertion == portMAX_DELAY )
    {
        // 对于value 等于最大值的直接插入链表尾
        // 避免导致下面 for 的死循环
        pxIterator = pxList->xListEnd.pxPrevious;
    }
    else
    {
        // 查找合适的插入位置 从小到大排序
        // 注意等号，如果存在相同值，后插入的在最后,
        // 保证每个 task 都能被运行 
        for(pxIterator = (ListItem_t *) &(pxList->xListEnd);
            pxIterator->pxNext->xItemValue <= xValueOfInsertion;
                pxIterator = pxIterator->pxNext )
        {
        /*
        在调试过程中如果发现程序挂死在此处，可能的情况：
        1.stack overflow
        2.中断优先级错误 （尤其在cotex-m系列 MCU）
        3.进入边界(关闭所有中断)后调用可能导致挂起的API,
            或者中断中使用没有"FrimISR"的API
        4.在队列，信号量没有初始化或者调度器没有起来前使用它们
        */
        }
    }
    // 插入节点 如下图 : 1步2步3步4步..（牵着手）
    pxNewListItem->pxNext = pxIterator->pxNext;
    pxNewListItem->pxNext->pxPrevious = pxNewListItem;
    pxNewListItem->pxPrevious = pxIterator;
    pxIterator->pxNext = pxNewListItem;
    
    // 更新插入节点所属链表
    pxNewListItem->pvContainer = ( void * ) pxList;
    // 借点统计
    ( pxList->uxNumberOfItems )++;
}

插入一个xItemValue == 1的节点 xLIST_ITEM_1 :

insert1.png

再插入一个xItemValue == ２ 的节点 xLIST_ITEM_2, 按照链表的排序规则(递减),得到如下链表 :

insert2.png

从链表尾插入新节点

FreeRTOS 提供另外一个插入节点的函数，可以直接把新节点插入到链表的尾部。
void vListInsertEnd( List_t * const pxList, ListItem_t * const pxNewListItem )
相比一般插入需要按值查找插入位置，从尾部插入更为简单。

移除节点

由于节点中包含指向所属链表的指针，所以移除节点时只需传递该节点即可。

UBaseType_t uxListRemove( ListItem_t * const pxItemToRemove )
{
    List_t * const pxList = ( List_t * ) pxItemToRemove->pvContainer;
    // 移除节点
    // 并没有释放内存之类的操作
    // 需要注意是否需要释放内存，自行调用。
    pxItemToRemove->pxNext->pxPrevious = pxItemToRemove->pxPrevious;
    pxItemToRemove->pxPrevious->pxNext = pxItemToRemove->pxNext;

    // ！！！ 细节 ： 避免指向已经移除的节点
    if( pxList->pxIndex == pxItemToRemove )
    {
        pxList->pxIndex = pxItemToRemove->pxPrevious;
    }
    else
    {
        mtCOVERAGE_TEST_MARKER();
    }
    // 清除所属关系
    pxItemToRemove->pvContainer = NULL;
    // 更新统计
    ( pxList->uxNumberOfItems )--;
    return pxList->uxNumberOfItems;
}

到此，结束，还有一些简单的宏定义这里不做详细介绍，基本都是链表的操作，这里介绍下，避免后续 task 调度分析带来一些不必要的困惑。

参考

源码