嵌入式操作系统内核原理和开发（内存分配算法）(1)

    内存分配是操作系统必须面对的一个环节，除非这个系统本身不需要内存安排，所有业务可以通过全局数据和堆栈搞定。内存分配其实不困难，但是由内存引申出来的东西就比较复杂了。早前没有MMU，系统本身的空间和用户空间没有优先级之分，所以不同的程序之间的内存都是共享的，相互影响也是不可避免的。所以，一般来说，除了内存分配之外，还需要一些日志信息、检测信息帮助我们进行调试和分析。当然，这些都不是我们关心的内容，我们关注的就是内存有哪些通用的分配算法。

 

    （1）固定内存分配

    固定内存分配算法是最简单的算法，也是最好理解的算法。比如说有16M内存，现在我们假设分配的基本内存是4K，那么总共有16M/4K = 4K个单元。所以，如果用户想申请内存，最多就是4K次。如果用户想要多一点内存，那么系统把相邻的内存分给用户使用即可。

 

    （2）链表内存分配

    固定内存分配虽然好，但是还有一个缺点，那就是如果存在很多的浪费机会。试想一下，如果用户只要几十个byte，那么也要分配给它4K个字节，浪费的空间超过了99%。所以在此基础之上，我们提出了链表内存算法。链表算法中保存有空闲结点，内存释放的时候，那么内存查到空闲结点，该合并合并，该释放的释放；当然如果要申请内存的话，那方法就多了去了，可以最差申请、最优申请、最好申请，这些都是可以的。

 

    （3）伙伴算法

    链表算法相比较固定内存算法，可以节省不少内存。但是链表算法本身有一个特点，那就是容易形成内存碎片。所以，我们可以结合固定分配和链表算法的特点，把内存分配成8、16、32、64、128、256、512大小的几种链表。链表内部的大小都是相同的，链表之间是倍数的关系。分配内存的时候，我们首先寻找最合适的链表，然后分配内存，如果内存空间不够，可以向高一级的内存链表申请，这样拆解下来的内存可以分配到低一级别的链表；释放内存的时候，我们也要注意内存的合并和组合。

 

    （4）基于内存池的伙伴算法

    伙伴算法固然好，但是如果某一种内存申请特别频繁，那么在伙伴算法中就需要进行反复的拆分和合并处理。一方面，这会影响了内存的分配效率，另外一方面也比较容易造成内存的分配碎片。所以，我们可以在伙伴算法的基础之上构建一个内存池，在内存释放的时候，只是标注当前内存不再使用，但是并没有真正释放，等到内存池中所有的内存都不再使用的时候再进行释放，这在一定的程度上会提高内存的分配效率。特别是系统运行一段时间后，这种效果是特别明显的。

 

    （5）工作集算法

    工作集的算法本质上说不是一种算法，它只是一种基本思想。我们知道，在系统稳定之后，内存中分配的大小、配置的比例关系都是相对固定的，变化不是特别大。如果我们可以把这些数据给记录下来，在系统启动的时候预先分配好这些内存，那么不就可以提升系统的启动速度了吗？当然工作集中的参数设定更多的是一种经验值，它需要我们综合各种因素进行分析，反复比较才会得出比较好的结果。

 

    这五种算法只是给出了基本思想，只有付出于实践，多加操练才能从中有所收获。