9.9.3 分配器的要求和目标

显式分配器必须在一些相当严格的约束条件下工作：

处理任意请求序列。 一个应用可以有任意的分配请求和释放请求序列，只要满足约束条件：每个释放请求必须对应于一个当前已分配块，这个块是由一个以前的分配请求获得的。因此，分配器不可以假设分配和释放请求的顺序。例如，分配器不能假设所有的分配请求都有相匹配的释放请求，或者有相匹配的分配和空闲请求是嵌套的。
立即响应请求。 分配器必须立即响应分配请求。因此，不允许分配器为了提高性能重新排列或者缓冲请求。
只使用堆。 为了使分配器是可扩展的，分配器使用的任何非标量数据结构都必须保存在堆里。
对齐块（对齐要求）。 分配器必须对齐块，使得它们可以保存任何类型的数据对象。
不修改已分配的块。 分配器只能操作或者改变空闲块。特别是，一旦块被分配了，就不允许修改或者移动它了。因此，诸如压缩已分配块这样的技术是不允许使用的。

在这些限制条件下，分配器的编写者试图实现吞吐率最大化和内存使用率最大化，而这两个性能目标通常是相互冲突的。

目标 1：最大化吞吐率。 假定 n 个分配和释放请求的某种序列：

R₀, R₁, …, R_k, …, R_n−1

我们希望一个分配器的吞吐率最大化，吞吐率定义为每个单位时间里完成的请求数。例如，如果一个分配器在 1 秒内完成 500 个分配请求和 500 个释放请求，那么它的吞吐率就是每秒 1000 次操作。一般而言，我们可以通过使满足分配和释放请求的平均时间最小化来使吞吐率最大化。正如我们会看到的，开发一个具有合理性能的分配器并不困难，所谓合理性能是指一个分配请求的最糟运行时间与空闲块的数量成线性关系，而一个释放请求的运行时间是个常数。
目标 2：最大化内存利用率。 天真的程序员经常不正确地假设虚拟内存是一个无限的资源。实际上，一个系统中被所有进程分配的虚拟内存的全部数量是受磁盘上交换空间的数量限制的。好的程序员知道虚拟内存是一个有限的空间，必须高效地使用。对于可能被要求分配和释放大块内存的动态内存分配器来说，尤其如此。

有很多方式来描述一个分配器使用堆的效率如何。在我们的经验中，最有用的标准是峰值利用率（peak utilization）。像以前一样，我们给定 n 个分配和释放请求的某种顺序

R₀, R₁, …, R_k, …, R_n−1

如果一个应用程序请求一个 p 字节的块，那么得到的已分配块的有效载荷（payload）是 p 字节。在请求 R_k 完成之后，聚集有效载荷（aggregate payload）表示为 P_k，为当前已分配的块的有效载荷之和，而 H_k 表示堆的当前的（单调非递减的）大小。

那么，前 k+1 个请求的峰值利用率，表示为 U_k，可以通过下式得到：

        maxᵢ≤ₖ Pᵢ
Uₖ = ───────────
            Hₖ

那么，分配器的目标就是在整个序列中使峰值利用率 U_n−1 最大化。正如我们将要看到的，在最大化吞吐率和最大化利用率之间是互相牵制的。特别是，以堆利用率为代价，很容易编写出吞吐率最大化的分配器。分配器设计中一个有趣的挑战就是在两个目标之间找到一个适当的平衡。

旁注放宽单调性假设

我们可以通过让 H_k 成为前 k+1 个请求的最高峰，从而使得在我们对 H_k 的定义中放宽单调非递减的假设，并且允许堆增长和降低。