基于μCOS-II的TLSF动态内存分配算法的应用与仿真
85 浏览量
2020-10-17
23:05:30
上传
评论
收藏 278KB PDF 举报
基于基于μCOS-II的的TLSF动态内存分配算法的应用与仿真动态内存分配算法的应用与仿真
以嵌入式实时系统为背景，深入研究了TLSF动态内存分配算法原理及实现过程，并将TLSF移植到μCOS-II中，
进行了基于x86平台的仿真测试，取得了很好的效果，为以后学习和应用TLSF算法提供了一种新的方式。
摘摘 要：要： 以嵌入式实时系统为背景，深入研究了
关键词：关键词： TLSF；
嵌入式实时系统中的关键问题之一是可调度性分析，以确定系统在运行时是否满足应用程序的时间约束。嵌入式实时应用
程序通常是在系统的整个生命周期过程中不断执行（几个月，几年，…），这种行为是直接影响动态内存管理的关键环节之
一，即内存碎片问题。考虑这两个方面，嵌入式实时应用程序中，动态存储分配DSA（Dynamic Storage Allocation）算法的
要求可以概括为：
（1）时间有界性
执行内存分配和释放的最坏执行时间是预先已知的，是独立于应用程序的数据，这是必须满足的最主要的要求。
（2）快速响应时间
除了具有一个有界的响应时间外，使用的DSA算法的响应时间应该很短。有界的DSA算法，如果响应时间是普通算法的10
倍，是不适用的。
（3）满足内存需要
系统运行内存不足时，非实时应用程序能够接收一个空指针或被操作系统终止。显然，任何时候都能满足内存需要是不切
实际的。但DSA算法必须把内存碎片和内存浪费降到最少以降低耗尽内存池的可能性。
1 RTOS的的DSA算法概述算法概述
DSA算法的目标是让应用程序访问空闲内存池中内存块。不同的算法在寻找最佳尺寸空闲块时的策略是不同的。DSA算法
可以分为以下类别：
（1）顺序拟合算法
在顺序拟合算法中，空闲内存块由单向或者双向链表管理。查询空闲内存块的时间复杂度为O（n）（n为内存块数目），当
内存块数目较大时，不能保证查询内存块的实时性，所以不宜在RTOS中使用该算法。
（2）索引查找算法
索引查找算法使用排序二叉树等非常复杂的数据结构来管理空闲内存，具有复杂的实现过程，并且因采用的数据结构的不
同而具有不同的性能。
（3）分类搜索算法
分类搜索算法把空闲内存划分为范围不同的多个区间，每个区间上的内存块由另一个数组链表管理，该数组链表保存着查
询空闲内存块的头指针。需要说明的是，同一区间内的空闲内存块，不一定物理相邻。
分类搜索算法虽然复杂，但查找空闲内存块的时间复杂度为O（1），能有效满足实时性，适合在RTOS使用。
（4）位图搜索算法
位图搜索算法使用位图管理空闲内存块，搜索空闲内存所需信息都被存储在一小块内存中，可以实时响应系统需求，是
RTOS中普遍采用的算法。
2 TLSF算法的数据结构和算法分析算法的数据结构和算法分析
在ECRTS 2004（Proceedings 16th Euromicro Conference on RealTime Systems 2004）上，MASMANO M提出了TLSF
算法。TLSF算法使用隔离适应机制实现了一个最佳适应策略，它结合了分类搜索算法和位图搜索算法的优点，即速度快、碎
片少。
隔离适应机制使用了空闲链表数组，每个数组内包含了一个区间范围的空闲内存块。为了加速访问空闲块，并且管理一大
组隔离链表（以减少碎片），该链表数组被分为两级数组来管理。第一级将空闲内存块划分为2n个区间（n=4，5，
……，31），称为FLI（First-level Segregated Fit），第二级别SLI（Second-level Segregated Fit）把第一级线性划分为2SLI
个区间（SLI是一个用户可配置参数），每个区间都由一条空闲内存块链表管理，每条链表对应一个相关的位图，用来标记链
表是否为空。1表示链表非空，即有空闲内存块可用，0则相反。
为了更快地分配与合并内存块，算法没有对空闲链表进行排序，而是用元素尺寸为32位的二维数组存储了所有链表头指
针。图1展示了数据结构的两个层面，第一级是指针数组，分别指向二级链表中的空闲内存块；第二级把第一级线性划分为8
个隔离链表。对应的位图如图2所示。
资源评论
