- 在程序运行时程序员使用动态内存分配器 (比如 malloc) 获得虚拟内存.
- 数据结构的大小只有运行时才知道.
- 动态内存分配器维护者一个进程的虚拟内存区域，称为堆.
- 堆的向上增长：如果分配一个块，我们想要一个 10 个字节的块，然后检查这堆里面现在所有的空闲块，如果它最大只有 8 个字节的空闲块，那这时候发现没有空闲的块可以供我们使用，那这个堆就会向上增长，然后给它分配 10 个字节空闲块，这个堆的总的空间就会变大
- 分配器将堆视为一组不同大小的块(blocks)的集合来维护，每个块要么是已分配的，要么是空闲的（就是可以往里面分配数据）
- 分配器的类型
- 显式分配器: 要求应用显式地释放任何已分配的快
- 例如，C 语言中的 malloc 和 free
- 隐式分配器: 应用检测到已分配块不再被程序所使用，就释放这个块
- 比如 Java，ML 和 Lisp 等高级语言中的垃圾收集 (garbage collection)
- 显式分配器: 要求应用显式地释放任何已分配的快
动态内存分配实例
对齐：新申请的空间的字节数必须能被 8 整除，int 是 4 字节的，p2 申请的内存空间是
空闲块：比如 p4 的申请
分配器
- Applications 应用
- 可以处理任意的分配( malloc)和释放(free)请求序列
- 只能释放已分配的块
- Allocators 分配器
- 无法控制分配块的数量或大小
- 立即响应 malloc 请求
- 比如, 不允许分配器重新排列或者缓冲请求
- 必须从空闲内存分配块
- 必须对齐块，使得它们可以保护任何类型的数据对象
- 8字节 (x86) or 16字节 (x86-64) 对齐在 Linux 上框
- 只能操作或改变空闲块
- 一旦块被分配，就不允许修改或移动它了
- 比如, 压缩已分配块的技术是不允许使用的
性能指标：吞吐量
- 假定 n 个分配和释放请求的某种序列:
- R0, R1, …, Rk, … , Rn-1
- 目标: 最大化吞吐量，最大化内存利用率
- 这些目标经常是互相矛盾的
- 吞吐量Throughput:
- 每个单位时间内完成的请求数
- 例如:
- 10秒内完成5,000个分配请求和5,000个释放请求
- 吞吐量是 1,000 次操作/秒
动态内存分配实现
对于处理碎片和分配内存，有这些问题需要处理：
- 我们如何知道一个指针可以释放多少内存?
- 我们如何记录空闲块（区分空闲与分配）?
- 将一个新分配的块放置到某个比较大的空闲块后，我们如何处理这个空闲块中的剩余部分?
- 我们如何选择一个空闲块去分配 – 很多都合适呢?
- 我们如何处理一个刚刚被释放的块—前后也有空闲呢?
标准方法（standard method）：我们如何知道释放多少 - 在块的前面的 word 中记录该块的长度.
- 这个 word 被称为头部
- 每个被分配块都需要一个这样的“word”
如上图，malloc(4)分配的有效载荷长度，我们还需要给这一个区域编码为一个内存块，也就是实际上要开五个格子，拿一个格子出来放头信息