blog
0%

freertos 列表项

发表于 更新于 分类于 Valine：

FreeRTOS内核调度大量使用了列表（list）和列表项（list item）数据结构。
列表被FreeRTOS调度器使用，用于跟踪任务，处于就绪、挂起、延时的任务，都会被挂接到各自的列表中。用户程序如果有需要，也可以使用列表。
FreeRTOS列表使用指针指向列表项(item)。一个列表（list）下面可能有很多个列表项（list item），每个列表项都有一个指针指向列表。


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

全功能版的列表项 xLIST_ITEM

1
2
3
4
5
6
7
8
9
10
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			/*用于检测列表项数据是否完整*/
};

xItemValue是列表项值，通常是一个被跟踪的任务优先级或是一个调度事件的计数器值。
如果任务因为等待从队列取数据而进入阻塞状态，则 任务的事件列表项 的列表项值保存任务优先级有关信息，状态列表项的列表项值保存阻塞时间有关的信息

迷你版的列表项 xMINI_LIST_ITEM

1
2
3
4
5
6
7
8
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;

和全功能xLIST_ITEM对比少了pvContainer, pvOwner

列表结构体需要一个列表项成员，但又不需要列表项中的所有字段，所以才有了迷你版列表项

列表 xLIST

1
2
3
4
5
6
7
8
9
typedef struct xLIST
{
	listFIRST_LIST_INTEGRITY_CHECK_VALUE				/*校验位 */
	volatile UBaseType_t uxNumberOfItems;               /*列表项的数目*/
	ListItem_t * configLIST_VOLATILE pxIndex;			/*列表项当前的游标*/
	MiniListItem_t xListEnd;							/*初始列表项*/
	listSECOND_LIST_INTEGRITY_CHECK_VALUE				/*用于检测列表项数据是否完整 */
} List_t;

列表项类型指针 pxIndex 用于遍历列表，列表初始化后，这个指针指向&xListEnd（表示空列表， 只有一个元素，xListEnd）。通过宏listGET_OWNER_OF_NEXT_ENTRY()来获取列表中的下一个列表项。

看一个例子:

1
2
3
//将TCB的事件列表项插入到 pxReadyTasksLists[prority]
//pxReadyTasksLists 这一项是一个 xLIST的数组, 根据priority index找到 xLIST
vListInsertEnd( &( pxReadyTasksLists[ ( pxTCB )->uxPriority ] ), &( ( pxTCB )->xStateListItem ) );
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void vListInsertEnd( List_t * const pxList, ListItem_t * const pxNewListItem )
 {
    // 此处的pxIndex 指向的列表项应该是xListEnd
    ListItem_t* const pxIndex = pxList->pxIndex;
    /*向列表中插入新的列表项*/
    pxNewListItem->pxNext = pxIndex;
    pxNewListItem->pxPrevious =pxIndex->pxPrevious;
    /* 以pxIndex xList->pxIndex 的位置插入新的列表项
    pxIndex->pxPrevious->pxNext =pxNewListItem;
    pxIndex->pxPrevious = pxNewListItem;
    // 列表项的pvContainer指向该列表
    pxNewListItem->pvContainer = ( void* ) pxList;
    // 列表元素的数目+1
    ( pxList->uxNumberOfItems )++;
  }

初始化列表

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

1
2
3
4
5
6
7
8
9
10
11
void vListInitialise( List_t * const pxList )
{
     /*列表索引指向列表项*/
     pxList->pxIndex = ( ListItem_t * )&( pxList->xListEnd );                  
     /* 设置为最大可能值 */ // 一个列表初始化后 有一个列表项 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;
 }

![d3ee6c0b-2979-4328-85cc-a0abbde954b1 (1)](attachments/d3ee6c0b-2979-4328-85cc-a0abbde954b1 (1)-171341083095748.png)

初始化列表项

1
2
3
4
5
void vListInitialiseItem( ListItem_t * const pxItem )
{
    //该指针用于指向包含该列表项的列表，这里设置为NULL表示这个列表项不属于任何列表
    pxItem->pvContainer = NULL;
}

