工程师都知道，C/C++语言与其他语言不同，它需要开发者自己管理内存资源，对于动态内存使用不当，容易造成段错误或者内存泄漏，因此内存管理至关重要。本文将以 C 语言为例介绍动态内存管理的原理。
 
C/C++语言与其他语言不同，它需要开发者自己管理内存资源。对于动态内存的使用不当容易造成段错误或者内存泄漏。尤其是内存泄漏，内存泄漏往往是在程序运行一段时间才会被发现，使得开发人员无法第一时间定位错误。
 
而相比于个人计算机，嵌入式系统的内存资源更是稀缺。作为嵌入式 C 的开发人员，了解其内存管理的原理能使其更加正确地使用内存资源以及定位程序的 bug。本文将以 C 语言为例介绍动态内存管理的原理。
 
一、动态内存的原理
1. 栈空间与堆空间
在介绍内存管理之前，我们先解释一下栈空间与堆空间：栈空间是由编译器自动分配释放，对于 AWorks 等操作系统，在用户创建一个任务的时候可以由自己决定任务栈空间的大小。
 
栈空间里面一般存放着如下数据：在函数内的局部变量（不包括 static 定义的变量），在调用另一个函数时保存的通用寄存器信息等。
 
参考如下例程（为了便于理解，省略通用寄存器等信息）：
 
 
在 task 执行 s = calculate_sum(a,b);之前，task 的栈内保存如下数据：
 
 
程序接下来执行 calculate_sum 函数，其栈向下增长。在返回 task 之前，其栈结构如下：
 
 
执行完 calculate_sum 之后，根据返回地址返回 task 之后，栈恢复调用之前的结构：
 
 
所以栈空间存储着代码块内的局部变量，动态地增减着内部的数据。这也就是为什么当接口调用结束后变量就不再“生存”的原因。
 
堆空间是由 OS 管理的一片区域，开发者可向 OS 动态申请一片区域用于操作数据。
 
堆空间在程序运行时一直有效，相当于定义了一个大型的全局数组。需要时向堆空间申请内存，使用完毕再还回去。这样可以使得开发者能够动态地控制空间的大小，而不需要在写代码的时候就考虑最糟的情况（定义一个数组必须在编译之前就确定其大小，使用过程中无法增加或减少，所以必须考虑最多需要的数据大小）。
 
堆空间由编译器决定，如果开发者想尝试实现一片动态内存，可向堆申请一片对齐的内存空间。
 
2. 内存资源的申请与释放
我们这里以常用的内存操作接口——malloc 与 free 为例，介绍操作动态内存的细节。
 
void* malloc(size)——申请一片大小为 size 字节的内存。
 
参考下图，灰色部分是已经被使用的内存，空白部分则是可以被申请使用的内存。在申请内存的时候，系统会首先判断有没有足够大的未被使用的区域，如果有，则将其分配给申请者，再将此区域标记为“已使用”；否则分配失败。
 
 
（为方便读图，从这里开始我们假定内存的地址从上往下增长）

 

 
void free(void *)——释放已申请的内存。与 malloc 相反，free 的作用是把“已使用”的区域标记为“未使用”，那么释放的内存下一次就可以再分配出去复用。free 释放的内存必须是 malloc 申请的内存。
 
 
由于需要对内存进行状态标记和位置记录（以便释放）。在申请 / 释放内存的时候需要额外的空间进行信息的记录。有的系统会将记录的信息集中管理，有的则是申请内存的时候额外地多申请一小片区域用于记录。
 
3. 内存泄漏
对于动态申请的内存，使用完毕之后应该还给堆，才能在后续继续分配出去。
 
而如果申请的内存如果没有还回去，就造成了内存泄漏。
 
参考如下一段代码：
 
 
现在我们设 flag=1，执行这个函数会发生什么？
 
 
首先 ptr 会指向申请的 128 字节的内存（图 b）,然后判断 flag==1 之后再申请 256 字节的内存（图 c）。假设我们现在使用完毕将 ptr 释放：
 
 
现在我们释放了 256 字节的内存块了，但是我们开始的时候还申请过 128 字节的内存块，这 128 字节的内存块最终会怎样呢？由当时唯一指向这块内存的指针 ptr 后面指向了 256 字节的内存块，现在没有任何指针指向这块内存，因此这一块内存再也无法被释放，这时候我们就说内存泄漏了。
 
在程序最开始运行的一段时间内，系统是没有异常的。即使一小片内存不被释放也不会造成错误，因为内存堆还有足够的空间可以使用。但是如果运行的时间足够长，多次调用这个函数（参数 flag==1）之后，堆空间会逐渐被泄漏的内存块占满，直到程序无法再从堆里申请到内存，程序才会报错。
 
