堆内存分配

malloc的实现：为了每次分配内存不进行系统调用（系统调用比较耗时），运行库会通过系统调用一次性分配一大块内存，然后零售给程序。

可以用来分配堆内存的两个系统调用：

• brk(): 将break往高地址移动(top of heap)，多出来的空间为heap空间。
• mmap(): 通过mmap申请一块匿名内存空间。

在数据段和共享库之间的区域都可以用来分配堆空间。linux 2.6之后共享库的加载地址被放在了0xbf000000处，可以占用大约2.9G左右的空间，不过还是要受内存大小+虚拟内存空间大小的限制。

堆分配算法：

1. 空闲链表

Paste_Image.png

空闲区域由链表链接在一起，分配时首先查找可以容纳请求大小的一个空闲块，然后将这个块分成两部分，一部分为程序请求的区域，一部分为剩余空间，再把剩余空间放回链表。如果剩余空间为0，则将其从链表中删除。

分配给程序的内存块通常增加4个字节存储内存块的大小，方便释放。

2. 位图

将堆内存分为相同大小的块，用户申请内存时，分配整数个块给用户，已分配区域的一个块为头，其余的称为body。一个块的状态为，head/body/free三种状态，可以用两位来表示。

Paste_Image.png

对应的位图为：

缺点是：分配必须是块大小的整数倍，容易产生浪费

堆分配算法往往是复合的，小于64字节采用对象池，大于512字节采用最佳适配算法，64到512字节采用最佳折中策略。