TLSF是Two Level Segregated Fit memory allocator的缩写，是一种动态内存分配算法。名称中有两个关键词，Segregated Fit和Two Level。
首先我们来了解什么是Segregated Fit。在内存分配算法中，空闲内存块的管理是算法的核心。根据寻找空闲内存块的策略，可以将内存分配算法分为以下几种：
- Sequential Fit：将所有的空闲内存块，放入到一个单向/双向链表中。这是最基础的管理策略。算法非常简单，但寻找空闲内存块的效率依赖于链表的大小。
- Segregated Fit：将所有的空闲块，放入到一组链表中，每一个链表中只包含某一个大小范围的空闲块。例如最典型的dlmalloc算法。
- Buddy System： Segregate Fit算法的变种，具有更好的切割和合并效率，又很多变种，如Binary Buddies，Fibonacci Buddies， Weighted Buddies等。通常这类算法的内部碎片化问题比较严重。
- Indexed Fit：通过一些高阶的数据结构来索引（Index）空闲的内存块。例如基于平衡树的“Best Fit”算法。
- Bitmap Fit： Indexed Fit算法的变种，通过一小段内存的位图来标记对应的内存是空闲的还是使用中。
所以TLSF是一种通过一组链表来管理不同大小内存块的内存分配算法。
为什么称为Two Level？
给定一个内存块的大小，确定在两级链表中的位置（f,s）的算法如下：
其中2的SLI次幂表示第二级链表的区间大小，比如上图中，区间大小为16，即2的4次方。这样大小为460字节的空闲快在链表中的位置为f=8,s=12,如下图：
实时系统RTOS对内存分配算法有以下两个要求：
- 内存分配/释放的执行时间可预期，可接受的。由于RTOS对指令的执行时间有严格要求，所以常常采用静态内存分配的方法，以获得一个可以预期的执行时间。
- 内存分配算法的碎片化程度要低，这是由于RTOS往往长时间执行，碎片化程度高会导致内存分配失败。
TLSF算法的目标运行系统是：
- 可信的执行环境，Trusted Environment，应用不会故意破坏数据或者窃取数据。
- 有限的物理内存。
- 没有物理MMU来支持虚拟内存。
为了在这样的环境下运行，TLSF算法使用了如下的策略：
- Immediate coalescing，立即合并，当内存块被释放后，立即与相邻的空闲内存块合并，以获得一个更大的空闲块，插入到链表的相应位置。这样可以减少碎片化。
- Splitting threshold，分割阈值，最小可分配的内存块大小为16字节，应用一般不会分配一些基本的数据结构，如int、char等。限定最小可分配大小为16字节，这样可以在空闲的内存块中存储一些管理信息。
- Good-fit strategy，TLSF会尽可能的返回一个最小的、能够满足需求的内存块。
- Same strategy for all block sizes，对于不同大小的内存请求，TLSF只有一个分配策略，实现相对简单，执行时间可以预期。相应的dlmalloc根据所请求的内存大小不同，有多达4种内存分配策略。
- Memory is not cleaned-up，分配个应用的内存没有被请0.
TLSF的特点在于：
- 可以预期的分配执行时间，无论对于多达的内存分配请求，TLSF可以在限定的时间内完成分配。
- 碎片化程度低。
版权声明：
本文来源网络，所有图片文章版权属于原作者，如有侵权，联系删除。
本文网址：https://www.mushiming.com/mjsbk/11333.html