内存泄漏令开发者头痛的地方也正是这个原因，内存泄漏的问题往往无法在第一时间被发现！而对于不熟悉内存管理的开发者更是难以定位错误。
 
对于动态内存的操作，需要时刻记住：当一块申请的内存不再使用的时候，必须及时释放。一个 malloc 操作需要对应一个 free 操作。
 
4. 内存对齐
在很多的场合下，分配的内存不仅要满足申请的大小，也需要进行对齐才能够使分配的空间能够被转换成除 char 之外其他的结构类型。系统对内存的分配一般会以 int 型变量的字节数进行对齐。AWorks 提供的 aw_mem_align 接口可以使用户获取自定义对齐的内存空间。
 
类型对齐相关的知识请读者自行查找相关资料，这里不再展开细讲。

 

 
二、内存管理算法
接下来我们学习一下怎么去对堆空间的内存进行管理。这里我们主要介绍嵌入式中两种常用的内存管理算法。
 
1. 链表法
链表法维护着两个链表，两个链表分别记录着已分配的使用内存段和未分配的空闲内存段。当申请一片内存的时候，从空闲内存段中找到合适的块分配给用户，同时链入使用内存段。而释放的时候则从已使用的内存段找到相应的表，然后释放到空闲内存段中以供下次分配。
 
现在我们以最先匹配算法为例介绍算法的细节。最先匹配算法是从空闲链表的表头出发，依次寻找空闲的内存，一旦找到足够大的连续区域则将其返回给用户。
 
还记得前面说的，管理内存区域需要额外的记录信息，链表法一般是在操作内存空间的时候申请额外的空间记录相应的信息。我们假定下图红色部分记录着使用的内存区，青色记录空闲的内存区，这里使用 free link 链表维护空闲内存段，used link 维护使用的内存段：
 
 
程序运行一段时间之后，假设堆内的空间分布如下：
 
 
空闲区和使用区的信息都被两个表维护着。
 
现在用户需要申请一片大小为 3k 的内存，系统会从 free link 出发，先是找到 2k 的空闲区，由于 2k 的空间不够用，接下来再继续寻找，找到了 4k 的区域，发现 4k 的区域够大了，就会将 4k 的空间取走 3k 的空间并将其链入 used link。
 
尽管后面 3k 的空间更加适合分配，但是最先匹配算法一旦找到足够大的空间便不会继续往下寻找。
 
 
当用户用完资源的时候，把申请的 3k 还回去，系统会从 used link 找到申请的内存，将链入 free link 以供下次分配，然后将空闲相邻的内存块合并成完整的一块：
 
 
现在考虑这样的一种情况：假设用户要申请 5k 的内存块，系统能够提供吗？并不能。
 
虽然空闲的内存块一共有 9k（2k+4k+3k），但是 9k 的内存并不连续，因此无法分配给用户。这就是外部内存碎片——虽然整个空间的空闲内存足够大，但却因为零碎的内存块割裂了连续内存而无法分配出去。
 
其他的链表法还有最佳匹配算法，下次匹配算法等 . 有兴趣的读者可以自行查找相关资料。
 
2. 位图法
使用位图法，系统的内存会被划分成固定的内存块。再用变量的其中一位指示其中的一块内存：
 
 
图中的一个方格代表一块固定大小的内存块，这里假定 1k。用一个 16 位的变量指代 16k 的内存段。如果一个块是空闲的，则用 0 表示，如果是被使用的，则用 1 表示。
 
下图的第 1，2 个内存块和第 7，8，9 个内存块都被使用了，而相应的位都被置 1 说明被占用了。
 
 
相比链表法，位图法采用更少的额外空间记录内存堆的信息，而且由于申请与释放都是整块的，会产生更少的外部碎片。
 
但是假如用户只申请几个字节的内存，但是却分配了 1k 的内存块，则大量的空间不会被使用，这样导致的无法使用的内存我们称为内部内存碎片。
 
减少内部内存碎片的其中一个方法是合理地选择内存块的大小，固定尺寸较小的内存块导致的内存碎片会更小——当用户申请几字节的内存，比起固定 1k 的内存块，固定 16 字节的内存块产生更少的碎片。但是固定尺寸变小了也会导致需要更多的位记录内存的信息。
 
现在有很多优秀的位图算法——将内存分成不同的固定大小获取更快的分配速度和更少的内存碎片，有兴趣的读者可自行查找相关资料。