堆分配算法

我们知道程序通过malloc申请的内存空间大小是不一定的，从数个字节到数个GB都是有可能的。

于是就需要堆内存管理。
我们将堆空间管理起来，将它分块的按照用户的需求出售给最终的程序，并且还可以按照一定的方式收回内存。

空闲链表

空闲链表的方法实际上就是把堆中的各个空闲的块按照链表的方式链接起来。
当用户请求一块空间时，可以遍历整个列表，直到找到合适大小的块并且将它拆分。

空闲链表是这样一种结构，在堆里的每一个空闲空间的开头有一个头，头结构里记录了上一个和下一个空闲块的地址。也就是说，所有的空闲块形成了一个链表。

空闲链表空间的分配

首先在空闲链表里面查找足够容纳请求大小的一个空闲块，然后将这个块分成两部分，一部分为程序请求的空间，另一部分为剩余下来的空闲空间。

同时，在实际分配大小的时候会多分配4个字节来存储该分配块的大小。

位图

位图的核心思想是将整个堆划分为大量的块，每个块的大小相同。当用户请求内存的时候，总是分配整数个块的空间给用户。

有点像页是不是！！？

第一个块称为头，其余称为主体。由于每个块只有头/空闲/主体三种状态，所以只需要两位就可以表示一个块。因此称为位图。

位图的优缺点

优点：

• 速度快
• 稳定性好
• 块不需要额外信息，易于管理

缺点：

• 分配的内存容易产生碎片

• 如果堆很大，位图也将会很大，会降低命中率

• 内存池项目代码(未完成)

参考文献

 [1] 俞甲子 石凡 潘爱明．程序员的自我修养．电子工业出版社，2009.4．