🐱作者:一只大喵咪1201
🐱专栏:《RTOS学习》
🔥格言:你只管努力,剩下的交给时间!
🥩FreeRTOS中的链表
链表是FreeRTOS的核心结构,它让系统的功能正常运行,本喵下面来解释一下FreeRTOS中的链表结构以及操作。
如上图所示是FreeRTOS源码中的链表的定义List_t
,这是一个链表头,重要的成员变量有三个:
- volatile UBaseType_t
uxNumberOfItems
:表示链表中包含的节点个数。 - ListItem_t * configLIST_VOLATILE
pxIndex
:这是一个指针变量,表示当前正在操作的节点。 - MiniListItem_t
xListEnd
:这是一个结构体变量,从这个变量可以找到链表中所有节点。
如上图所示MinListItem_t
结构体定义,它也有三个重要的成员变量:
- configLIST_VOLATILE TickType_t
xItemValue
:这是一个值,需要排序的时候才有意义,后面会见识到。 - struct xLIST_ITEM * configLIST_VOLATILE
pxNext
:这是一个指针变量,该变量指向链表中的第一个链表项。 - struct xLIST_ITEM * configLIST_VOLATILE
pxPrevious
:这也是一个指针变量,该变量指向链表中的最后一个链表项。
如上图所示是链表项ListItem_t
的定义,它包含五个重要的成员变量:
- configLIST_VOLATILE TickType_t
xItemValue
:该值作为链表项中的一个数值,在排序时才会起作用。 - struct xLIST_ITEM * configLIST_VOLATILE
pxNext
:该指针变量指向下一个链表项。 - struct xLIST_ITEM * configLIST_VOLATILE
pxPrevious
:该指针变量指向前一个链表项。 - void *
pvOwner
:这也是一个指针变量,指向该链表项所属的容器。以后本喵会介绍。 - struct xLIST * configLIST_VOLATILE
pxContainer
:这也是一个指针变量,指向该链表项所在的List_t
类型链表头。
- 从链表头以及链表项的定义中就可以看出,FreeRTOS中的链表是一个带头双向循环链表。
如上图所示便是FreeRTOS中链表的链接关系,链表头结构体成员xListEnd
中的pxNext
指向第一个链表项的起始地址,链表项中的pxNext
指向下一个链表项的起始地址,如此下去,最后一个链表项中的pxNext
指向链表头中的xListEnd
。
-
此时链表头和链表项中的所有
pxNext
构成一个环路。
链表头中的结构体成员xListEnd
中的pxPrevious
指向最后一个链表项的起始地址,该链表项中的pxPrevious
指向前一个链表项,如此下去,第一个链表项中的pxPrevious
指向链表头中的xListEnd
。
-
此时链表头和链表项中的所有
pxPrevious
构成另一个环路。
如上图所示,由于真正的指向关系不直观,所以本喵后面使用这样的示意图来表示这个链表,要记住无论是pxNext
还是pxPrevious
指向的都是链表项的起始地址。
🥞初始化
如上图所示链表初始化函数vListInitialise
,在该函数中对传入的链表pxList
主要进行了四步操作:
- 让链表头中当前操作节点指针
pxIndex
指向自己的xListEnd
。 - 让
xListEnd
中的xItemValue = portMAX_DELAY
,用该值来区别这是链表尾而不是链表项。 - 让
xListEnd
中的pxNext
和pxPrevious
都指向自己的xListEnd
,初步形成两个环路。 - 让
uxNumberOfItems = 0
表示当前链表中没有链表项,是一个空链表。
此时一个初步的链表就形成了,操作的都是链表头自己。
如上图所示链表项初始化函数vListInitialiseItem
,在该函数中,仅是将链表项中的pxContainer
设置为NULL,因为此时并不知道该链表项属于哪个链表头。
🥞尾部插入
如上图所示插入链表尾部的函数vListInsertEnd
,在该函数中,总体进行了四步操作:
- 从链表头中获得当前正常操作的链表项
pxIndex
。 - 将新的链表项插入到
pxIndex
和pxIndex->pxPrevious
之间。 - 让新链表项的
pxContainer = pxList
,让其找到所属的链表。 - 将链表头中记录链表项个数的
unNumberOfItems
加一。
如上图所示便是尾部插入新链表项的结果,但是它并不是插入到了尾部呀。
假设现在正在操作的是编号为2的链表项,所以pxIndex
指向它,如果没有新链表项插入的话,这几个链表项的操作顺序是2->3->1
。
此时要插入新的链表项,但是并不能影响原本的操作顺序,否则就破坏了公平性,所以将新的链表项4插入到pxIndex
和pxIndex->pxPreviou
之间,此时这几个链表项的操作顺序是2->3->1->4
,并不会影响原来三个链表项的操作顺序。
- 尾插时要保证公共性,插入于正在操作链表项
pxIndex
和它的前一个链表项pxIndex->pxPrevious
之间。
上面所演示的是链表中已经存在链表项时尾插的结果,如果是一个空链表呢?
如上图所示第一次尾插的结果,在插入之前pxIndex
和pxIndex->pxPrevious
都是指向的链表头中的xListEnd
,当新节点插入时,pxIndex->pxPrevious
指向新节点,pxIndex->pxNext
也指向新节点,新节点的pxIndex
和pxPrevious
都指向链表头中的xListEnd
。
所以说,尾插函数vListInsertEnd
可以实现第一次插入和已经存在多个链表项时再插入新链表项两个场景。
🥞按顺序插入
如上图所示按照链表项中的xItemValue
值插入函数vListInsert
,该函数中主要进行了四步操作:
- 获取新插入链表项中的
xItemValue
值。 - 根据
xItemValue
值在链表中寻找合适位置:-
xItemValue = portMAX_DELAY
说明新的链表项应该插入到链表的最后面,直接让插入位置pxIterator
等于链表的最后一项。 -
xItemValue
不是最大,则迭代寻找合适位置,pxIterator
从链表头开始,直到pxIterator->pxNext
指向的链表项中的xItemValue
大于新链表项的xItemValue
,此时得到插入位置就是pxIterator
后面。
-
- 插入新链表项,改变指向关系。
- 修改新链表项中的
pxContainer
,让其属于当前链表头,并且修改链表头中的链表项个数。
如上图所示是插入后的结果,原本链表中的xItemValue
从左到右依次是1->3->4
,将xItemValue
为2的新链表项插入以后,xItemValue
成了1->2->3->4
。
🥞删除
如上图所示删除指定链表项的函数uxListRemove
,该函数中进行的主要操作也是四步:
- 从要删除的链表项中得到它所属的链表
pxList
。 - 改变链表中的指向关系,让被删除链表项的前一个直接和被删除链表项的后一个建立互相的指向关系。
- 进行判断,如果删除的是正在操作的链表项,那么需要将
pxIndex
指向下一个链表项,更换正在操作的链表项。 - 让被删除的链表项失忆,也就是将其
pxContainer = NULL
,让它找不到原本所属的链表,再将链表头中链表项的个数减一,最后返回链表项的个数。
如上图所示是删除后的示意图,所谓删除就是改变被删除链表项的前一个和后一个链表项的指向关系,让其从链表中脱离出来。
🥩堆的管理
很多人把"堆栈"相提并论,其实"堆"、"栈"是完全没有联系。"栈"的作用我们前面已经讲了很多,"堆"是什么?
-
在汇编代码里指定一个AREA:在汇编代码里,使用SPACE命令可以分配一段空间,这段空间就是堆:
- 在C代码里,定义一个全局数组:该数组的大小是17KB,这段空间就是堆:
"堆"就是一块或者多块内存,我们可以从中申请一小块内存来使用,使用完毕后可以释放这一小块内存。
简单地说,一开始,"堆"是一些空闲内存,我们可以:
- 使用malloc函数从中申请、获得一小块内存
- 使用free函数释放这一小块内存
- 这些malloc、free函数就是用来管理这些内存的
- malloc、free函数可以有其他名称,比如FreeRTOS里是pvPortMalloc、vPortFree。
在FreeRTOS的源码中,默认提供了5个文件,对应内存管理的5种方法:
文件 | 优点 | 缺点 |
---|---|---|
heap_1.c | 分配简单,时间确定 | 只分配、不回收 |
heap_2.c | 动态分配、最佳匹配 | 碎片、时间不定 |
heap_3.c | 调用标准库函数 | 速度慢、时间不定 |
heap_4.c | 相邻空闲内存可合并 | 可解决碎片问题、时间不定 |
heap_5.c | 在heap_4基础上支持分隔的内存块 | 可解决碎片问题、时间不定 |
只能使用上诉五种方式的中的一种来管理堆,其中heap_3.c
由于使用的是标准库函数中的malloc
和free
,速度比较慢,所以本喵这里也不做介绍,只介绍其他四种。
🥞heap_1.c
如上图所示在堆区上申请空间的函数pvPortMalloc
,其中xWantedSize
是要申请的空间大小,申请过程主要分为四步:
- 创建返回地址
pvReturn
和对齐地址pucAlignedHeap
,让这两个指针都为0。 - 对申请的空间大小进行对齐。
如上图所示宏定义#define portBYTE_ALIGNMENT 8
规定了8字节对齐,什么是字节对齐呢?
如上图所示,假设现在有9个字节的空间在内存中连续排列,而我们的CPU是32位的,也就是说一次读取或者写入数据必须操作的是4字节大小的空间。
现在一共9字节,操作两次以后还剩下一个字节,再操作时仍然是4字节,所以要想操作第9个字节,就会额外多操作三个字节,此时就会导致效率低下。
- 甚至有的CPU并不支持这种不对齐访问。
由于是8字节对齐,所以申请的空间大小必须是8的整数倍,如果不符合8字节对齐,就需要向上对齐,如申请100个字节,实际上申请的是对齐后的104字节。
- 找到堆区的对齐地址
pucAlignedHeap
如上图所示,假设整个堆区ucHeap
在内存上的起始地址是0x20000001
,按照CPU每次操作4字节的规律,该地址无论如何也无法作为单次CPU的起始地址,所以操作起来不方便。
按照代码中所写,所以对齐地址求出来就是0x20000008
,该地址一定是CPU操作时4字节中的起始地址。
此时对齐地址pucAlignedHeap
就是指向这里,而且让xNextFreeByte + = xWantedSize
,得到此次申请空间大小。
- 获取申请空间
如上图所示,如果是第一次申请空间,那么最后返回的就是对齐地址pucAlignedHeap
所指向的地址,如果不是第一次申请,那么在pucAlignedHeap
基础上增加上次空间大小的偏移量pxNextFreeByte
得到的就是返回地址。
简单来说,heap_1
管理堆的方式就是,通过pucAlignedHeap
和pxNextFreeByte
两个全局变量,每申请一次,就返回上一次申请后剩余空间的起始位置。
如上图释放动态空间函数vPortFree
,并不支持释放空间。
- heap_1.c里,只能用pvPortMalloc函数来申请空间,无法使用vPortFree函数来释放空间。
🥞heap_2.c
heap_2.c里,使用链表来管理内存。链表结构体为:
这个结构体用来表示空闲块:
-
pxNextFreeBlock
:指向下一个空闲块 -
xBlockSize
:当前空闲块的内存大小
如上图所示,在这个结构体后面,紧跟着空闲内存。
- 在堆空间
static uint8_t ucHeap[ configTOTAL_HEAP_SIZE ]
上,空闲空间往前偏移8个字节就得到BlockLink_t
结构体的起始地址。
初始化:
如上图所示堆的初始化函数prvHeapInit
,在该文件中定义了两个BlockLink_t
类型的全局变量,一个是链表头xStart
,另一个是链表尾xEnd
,在该函数中主要进行四步操作:
- 从整个堆空间上计算对齐地址
pucAlignedHeap
。 - 让链表头
xStart
中的pxNextFreeBlock
指向对齐地址,并且将链表头中的xBlockSize = 0
,因为链表头并不管理空闲内存。 - 让链表尾
xEnd
中的pxNextFreeBlock
指向空,xBlockSize = configADJUSTED_HEAP_SIZE
,这是堆的最大值,为了排序时方便才这样设计的。 - 让
pxFirstFreeBlock
指向对齐地址,并且构造BlockLink_t
中的成员,让xBlockSize = configADJUSTED_HEAP_SIZE
,pxNextFreeBlock
指向链表尾。
如上图所示初始化完成的结果,此时在整块堆空间的中,最前面的8字节就是BlockLink_t
结构体,包含该空间的大小,并链入了管理空闲堆空间的链表中。
分配内存:
如上图所示分配空间函数pvPortMalloc
的部分代码,主要进行了四步操作:
- 如果是第一次调用
pvPortMalloc
,则先对整个堆区进行初始化,让整个堆区作为空闲空间链入到空闲空间管理链表xStart
和xEnd
之间。 - 对申请的空间大小进行对齐计算。
- 从空闲空间管理链表中寻找合适的空间块。
- 假设此时链表中存在多个含有
BlockLink_t
的空闲块,所以根据要申请空间的大小迭代找到比申请空间大的空闲块。
- 假设此时链表中存在多个含有
- 通过链表找到的是空闲块的起始地址,包含
BlockLink_t
,所以向后偏移8个字节,得到该空闲块的对齐地址作为返回值供申请者使用。
如上图,返回的是该空闲块中红色箭头指向的地址。
如上图所示的紧接着前面pvPortMalloc
函数剩下的代码,主要有四步操作,本喵这里接着前面从标号5开始讲解:
- 将寻找到的空闲块从空闲链表中移除,也就是修改该块前后的指向关系。
- 如果找到的这块空间大于所申请的字节数,将用不了的部分赋值给
pxNewBlockLink
。 - 构造用不了的那部分块中的
BlockLink_t
结构体。 - 调用
prvInsertBlockIntoFreeList
将这个剩余的块作为空闲块插入到管理链表中。
如上图所示prvInsertBlockIntoFreeList
宏函数,用来插入空闲内存块到管理链表中,主要操作分为三步:
- 获取插入内存块的大小
xBlockSize
。 - 根据大小
xBlcokSize
迭代按照升序找到合适的插入位置pxIterator
。 - 将内存块
pxBlockToInsert
插入到pxIterator
之后。
如上图所示是最终分配效果,Block1
从管理链表中移除,供申请者使用,Blcok2
是用不了剩下的部分,重新链入到管理链表中。
释放内存:
如上图所示释放内存函数vPortFree
,主要操作有两步:
- 由于传入的
pv
是申请者使用的地址,所以向前偏移8个字节得到该内存块的BlcokLink_t
地址。 - 调用
pxBlockToInsert
将该内存块链入到管理链表中。
如上图所示,假设释放的是Block1
内存块,此时该内存块和原本的Block2
一起在管理链表中。
heap_2
管理的链表,支持内存的申请和释放。- 由于释放的内存块直接链入到管理链表,所以如果再次申请的内存比上次释放的大,那么释放的这块就无法再次利用,就会存在内存碎片。
- 所以
heap_2
适合用在频繁申请和释放固定大小内存的场景。
🥞heap_4.c
初始化:
如上图所示是使用prvHeapInit
初始化完的示意图,heap_4
整体上和heap_2
的管理方式一样,也是通过链表和BlockLink_t
来管理空闲内存块,但是不一样的是:
- 链表尾
xEnd
位于整个堆空间的末尾,它并不是独立的一个变量,而是依附在空闲空间上。 - 链表尾
xEnd
中的xBlockSize = 0
,和heap_2
中的configADJUSTED_HEAP_SIZE
不一样。
分配内存:
如上图所示,分配内存时和heap_2
一样,将Block1
中管理链表中移除,将用不完的Block2
部分再次链入到链表中,返回值也是Block1
的对齐地址。
在将用不了的内存块重新链入到管理链表中时,也会调用prvInsertBlockIntoFreeList
函数,heap_4
和heap_2
的区别就在这个函数中。
释放内存:
释放内存时,和heap_2
一样,也会调用到prvInsertBlockIntoFreeList
函数来将释放的内存块链入到管理链表,来分析一下这个函数:
如上图所示prvInsertBlockIntoFreeList
的部分代码,这里进行的操作就是寻找合适的插入位置。
- 没有获取插入内存块的大小。
- 迭代时按照内存块的地址寻找,当插入内存块
pxBlockToInsert
的地址小于等于pxIterator->pxNextFreeBlock
时,将内存块插入到pxIterator
后面。
如上图所示prvInsertBlockIntoFreeList
中紧接前面部分的后续代码,进行的操作主要分为3步:
-
在寻找到插入位置
pxIterator
以后,先判断插入内存块pxBlockToInsert
和其前面的pxIterator
是否紧挨着(pxIterator
的地址 + 偏移量 ==pxBlockToInsert
的地址)。- 如果相等,说明
pxBlockToInsert
和pxIterator
紧挨着,可以进行合并,此时改变pxBlockToInsert
的大小xBlockSize
和pxNextFreeBlock
覆盖pxIterator
。
- 如果相等,说明
-
再判断判断插入内存块
pxBlockToInsert
和其后面的pxIterator->pxNextFreeBlock
是否紧挨着(pxBlockToInsert
的地址 + 偏移量 ==pxIterator->pxNextFreeBlock
的地址)。- 如果相等,说明
pxBlockToInsert
和pxIterator->pxNextFreeBlock
是紧挨着,可以进行合并,同样仅修改pxBlockToInsert
的BlockLink_t
覆盖pxIterator->pxNextFreeBlock
即可。
- 如果相等,说明
- 这里的偏移量就是块的大小
pxBlockToInsert->xBlockSize
。
- 如果找到插入位置
pxIterator
后,发现pxBlockToInsert
和它前面以及后面的内存块都不挨着,就无法实现合并,只能和heap_2
一样将pxBlockToInsert
插入到管理链表中。
如上图所示是在分配内存后将用不了的内存块插入管理链表和释放内存时将释放的内存块插入管理链表时,没有进行合并的结果示意图,此时和heap_2
没有区别。
如上图所示是将插入的内存块与管理链表中的其他内存块合并后的结果示意图。
- 管理链表中的内存块合并以后变大了,再次申请比上一次释放掉的更大内存块时,合并后的内存可以继续被利用。
- 克服了
heap_2
再次申请更大空间时会有内存碎片的问题。
🥞heap_5.c
heap_5
和heap_4
机会一样,只是heap_5
支持多个不连续区域作为堆。
初始化:
如上图所示结构体HeapRegion_t
是用来描述用作堆的区域的,pucStartAddress
表示该区域的起始地址,xSizeInbytes
表示该区域的大小。
如上图所示,在使用heap_5
之前,需要先定义一个全局的HeapRegion_t
类型的数组array
,该数组中存放的就是多个连续的堆区,然后调用vPortDefineHeapRegions
来初始化所有的堆。
- 数组中的最后一项是
{NULL, 0}
,当发现某一个堆区的地址是NULL
的时候,说明就遍历到了数组中的最后一项。
如上图所示vPortDefineHeapRegions
函数,该函数内部主要进行了五步操作:
- 创建
while
循环来遍历所有不连续的堆区域。 - 求每个堆区域的对齐地址和对齐大小。
- 处理第一个堆区时,将其链入到
xStart
链表头。 - 在每个堆区域末尾构造
BlockLink_t
。 - 将所有堆区域首尾相连在一起。
如上图所示是将两个不连续堆区初始化后首尾相连在一起的结果示意图。
其他操作:
在初始化以后,就可以将这些不连续的堆看成是一个堆,其他操作完全按照heap_4
来就可以。
🥩总结
对于FreeRTOS的链表操作,一定要理解透彻,因为后面的任务TCB等结构体完全依赖于链表操作,尤其注意尾部插入时不能破坏原本链表的公平性。文章来源:https://www.toymoban.com/news/detail-756763.html
对于多种堆的管理方式,要知道它们适用的场合和大致的原理,根据适用场景适用合适的管理方式。文章来源地址https://www.toymoban.com/news/detail-756763.html
到了这里,关于【RTOS学习】FreeRTOS中的链表 | 堆的管理的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!