动态内存分配算法(c++动态分配内存数组)

---

一、动态分区分配的算法有哪些？动态分割算法：
1．首次拟合算法（FF/firstfit）
2除以最小分区
4。最坏适应算法（worstfit）
从最大分区开始分区
5分区根据容量大小进行分类。

---

二、LiteOS内存管理：TLSF算法

TLSF算法主要是针对实时操作系统提出的。DMA，DynamicMemoryAllocator一个大问题

TLSF提案较好地解决了上述两个问题：将动态内存分配和回收的时间复杂度降低到O(1)时间复杂度，并采用Good-.适配分配策略保证系统在执行过程中不会产生过多的碎片。

TLSF（全称Two-LevelSegregateFit），从命名上看主要分为三个部分

TLSF主要使用二级位图（Two-LevelBitmap）和自由分层SegregedFreeList）数据结构管理动态内存池（memorypool）及其空闲块（freeblocks），这些块是使用Good-Fit策略分配的。下面我们简单介绍一下这三者。

仍然掌握隔离和推导的方法，继续隔离SegreatedFreeList并探索其设计思想和开发过程

链表是内存管理中最常见的数据结构添加了一个Header节点区块头记录了区块本身的信息以及前后区块之间的关系。

最简单的是隐式链表，将所有内存块链接起来，只记录该内存块的大小，由于内存块之间紧密相关，所以其他内存可以通过添加头节点指针来获取内存块大小。由于内存块的地址不是显式指定的，而是计算出来的，所以也称为隐式链表。

当需要分配内存时，必须从第一个内存块开始回收，检查该内存块是否分配以及存块大小是否满足，直到找到大小合适且单独的空闲块。

上面提到的隐式链表和显式链表的主要问题是，当空闲块数为n时，检索的复杂度为O(n)级，速度较慢空闲块的分层链表优化了获取空闲块的复杂度，近似计算将其降低到O(log(n))级。

隔离空闲列表的设计思想是将空闲块按大小进行分类，形成不同块大小范围的类，组内的空闲块与链表关联起来。每次分配时，首先根据层次大小范围查找对应的链表，然后从对应的链表中逐一获取合适的空闲块，如果没有找到，则在大小较大的级别进行查找范围，直到找到并分配合适的块。

我们介绍了空闲块分层链表的原理，但是没有提到如何按照内存块大小进行分层。TLSF算法引入位图来解决这个问题。

当空闲块的分层链表遇到位图时，动态内存管理构会发生轻微的变化。问）。

TLSF使用两级位图（Two-LevelBitmap）来管理不同大小范围的空闲块列表（freeblocklist）。上图包含三个虚线矩形框：

一旦你有了TLSF框架的大致概念，你就可以先看一下简短且空闲的内存分配过程。（下一节结合源码详细讨论）
内存分配过程

内存释放过程

我们已经对内存结构有了一个大概的了解，分配和释放的过程，但还有一个小问题没有解释：

总体思路是：找到能够满足内存请求大小的最小空闲块，然后进行以下过程（以搜索大小为69字节的空闲块为例）

看起来Best-fit已经很好了，但是还有改进的空间。最佳策略的主要问题在于第三步。仍然需要获取对应范围的空闲块列表，存在潜在的时间复杂度。

Good-fit和Best-fit的思想区别在于，Good-fit并不保证找到满足请求的最小空闲块，而是尽能接近大小待分配。

同样以上面搜索大小为69字节的空闲块为例，Good-fit并没有找到范围[68~70]，而是比这个范围稍大的范围（例如[71~73]）。这种设计的优点是，[71~73]对应的自由区块链中的任意区块都可以直接满足自由区块链中的请求。一般来说，不会造成太多浪费。

在本节中，我们看一下LiteOS源代码并分析其数据结构和内存布局。

空闲块和已用块复用相同的数据结构，但在使用时并非所有字段都被使用。

主要参考了下面两篇博客，从安装eclipse、配置到编译运行项目，在Mac上没有问题，但是eclipse有点卡-_-！
怎么办Windows10安装LiteOS开发环境（一）
如何在Windows10上安装LiteOS开发环境（二）
温馨提示：

---

三、内存的分配方式有哪几种分配内存的三种方式：
1．从静态存储分配：在这种情况下，内存是在程序编译时分配的，并且存在于程序的整个执行过程中。这里存放的是全局变量、静态变量等。
2．栈区分配：相应代码执行时创建，执行结束时自动释放。局部变量存储在这里。堆栈内存分配操作内置于处理器的指令集中，非常高效，但容量有限。
3.堆区分配：动态分配内存。使用new/malloc打开它，使用delete/free释放它。使用寿命由用户指定且灵活。但存在内存泄漏等问题。
常见的内存错误及对策
1．内存分配失败但已使用。
对策：使用内存前检查是否分配成功。使用p!=NULL来确定。
2．内存已分配成功，无需初始化即可使用。
内存默认值没有统一的标准。大多数编译器都以0开头，但并非总是如此。
对策：初始化内存时，请指定初始值。
3.内存操作超出范围。
对策：小心。
4.内存已释放但仍在使用。
(1)使用野指针来表示删除和释放。
对策：释放内存并将指针设置为NULL。
(2)使用隐式删除和自由野指针。它主要表示返回堆栈内存的指针或引用的函数。
对策：然，不要直接回去。
5.内存泄漏是因为内存没有被释放。
使用new/malloc打开内存，使用delete/free释放内存。
对策：new和delete的数量必须相同，malloc和free的数量也必须相同。new[]和[]delete必须匹配。