列表项插入到列表

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

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
void vListInsert( List_t * const pxList, ListItem_t * const pxNewListItem )
{
    ListItem_t *pxIterator;
    const TickType_t xValueOfInsertion = pxNewListItem->xItemValue;

	if( xValueOfInsertion == portMAX_DELAY )
	{
        //如果列表的xItemValue 为UINT_MAX, 将其插入到xListEnd的前面,表示最后一个元素, 升序排列,前面的小,后面的大
		pxIterator = pxList->xListEnd.pxPrevious;
	}
	else
	{
        //链表遍历,查找插入位置,找到后记录为pxIterator
		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;
	// 列表项的owner指向该xList
	pxNewListItem->pvContainer = ( void * ) pxList;
	// 列表项数目+1
	( pxList->uxNumberOfItems )++;
}

![ebc8d88c-d45a-488d-9d62-f099e5d032ea (1)](attachments/ebc8d88c-d45a-488d-9d62-f099e5d032ea (1).png)

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

![f56dbc83-6914-4aca-adce-da47e9fa3148 (1)](attachments/f56dbc83-6914-4aca-adce-da47e9fa3148 (1).png)

调度相关的列表

先看一下任务的结构体的定义

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
30
31
32
33
34
35
typedef struct tskTaskControlBlock
{
	volatile StackType_t	*pxTopOfStack;	/*< Points to the location of the last item placed on the tasks stack.  THIS MUST BE THE FIRST MEMBER OF THE TCB STRUCT. */

	ListItem_t			xStateListItem;	    // 状态列表项, ready blocked suspended 状态轮转
	ListItem_t			xEventListItem;		// 事件列表项 
	UBaseType_t			uxPriority;			/* 任务优先级, 0是最低的优先级 */
	StackType_t			*pxStack;			/* 任务栈的起始地址*/
	char				pcTaskName[ configMAX_TASK_NAME_LEN ]; // 任务名字

	#if ( ( portSTACK_GROWTH > 0 ) || ( configRECORD_STACK_HIGH_ADDRESS == 1 ) )
		StackType_t		*pxEndOfStack;		/* 任务栈的 结束地址*/
	#endif

	#if ( portCRITICAL_NESTING_IN_TCB == 1 )
		UBaseType_t		uxCriticalNesting;	/* 任务嵌套深度*/
	#endif

	#if ( configUSE_MUTEXES == 1 )
		UBaseType_t		uxBasePriority;		/*< The priority last assigned to the task - used by the priority inheritance mechanism.  用于任务优先级继承的机制*/
		UBaseType_t		uxMutexesHeld;
	#endif

	#if( configUSE_TASK_NOTIFICATIONS == 1 )  // 任务通知机制, 用于简洁的任务通信
		volatile uint32_t ulNotifiedValue;
		volatile uint8_t ucNotifyState;
	#endif

	/* See the comments above the definition of
	tskSTATIC_AND_DYNAMIC_ALLOCATION_POSSIBLE. */
	#if( tskSTATIC_AND_DYNAMIC_ALLOCATION_POSSIBLE != 0 ) 
		uint8_t	ucStaticallyAllocated; 		/* true 标识任务栈是静态分配的, 不需要free*/
	#endif

} tskTCB;

TCB结构体中包括 xEventListItem 和 xStateListItem

状态列表项

大概的用途, 用于追踪任务的状态, 从ready blocked delay suspend等状态间轮转, 其xItemValue值是调度事件的计数器值, 比如timeout等

1
xNextTaskUnblockTime = listGET_LIST_ITEM_VALUE( &( ( pxTCB )->xStateListItem ) );

前面的章节中介绍过一个例子: 将TCB的事件列表项挂入到readyTaskList中, 表示该TCB 转到就绪状态. 

1
2
3
//将TCB的事件列表项插入到 pxReadyTasksLists[prority]
//pxReadyTasksLists 这一项是一个 xLIST的数组, 根据priority index找到 xLIST
vListInsertEnd( &( pxReadyTasksLists[ ( pxTCB )->uxPriority ] ), &( ( pxTCB )->xStateListItem ) );

通常的用法是 状态轮转, 调用 uxListRemove 将其从之前的状态列表中删除, 然后调用vListInsert 等插入函数挂入到新的状态列表中

事件列表项

等待事件的列表? 其xItemValue值 保存的是任务优先级.

  1. 任务调度器相关的操作
    1
    2
    // 调度器挂起时, ready的任务挂入到xPendingReadyList下, 调度器resume后, 从ready list中取任务调度执行
    PRIVILEGED_DATA static List_t xPendingReadyList;	/*< Tasks that have been readied while the scheduler was suspended.  They will be moved to the ready list when the scheduler is resumed. */
    xTaskResumeFromISR
    xTaskGenericNotifyFromISR
    xTaskResumeAll
    prvTaskIsTaskSuspended
    xTaskRemoveFromEventList -> 用于队列的出队队列
    因等待出队而阻塞的任务会将任务的事件列表项xEventListItem挂接到队列的等待出队列表上
    要解除任务阻塞，我们需要将任务的事件列表项从**队列**的等待出队队列（xTasksWaitingToReceive）上删除，并且将任务移动到就绪列表中。
    调用函数xTaskRemoveFromEventList()实现。
    xTasksWaitingToReceive是xQUEUE的成员
    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

    typedef struct QueueDefinition
    {
    	int8_t *pcHead;					/*< Points to the beginning of the queue storage area. */
    	int8_t *pcTail;					/*< Points to the byte at the end of the queue storage area.  Once more byte is allocated than necessary to store the queue items, this is used as a marker. */
    	int8_t *pcWriteTo;				/*< Points to the free next place in the storage area. */

    	union							/* Use of a union is an exception to the coding standard to ensure two mutually exclusive structure members don't appear simultaneously (wasting RAM). */
    	{
    		int8_t *pcReadFrom;			/*< Points to the last place that a queued item was read from when the structure is used as a queue. */
    		UBaseType_t uxRecursiveCallCount;/*< Maintains a count of the number of times a recursive mutex has been recursively 'taken' when the structure is used as a mutex. */
    	} u;

    	List_t xTasksWaitingToSend;		/*< List of tasks that are blocked waiting to post onto this queue.  Stored in priority order. */
    	List_t xTasksWaitingToReceive;	/*< List of tasks that are blocked waiting to read from this queue.  Stored in priority order. */

    	volatile UBaseType_t uxMessagesWaiting; /*< The number of items currently in the queue. */
    	UBaseType_t uxLength;			/*< The length of the queue defined as the number of items it will hold, not the number of bytes. */
    	UBaseType_t uxItemSize;			/*< The size of each items that the queue will hold. */

    	volatile int8_t cRxLock;		/*< Stores the number of items received from the queue (removed from the queue) while the queue was locked.  Set to queueUNLOCKED when the queue is not locked. */
    	volatile int8_t cTxLock;		/*< Stores the number of items transmitted to the queue (added to the queue) while the queue was locked.  Set to queueUNLOCKED when the queue is not locked. */

    	#if( ( configSUPPORT_STATIC_ALLOCATION == 1 ) && ( configSUPPORT_DYNAMIC_ALLOCATION == 1 ) )
    		uint8_t ucStaticallyAllocated;	/* true 标识任务栈是静态分配的, 不需要free*/
    	#endif
    } xQUEUE;