FreeRTOS系列学习笔记二---FreeRTOS内核详解LIST

朴灿烈づ我的快乐病毒、 2022-06-10 01:20 417阅读 0赞

出处：[http://blog.csdn.net/hehao9051/article/details/51477127][http_blog.csdn.net_hehao9051_article_details_51477127]

# FreeRTOS内核详解—-LIST(非9.0版本) #

--------------------

从LIST对FreeRTOS的内核进行分析，可能是最容易入手的，也是最明智的。因为他是FreeRTOS内核最基本的一种数据结构，是分析内核最重要部分任务调度的基础。它其实就是一个双向的链表，下面按照链表的基本操作进行讲述，分成如下几个部分：

>  *  LIST项的结构分析
>  *  LIST的结构分析
>  *  LIST的创建
>  *  LIST的初始化
>  *  LIST项的插入
>  *  LIST 项的删除

## 1. LIST项 ##

struct xLIST_ITEM
    {
        portTickType xItemValue;                 //列表项的值 通常用来进行列表项排序 例如延迟                                                                               //链表中此值记录的是延迟时间结束的TICK值    volatile struct xLIST_ITEM * pxNext;            //指向此列表中链表项的下一个链表项
        volatile struct xLIST_ITEM * pxPrevious;        //指向此列表中链表项的前一个链表项
        void * pvOwner;                               //此列表项的拥有者一般是任务控制块，通过此找到相应的任务 
        void * pvContainer;                           //指向列表项当前属于哪个链表
    };
     
      
       1 
       2 
       3 
       4 
       5 
       6 
       7 
       8

每个任务都用链表项用于将任务挂接到相应的LIST中，列表通过列表项的pvOwner可以找到相应的任务。有时链表需要对链表项进行排序，例如`pxDelayedTaskList`就需要按照延迟的时间长短对任务的链表项进行排序，`xItemValue`的作用就是做这个。`pxNext`和`pxPrevious`的作用就是将链表项串联起来。

## 2.LIST ##

typedef struct xLIST
    {
        volatile unsigned portBASE_TYPE uxNumberOfItems;// 列表中链表项的数目（链表是循环表，可以根据前后指针判断是够为空，此项作用是什么？）    volatile xListItem * pxIndex;                   // 用于walk through列表中得链表项 记录当前指向的链表项
        volatile xMiniListItem xListEnd;                // 链表结尾项（这个作用是什么？）
    } xList;
     
      
       1 
       2 
       3 
       4 
       5 
       6

列表的作用是对列表项进行管理。`pxIndex`的作用是对列表中的列表项进行遍寻，例如`pxReadyTasksLists[0]`的任务优先级是相同的，如果包含有5个任务需要运行，FreeRTOS这时就会对这些任务进行分时运行，通过`pxIndex`来记录当前运行的是哪个任务正在运行，例如任务1运行10ms（`pxIndex`指向任务1中的列表项）之后，`pxIndex`就指向下个任务2的列表项，任务2再运行10ms，以此下去从而达到让这5个任务都能够得到执行的目的。`list.c`中`listGET_OWNER_OF_NEXT_ENTRY`的作用就是没调用一次`pxIndex`就会指向就会后移一位，直到结尾然后再从头来过（循环表，没有结尾吧？）。

## 3.LIST的初始化 ##

void vListInitialise( xList *pxList )
    {
        pxList->pxIndex = ( xListItem * ) &( pxList->xListEnd );    //链表步寻指针指向料表结尾项 这样下次在更新是就会                                                                                                                     指向第一个料表项
        pxList->xListEnd.xItemValue = portMAX_DELAY;                //将链表结尾项的链表值设置为最大,以此来确保此链表                                                                                                                     项处于链表结尾
        pxList->xListEnd.pxNext = ( xListItem * ) &( pxList->xListEnd );//将链表结尾项NEXT和PREVIOUS指向自己，这样                                                                                                                          就可以判断链表是否为空
        pxList->xListEnd.pxPrevious = ( xListItem * ) &( pxList->xListEnd );
        pxList->uxNumberOfItems = ( unsigned portBASE_TYPE ) 0U;    //将链表项的数目设置为0
    }
     
      
       1 
       2 
       3 
       4 
       5 
       6 
       7 
       8

初始化的部分很简单，初始化后的列表结构如下图  
![20170807111402961][]

## 4.LIST项的插入 ##

FreeRTOS中根据实际需要提供了两种列表项插入方法：

>  *  vListInsertEnd 插入到列表结尾
>  *  vListInsert 根据链表项xItemValue大小进行升序插入

void vListInsert( xList *pxList, xListItem *pxNewListItem )
    {
        volatile xListItem *pxIterator;
        portTickType xValueOfInsertion;
    
        xValueOfInsertion = pxNewListItem->xItemValue;      //需要插入的链表项的值
    
        if( xValueOfInsertion == portMAX_DELAY )          //如果插入链表项值为允许最大值，则直接插入到链表结尾出
        {
            pxIterator = pxList->xListEnd.pxPrevious;
        }
        else
        {
            for( pxIterator = ( xListItem * ) &( pxList->xListEnd ); pxIterator->pxNext->xItemValue <= xValueOfInsertion; pxIterator = pxIterator->pxNext )
            {
                //找到插入位置
            }
        }
        // 插入链表项
        pxNewListItem->pxNext = pxIterator->pxNext;
        pxNewListItem->pxNext->pxPrevious = ( volatile xListItem * ) pxNewListItem;
        pxNewListItem->pxPrevious = pxIterator;
        pxIterator->pxNext = ( volatile xListItem * ) pxNewListItem;
    
    
        pxNewListItem->pvContainer = ( void * ) pxList;
    
        ( pxList->uxNumberOfItems )++;  //更新链表项值
    }
     
      
       1 
       2 
       3 
       4 
       5 
       6 
       7 
       8 
       9 
       10 
       11 
       12 
       13 
       14 
       15 
       16 
       17 
       18 
       19 
       20 
       21 
       22 
       23 
       24 
       25 
       26 
       27 
       28 
       29

这个插入函数用在需要对列表项进行排序的链表中，例如任务加入到任务延迟列表一般使用此函数，注意插入的列表必须是已经排好序的。下面是一个使用插入函数前后的链表示意图  
插入前  
![20170807111408636][]  
插入后  
![20170807111414279][]

void vListInsertEnd( xList *pxList, xListItem *pxNewListItem )
    {
        volatile xListItem * pxIndex;
    
        pxIndex = pxList->pxIndex;                      //pxIndex指向当前正在处理的链表项
        pxNewListItem->pxNext = pxIndex->pxNext;        //目的就是把pxList->pxIndex指向插入的链表项
        pxNewListItem->pxPrevious = pxList->pxIndex;
        pxIndex->pxNext->pxPrevious = ( volatile xListItem * ) pxNewListItem;
        pxIndex->pxNext = ( volatile xListItem * ) pxNewListItem;
        pxList->pxIndex = ( volatile xListItem * ) pxNewListItem;
    
        pxNewListItem->pvContainer = ( void * ) pxList; //更新当前链表项属于哪链表
    
        ( pxList->uxNumberOfItems )++;                  //更新链表项数目
    }
     
      
       1 
       2 
       3 
       4 
       5 
       6 
       7 
       8 
       9 
       10 
       11 
       12 
       13 
       14 
       15

向列表结尾处插入列表项。这个插入是不进行排序的，仅仅是插入到列表的结尾处，因为是环形的列表，所以也没有什么绝对的结尾，`pxIndex`指向的就是结尾，因为如果`pxIndex`指向当前列表项，意味着再访问到此列表项需要转一圈才能实现。任务加入到任务就绪列表一般使用此函数。下面一个是使用插入到结尾函数前后的列表示意图  
列表项为空情况下的插入  
![20170807111418642][]  
列表项不为空情况下的插入  
![20170807111425506][]

## 4.LIST项的删除 ##

unsigned portBASE_TYPE uxListRemove( xListItem *pxItemToRemove )
    {
    xList * pxList;
    
        pxItemToRemove->pxNext->pxPrevious = pxItemToRemove->pxPrevious;//更新后一个链表项的前一个链表项指针
        pxItemToRemove->pxPrevious->pxNext = pxItemToRemove->pxNext;    //更新前一个链表项的前一个链表项指针
    
        pxList = ( xList * ) pxItemToRemove->pvContainer;   //找到当前链表项属于哪个链表
    
        if( pxList->pxIndex == pxItemToRemove )
        {
            pxList->pxIndex = pxItemToRemove->pxPrevious;   //如果链表遍寻指针指向当前当前链表项，更新其指向前一个
        }
    
        pxItemToRemove->pvContainer = NULL;
        ( pxList->uxNumberOfItems )--;                      //链表项数目减
    
        return pxList->uxNumberOfItems;
    }
     
      
       1 
       2 
       3 
       4 
       5 
       6 
       7 
       8 
       9 
       10 
       11 
       12 
       13 
       14 
       15 
       16 
       17 
       18 
       19

列表项的移除主要就是将此列表项的前一个列表项的`pxNext`更新为此列表项的前后一个个列表项、此列表项的后一个列表项的`pxPrevious`更新为此列表项的前一个列表项，也就是将此链表项的前后列表项连起来。

#define listGET_OWNER_OF_NEXT_ENTRY( pxTCB, pxList )                                    \
    {                                                                                       \
        xList * const pxConstList = ( pxList );                                             \
        ( pxConstList )->pxIndex = ( pxConstList )->pxIndex->pxNext;//链表遍寻指针指向下一个链表项    \
        if( ( pxConstList )->pxIndex == ( xListItem * ) &( ( pxConstList )->xListEnd ) )    \
        {                                                                                   \
            ( pxConstList )->pxIndex = ( pxConstList )->pxIndex->pxNext;//如果到结尾 从头开始遍寻                  \
        }                                                                                   \
        ( pxTCB ) = ( pxConstList )->pxIndex->pvOwner;                                      \
    }
     
      
       1 
       2 
       3 
       4 
       5 
       6 
       7 
       8 
       9 
       10

LIST中还有一些宏，这里只讲述一个：是循环遍寻的，一般用在就绪列表中的任务进行顺序执行,没调用一次`pxIndex`指向就会后移一位，以此达到相同优先级就绪任务都能够执行的目的。

[http_blog.csdn.net_hehao9051_article_details_51477127]: http://blog.csdn.net/hehao9051/article/details/51477127
[20170807111402961]: /images/20220610/fa0e69649a934cd895bc4be39be87f0e.png
[20170807111408636]: /images/20220610/57c1430a7151495a930c4737852d8ab8.png
[20170807111414279]: /images/20220610/c7345ee315bf447f925e0399fe20d8f0.png
[20170807111418642]: /images/20220610/75297c6d2c714918b65af353bdb0d6b1.png
[20170807111425506]: /images/20220610/a015ff2ddf9d4aaa993b58dbefee83a7.png