FreeRTOS高级篇1---FreeRTOS列表和列表项

向右看齐 2022-07-30 14:59 185阅读 0赞

FreeRTOS内核调度大量使用了列表（list）和列表项（list item）数据结构。我们如果想一探FreeRTOS背后的运行机制，首先遇到的拦路虎就是列表和列表项。对于FreeRTOS内核来说，列表就是它最基础的部分。我们在这一章集中讲解列表和列表项的结构以及操作函数，在下一章讲解任务创建时，会用到本章的知识点。

列表被FreeRTOS调度器使用，用于跟踪任务，处于就绪、挂起、延时的任务，都会被挂接到各自的列表中。用户程序如果有需要，也可以使用列表。

FreeRTOS列表使用指针指向列表项。一个列表（list）下面可能有很多个列表项（list item），每个列表项都有一个指针指向列表。如图1-1所示。

![SouthEast][]

图1-1：列表与列表项

列表项有两种形式，全功能版的列表项xLIST\_ITEM和迷你版的列表项xMINI\_LIST\_ITEM。我们来看一下它们具体的定义，先看全功能版。

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;  /*指向列表中上一个列表项*/
         void * pvOwner;                                     /*指向一个任务TCB*/
         void * configLIST_VOLATILE pvContainer;             /*指向包含该列表项的列表 */
         listSECOND_LIST_ITEM_INTEGRITY_CHECK_VALUE          /*用于检测列表项数据是否完整*/
    };
    typedef struct xLIST_ITEM ListItem_t;

宏listFIRST\_LIST\_ITEM\_INTEGRITY\_CHECK\_VALUE和listSECOND\_LIST\_ITEM\_INTEGRITY\_CHECK\_VALUE用于检查列表项数据是否完整，在projdefs.h中，如果将宏configUSE\_LIST\_DATA\_INTEGRITY\_CHECK\_BYTES设置为1，则使能列表项数据完整性检查，则宏listFIRST\_LIST\_ITEM\_INTEGRITY\_CHECK\_VALUE和listSECOND\_LIST\_ITEM\_INTEGRITY\_CHECK\_VALUE会被两个已知的数值代替。

xItemValue是列表项值，通常是一个被跟踪的任务优先级或是一个调度事件的计数器值。如果任务因为等待从队列取数据而进入阻塞状态，则任务的事件列表项的列表项值保存任务优先级有关信息，状态列表项的列表项值保存阻塞时间有关的信息。这个变量被configLIST\_VOLATILE修饰，configLIST\_VOLATILE被映射成C语言关键字volatile，表明这个变量是“易变的”，告诉编译器不得对这个变量进行代码优化，因为列表项的成员可能会在中断服务程序中被更新。关于volatile关键字，如果不是熟悉的话，可以参考我的博文[《编写优质嵌入式C程序》][C]第3.2.4节。

pxNext和pxPrevious是列表项类型指针，用来指向列表中下一个和上一个列表项，通过这两个指针，列表项之间可以形成类似双向链表结构。

指针pvOwner通常指向一个任务TCB。

指针pvContainer指向包含该列表项的列表。

迷你版的列表项xMINI\_LIST\_ITEM是全功能版列表项xLIST\_ITEM的一个子集，定义如下所示：

struct xMINI_LIST_ITEM
    {
         listFIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE           /*用于检测列表项数据是否完整*/
         configLIST_VOLATILE TickType_t xItemValue;
         struct xLIST_ITEM * configLIST_VOLATILE pxNext;
         struct xLIST_ITEM * configLIST_VOLATILE pxPrevious;
    };
    typedef struct xMINI_LIST_ITEM MiniListItem_t;

既然有了全功能版的列表项，为什么还要声明迷你版的列表项呢？这是因为列表结构体需要一个列表项成员，但又不需要列表项中的所有字段，所以才有了迷你版列表项。列表结构体定义为：

typedef struct xLIST
    {
         listFIRST_LIST_INTEGRITY_CHECK_VALUE                        /*用于检测列表项数据是否完整*/
         configLIST_VOLATILE UBaseType_t uxNumberOfItems;
         ListItem_t * configLIST_VOLATILE pxIndex;                   /*用于遍历列表*/
         MiniListItem_t xListEnd;                                    /*列表项*/
         listSECOND_LIST_INTEGRITY_CHECK_VALUE                       /*用于检测列表项数据是否完整*/
    }List_t;

