• FreeRTOS列表和列表项


    FreeRTOS内核调度使用了大量的列表(list)和列表项(listitem)数据结构。它的源码中涉及到很多列表的操作,对于FreeRTOS来说,列表就是它最基础的一部分,列表被用作FreeRTOS调度器使用,用于跟踪任务,处于就绪,挂起,延时的任务都会被挂接到各自的列表中,用户程序如果有需要,也可以使用列表,其中就连FreeRTOS的任务调度其实核心也涉及到列表。

      FreeRTOS列表使用指针指向列表项。一个列表(list)下面可能有很多个列表项(list item),每个列表项都有一个指针指向列表。如图所示

    列表和列表项

    列表项有两种形式,全功能版的列表项xLIST_ITEM和迷你版的列表项xMINI_LIST_ITEM。我们来看一下它们具体的定义,先看全功能版。

    1. struct xLIST_ITEM
    2. {
    3. listFIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE /*用于检测列表项数据是否完整*/
    4. configLIST_VOLATILE TickType_t xItemValue; /*列表项值*/
    5. struct xLIST_ITEM * configLIST_VOLATILE pxNext; /*指向列表中下一个列表项*/
    6. struct xLIST_ITEM * configLIST_VOLATILE pxPrevious; /*指向列表中上一个列表项*/
    7. void * pvOwner; /*指向一个任务TCB*/
    8. void * configLIST_VOLATILE pvContainer; /*指向包含该列表项的列表 */
    9. listSECOND_LIST_ITEM_INTEGRITY_CHECK_VALUE /*用于检测列表项数据是否完整*/
    10. };
    11. 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,表明这个变量是“易变的”,告诉编译器不得对这个变量进行代码优化,因为列表项的成员可能会在中断服务程序中被更新。

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

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

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

          迷你版的列表项xMINI_LIST_ITEM是全功能版列表项xLIST_ITEM的一个子集,定义如下所示:
     

    1. struct xMINI_LIST_ITEM
    2. {
    3. listFIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE /*用于检测列表项数据是否完整*/
    4. configLIST_VOLATILE TickType_t xItemValue;
    5. struct xLIST_ITEM * configLIST_VOLATILE pxNext;
    6. struct xLIST_ITEM * configLIST_VOLATILE pxPrevious;
    7. };
    8. typedef struct xMINI_LIST_ITEM MiniListItem_t;

        既然有了全功能版的列表项,为什么还要声明迷你版的列表项呢?这是因为列表结构体需要一个列表项成员,但又不需要列表项中的所有字段,所以才有了迷你版列表项。迷你列表项起到的主要作用就是标识列表的末尾,所以它的值也设置成了最大值,列表结构体定义为:

    1. typedef struct xLIST
    2. {
    3. listFIRST_LIST_INTEGRITY_CHECK_VALUE /*用于检测列表项数据是否完整*/
    4. configLIST_VOLATILE UBaseType_t uxNumberOfItems;
    5. ListItem_t * configLIST_VOLATILE pxIndex; /*用于遍历列表*/
    6. MiniListItem_t xListEnd; /*列表项*/
    7. listSECOND_LIST_INTEGRITY_CHECK_VALUE /*用于检测列表项数据是否完整*/
    8. }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位架构)。
     

    关于列表的一些操作

    初始化列表

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

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

    如果宏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。
     

     初始化列表项

    列表项的初始化很简答, 只需要声明该列表项不属于任何一个列表就可以了。

    1. void vListInitialiseItem( ListItem_t * const pxItem )
    2. {
    3. pxItem->pvContainer = NULL;
    4. /*设置为已知值,用于检测列表项数据是否完整*/
    5. listSET_FIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE(pxItem );
    6. listSET_SECOND_LIST_ITEM_INTEGRITY_CHECK_VALUE(pxItem );
    7. }

    如果宏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表示这个列表项不属于任何列表。
     

     

    列表插入列表项

     

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

    1. void vListInsert( List_t * const pxList, ListItem_t * const pxNewListItem )
    2. {
    3. ListItem_t *pxIterator;
    4. const TickType_t xValueOfInsertion = pxNewListItem->xItemValue;
    5. /* 检查列表和列表项数据的完整性,仅当configASSERT()定义时有效。*/
    6. listTEST_LIST_INTEGRITY( pxList );
    7. listTEST_LIST_ITEM_INTEGRITY(pxNewListItem );
    8. /*将新的列表项插入到列表,根据xItemValue的值升序插入列表。*/
    9. if( xValueOfInsertion == portMAX_DELAY)
    10. {
    11. pxIterator =pxList->xListEnd.pxPrevious;
    12. }
    13. else
    14. {
    15. for( pxIterator = (ListItem_t * ) &( pxList->xListEnd );pxIterator->pxNext->xItemValue <= xValueOfInsertion; pxIterator =pxIterator->pxNext )
    16. {
    17. /* 这里为空 */
    18. }
    19. }
    20. pxNewListItem->pxNext =pxIterator->pxNext;
    21. pxNewListItem->pxNext->pxPrevious= pxNewListItem;
    22. pxNewListItem->pxPrevious =pxIterator;
    23. pxIterator->pxNext = pxNewListItem;
    24. pxNewListItem->pvContainer = ( void* ) pxList;
    25. ( pxList->uxNumberOfItems )++;
    26. }

     列表项末尾插入

    1. void vListInsertEnd( List_t * const pxList, ListItem_t * const pxNewListItem )
    2. {
    3. ListItem_t* const pxIndex = pxList->pxIndex;
    4. /*检查列表和列表项数据的完整性,仅当configASSERT()定义时有效。*/
    5. listTEST_LIST_INTEGRITY( pxList );
    6. listTEST_LIST_ITEM_INTEGRITY(pxNewListItem );
    7. /*向列表中插入新的列表项*/
    8. pxNewListItem->pxNext = pxIndex;
    9. pxNewListItem->pxPrevious =pxIndex->pxPrevious;
    10. mtCOVERAGE_TEST_DELAY();
    11. pxIndex->pxPrevious->pxNext =pxNewListItem;
    12. pxIndex->pxPrevious = pxNewListItem;
    13. pxNewListItem->pvContainer = ( void* ) pxList;
    14. ( pxList->uxNumberOfItems )++;
    15. }

    Tips: 这个函数是最容易造成误解的一个函数,字面理解,在我开始学的时候我以为就是插入到最后一个迷你列表项的前面,所谓末尾插入肯定是最后一项嘛,阅读源码之后,其实不然,因为列表中有一项成员 

    1. ListItem_t * configLIST_VOLATILE pxIndex;

    该成员主要作用就是用来遍历列表的。阅读源码发现它是插入在pxIndex所指的列表项的前面。这里体现了FreeRTOS的哲学理念,“公平”,如果pxIndex,指向的是当前的索引的列表项表示正在使用,这时比如顺序是1->2->3,现在pxIndex指向2,要插入4,这时你4肯定是要最后遍历访问的,意味着就是访问顺序应该是2->3->1->4,所以它要插入在2前面,我的方法是记住一个口诀,末尾插入就是插入pxIndex所指列表项的前一项的后面,可能听着有点别扭(不就是所指列表项的前面嘛🤣 ,细细体会,有公平的哲学思想)

    重点

    重点:一开始学习的时候,一直不明白这个pxIndex有什么用,因为我在有关列表的list.c中的API函数中根本没发现有改变它的代码,以为它一直是初始化的值,就是一直指向迷你列表项,其实不然,作为一名程序员,一切从源码中得到答案。

    搜索代码之后发现,中间对pxIndex赋值的地方只有listGET_OWNER_OF_NEXT_ENTRY这个接口(list.h中的一个有参宏)

     每调用一次listGET_OWNER_OF_NEXT_ENTRY,列表的pxIndex会指向下一个列表项。
    而调用listGET_OWNER_OF_NEXT_ENTRY,主要是

     

    FreeRTOS的列表和列表项采用了一种统一的列表管理,不像我以前学的数据结构中的链表操作一样,其中的节点都是具体的结构体的内容,所以是针对具体的一类结构体,比如struct people,这样导致的后果就是所有有关链表操作的内容都是针对这类结构体,如果稍微改成struct dog,这样就需要全部重写链表的所有操作了。FreeRTOS采用一种方法,写出了通用的链表操作,让我不得不感叹这代码确实是写的好!🤣 

  • 相关阅读:
    MAC地址、IP地址以及ARP协议详细讲解
    技术干货 | 提速40%,MindSpore 二阶优化器技术解密!
    搜索框的测试
    代码随想录第56天
    简单几步实现滑动验证码(后端验证)
    数据库设计之E-R图和关系表
    【MyBatis框架】第二章 MyBatis入门
    E. Iva & Pav -前缀和 + 二分 +位运算
    纯数、应用数学论文EE优秀选题推荐
    黑客为什么不攻击支付宝
  • 原文地址:https://blog.csdn.net/qq_43460068/article/details/134564192