* 本次只是简要的总结堆的基本情况，具体的函数分析和堆算法分析今后会继续再学习。。。→_→ *

程序在任意时刻都可能会发出请求，申请或释放一段内存资源，堆由此而生。

1. 堆(Heap)

• 堆是一块巨大的内存空间，占据虚拟空间的绝大部分。在这片空间里，程序可以请求一块连续内存并自由使用，这块内存在程序主动释放之前一直保持有效

• 程序向操作系统申请一块适当大小的堆空间，程序自己管理这块空间。管理堆空间分配的一般是程序的运行库，运行库向操作系统“批发”了一大块堆空间，然后“零售”给程序用。当全部“售完”或程序有已满足不了的更大内存需求时，再向操作系统“进货”

2. Linux进程堆管理
   Linux下的进程堆管理提供了两种堆空间分配方式（系统调用）：

• int brk(void *end_data_segment);

  - **作用为设置进程数据段的结束地址，即扩大或缩小数据段重点内容**。将数据段的结束地址向高地址移动为扩大空间，反之亦然
  
  - **sbrk**与之类似，其**以一个增量（Increment）作为参数，表示需要增加或减少的空间大小，返回值为增加或减少后的数据段结束地址，实际上是对brk 系统调用的包装**

• void* mmap(void *start, size_t length, int prot, int flags, int fd, off_t offset);

  • 作用为向操作系统申请一段虚拟地址空间，这块虚拟地址空间也可以映射到文件，当其映射到文件时，称这块空间为匿名空间（Anonymous Space），匿名空间就可以作为堆空间

  • 第一、二个参数表示需要申请的空间的起始地址和长度，如果起始地址设置为0，那么Linux系统自动挑选合适的起始地址

  • 第三、四个参数表示申请空间的权限（可读、可写、可执行）和映射类型（文件映射、匿名空间）

  • 第五、六个参数表示当文件映射时指定文件描述符和文件偏移

  glibc中的malloc函数处理请求方式如下

  • 当请求小于128KB时，在现有堆空间中，按照堆分配算法为其分配一块空间并返回
  • 当请求大于128KB时，使用mmap()函数为其分配一块匿名空间，在这个匿名空间中为用户分配空间
  • 系统虚拟空间申请函数，申请的空间的起始地址和大小必须是系统页大小的整数倍
  • 影响malloc申请的最大空间大小的因素：系统资源限制（ulimit）、物理内存和交换空间的总和。因为mmap申请匿名空间时，系统会为它在内存或交换空间中预留地址，但申请空间的大小不能超过空闲内存和空闲交换空间的总和

3. 堆分配算法：管理一大块连续的内存空间，按照需求分配或释放其中的空间

• 空闲链表（Free List）：把堆中各个空闲的块按照链表的方式连接起来，当用户请求一块空间时，遍历整个列表，直到找到合适大小的块并将它拆分；当用户释放空间时将它合并到空闲链表中

  数据结构：在堆里的每一个**空闲空间的开头或结尾有一个头（header）**，头结构中记录了**上一个（prev）和下一个（next）空闲块的地址**，即所有的空闲块形成了一个空闲链表。

  

  具体分配算法：
  
  - **在空闲链表中查找足够容纳请求大小的一个空闲块，将其分成两块，一部分为程序请求的空间，另一部分为剩余的空闲空间**
  
  - **将空闲链表进行更新，若剩余的空闲块大小为0，则直接从空闲链表中删除**
  
      ![空闲链表更新](https://imgconvert.csdnimg.cn/aHR0cDovL2ltZy5ibG9nLmNzZG4ubmV0LzIwMTcwNjA0MTUyMzAyOTY1?x-oss-process=image/format,png)
  - 释放时需要知道资源大小，所以当**分配k个字节资源时，实际分配k+4个字节资源，这4个字节用于存储该分配资源的大小**，因此释放时查看这4个字节的值就能知道该内存块的大小再将其插入到空闲链表中

• 位图（Bitmap）：将整个堆划分为许多相同大小的块（block），当用户请求资源时，分配给用户整数个块空间。第一个块称为已分配区域的头（head），其余的块称为已分配区域的主体（Body）。因此每个块只有头/主体/空闲三种状态，只需要两位二进制位即可表示一个块。

  数据结构：使用**整数数组记录块的使用情况**
  
  **使用11表示H（Head），10表示主体（Body），00表示空闲（Free）**
  
  对应的位图为：（High）11-00-00-10-10-10-11-00-00-00-00-00-00-00-10-11
  
  ![位图分配方式](https://imgconvert.csdnimg.cn/aHR0cDovL2ltZy5ibG9nLmNzZG4ubmV0LzIwMTcwNjA0MTY1OTQ0NDI5?x-oss-process=image/format,png)
  
  分配算法特点：
  优点：
  - **速度快**：整个堆的空闲信息存储在一个数组中，因此访问该数组时cache容易命中
  
  - **稳定性好**：即使部分数据被破坏，也不会导致整个堆的无法工作
  
  - **块不需要额外信息，易于管理**
  
  缺点：
  - **分配内存时容易产生内存碎片**
  
  - 如**果堆很大或设置的块很小，那么位图将会很大，可能失去cache命中率高的优势而且会浪费空间**

• 对象池：把整个堆空间划分为大量小块每次请求时只需要找到一个小块

  - 数据结构：可采用空闲链表、位图等
  
      区别在于，它**假定每次请求的都是一个固定大小，由于每次只请求一个单位的内存，因此请求得到满足的速度很快，无需查找一个足够大的空间**
  
  - 具体分配算法：
  
      在现实应用中，堆的分配算法一般是多种算法复合而成的。**在Glibc中，当申请的空间资源小于64字节时，采用类似于对象池的方法；当大于64字节且小于512字节时，采用上述方法中的最佳折中策略；当大于512字节时，采用最佳适配算法；当大于128KB时，直接使用mmap向操作系统申请空间**