创意设计一个网站,wordpress 登录信息,优化网站seo策略,网站制作公问题背景
TLSF算法主要是面向实时操作系统提出的#xff0c;对于RTOS而言#xff0c;执行时间的确定性是最根本的#xff0c;然而传统的动态内存分配器#xff08;DMA#xff0c;Dynamic Memory Allocator#xff09;存在两个主要问题#xff1a;
最坏情况执行时间不确…问题背景
TLSF算法主要是面向实时操作系统提出的对于RTOS而言执行时间的确定性是最根本的然而传统的动态内存分配器DMADynamic Memory Allocator存在两个主要问题
最坏情况执行时间不确定not bounded或者复杂度过高。碎片化问题。
TLSF的提出较好地解决了以上两个问题将动态内存的分配与回收时间复杂度都降到了O(1)时间复杂度并且采用了Good-fit的分配策略保证系统运行时不会产生过多碎片。
TLSF概要
TLSFTwo-Level Segregated Fit从命名来看主要分为三部分
Segregated Free ListTwo-Level BitmapGood Fit
前两个是数据结构第三个是分配策略。 TLSF主要采用两级位图Two-Level Bitmap与分级空闲块链表Segregated Free List的数据结构管理动态内存池memory pool以及其中的空闲块free blocks用Good-Fit的策略进行分配。
隔离空闲链表
将Segregated Free List拆开分为
List隐式链表管理所有内存块。Free List显示链表只管理空闲块。Segregated Free List隔离空闲块链表按空闲块大小分级用多个链表管理。
List 链表是内存管理中最常见的数据结构在一块内存块头部添加一个头结点记录该Block本身的信息以及前后级Block的关系。 隐式链表链接所有内存块只记录内存块大小由于内存块相连通过头结点指针加内存块大小即可得到下一个内存块的位置。 没有显示指明内存块的地址而是通过计算得到所以又叫做隐式链表。
当需要分配内存时需要从第一块内存块开始检索检查该内存块是否被分配以及内存块大小是否满足需要直到找到大小合适的空闲块分配出去。
隐式链表主要问题在于当内存分配时并不需要检索已分配的内存块这浪费了不少时间只需要检索空闲块即可。
因此显示空闲块链表在空闲块头部添加一个指针域指向下一个空闲块这样检索时会跳过已分配的内存块used blocks。 Segregated Free List 隐式链表和显示链表主要问题在于当空闲块个数为n时检索复杂度在O(n)级别速度较慢分级空闲块链表优化了空闲块检索的复杂度粗略计算大概降到O(log n)级别。
分级空闲块链表Segregated Free List的设计思想是将空闲块按照大小分级形成了不同块大小范围的分级class组内空闲块用链表链接起来。 每次分配时先按分级大小范围查找到相应链表再从相应链表挨个检索合适的空闲块如果找不到就在大小范围更大的一级查找直到找到合适的块分配出去。
Two-Level Bitmap
上面我们介绍了分级空闲块链表的原理但是我们并没有提及如何按照空闲块大小分级。 TLSF算法引入了位图bitmap来解决这个问题。
位图Bitmap
节省存储空间用1-bit表示某个区间范围大小的空闲块是否存在。位操作速度快部分体系结构有加速特殊位操作的指令如clz,ffs,fls。
SEgregated List Two-Level Bitmap TLSF采用了两级位图Two-Level Bitmap来管理不同大小范围的空闲块链free block lists。上图中包含三个虚线矩形框分别是
第一级位图表示内存块的粗粒度范围一般是2的幂次粒度。第二级位图表示内存块的细粒度范围。第三个框是内存中真正的空闲内存块free blocks。
内存分配与释放流程简版
有了TLSF的大体框架概念以后就可以先看一下内存alloc与free的简要流程。
内存分配流程
在位图中搜索合适的空闲块大小范围找到free list的头指针。基于free list的头指针检索list分配空闲块。
内存释放流程
将需要释放的内存块置为空闲块。与该空闲块物理上相邻的空闲块合并。计算合并后的空闲块大小范围检索位图找到对应的free list。将该内存块加入free list返回给内存池。
Good-fit
常规思路Best-fit内部碎片最优 常规思路是找到能满足内存请求大小的最小空闲块就会有下面的流程以搜索大小为69字节的空闲块为例。
基于位运算找到请求大小所在的第一级位图(First-Level bitmap)对应的粗粒度范围([ 64 ~ 128 ])也就是二级位图的索引在粗粒度范围内根据二级位图索引检索第二级位图(Second-Level bitmap)得到细粒度范围([ 68 ~ 70 ])如上图所示沿着右下角空闲块链表可以检索到69字节的那一块是Best-fit
Best-fit已经很不错了但仍然有提升空间。Best-fit策略最主要的问题还在于第三步仍然需要检索对应范围的那一条空闲块链表存在潜在的时间复杂度。
Good-fit少量碎片换取O(1)时间复杂度 Good-fit并不保证找到满足需求的最小空闲块而是尽可能接近要分配的大小。
还以上述搜索大小为69字节的空闲块为例查找范围稍微大一点儿的如[70,72]这样设计的好处是[70,72]对应的空闲块链中每一块都能满足需求不需要检索空闲块链表找到最小的而是直接取空闲块链中第一块即可。整体上也不会造成太多碎片。