和列表项定义相同，宏listFIRST\_LIST\_INTEGRITY\_CHECK\_VALUE和listSECOND\_LIST\_INTEGRITY\_CHECK\_VALUE用于检查列表项数据是否完整，在projdefs.h中，如果将宏configUSE\_LIST\_DATA\_INTEGRITY\_CHECK\_BYTES设置为1，则使能列表项数据完整性检查，则宏listFIRST\_LIST\_ITEM\_INTEGRITY\_CHECK\_VALUE和listSECOND\_LIST\_ITEM\_INTEGRITY\_CHECK\_VALUE会被两个已知的数值代替。

uxNumberOfItems表示该列表中挂接的列表项数目，0表示列表为空。

列表项类型指针用于遍历列表，列表初始化后，这个指针指向&xListEnd。通过宏listGET\_OWNER\_OF\_NEXT\_ENTRY()来获取列表中的下一个列表项。

列表项xListEnd用于标记列表结束。xListEnd.xItemValue被初始化为一个常数，其值与硬件架构相关，为0xFFFF（16位架构）或者0xFFFFFFFF（32位架构）。

下面我们看一下列表操作。FreeROTS提供了几个API函数，用于初始化列表和列表项以及列表项插入操作。

### 1.初始化列表 ###

列表结构体中包含一个列表项成员，主要用于标记列表结束。初始化列表就是把这个列表项插入到列表中。

void vListInitialise( List_t * const pxList )
    {
         /*列表索引指向列表项*/
         pxList->pxIndex = ( ListItem_t * )&( pxList->xListEnd );                  
         /* 设置为最大可能值 */
         pxList->xListEnd.xItemValue =portMAX_DELAY;
     
         /* 列表项xListEnd的pxNext和pxPrevious指针指向了它自己 */
         pxList->xListEnd.pxNext = (ListItem_t * ) &( pxList->xListEnd );
         pxList->xListEnd.pxPrevious= ( ListItem_t * ) &( pxList->xListEnd );
         pxList->uxNumberOfItems = ( UBaseType_t) 0U;
     
         /* 设置为已知值，用于检测列表数据是否完整*/
         listSET_LIST_INTEGRITY_CHECK_1_VALUE(pxList );
         listSET_LIST_INTEGRITY_CHECK_2_VALUE(pxList );
    }

如果宏configUSE\_LIST\_DATA\_INTEGRITY\_CHECK\_BYTES设置为1，则使能列表项数据完整性检查，则宏listSET\_LIST\_INTEGRITY\_CHECK\_1\_VALUE()和listSET\_LIST\_INTEGRITY\_CHECK\_2\_VALUE被一个已知值代替，默认为0x5a5a（16位架构）或者0x5a5a5a5a（32位架构）。

假设禁止列表数据完整性检查，初始化后的列表如图1-2所示，uxNumberOfItems被初始化为0，xListEnd.xItemValue初始化为0xffffffff，pxIndex、xListEnd.pxNext和xListEnd.pxPrevious初始化为指向列表项xListEnd。

![SouthEast 1][]

图1-2：初始化后的列表

### 2.初始化列表项 ###

列表项的初始比较简单，只要确保列表项不在任何列表中即可。

void vListInitialiseItem( ListItem_t * const pxItem )
    {
         pxItem->pvContainer = NULL;
     
         /*设置为已知值，用于检测列表项数据是否完整*/
         listSET_FIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE(pxItem );
         listSET_SECOND_LIST_ITEM_INTEGRITY_CHECK_VALUE(pxItem );
    }

如果宏configUSE\_LIST\_DATA\_INTEGRITY\_CHECK\_BYTES设置为1，则使能列表项数据完整性检查，则宏listFIRST\_LIST\_ITEM\_INTEGRITY\_CHECK\_VALUE和listSECOND\_LIST\_ITEM\_INTEGRITY\_CHECK\_VALUE会被两个已知的数值代替，默认为0x5a5a（16位架构）或者0x5a5a5a5a（32位架构）。

假设禁止列表项数据完整性检查，初始化后的列表项如图1-3所示。仅是将指针pvContainer设置为空指针，该指针用于指向包含该列表项的列表，这里设置为NULL表示这个列表项不属于任何列表。

![SouthEast 2][]

图1-3：初始化后的列表项

