LiteOS内存管理：TLSF算法

TLSF算法主要是面向实时操作系统提出的，对于RTOS而言，执行时间的确定性是最根本的(吞吐量不一定高)，然而传统的动态内存分配器(DMA, Dynamic Memory Allocator)存在两个主要问题

TLSF的提出较好地解决了以上两个问题: 将动态内存的分配与回收时间复杂度都降到了O(1)时间复杂度，并且采用了Good-fit的分配策略保证系统运行时不会产生过多碎片。

TLSF(全称Two-Level Segregated Fit),从命名来看主要分为三部分

TLSF主要采用两级位图(Two-Level Bitmap)与分级空闲块链表(Segregated Free List)的数据结构管理动态内存池(memory pool)以及其中的空闲块(free blocks)，用Good-Fit的策略进行分配。下面我们先简单介绍一下这三者。

还是采用拆分理解的方式，继续把Segregated Free List拆开，探究其设计思路和发展演变过程

链表是内存管理中最常见的数据结构，在一块内存块头部添加一个头结点，记录该block本身的信息以及前后继block的关系。

其中最简单的一种就是 隐式链表 ，链接 所有内存块 , 只记录内存块大小，由于内存块紧密相连，通过头结点指针加内存块大小即可得到下一个内存块的位置。由于没有显式指明内存块的地址，而是通过计算得到，所以又叫做隐式链表。

当需要分配内存时，需要从第一块内存块开始检索，检查该内存块是否被分配以及内存块大小是被满足，直到找到大小合适的空闲块分配出去。

上面提到的隐式链表和显式链表主要问题在于当空闲块个数为n时，检索复杂度在O(n)级别，速度较慢，分级空闲块链表优化了空闲块检索的复杂度，粗略计算大概降到O(log(n))级别。

分级空闲块链表（Segregated Free List）的设计思想是将空闲块按照大小分级，形成了不同块大小范围的分级(class)，组内空闲块用链表链接起来。每次分配时先按分级大小范围查找到相应链表，再从相应链表挨个检索合适的空闲块，如果找不到，就在大小范围更大的一级查找，直到找到合适的块分配出去。

上面我们介绍了分级空闲块链表的原理，但是我们并没有提及如何按照内存块大小分级。TLSF算法引入了位图(Bitmap)来解决这个问题。

当分级空闲块链表碰上位图，动态内存管理结构变化稍微有些大，下面这张图画得还算清晰(能依稀看到分级空闲块链表的影子就好:-P)。

TLSF采用了两级位图(Two-Level Bitmap)来管理不同大小范围的空闲块链(free block lists)。 上图中包含三个虚线矩形框分别是:

有了TLSF的大体框架概念以后，就可以先看一下内存alloc与free的简要流程。(细节下一节结合源码探讨)

内存分配流程

内存释放流程

内存结构和分配释放流程已经有了大致的了解，但是其中还有一个小问题并没有说明：

常规思路是：找到能满足内存请求大小的最小空闲块,就会有下面的流程（以搜索大小为69字节的空闲块为例）

看起来Best-fit 已经很不错了，但仍然还有提升空间。Best-fit策略最主要的问题还在于第三步，仍然需要检索对应范围的那一条空闲块链表，存在潜在的时间复杂度。

Good-fit思路与Best-fit不同之处在于，Good-fit并不保证找到满足需求的最小空闲块，而是 尽可能接近 要分配的大小。

还以上述搜索大小为69字节的空闲块为例，Good-fit并不是找到[68 ~ 70]这一范围，而是比这个范围稍微大一点儿的范围(例如[71 ~ 73])。这样设计的好处就是[71 ~ 73]对应的空闲块链中每一块都能满足需求，不需要检索空闲块链表找到最小的，而是直接取空闲块链中第一块即可。整体上还不会造成太多碎片。

这一节我们扒一扒LiteOS的源码，分析其中的数据结构和内存布局。

空闲块和使用块复用同一数据结构,但在使用时并非所有字段都使用。

主要参考下面这两篇博客，从安装eclipe、配置到项目编译运行，挺完整的,Mac下也没什么问题，就是eclipse有点卡-_- !

Windows10如何安装LiteOS开发环境（一）

Windows10如何安装LiteOS开发环境（二）

提个醒：