申请(虚拟)内存空间时,可以使用mmap、munmap函数,不过使用经过封装的动态内存分配器,更方便,移植性更好。

动态内存分配器维护一个进程的虚拟内存区域。对每个进程,内核维护一个变量brk,是一个指向堆顶的指针。

分配器将堆视为一组不同大小的块的集合。每个块是一个连续的虚拟内存片,或是已分配的,或是空闲的

分配器存在两种风格:显式分配器、隐式分配器。显式分配器的典型例子就是malloc、free。隐式分配器广泛被如Java、Lisp等依赖垃圾回收机制的高级语言应用。本节之后讨论的内容都属于显式分配器。

unistd.h内声明了sbrk函数,使用该函数手动扩展和收缩堆大小。

显式分配器在设计时需要满足如下要求:

  • 处理任意请求序列。分配器不可以假设未来任何分配和释放请求的顺序。
  • 立即响应请求。意味着缓存、重新排列请求等策略在分配器设计中不可用。
  • 只使用堆。为保证分配器扩展性,分配器使用的任何非标量数据结构(是啥我也不知道)都必须保存在堆中。
  • 对齐块。分配器所分配的块必须满足操作系统和硬件的字节对齐要求,使块可以保存任何数据对象。
  • 不修改已分配的块。只能操作或改变空闲块,意味着压缩已分配块这类技术在分配器设计中无法使用。

分配器的吞吐率:单位时间内完成的“请求”数,“请求”包括分配请求和释放请求。

分配器的“合理性能”:一个分配请求的最坏运行时间和空闲块的数量成正比;释放请求的运行时间是一个常数。

下面几个概念建立在这个假设上:假设存在一组分配和释放请求的顺序R0、R1、R2、……、R(k – 1)、Rk、R(k + 1)、……、R(n – 2)、R(n – 1)。

有效载荷:如果一个应用程序请求一个p字节的块,则得到的已分配块的有效载荷是p字节。(注:块大小可能比p字节大,因为存在块的元信息,也可能要考虑因对齐而加入的填充字节,也可能分配器存在分配块的最小大小)

聚集有效载荷:在上述请求序列下,Pk是完成Rk请求后,当前已分配的有效载荷之和。

前k + 1个请求的峰值利用率:Uk = max(Pi) / Hk。Hk为Rk执行完毕后堆的大小,i从0到k。

碎片:存在未使用的内存,但无法满足分配请求。

内部碎片:已分配块大小大于有效载荷。量化标准就是块大小之和 – 有效载荷之和。决定因素是以前请求的模式和分配器的模式。

外部碎片:空闲内存大小之和大于分配请求要求的空间,但没有单独的空闲块大小大于请求的空间。决定因素是以前请求的模式、分配器的模式、未来请求的模式。

实现任何分配器,需要思考的四个方面:

  • 如何记录空闲块?
  • 如何选择被牺牲的空闲块?
  • 如何处理一个被利用的空闲块的剩余部分?
  • 如何处理释放请求?

任何实际的分配器需要一些数据结构以确定块边界,区分已分配块和空闲块。大多数分配器将这些信息嵌入块本身。

隐式空闲链表:

隐式:用一个块的大小信息,作为遍历块时从一个块切换到下一个块的依据,替代了普通链表的next指针。

一个块由一个字大小的头部、有效载荷和可能的填充组成的。头部编码了块大小(包括头部本身、有效载荷、填充)和块的分配状态。因为分配时一般都需要满足对齐要求,所以表示大小的二进制位中一般后面几位一定为0。可以利用这几个一定为0的位表示更多的块信息,比如块是否被分配等。

结束块:链表的遍历需要一个结束标志。一个设置了已分配位,且大小为0的块可作为终止标记。