内存分配是操作系统必须面对的一个环节,除非这个系统本身不需要内存安排,所有业务可以通过全局数据和堆栈搞定。内存分配其实不困难,但是由内存引申出来的东西就比较复杂了。早前没有MMU,系统本身的空间和用户空间没有优先级之分,所以不同的程序之间的内存都是共享的,相互影响也是不可避免的。所以,一般来说,除了内存分配之外,还需要一些日志信息、检测信息帮助我们进行调试和分析。当然,这些都不是我们关心的内容,我们关注的就是内存有哪些通用的分配算法。
(1)固定内存分配
固定内存分配算法是最简单的算法,也是最好理解的算法。比如说有16M内存,现在我们假设分配的基本内存是4K,那么总共有16M/4K =4K个单元。所以,如果用户想申请内存,最多就是4K次。如果用户想要多一点内存,那么系统把相邻的内存分给用户使用即可。
(2)链表内存分配
固定内存分配虽然好,但是还有一个缺点,那就是如果存在很多的浪费机会。试想一下,如果用户只要几十个byte,那么也要分配给它4K个字节,浪费的空间超过了99%。所以在此基础之上,我们提出了链表内存算法。链表算法中保存有空闲结点,内存释放的时候,那么内存查到空闲结点,该合并合并,该释放的释放;当然如果要申请内存的话,那方法就多了去了,可以最差申请、最优申请、最好申请,这些都是可以的。
(3)伙伴算法
链表算法相比较固定内存算法,可以节省不少内存。但是链表算法本身有一个特点,那就是容易形成内存碎片。所以,我们可以结合固定分配和链表算法的特点,把内存分配成8、16、32、64、128、256、512大小的几种链表。链表内部的大小都是相同的,链表之间是倍数的关系。分配内存的时候,我们首先寻找最合适的链表,然后分配内存,如果内存空间不够,可以向高一级的内存链表申请,这样拆解下来的内存可以分配到低一级别的链表;释放内存的时候,我们也要注意内存的合并和组合。
(4)基于内存池的伙伴算法
伙伴算法固然好,但是如果某一种内存申请特别频繁,那么在伙伴算法中就需要进行反复的拆分和合并处理。一方面,这会影响了内存的分配效率,另外一方面也比较容易造成内存的分配碎片。所以,我们可以在伙伴算法的基础之上构建一个内存池,在内存释放的时候,只是标注当前内存不再使用,但是并没有真正释放,等到内存池中所有的内存都不再使用的时候再进行释放,这在一定的程度上会提高内存的分配效率。特别是系统运行一段时间后,这种效果是特别明显的。
(5)工作集算法
工作集的算法本质上说不是一种算法,它只是一种基本思想。我们知道,在系统稳定之后,内存中分配的大小、配置的比例关系都是相对固定的,变化不是特别大。如果我们可以把这些数据给记录下来,在系统启动的时候预先分配好这些内存,那么不就可以提升系统的启动速度了吗?当然工作集中的参数设定更多的是一种经验值,它需要我们综合各种因素进行分析,反复比较才会得出比较好的结果。
这五种算法只是给出了基本思想,只有付出于实践,多加操练才能从中有所收获。