大家好，又见面了，我是你们的朋友全栈君。
注：本文的大部分内容摘录自论文《TLSF: a New Dynamic Memory Allocator for Real-Time Systems》，可以通过“科学上网”访问如下链接阅读原文：http://www.gii.upv.es/tlsf/files/ecrts04_tlsf.pdf。
什么是TLSF
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？
基本的Segregated Fit算法是使用一组链表，每个链表只包含特定长度范围来的空闲块的方式来管理空闲块的，这样链表数组的长度可能会很大。如下图，TLSF为了简化查找定位过程，使用了两层链表。第一层，将空闲内存块的大小根据2的幂进行分类，如（16、32、64…）。第二层链表在第一层的基础上，按照一定的间隔，线性分段。比如2的6次方这一段，分为4个小区间【64,80），【80,96），【96,112），【112，128）.每一级的链表都有一个bitmap用于标记对应的链表中是否有内存块。比如第一级别bitmap的后4bit位0100，即2的6次方这个区间有空闲块。对应的第二级链表的bitmap位0010及【80,96）这个区间有空闲块，即下面的89 Byte。
![TLSF算法分析[通俗易懂]](http://qn.javajgs.com/20220614/67841882-185b-44e3-aa13-bb5a0f968ee520220614f61e5c6f-3997-4d90-bf6e-cd02a2a2ba3f1.jpg)
![TLSF算法分析[通俗易懂]](https://javaforall.net/wp-content/uploads/2020/11/2020110817443450.jpg)
给定一个内存块的大小，确定在两级链表中的位置（f,s）的算法如下：
![TLSF算法分析[通俗易懂]](http://qn.javajgs.com/20220614/bcc3b7ff-3437-41e3-994b-b47362ee2063202206148751ba59-81b7-40b9-80d1-16d5dbf4d2b11.jpg)
其中2的SLI次幂表示第二级链表的区间大小，比如上图中，区间大小为16，即2的4次方。这样大小为460字节的空闲快在链表中的位置为f=8,s=12,如下图：
![TLSF算法分析[通俗易懂]](http://qn.javajgs.com/20220614/3e43cf30-3299-4e27-8e26-7e13e354675a20220614bb18cfb3-3266-4992-ba8d-c1fb4e1b26ab1.jpg)
TLSF适用环境
实时系统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://javaforall.net/147337.html原文链接：https://javaforall.net
