这个章节的内容是非常重要的,因为 FreeRTOS 的源码实现离不开列表,所以说大家如果想要看懂 FreeRTOS 的源码,看它是如何实现的,那么这个列表你必须要掌握。
1. 列表和列表项
1.1 列表和列表项的简介
列表 是 FreeRTOS 中的一个数据结构,概念上和链表有点类似,列表被用来跟踪 FreeRTOS中的任务。
那我们前面说过列表有就绪列表、挂起列表、阻塞列表等等这些,那这些表示什么?表示任务的一种状态。
列表项 就是存放在列表中的项目 。意思它就是列表的子集。
列表相当于链表,列表项相当于节点,FreeRTOS 中的列表是一个双向环形链表 。
- 列表的特点:
- 列表项间的地址非连续的,它并不是依靠地址连接在一起,而是人为的连接到一起的。
- 列表项的数目是由后期添加的个数决定的,随时可以改变
- 数组的特点:
- 数组成员地址是连续的。
- 数组在最初确定了成员数量后期无法改变。
比如列表项就是来存放我们任务的,假设一个列表叫就绪列表,其中的列表项 1 是 任务 1 的列表项,这就代表任务 1 在就绪态,假设其中的列表项 2 是 任务 2 的列表项,这就代表任务 1 和任务 2 它都在就绪态。列表项大家可以理解成存放数据的,一个数据就下一个、上一个指向谁;还有一个数据,就是列表项是代表哪一个任务,那这个在结构体的时候会介绍到。
那大家只要知道:列表项跟任务是有关系的,每个列表项都代表某一个任务。
在 OS 中任务的数量是不确定的,并且任务状态是会发生改变的,所以非常适用列表(链表)这种数据结构。(随时可以改变数目)
1.2 列表和列表项的结构体
1.2.1 列表的结构体
有关于列表的东西均在文件 list.c 和 list.h 中(都是属于 FreeRTOS 的源码),首先我们先看下在 list.h 中的,列表相关结构体:
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;
- 在该结构体中, 包含了两个宏,这两个宏是确定的已知常量,FreeRTOS 通过检查这两个常量的值,来判断列表的数据在程序运行过程中,是否遭到破坏(数据的完整性) ,该功能一般用于调试。因为默认是不开启的,所以我们并没有用到这两个宏。
- 成员 uxNumberOfItems,用于记录列表中列表项的个数(不包含 xListEnd)。
- 成员 pxIndex 用于指向列表中的某个列表项,一般用于遍历列表中的所有列表项。
- 成员变量 xListEnd 是一个迷你列表项,排在最末尾,我们也称它为末尾列表项。
注意:xListEnd 就是排在某位的。我们的列表里面有很多列表项,可以挂载很多列表项,但是 xListEnd 这个列表项总是排在最底,也就是最末尾的位置。记住这个特性就行了。
列表结构示意图:
1.2.2 列表项的结构体
列表项是列表中用于存放数据的地方,在 list.h 文件中,有列表项的相关结构体定义:
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 /* 列表项的拥有者 */
struct xLIST * configLIST_VOLATILE pxContainer; /* 列表项所在列表 */
listSECOND_LIST_ITEM_INTEGRITY_CHECK_VALUE /* 用于检测列表项的数据完整性,我们并没有使用 */
};
typedef struct xLIST_ITEM ListItem_t;
- 成员变量 xItemValue 为列表项的值,这个值多用于按升序对列表中的列表项进行排序(升序排列)。
像我们阻塞延时的时候,我们有些阻塞 20ms,有些阻塞 30ms,那 20ms 和 30ms 都会写入到这个值里面,它代表两个列表项,那 20ms 的列表项肯定是排在前面,因为它的 xItemValue 这个数值比较小,30ms 的排在后面,这样我就可以优先解除 20ms 这个列表项。它呢就这么一个作用,也是经常使用的。
- 成员变量 pxNext 和 pxPrevious 分别用于指向列表中列表项的下一个列表项和上一个列表项
- 成员变量 pxOwner 用于指向包含列表项的对象(通常是任务控制块)
每一个任务控制块都有一个列表项,它们都会保存在 pvOwner 这里。那 pvOwner 这个成员变量就用来保存任务控制块的。
- 成员变量 pxContainer 用于指向列表项所在列表。 (三大任务列表:就绪、阻塞、挂起。每一个列表代表它的一个状态:就绪态、阻塞态、挂起态)
其实它就是通过 pvOwner 和 configLIST_VOLATILE pxContainer 这两个,一个指向某一个任务,一个指向某一个列表,我们就可以通过这样就可以知道这个任务属于什么状态。
列表项结构示意图:
1.2.3 迷你列表项
迷你列表项也是列表项,但迷你列表项仅用于标记列表的末尾(末尾列表项)和挂载其他插入列表中的列表项。
迷你:就相对于正常的来说,它说了一点东西,所以叫迷你
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;
- 成员变量 xItemValue 为列表项的值,这个值多用于按升序对列表中的列表项进行排序
- 成员变量 pxNext 和 pxPrevious 分别用于指向列表中列表项的下一个列表项和上一个列表项
- 迷你列表项只用于标记列表的末尾和挂载其他插入列表中的列表项,因此不需要成员变量 pxOwner 和 pxContainer,以节省内存开销。
列表一开始初始化的时候只有 3 个成员变量:列表项数目、指向列表项的指针和末尾列表项,它根本没有其他列表项,它只有一个迷你列表项,那么我要插入一个列表项 1,怎么插入?是不是得通过迷你列表项的上一个指向列表项 1,列表项 1 的上一个指向迷你列表项;迷你列表项的下一个指向列表项 1,列表项 1 的下一个指向迷你列表项;这样才能把列表项 1 给归纳到了列表中,这个叫挂载。
如果列表一开始初始化的时候就没有迷你列表项,大家想象一下我怎么挂载啊,所以列表初始化的时候有一个末尾列表项。
迷你列表项结构示意图
1.3 列表和列表项的关系
列表初始状态,以及即将插入的两个列表项如下:
- 列表初始化
末尾列表项是永远排在最末尾的,所以它的 xItemValue 这个数值(升序排列)要最大,32 位最大就是 0xFFFF FFFF(数值最大就是要把它排最后面)。
- 插入列表项 1
- 插入列表项 2
排序 + 连接
2. 列表相关 API 函数介绍
函数 | 描述 |
---|---|
vListInitialise() | 初始化列表 |
vListInitialiseItem() | 初始化列表项 |
vListInsertEnd() | 列表插入列表项(末尾插入) |
vListInsert() | 列表插入列表项(升序插入) |
uxListRemove() | 列表移除列表项 |
参考文档:《FreeRTOS开发指南》第七章 ——“FreeRTOS列表和列表项”
2.1 初始化列表 vListInitialise()
给列表的结构体成员做一个初始值的赋值。
void vListInitialise(List_t * const pxList){
/* 初始化时,列表中只有 xListEnd,因此 pxIndex 指向 xListEnd */
pxList->pxIndex = ( ListItem_t * ) &( pxList->xListEnd );
/* xListEnd 的值初始化为最大值,用于列表项升序排序时,排在最后 */
pxList->xListEnd.xItemValue = portMAX_DELAY;
/* 初始化时,列表中只有 xListEnd,因此上一个和下一个列表项都为 xListEnd 本身 */
pxList->xListEnd.pxNext = ( ListItem_t * ) &( pxList->xListEnd );
pxList->xListEnd.pxPrevious = ( ListItem_t * ) &( pxList->xListEnd );
/* 初始化时,列表中的列表项数量为 0(不包含 xListEnd) */
pxList->uxNumberOfItems = ( UBaseType_t ) 0U;
/* 初始化用于检测列表数据完整性的校验值 */
listSET_LIST_INTEGRITY_CHECK_1_VALUE( pxList );
listSET_LIST_INTEGRITY_CHECK_2_VALUE( pxList );
}
形参 | 描述 |
---|---|
pxList | 待初始化列表 |
初始化后列表结构:
2.2 初始化列表项 vListInitialiseItem()
void vListInitialiseItem( ListItem_t * const pxItem ){
/* 初始化时列表项不属于任何的列表的,所以列表项所在列表设为空 */
pxItem->pxContainer = NULL;
/* 初始化用于检测列表项数据完整性的校验值 */
listSET_FIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE( pxItem );
listSET_SECOND_LIST_ITEM_INTEGRITY_CHECK_VALUE( pxItem );
}
形参 | 描述 |
---|---|
pxItem | 待初始化列表项 |
初始化后的列表项结构
2.3 列表插入列表项(升序插入)vListInsert()
void vListInsert ( List_t * const pxList , ListItem_t * const pxNewListItem )
此函数用于将待插入列表的列表项按照列表项值进行升序排序,有序地插入到列表中
形参 | 描述 |
---|---|
pxList | 列表 |
pxNewListItem | 待插入列表项 |
代码详解查看手册《FreeRTOS开发指南》第七章 ——“FreeRTOS列表和列表项”
void vListInsert( List_t * const pxList, ListItem_t * const pxNewListItem )
{
ListItem_t * pxIterator;
const TickType_t xValueOfInsertion = pxNewListItem->xItemValue; /* 获取列表项的数值,依据数值升序排列 */
listTEST_LIST_INTEGRITY( pxList ); /* 检查参数是否正确 */
listTEST_LIST_ITEM_INTEGRITY( pxNewListItem );
if( xValueOfInsertion == portMAX_DELAY ) /* 如果待插入列表项的值为最大值 */
{
pxIterator = pxList->xListEnd.pxPrevious; /* 插入的位置为列表 xListEnd 前面 */
} else
{
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;
pxNewListItem->pxContainer = pxList; /* 更新待插入列表项所在列表 */
( pxList->uxNumberOfItems )++; /* 更新列表中列表项的数量 */
}
这个其实跟链表的操作是很类似的,那大家只要掌握了链表,学习这一块是很简单的。
列表项升序插入图示:
- 插入值为40的列表项
将列表项xList_Item1,插入列表List中
- 插入值为60的列表项
在前面的基础上,在插入值为60的列表项,结果如下:
- 插入值为50的列表项
在前面的基础上,在插入值为50的列表项,结果如下:
总结:函数 vListInsert(),是将待插入列表的列表项按照列表项值进行升序排序,有序地插入到列表中。
2.4 列表插入列表项(尾部插入)vListInsertEnd()
形参 | 描述 |
---|---|
pxList | 列表 |
pxNewListItem | 待插入列表项 |
void vListInsertEnd ( List_t * const pxList , ListItem_t * const pxNewListItem )
{
省略部分非关键代码 … …
/* 获取列表 pxIndex 指向的列表项 */
ListItem_t * const pxIndex = pxList->pxIndex;
/* 更新待插入列表项的指针成员变量 */
pxNewListItem->pxNext = pxIndex;
pxNewListItem->pxPrevious = pxIndex->pxPrevious;
/* 更新列表中原本列表项的指针成员变量 */
pxIndex->pxPrevious->pxNext = pxNewListItem;
pxIndex->pxPrevious = pxNewListItem;
/* 更新待插入列表项的所在列表 */
pxNewListItem->pxContainer = pxList;
/* 更新列表中列表项的数量 */
( pxList->uxNumberOfItems )++;
}
此函数用于将待插入列表的列表项插入到列表 pxIndex 指针指向的列表项前面,是一种无序的插入方法
列表项末尾插入图示:
假设默认列表如下:
此时插入值为30的列表项2,结果如何?
插入值为30的列表项
假设默认列表如下:
此时插入值为30的列表项2,结果如何?
插入值为30的列表项
总结:函数 vListInsertEnd(),是将待插入的列表项插入到列表 pxIndex 指针指向的列表项前面。
它是一种无序的插入方法!!
2.5 列表移出列表项 uxListRemove()
UBaseType_t uxListRemove ( ListItem_t * const pxItemToRemove )
此函数用于将列表项从列表项所在列表中移除
形参 | 描述 |
---|---|
pxItemToRemove | 待移除的列表项 |
列表项有一个结构体成员存取的就是它所属列表,所以我们完全可以通过列表项找到它所属哪一个列表。
返回值 | 描述 |
---|---|
整数 | 待移除列表项移除后,所在列表剩余列表项的数量 |
代码详解查看手册《FreeRTOS开发指南》第七章 ——“FreeRTOS列表和列表项”
UBaseType_t uxListRemove( ListItem_t * const pxItemToRemove )
{
/* 获取待删除列表项所属列表 */
List_t * const pxList = pxItemToRemove->pxContainer;
/* 从列表中移除列表项 */
pxItemToRemove->pxNext->pxPrevious = pxItemToRemove->pxPrevious;
pxItemToRemove->pxPrevious->pxNext = pxItemToRemove->pxNext;
/*如果 pxIndex 正指向待移除的列表项 */
if( pxList->pxIndex == pxItemToRemove )
{
/*pxIndex 指向上一个列表项*/
pxList->pxIndex = pxItemToRemove->pxPrevious;
} else
{
mtCOVERAGE_TEST_MARKER();
}
/*将待移除的列表项的所在列表指针清空*/
pxItemToRemove->pxContainer = NULL;
/*更新列表中列表项的数量*/
( pxList->uxNumberOfItems )--;
/*返回移除后的列表中列表项的数量*/
return pxList->uxNumberOfItems;
}
列表项的删除图示:
移除xList_Item2
3. 列表项的插入和删除实验
实验目的:学会对FreeRTOS 列表和列表项的操作函数使用,并观察运行结果和理论分析是否一致
实验设计:将设计三个任务:start_task、task1、task2
三个任务的功能如下:
start_task:用来创建其他的2个任务
task1:实现LED0每500ms闪烁一次,用来提示系统正在运行
task2:调用列表和列表项相关API函数,并且通过串口输出相应的信息,进行观察
3.1 实现任务函数
task2
List_t TestList; /* 定义测试列表 */
ListItem_t ListItem1; /* 定义测试列表项1 */
ListItem_t ListItem2; /* 定义测试列表项2 */
ListItem_t ListItem3; /* 定义测试列表项3 */
/* 任务二,列表项的插入和删除实验 */
void task2( void * pvParameters )
{
vListInitialise(&TestList); /* 初始化列表 */
vListInitialiseItem(&ListItem1); /* 初始化列表项1 */
vListInitialiseItem(&ListItem2); /* 初始化列表项2 */
vListInitialiseItem(&ListItem3); /* 初始化列表项3 */
ListItem1.xItemValue = 40;
ListItem2.xItemValue = 60;
ListItem3.xItemValue = 50;
/* 第二步:打印列表和其他列表项的地址 */
printf("/**************第二步:打印列表和列表项的地址**************/\r\n");
printf("项目\t\t\t地址\r\n");
printf("TestList\t\t0x%p\t\r\n", &TestList);
printf("TestList->pxIndex\t0x%p\t\r\n", TestList.pxIndex);
printf("TestList->xListEnd\t0x%p\t\r\n", (&TestList.xListEnd));
printf("ListItem1\t\t0x%p\t\r\n", &ListItem1);
printf("ListItem2\t\t0x%p\t\r\n", &ListItem2);
printf("ListItem3\t\t0x%p\t\r\n", &ListItem3);
printf("/**************************结束***************************/\r\n");
printf("\r\n/*****************第三步:列表项1插入列表******************/\r\n");
vListInsert((List_t* )&TestList, /* 列表 */
(ListItem_t*)&ListItem1); /* 列表项 */
printf("项目\t\t\t\t地址\r\n");
printf("TestList->xListEnd->pxNext\t0x%p\r\n", (TestList.xListEnd.pxNext));
printf("ListItem1->pxNext\t\t0x%p\r\n", (ListItem1.pxNext));
printf("TestList->xListEnd->pxPrevious\t0x%p\r\n", (TestList.xListEnd.pxPrevious));
printf("ListItem1->pxPrevious\t\t0x%p\r\n", (ListItem1.pxPrevious));
printf("/**************************结束***************************/\r\n");
/* 第四步:列表项2插入列表 */
printf("\r\n/*****************第四步:列表项2插入列表******************/\r\n");
vListInsert((List_t* )&TestList, /* 列表 */
(ListItem_t*)&ListItem2); /* 列表项 */
printf("项目\t\t\t\t地址\r\n");
printf("TestList->xListEnd->pxNext\t0x%p\r\n", (TestList.xListEnd.pxNext));
printf("ListItem1->pxNext\t\t0x%p\r\n", (ListItem1.pxNext));
printf("ListItem2->pxNext\t\t0x%p\r\n", (ListItem2.pxNext));
printf("TestList->xListEnd->pxPrevious\t0x%p\r\n", (TestList.xListEnd.pxPrevious));
printf("ListItem1->pxPrevious\t\t0x%p\r\n", (ListItem1.pxPrevious));
printf("ListItem2->pxPrevious\t\t0x%p\r\n", (ListItem2.pxPrevious));
printf("/**************************结束***************************/\r\n");
/* 第五步:列表项3插入列表 */
printf("\r\n/*****************第五步:列表项3插入列表******************/\r\n");
vListInsert((List_t* )&TestList, /* 列表 */
(ListItem_t*)&ListItem3); /* 列表项 */
printf("项目\t\t\t\t地址\r\n");
printf("TestList->xListEnd->pxNext\t0x%p\r\n", (TestList.xListEnd.pxNext));
printf("ListItem1->pxNext\t\t0x%p\r\n", (ListItem1.pxNext));
printf("ListItem2->pxNext\t\t0x%p\r\n", (ListItem2.pxNext));
printf("ListItem3->pxNext\t\t0x%p\r\n", (ListItem3.pxNext));
printf("TestList->xListEnd->pxPrevious\t0x%p\r\n", (TestList.xListEnd.pxPrevious));
printf("ListItem1->pxPrevious\t\t0x%p\r\n", (ListItem1.pxPrevious));
printf("ListItem2->pxPrevious\t\t0x%p\r\n", (ListItem2.pxPrevious));
printf("ListItem3->pxPrevious\t\t0x%p\r\n", (ListItem3.pxPrevious));
printf("/**************************结束***************************/\r\n");
/* 第六步:移除列表项2 */
printf("\r\n/*******************第六步:移除列表项2********************/\r\n");
uxListRemove((ListItem_t* )&ListItem2); /* 移除列表项 */
printf("项目\t\t\t\t地址\r\n");
printf("TestList->xListEnd->pxNext\t0x%p\r\n", (TestList.xListEnd.pxNext));
printf("ListItem1->pxNext\t\t0x%p\r\n", (ListItem1.pxNext));
printf("ListItem3->pxNext\t\t0x%p\r\n", (ListItem3.pxNext));
printf("TestList->xListEnd->pxPrevious\t0x%p\r\n", (TestList.xListEnd.pxPrevious));
printf("ListItem1->pxPrevious\t\t0x%p\r\n", (ListItem1.pxPrevious));
printf("ListItem3->pxPrevious\t\t0x%p\r\n", (ListItem3.pxPrevious));
printf("/**************************结束***************************/\r\n");
/* 第七步:列表末尾添加列表项2 */
printf("\r\n/****************第七步:列表末尾添加列表项2****************/\r\n");
TestList.pxIndex = &ListItem1;
vListInsertEnd((List_t* )&TestList, /* 列表 */
(ListItem_t* )&ListItem2); /* 列表项 */
printf("项目\t\t\t\t地址\r\n");
printf("TestList->pxIndex\t\t0x%p\r\n", TestList.pxIndex);
printf("TestList->xListEnd->pxNext\t0x%p\r\n", (TestList.xListEnd.pxNext));
printf("ListItem1->pxNext\t\t0x%p\r\n", (ListItem1.pxNext));
printf("ListItem2->pxNext\t\t0x%p\r\n", (ListItem2.pxNext));
printf("ListItem3->pxNext\t\t0x%p\r\n", (ListItem3.pxNext));
printf("TestList->xListEnd->pxPrevious\t0x%p\r\n", (TestList.xListEnd.pxPrevious));
printf("ListItem1->pxPrevious\t\t0x%p\r\n", (ListItem1.pxPrevious));
printf("ListItem2->pxPrevious\t\t0x%p\r\n", (ListItem2.pxPrevious));
printf("ListItem3->pxPrevious\t\t0x%p\r\n", (ListItem3.pxPrevious));
printf("/************************实验结束***************************/\r\n");
while(1)
{
vTaskDelay(1000);
}
}