### 3.将列表项插入到列表中，列表项所在的位置取决于列表项的列表项值（xItemValue）。 ###

每个列表项对象都有一个列表项值（xItemValue），通常是一个被跟踪的任务优先级或是一个调度事件的计数器值。调用API函数vListInsert( List\_t \* const pxList, ListItem\_t \* const pxNewListItem)可以将pxNewListItem指向的列表项插入到pxList指向的列表中，列表项在列表的位置由pxNewListItem->xItemValue决定，按照升序排列。

void vListInsert( List_t * const pxList, ListItem_t * const pxNewListItem )
    {
    ListItem_t *pxIterator;
    const TickType_t xValueOfInsertion = pxNewListItem->xItemValue;
     
             /* 检查列表和列表项数据的完整性，仅当configASSERT()定义时有效。*/
             listTEST_LIST_INTEGRITY( pxList );
             listTEST_LIST_ITEM_INTEGRITY(pxNewListItem );
     
             /*将新的列表项插入到列表，根据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->pvContainer = ( void* ) pxList;
     
             ( pxList->uxNumberOfItems )++;
    }

根据xItemValue的值将新的列表项插入到列表。如果列表中存在与新列表项xItemValue值相同的列表项，则新插入的列表项位于它之后。如果列表项的xItemValue值等于portMAX\_DELAY（列表结束标记，我们在讲列表数据结构时，说到每个列表数据结构体中都有一个列表项成员xListEnd，用于标记列表结束。xListEnd.xItemValue被初始化为一个常数，其值与硬件架构相关，为0xFFFF或者0xFFFFFFFF。这个常数在移植层定义，即宏portMAX\_DELAY），则表示到达了列表结束位置。

我们用图示的方法来讲解这个函数，我们假设一个列表项值（xItemValue）为32的列表项插入到如图1-2所示的初始化后的列表中，调用vListInsert()函数后，列表和列表项的关系如图1-4所示。列表项xListItem\_1的成员指针pxNext和pxPrevious都指向了xListEnd，而xListEnd的成员指针pxNext和pxPrevious都指向了列表项xListItem\_1；列表项xListItem\_1的成员指针pvContainer指向了列表xList\_1；列表成员uxNumberOfItems为1。

![SouthEast 3][]

图1-4：将列表项插入到列表

在此基础上，如果再将一个列表项值（xItemValue）为40的列表项插入到列表中，调用vListInsert()函数后，列表和列表项的关系如图1-5所示。

![SouthEast 4][]

图1-5：将列表项插入到列表

### 4.将列表项插入到列表末端 ###

第3节讲的API插入函数是根据列表项中的列表项值（xItemValue）来决定插入位置的，本节所讲的API函数vListInsertEnd()是简单的将列表项插入到列表的末端。在下一章任务创建分析的文章中，将会遇到这个API函数，到时再以图标的形式分析这个函数，现在给出这个函数的源码。

void vListInsertEnd( List_t * const pxList, ListItem_t * const pxNewListItem )
    {
    ListItem_t* const pxIndex = pxList->pxIndex;
     
             /*检查列表和列表项数据的完整性，仅当configASSERT()定义时有效。*/
             listTEST_LIST_INTEGRITY( pxList );
             listTEST_LIST_ITEM_INTEGRITY(pxNewListItem );
     
             /*向列表中插入新的列表项*/
             pxNewListItem->pxNext = pxIndex;
             pxNewListItem->pxPrevious =pxIndex->pxPrevious;
     
             mtCOVERAGE_TEST_DELAY();
     
             pxIndex->pxPrevious->pxNext =pxNewListItem;
             pxIndex->pxPrevious = pxNewListItem;
     
             pxNewListItem->pvContainer = ( void* ) pxList;
     
             ( pxList->uxNumberOfItems )++;
    }

[SouthEast]: /images/20220724/da891b04291440e8b4c8368cc3b7c9a3.png
[C]: http://blog.csdn.net/zhzht19861011/article/details/45508029#t20
[SouthEast 1]: /images/20220724/f130faa19d634ce28c55786fb27377e8.png
[SouthEast 2]: /images/20220724/60b4d54fbeec4bc6a34319fd9ec36f91.png
[SouthEast 3]: /images/20220724/11b6adf72b904e7eabadb6e7f6a2183a.png
[SouthEast 4]: /images/20220724/5d1d81b8762c44d29b7a2112a2bb0f7c.png