目录
1.为什么要学列表?
2.什么是列表和列表项?
2.1 列表
2.2列表项
2.3,迷你列表项
3.列表与列表项的初始化
3.1 列表初始化
3.2列表项初始化
4.列表项的“增删查”(插入、删除、遍历)
4.1列表项的插入
4.1.1普通插入vListInsert()
4.1.2列表项末尾插入vListInsertEnd()
4.2 列表项的删除
4.3列表的遍历
总结:
1.为什么要学列表?
要想看懂 FreeRTOS 源码并学习其原理,有一个东西绝对跑不了,那就是 FreeRTOS 的列表和列表项。列表和列表项是FreeRTOS的一个数据结构,FreeRTOS 大量使用到了列表和列表项,它是 FreeRTOS 的基石。要想深入学习并理解 FreeRTOS,那么列表和列表项就必须首先掌握,否则后面根本就没法进行。
2.什么是列表和列表项?
2.1 列表
列表是 FreeRTOS 中的一个数据结构,概念上和链表有点类似,列表被用来跟踪 FreeRTOS 中的任务。与列表相关的全部东西都在文件 list.c 和 list.h 中。在 list.h 中定义了一个叫 List_t 的结构体,代码如下:
代码可能有些难以理解,下面是容易理解的列表图:
其中:
uxNumberOfItems 用来记录列表中列表项的数量
pxIndex 用来记录当前列表项索引号,用于遍历列表
列表中最后一个列表项xListEnd,用来表示列表结束,此变量类型为 MiniListItem_t,这是一个迷你列表项。
注意!此图只是主要列表成员变量。
2.2列表项
列表项就是存放在列表中的项目,FreeRTOS 提供了两种列表项:列表项和迷你列表项。这
两个都在文件 list.h 中有定义,定义如下:
同样,下面是容易理解的列表项图:
xItemValue 为列表项值
pxNext 指向下一个列表项
pxPrevious 指向前一个列表项,和 pxNext 配合起来实现类似双向链表的功能
pvOwner 记录此链表项归谁拥有,通常是任务控制块
pvContainer 用来记录此列表项归哪个列表。注意和 pvOwner 的区别,在前面讲解任务
控制块 TCB_t 的时候说了在 TCB_t 中有两个变量 xStateListItem 和 xEventListItem,这两个变量的类型就是 ListItem_t,也就是说这两个成员变量都是列表项。以xStateListItem 为例,当创建一个任务以后 xStateListItem 的 pvOwner 变量就指向这个任务的任务控制块,表示 xSateListItem 属于此任务。当任务就绪态以后 xStateListItem 的变量 pvContainer 就指向就绪列表,表明此列表项在就绪列表中。举个通俗一点的例子:小王在上二年级,他的父亲是老王。如果把小王比作列表项,那么小王的 pvOwner 属性值就是老王,小王的 pvContainer 属性值就是二年级。
注意!此图也只是主要列表成员变量。
2.3,迷你列表项
上面我们我们说了列表项,现在来看一下迷你列表项,迷你列表项在文件 list.h 中有定义,
如下:
同上,迷你列表项图如下:
3.列表与列表项的初始化
3.1 列表初始化
新创建或者定义的列表需要对其做初始化处理,列表的初始化其实就是初始化列表结构体 List_t 中的各个成员变量,列表的初始化通过使函数 vListInitialise()来完成,此函数在 list.c 中有定义,函数如下:
xListEnd 用来表示列表的末尾,而 pxIndex 表示列表项的索引号,此时列表只有一个列表项,那就是 xListEnd,所以 pxIndex 指向 xListEnd。
xListEnd 的列表项值初始化为 portMAX_DELAY, portMAX_DELAY 是个宏,在文件portmacro.h 中有定义。根据所使用的 MCU 的不同,portMAX_DELAY 值也不相同,可以为 0xffff 。
初始化列表项 xListEnd 的 pxNext 变量,因为此时列表只有一个列表项 xListEnd,因此 pxNext 只能指向自身。
初始化 xListEnd 的 pxPrevious 变量,也指向 xListEnd 自身。
由于此时没有其他的列表项,因此 uxNumberOfItems 为 0,注意,这里没有算 xListEnd。初始化列表项中用于完整性检查字段,只有宏configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES 为 1 的时候才有效。同样的根据所选的MCU 不同其写入的值也不同,可以为 0x5a5a 或者 0x5a5a5a5aUL。STM32 是 32 位系统写入的是 0x5a5a5a5aUL,或者 0xffffffffUL,本文中为 0xffffffffUL。
下面是相应列表初始化图:
3.2列表项初始化
同列表一样,列表项在使用的时候也需要初始化,列表项初始化由函数 vListInitialiseItem()
来完成,函数如下:
列表项的初始化很简单,只是将列表项成员变量 pvContainer 初始化为 NULL,并且给用于完整性检查的变量赋值。有朋友可能会问,列表项的成员变量比列表要多,怎么初始化函数就这么短?其他的成员变量什么时候初始化呢?这是因为列表项要根据实际使用情况来初始化,比如任务创建函数 xTaskCreate()就会对任务堆栈中的 xStateListItem 和xEventListItem 这两个列表项中的其他成员变量在做初始化,任务创建过程后面会详细说明。
4.列表项的“增删查”(插入、删除、遍历)
4.1列表项的插入
列表项有两种插入方式,普通插入与末尾插入。
4.1.1普通插入vListInsert()
下面首先来讲普通插入,它通过函数 vListInsert()来完成,函数原型如下:
其中:
pxList:列表项要插入的列表。
pxNewListItem: 要插入的列表项。
函数 vListInsert()的参数 pxList 决定了列表项要插入到哪个列表中,pxNewListItem 决定了
要插入的列表项,但是这个列表项具体插入到什么地方呢?要插入的位置由列表项中成员变量xItemValue 来决定。列表项的插入根据 xItemValue 的值按照升序的方式排列!接下来我们来具体看一下函数 vListInsert()的整个运行过程,函数代码如下:
我总结一下该代码的逻辑,
首先是获取要插入的列表项值,即列表项成员变量 xItemValue 的值,因为要根据这个值来确定列表项要插入的位置。
其次检查列表和列表项的完整性。
再然后获取该列表项要插入到什么位置!如果要插入的列表项的值等于portMAX_DELAY,也就是说列表项值为最大值,要插入的位置就是列表最末尾。
之后获取要插入点,注意!插入的列表项会被放到 xListEnd 前面。
如果要插入的列表项的值如果不等于 portMAX_DELAY 那么就需要在列表中一个一个的找自己的位置,这个 for 循环就是找位置的过程,当找到合适列表项的位置的时候就会跳出。由于这个 for 循环是用来寻找列表项插入点的,所以 for 循环体里面没有任何东西。这个查找过程是按照升序的方式查找列表项插入点的。
获取插入点之后,将列表项插入到列表中,如图(6)中的四行,插入过程和数据结构中双向链表的插入类似。
列表项的成员变量 pvContainer 记录此列表项属于哪个列表的。
列表的成员变量 uxNumberOfItems 加一,表示又添加了一个列表项。
普通插入是按插入值以升序的方式插入的,若从头先插入40插入值的列表项,如下图:
之后插入60插入值的列表项:
再插入一个50插入值的列表项:
4.1.2列表项末尾插入vListInsertEnd()
列表末尾插入列表项的操作通过函数 vListInsertEnd ()来完成,函数原型如下:
参数:
pxList:列表项要插入的列表。
pxNewListItem: 要插入的列表项。
函数 vListInsertEnd()源码如下:
它与vListInsert()的区别在于,函数vListInsert()向列表中插入一个列表项的时候这个列表项的位置是通过列表项的值,也就是列表项成员变量 xItemValue 来确定。vListInsertEnd()是往列表的末尾添加列表项的,我们知道列表中的 xListEnd 成员变量表示列表末尾的,那么函数 vListInsertEnd()插入一个列表项是不是就是插到 xListEnd 的前面或后面啊?这个是不一定的,这里所谓的末尾要根据列表的成员变量pxIndex 来确定的!前面说了列表中的 pxIndex 成员变量是用来遍历列表的,pxIndex 所指向的列表项就是要遍历的开始列表项,也就是说 pxIndex 所指向的列表项就代表列表头!由于是个环形列表,所以新的列表项就应该插入到 pxIndex 所指向的列表项的前面。
标记新的列表项 pxNewListItem 属于列表 pxList。
列表项末尾插入图示:
我们先准备一个默认列表,如下图:
在40与60的插入值里插入50的列表项。
列表 List 的 pxIndex 指向列表项 ListItem1,因此调用函数 vListInsertEnd()插入 ListItem3 的话就会在 ListItem1 的前面插入。
4.2 列表项的删除
有列表项的插入,那么必然有列表项的删除,列表项的删除通过函数 uxListRemove()来完成,函数原型如下:
UBaseType_t uxListRemove( ListItem_t * const pxItemToRemove )
参数:
pxItemToRemove:要删除的列表项。
返回值:
返回删除列表项以后的列表剩余列表项数目。
注意,列表项的删除只是将指定的列表项从列表中删除掉,并不会将这个列表项的内存给
释放掉!如果这个列表项是动态分配内存的话。
函数 uxListRemove()的源码如下:
首先,要删除一个列表项我们得先知道这个列表项处于哪个列表中,读取列表项中的成员变量 pvContainer 就可以得到此列表项处于哪个列表中,所以直接读取。
将要删除的列表项的前后两个列表项“连接”在一起,完成列表项的删除。
如果列表的 pxIndex 正好指向要删除的列表项,那么在删除列表项以后要重新给pxIndex 找个“对象”,这个新的对象就是被删除的列表项的前一个列表项。
把被删除列表项的成员变量 pvContainer 清零。
返回新列表的当前列表项数目。
4.3列表的遍历
介绍列表结构体的时候说过列表 List_t 中的成员变量 pxIndex 是用来遍历列表的,FreeRTOS 提供了一个函数来完成列表的遍历,这个函数是 listGET_OWNER_OF_NEXT_ENTRY()。每调用一次这个函数列表的 pxIndex 变量就会指向下一个列表项,并且返回这个列表项的 pxOwner变量值。这个函数本质上是一个宏,这个宏在文件 list.h 中如下定义:
pxTCB 用来保存 pxIndex 所指向的列表项的 pvOwner 变量值,也就是这个列表项属于谁的?通常是一个任务的任务控制块。pxList 表示要遍历的列表。
列表的 pxIndex 变量指向下一个列表项。
然后判断,如果 pxIndex 指向了列表的 xListEnd 成员变量,表示到了列表末尾。
最后将 pxIndex 所指向的新列表项的 pvOwner 赋值给 pxTCB。
此函数用于从多个同优先级的就绪任务中查找下一个要运行的任务。
总结:
FreeRTOS的列表与列表项是我们学习并理解FreeRTOS任务控制的基础,任务创建,删除,任务的上下文切换都会有列表与列表项的参与,由此可见他们的重要性,,也希望大家看我的文章能够有所收获,早日掌握FreeRTOS!
FreeRTOS开发手册word版网盘
通过百度网盘分享的文件:STM32F1 FreeRTOS开发手册_V1.1.docx
链接:https://pan.baidu.com/s/14On7A8iwbEeLxLN2Ghb0HQ
提取码:sxss