具有O(1)时间复杂度的tlsf内存管理算法分享

WZH · 发表于 2022-2-18 20:01:15

最近使用lvgl时，发现其中底层的内存分配管理很优秀，在网上查询后知道，这个算法名字为tlsf内存分配算法。 tlsf 全称 Two-Level Segregated Fit memory allocator，两级隔离Fit内存分配器，是一款通用的动态内存分配器，专门设计用于满足实时要求，malloc和free可以达到O(1)的时间复杂度，也就是说无论之前申请过多少次内存，其调用时间都是一定的，这一点是一般的内存管理算法无法比拟的。
一般简单的内存管理算法都是把所有内存块或者空闲块使用单链表进行管理，malloc和free的时间复杂度为O(n)。这种方法在系统内存碎片少时，其效率较高，而当内存碎片多的时候，大部分时间都浪费在了查找空闲块上了，导致系统随着内存分配的增多越分配越卡。不过这种简单的顺序链表内存管理算法由于实现很简单，所以依旧有很多很多嵌入式系统使用这种分配策略，像是RTX5，FreeRTOS的heap4、heap5都是采用的这种内存分配策略，包括楼主以前也实现过一个使用单链表管理内存的算法，在简单的内存应用中这种办法是不错的选择。
而tlsf算法主要采用两级位图(Two-Level Bitmap)与分级空闲块链表(Segregated Free List)的数据结构管理动态内存池(memory pool)以及其中的空闲块(free blocks)，用Good-Fit（选择最匹配的内存块进行分配，可以进一步降低内存碎片）的策略进行分配。
tlsf的实现原理以及其技术参数可以看这个网址http://www.gii.upv.es/tlsf/mm/arch
楼主也对普通的单链表内存管理算法与tlsf进行了仿真测试，使用的VisualStudio编写的测试代码，测试工程与tlsf源码见附件。
测试结果如下：

相同的测试条件下，普通的单链表内存管理算法耗时7.99s，而tlsf算法仅耗时0.28s，差距不是一般的大。

tlsf.zip (10.67 KB, 下载次数: 53)

tlsf_test.zip (20.59 MB, 下载次数: 54)

eric2013 · 发表于 2022-2-18 20:11:40

是不是这个，我记得好几个网友分享过。

我来分享一下 tlsf v2.4.4 / v2.4.6 malloc 动态内存管理 , 据说是比较牛逼的
https://www.armbbs.cn/forum.php?mod=viewthread&tid=108293

分享一个实时系统动态内存算法TLSF
https://www.armbbs.cn/forum.php?mod=viewthread&tid=91606

WZH · 发表于 2022-2-18 20:15:14

eric2013 发表于 2022-2-18 20:11
是不是这个，我记得好几个网友分享过。

我来分享一下 tlsf v2.4.4 / v2.4.6 malloc 动态内存管理 , 据 ...

是这个

，算法很优秀，可惜没有早点发现

WZH · 发表于 2022-2-18 20:38:26

eric2013 发表于 2022-2-18 20:11
是不是这个，我记得好几个网友分享过。

我来分享一下 tlsf v2.4.4 / v2.4.6 malloc 动态内存管理 , 据 ...

对的

，这个内存管理算法很优秀，可惜没能早些发现

eric2013 · 发表于 2022-2-18 20:54:22

WZH 发表于 2022-2-18 20:38
对的，这个内存管理算法很优秀，可惜没能早些发现

坛友反馈这个比较费空间，有时间了你看你方便对比测试下不

WZH · 发表于 2022-2-18 21:11:32

eric2013 发表于 2022-2-18 20:54
坛友反馈这个比较费空间，有时间了你看你方便对比测试下不

刚刚测试了下，具体的参数如下：
tlsf句柄大小: 3188B=3.11KB(可能是因为利用位图查找，所以用这么多内存）
tlsf内存池的头部大小：8B
tlsf每个内存块的头部大小：4B

Mem_Manage句柄大小：24B
Mem_Manage每个内存块的头部大小：8B

eric2013 · 发表于 2022-2-19 08:28:20

WZH 发表于 2022-2-18 21:11
刚刚测试了下，具体的参数如下：
tlsf句柄大小: 3188B=3.11KB(可能是因为利用位图查找，所以用这么多内 ...

通过位图来保证搜索时间，就得额外占用内存来弥补，估计是这个思路。

WZH · 发表于 2022-2-19 15:06:06

eric2013 发表于 2022-2-19 08:28
通过位图来保证搜索时间，就得额外占用内存来弥补，估计是这个思路。

对的，这个算法选择用位图搜索原因就是很多单片机都带有clz指令等位操作指令，能加速查找。

eric2013 · 发表于 2022-2-19 15:20:47

WZH 发表于 2022-2-19 15:06
对的，这个算法选择用位图搜索原因就是很多单片机都带有clz指令等位操作指令，能加速查找。

嗯，这种动态内存分配，要么费时间，要么费RAM。

		自动登录	找回密码
密码			立即注册