FreeRTOS链表
链表概念
经过了链表基础知识的学习，现在进一步来分析FreeRTOS中的链表。
在FreeRTOS中的根节点为List_t
1typedef struct xLIST
2{
3 volatile UBaseType_t uxNumberOfItems; /* 记录链表中共有多少个节点 */
4 ListItem_t * configLIST_VOLATILE pxIndex; /* 指向当前正在使用的节点，可用于遍历链表 */
5 MiniListItem_t xListEnd; /* 用于链表的最后的元素，相当于一个标记 */
6} List_t;
其中嵌套了一个MiniListItem_t 。MiniListItem_t 与普通的ListItem_t 相比少了pxContainer 。
1struct xMINI_LIST_ITEM
2{
3 configLIST_VOLATILE TickType_t xItemValue;
4 struct xLIST_ITEM * configLIST_VOLATILE pxNext;
5 struct xLIST_ITEM * configLIST_VOLATILE pxPrevious;
6};
7typedef struct xMINI_LIST_ITEM MiniListItem_t;
其中节点为ListItem_t
1struct xLIST_ITEM
2{
3 configLIST_VOLATILE TickType_t xItemValue; /*< 可用于对链表进行排序 */
4 struct xLIST_ITEM * configLIST_VOLATILE pxNext; /*< Pointer to the next ListItem_t in the list. */
5 struct xLIST_ITEM * configLIST_VOLATILE pxPrevious; /*< Pointer to the previous ListItem_t in the list. */
6 void * pvOwner; /* 相当于container的地址 */
7 struct xLIST * configLIST_VOLATILE pxContainer; /* 指向根节点 */
8};
9typedef struct xLIST_ITEM ListItem_t;
初始化链表
初始化链表主要做几件事情：
将链表中的pxIndex指向链表的xListEnd
将xListEnd->xItemValue 赋值为最大值，这样的话，在链表排序的时候该项永远在最后，这也是为什么叫xListEnd 的原因。
将xListEnd 的pxNext和 pxPrevious 指向自身。因为链表中没有链表项，所以uxNumberOfItems 也为0。
1void vListInitialise( List_t * const pxList )
2{
3 /* The list structure contains a list item which is used to mark the
4 end of the list. To initialise the list the list end is inserted
5 as the only list entry. */
6 pxList->pxIndex = ( ListItem_t * ) &( pxList->xListEnd ); /*lint !e826 !e740 !e9087 The mini list structure is used as the list end to save RAM. This is checked and valid. */
7
8 /* The list end value is the highest possible value in the list to
9 ensure it remains at the end of the list. */
10 pxList->xListEnd.xItemValue = portMAX_DELAY;
11
12 /* The list end next and previous pointers point to itself so we know
13 when the list is empty. */
14 pxList->xListEnd.pxNext = ( ListItem_t * ) &( pxList->xListEnd ); /*lint !e826 !e740 !e9087 The mini list structure is used as the list end to save RAM. This is checked and valid. */
15 pxList->xListEnd.pxPrevious = ( ListItem_t * ) &( pxList->xListEnd );/*lint !e826 !e740 !e9087 The mini list structure is used as the list end to save RAM. This is checked and valid. */
16
17 pxList->uxNumberOfItems = ( UBaseType_t ) 0U;
18
19}
将链表项添加到尾部
在整理思路之前，必须要先理解到”尾部“的定义。
我们现在假设链表中有4个链表项。pxList->pxIndex=Item3，表明正在使用item3，当前遍历顺序为item3→item4→item1→item2。那么新item5是插在哪个位置呢？item3后面还是插入item4后面呢？
我们可以看到，不管插在item3后面还是item4后面，都会影响原本正在排队的item1和item2的执行顺序。要想不影响正在排队链表项，那么最好就是插在item2后，即item3前。
基于此基础，再来分析源码。实际上就是把pxNewListItem添加到pxList->pxIndex->pxPrevious 。分为以下几个步骤：
-
新链表项的
Next为当前正在执行的链表项，即pxList->pxIndex； -
新链表项的
pxPrevious为当前正在执行的链表项的前一项，即pxList->pxIndex->pxPrevious； -
当前正在执行的链表项的前一项的
Next为新链表项，即pxList->pxIndex->pxPrevious->Next； -
当前正在执行的链表项的前一项为新链表项，即
pxList->pxIndex->pxPrevious； -
新链表项的pxContainer指向链表；
-
链表中的uxNumberOfItems加1 。
1void vListInsertEnd( List_t * const pxList, ListItem_t * const pxNewListItem )
2{
3ListItem_t * const pxIndex = pxList->pxIndex;
4
5 /* Only effective when configASSERT() is also defined, these tests may catch
6 the list data structures being overwritten in memory. They will not catch
7 data errors caused by incorrect configuration or use of FreeRTOS. */
8 listTEST_LIST_INTEGRITY( pxList );
9 listTEST_LIST_ITEM_INTEGRITY( pxNewListItem );
10
11 /* Insert a new list item into pxList, but rather than sort the list,
12 makes the new list item the last item to be removed by a call to
13 listGET_OWNER_OF_NEXT_ENTRY(). */
14 pxNewListItem->pxNext = pxIndex;
15 pxNewListItem->pxPrevious = pxIndex->pxPrevious;
16
17 /* Only used during decision coverage testing. */
18 mtCOVERAGE_TEST_DELAY();
19
20 pxIndex->pxPrevious->pxNext = pxNewListItem;
21 pxIndex->pxPrevious = pxNewListItem;
22
23 /* Remember which list the item is in. */
24 pxNewListItem->pxContainer = pxList;
25
26 ( pxList->uxNumberOfItems )++;
27}
按序插入
根据xItemValue按序将列表项插入到链表中，其核心点在于找到小于等于pxNewListItem->xItemValue的值。
1void vListInsert( List_t * const pxList, ListItem_t * const pxNewListItem )
2{
3ListItem_t *pxIterator;
4const TickType_t xValueOfInsertion = pxNewListItem->xItemValue;
5
6 /* Only effective when configASSERT() is also defined, these tests may catch
7 the list data structures being overwritten in memory. They will not catch
8 data errors caused by incorrect configuration or use of FreeRTOS. */
9 listTEST_LIST_INTEGRITY( pxList );
10 listTEST_LIST_ITEM_INTEGRITY( pxNewListItem );
11
12 /* Insert the new list item into the list, sorted in xItemValue order.
13
14 If the list already contains a list item with the same item value then the
15 new list item should be placed after it. This ensures that TCBs which are
16 stored in ready lists (all of which have the same xItemValue value) get a
17 share of the CPU. However, if the xItemValue is the same as the back marker
18 the iteration loop below will not end. Therefore the value is checked
19 first, and the algorithm slightly modified if necessary. */
20 if( xValueOfInsertion == portMAX_DELAY )
21 {
22 pxIterator = pxList->xListEnd.pxPrevious;
23 }
24 else
25 {
26 /* *** NOTE ***********************************************************
27 If you find your application is crashing here then likely causes are
28 listed below. In addition see https://www.freertos.org/FAQHelp.html for
29 more tips, and ensure configASSERT() is defined!
30 https://www.freertos.org/a00110.html#configASSERT
31
32 1) Stack overflow -
33 see https://www.freertos.org/Stacks-and-stack-overflow-checking.html
34 2) Incorrect interrupt priority assignment, especially on Cortex-M
35 parts where numerically high priority values denote low actual
36 interrupt priorities, which can seem counter intuitive. See
37 https://www.freertos.org/RTOS-Cortex-M3-M4.html and the definition
38 of configMAX_SYSCALL_INTERRUPT_PRIORITY on
39 https://www.freertos.org/a00110.html
40 3) Calling an API function from within a critical section or when
41 the scheduler is suspended, or calling an API function that does
42 not end in "FromISR" from an interrupt.
43 4) Using a queue or semaphore before it has been initialised or
44 before the scheduler has been started (are interrupts firing
45 before vTaskStartScheduler() has been called?).
46 **********************************************************************/
47
48 for( pxIterator = ( ListItem_t * ) &( pxList->xListEnd ); pxIterator->pxNext->xItemValue <= xValueOfInsertion; pxIterator = pxIterator->pxNext ) /*lint !e826 !e740 !e9087 The mini list structure is used as the list end to save RAM. This is checked and valid. *//*lint !e440 The iterator moves to a different value, not xValueOfInsertion. */
49 {
50 /* There is nothing to do here, just iterating to the wanted
51 insertion position. */
52 }
53 }
54
55 pxNewListItem->pxNext = pxIterator->pxNext;
56 pxNewListItem->pxNext->pxPrevious = pxNewListItem;
57 pxNewListItem->pxPrevious = pxIterator;
58 pxIterator->pxNext = pxNewListItem;
59
60 /* Remember which list the item is in. This allows fast removal of the
61 item later. */
62 pxNewListItem->pxContainer = pxList;
63
64 ( pxList->uxNumberOfItems )++;
65}
删除
删除链表项的核心根据被删除链表项找到其左右的链表项。
左边的链表项可以表示为：left = pxItemToRemove ->pxPrevious
右边的链表项可以表示为：right = pxItemToRemove ->pxNext
删除链表项：
left->pxNext = right
right->pxPrevious = left
1UBaseType_t uxListRemove( ListItem_t * const pxItemToRemove )
2{
3/* The list item knows which list it is in. Obtain the list from the list
4item. */
5List_t * const pxList = pxItemToRemove->pxContainer;
6
7 pxItemToRemove->pxNext->pxPrevious = pxItemToRemove->pxPrevious;
8 pxItemToRemove->pxPrevious->pxNext = pxItemToRemove->pxNext;
9
10 /* Only used during decision coverage testing. */
11 mtCOVERAGE_TEST_DELAY();
12
13 /* Make sure the index is left pointing to a valid item. */
14 if( pxList->pxIndex == pxItemToRemove )
15 {
16 pxList->pxIndex = pxItemToRemove->pxPrevious;
17 }
18 else
19 {
20 mtCOVERAGE_TEST_MARKER();
21 }
22
23 pxItemToRemove->pxContainer = NULL;
24 ( pxList->uxNumberOfItems )--;
25
26 return pxList->uxNumberOfItems;
27}
至此，我们了解过FreeRTOS中链表的基本概念和实现。接下来我们分析下在哪些地方使用到了链表。
链表使用
我们在FreeRTOS源码里面搜索vListInitialise
可以看到在任务，队列，事件组等内核对象都有使用链表。
因为我们在前文中只分析过任务的，所以就举例说明链表在任务中的作用。
在prvInitialiseTaskLists 函数中创建了链表。
1static void prvInitialiseTaskLists( void )
2{
3UBaseType_t uxPriority;
4
5 for( uxPriority = ( UBaseType_t ) 0U; uxPriority < ( UBaseType_t ) configMAX_PRIORITIES; uxPriority++ )
6 {
7 vListInitialise( &( pxReadyTasksLists[ uxPriority ] ) );
8 }
9
10 vListInitialise( &xDelayedTaskList1 );
11 vListInitialise( &xDelayedTaskList2 );
12 vListInitialise( &xPendingReadyList );
13
14 #if ( INCLUDE_vTaskDelete == 1 )
15 {
16 vListInitialise( &xTasksWaitingTermination );
17 }
18 #endif /* INCLUDE_vTaskDelete */
19
20 #if ( INCLUDE_vTaskSuspend == 1 )
21 {
22 vListInitialise( &xSuspendedTaskList );
23 }
24 #endif /* INCLUDE_vTaskSuspend */
25
26 /* Start with pxDelayedTaskList using list1 and the pxOverflowDelayedTaskList
27 using list2. */
28 pxDelayedTaskList = &xDelayedTaskList1;
29 pxOverflowDelayedTaskList = &xDelayedTaskList2;
30}
由于FreeRTOS采用的是链表数组的形式，所以需要需要初始化最大优先级数量的链表。如下图所示，如果优先级为5，那么就需要初始化5个链表，对应不同优先级的任务。
除了任务链表外，还会创建其他的一些链表。
xDelayedTaskList1 ：对应pxDelayedTaskList 。调用vTaskDelay时，如果函数调用时间加上需要延迟时间没有溢出32bit计数值，那么添加到该链表。
xDelayedTaskList2 ：对应pxOverflowDelayedTaskList 。调用vTaskDelay时，如果函数调用时间加上需要延迟时间溢出32bit计数值，那么添加到该链表。
用代码来表示两者的区别
1const TickType_t xConstTickCount = xTickCount; // 当前时间
2TickType_t xTimeToWake = xConstTickCount + xTicksToWait; // 唤醒时间
3if( xTimeToWake < xConstTickCount )
4{
5 /* Wake time has overflowed. Place this item in the overflow list. */
6 vListInsert( pxOverflowDelayedTaskList, &( pxCurrentTCB->xStateListItem ) );
7}
8else
9{
10 /* The wake time has not overflowed, so the current block list is used. */
11 vListInsert( pxDelayedTaskList, &( pxCurrentTCB->xStateListItem ) );
12}
但调用vTaskDelay 的延迟tick为portMAX_DELAY，则调用者进入挂起态，为其他值时，调用者进入阻塞态。
xPendingReadyList ：任务进入就绪状态，但是没有放入readylist链表。这种情况发生在调度器被停止时，有些任务进入到ready状态，这时就讲任务加入到xPendingReadyList，等待调度器开始时，从新进行一次调度。
xTasksWaitingTermination ：表示等待结束的任务，注意是为了释放这些任务的资源。函数自己删除自己的时候会先将添加到该链表中，然后在idle task中删除该链表中的任务。
xSuspendedTaskList ：表示被暂停的任务列表，调用vTaskSuspend函数或者vTaskDelay的参数为portMAX_DELAY。
至此，我们了解到FreeRTOS中的基本的链表使用方法以及何处使用。
原文始发于微信公众号（TreeNewBeer）：FreeRTOS源码解读—-链表
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/115045.html
