1. dlmalloc  : 第一个被广泛使用的通用动态内存分配器，Linux 早期使用，SylixOS 应用程序默认选用。
2. ptmalloc2 :Linux glibc默认内存分配算法，由dlmalloc发展而来，发布于2006年。
3. tcmalloc （Thread-Caching Malloc）: Google 贡献的分配器。
4. TLSF (two-level segregated-fit) : 是一种用于实时操作系统的内存分配算法。
5. SylixOS 内核默认分配算法

• jemalloc – FreeBSD ＆ Firefox 所用分配器，很多中间件可只选分配算法，如redis。
• libumem – Solaris 所用分配器。

TLSF 在 SylixOS 中使用注意：

TLSF 虽然拥有 O(1) 时间复杂度的内存管理算法, 适用于实时操作系统, 但是在 32 位系统上仅能保持 4 字节对齐特性, 在 64 位系统上仅能保持 8 字节对齐特性, 不满足 POSIX 对 malloc 具有 2 * sizeof(size_t)对齐的要求, 所有有些软件可能会严重错误, 例如Qt/JavaScript 引擎, 所以使用时需慎重! 只有确认应用没有 2 * sizeof(size_t) 对齐要求时, 方可使用.TLSF 由于具有 O(1) 时间复杂度, 所以他可以使用自旋锁来提高效率, 但会降低系统实时性, 请权衡使用.

什么是TLSF

以下大部分内容摘录自论文《TLSF: a New Dynamic Memory Allocator for Real-Time Systems》http://www.gii.upv.es/tlsf/files/ecrts04_tlsf.pdf%E3%80%82

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。

实时系统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可以在限定的时间内完成分配。
• 碎片化程度低。