注：本文大部分内容摘自论文《TLSF: a New Dynamic Memory Allocator for Real-Time Systems》，可通过“科学互联网”访问以下链接阅读原文： http://www.gii.upv.es/tlsf/files/e CRTs 04 _ tlsf.pdf。
TLSF TLSF是twolevelsegregatedfitmemoryallocator的缩写，是一种动态内存分配算法。 名称有两个关键字： Segregated Fit和Two Level。
首先，让我们了解什么是Segregated Fit。 在内存分配算法中，空闲内存块的管理是算法的核心。 根据查找可用内存块的方式，可以将内存分配算法分为以下几种：
Sequential Fit :将所有可用内存块放在一个单向/双向链表中。 这是最基本的管理战略。 算法非常简单，但查找可用内存块的效率取决于链表的大小。 Segregated Fit :将所有空闲块放置在一系列链表中。 每个链表只包含一个大小范围的空闲块。 例如最典型的dlmalloc算法。 Segregatefit算法的变种，切割和整合效率更高，如二进制构建、光纤构建、加权构建等。 通常，这类算法的内部碎片化问题比较严重。 索引配合：通过一些高级数据结构对空闲的内存块进行索引(索引)。 例如基于平衡树的“最佳拟合”算法。 bitmap fit :索引拟合算法的变种。 用小内存的位图标记对应的内存是空闲的还是使用中的。 因此，TLSF是一种通过一系列链表来管理不同大小的存储器块的存储器分配算法。
为什么叫Two Level？
的基本Segregated Fit算法使用一系列链表来管理自由块，使每个链表只包含特定长度范围的自由块，因此链表数组的长度可能会变大。 如下图所示，TLSF为了简化位置检索过程，使用了两个链表。 在第一级，可用内存块的大小按2的幂进行分类。 例如，(16、32、64 . )。 第二层链表基于第一层，以一定的间隔线性分段。 例如，2的6次方这一段落分为4个小区间【64、80】、【80、96】、【96、112】、【112、128】。 每个级别的链表都有一个bitmap，用于标记相应的链表中是否有内存块。 例如，在一级比特映射的低4比特0到100，即2的6次方的区间中存在空块。 的二级链表对应的bitmap位0010和【80，96】区间有空闲块。 也就是说，下一个89字节。
指定内存块的大小，决定二阶段链表位置(f，s )的算法如下。
其中2的SLI次方表示二级链表的区间大小。 例如，在上图中，区间的大小为16，即2的4次方。 这样大小为460字节的空闲在链表位置为f=8，s=12，如下图所示。
支持TLSF的环境实时系统RTOS对内存分配算法有两个要求：
内存分配/释放的执行时间预期且可接受。 由于RTOS对指令的执行时间有严格的要求，所以为了得到预期的执行时间，经常采用静态内存分配的方法。 内存分配算法碎片化程度低，是因为RTOS经常长时间运行，碎片化程度高则内存分配失败。 TLSF算法的目标执行系统如下。
可靠的执行环境、可信环境和APP应用程序不会故意破坏或窃取数据。 有限的物理内存。 没有支持虚拟内存的物理MMU。 为了在这种环境下运行，TLSF算法使用了以下策略：
Immediate coalescing会立即合并，并在释放内存块后立即与相邻的空闲内存块合并，以获得更大的空闲块，并将其插入链表中的适当位置。 这样可以减少碎片化。 Splitting threshold，划分门限，最小可分配内存块大小为16字节，APP应用程序通常不分配int、char等基本数据结构。 将最小可用大小限制为16字节，以便可以将管理信息存储在可用内存块中。 Good-fit strategy、TLSF返回尽可能满足最低需求的内存块。 对于大小不同的内存请求，same strategy for all block sizes tlsf只有一个分配策略，实现相对简单，运行时间可预期。 相应的dlmalloc最多有四个内存分配策略，具体取决于所需的内存大小。 内存is not cleaned-up，分配APP应用程序的内存不依赖于0.TLSF的特点如下：
即使对于最大存储器分配请求，预期的分配执行时间也可在有限的时间内完成分配。 碎片化程度低。
未完待续