2021SC@SDUSC TencentOS Tiny源码分析（十二）动态内存管理机制模块一
2021SC@SDUSC
文章目录
- 一. 区分动态内存和静态内存
- 二. RTOS的动态内存管理
- 三. 动态内存堆管理算法-TLSF算法
- （一）分级空闲块链表 Segregated Free List
- 1. 隐式链表 Implicit list
- 2. 显式空闲块链表 Explicit list
- 3. 分级空闲块链表 Segregated Free List
- （二）两级位图 Two-Level Bitmap
- （三）Good Fit
- （四）小结
- 四. TencentOS Tiny中TLSF的实现
本周我们开始分析TencentOS Tiny中 动态内存的管理机制
一. 区分动态内存和静态内存
静态内存：
静态内存是指在程序开始运行时由编译器分配的内存，它的分配是在程序开始编译时完成的，不占用CPU资源。程序中的各种变量，在编译时系统已经为其分配了所需的内存空间，当该变量在作用域内使用完毕时，系统会自动释放所占用的内存空间。变量的分配与释放，都无须程序员自行考虑。
动态内存：
当用户无法在程序运行之前确定所需要的空间大小，或者所需空间太大导致在栈上无法分配时，会采用动态内存分配。动态内存发生在程序的调用和执行的时候，会占用CPU资源，需要通过专门函数进行空间申请和释放，比如malloc和free函数
二. RTOS的动态内存管理
由于静态内存是由编译器在程序正是执行之前自动分配，所以我们就暂时不过多对其研究。在一般情况下，用malloc申请动态内存有两个缺陷：
- 由于分配算法的复杂度和堆空间的使用情况，分配的时间不定
- 在不断申请、释放的过程中，容易因为内存对齐而产生碎片化内存
这两个缺陷对于实时操作系统来说都是不允许的，所以操作系统必须能够提供一套有效、合理、分配时间可确定的动态内存管理机制
关于什么是实时操作系统RTOS实际上在之前也提到过，这里再记录一下：简要来说，实时操作系统最大的特点就是实时性，当有一个任务需要执行时，操作系统会在较短时间内执行，而不会有较长的延时。而且，实时操作系统一般都是嵌入式操作系统，但是嵌入式操作系统并不都是实时的
目前对于动态内存分配的管理一共有两种不同的解决方案：
- 动态内存堆管理算法–mmheap
- 静态内存池管理算法–mmblk
TencentOS-tiny中对于这两种管理算法都提供，下面我们依次来分析
三. 动态内存堆管理算法-TLSF算法
对于动态内存堆管理算法，我们以TLSF算法为例分析
TLSF全称Two-Level Segregated Fit memory allocator，两级隔离Fit内存分配器，是一款通用的动态内存分配器，专门设计用于满足实时要求。
TSLF实际是多个有含义单词的首字母缩写，我们分别来看这几个单词是什么含义：
- Segregated Free List 分级空闲块链表
- Two-Level Bitmap 两级位图
- Good Fit
前两个是数据结构，第三个是它的内存分配策略，也就是说：TLSF主要采用两级位图(Two-Level Bitmap)与分级空闲块链表(Segregated Free List)的数据结构管理动态内存池(memory pool)以及其中的空闲块(free blocks)，用Good-Fit的策略进行分配
那么我们依次来分析：
（一）分级空闲块链表 Segregated Free List
1. 隐式链表 Implicit list
实际上，链表是内存管理中最常见的数据结构，在一块内存块头部添加一个头结点，记录该block本身的信息以及前后继block的关系。
其中最简单的一种就是隐式链表（Implicit list），链接所有内存块，只记录内存块大小，由于内存块是连续的，加内存块大小即可得到下一个内存块的位置。因此没有显式指明内存块的地址，而是通过计算得到，所以又叫做隐式链表。
使用隐式链表进行内存分配的时候会从第一块内存块开始检索，检查该内存块是否被分配以及内存块大小是被满足，直到找到大小合适的空闲块分配出去。
隐式链表的问题：
- 隐式链表中不会区分内存块是空闲块还是已分配块，在寻找下一个适合的空闲块时会将已分配块当做普通块进行遍历，这无疑是没有必要的消耗
为了解决这个问题，减少不必要的遍历开销，显式空闲块链表就应运而生了
2. 显式空闲块链表 Explicit list
显式空闲块链表（Explicit list）会在空闲块头部添加一个指针域，指向下一个空闲块，这样检索时会跳过已分配的内存块
那么显式空闲块链表的问题在哪呢？
- 主要问题在于当空闲块个数为n时，虽然在一定程度上提升了原来使用隐式链表时的效率，但是检索复杂度依旧在O(n)级别，速度仍然较慢
于是便出现了分级空闲块链表
3. 分级空闲块链表 Segregated Free List
分级空闲块链表优化了空闲块检索的复杂度，粗略计算大概降到O(logn)级别
分级空闲块链表（Segregated Free List）的设计思想是将空闲块按照大小分级，形成了不同块大小范围的分级，组内空闲块用链表
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！