出处：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; //指向列表项当前属于哪个链表 }; 12345678

每个任务都用链表项用于将任务挂接到相应的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; 123456

列表的作用是对列表项进行管理。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 } 12345678

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

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 )++; //更新链表项值 } 1234567891011121314151617181920212223242526272829

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

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 )++; //更新链表项数目 } 123456789101112131415

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

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; } 12345678910111213141516171819

列表项的移除主要就是将此列表项的前一个列表项的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; \ } 12345678910

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