1. 章引论：内存管理¶

大多数数据结构都为存储和访问等长对象而设计。 一个典型的例子是存储在线性表或队列中的整数。 有些应用需要存储变长记录的能力，比如任意长度的字符串。 一种解决方案是在线性表或队列中存储一批指向字符串的指针， 每个指针指向一块大小恰好能容纳相应字符串的空间。 对存储在内存中的数据结构来说，这没问题。 但如果这批字符串要存储在磁盘上，我们就得操心这些字符串到底 是如何存储的。 而且即使存储在内存中，也必须有某种机制弄清楚哪里有可用字节来 容纳字符串。 在 C++ 或 Java 这类语言中，程序员可以按需分配空间 （通过 new 显式分配，或通过变量声明隐式分配）。 这些空间从哪里来？ 本节讨论内存管理技术，用于解决处理变长空间请求的一般性问题。

内存管理的基本模型是：我们有一大块连续的内存位置， 称之为 内存池。 内存请求会周期性地发出，要求池中一定量的空间。 内存管理器 的职责是在内存池中的某处找到一块 至少具有请求大小的连续位置。 响应这样的请求称为 内存分配。 内存管理器通常会返回一些信息，请求者可以持有这些信息， 以便日后取回刚由内存管理器存储的数据。 这块信息称为 句柄。 某段时间之后，被请求的空间可能不再需要， 这些空间可以交还给内存管理器以便复用。 这称为 内存释放。 我们可以为存储变长整数数组的一个简单内存管理器定义如下 ADT。

// Memory Manager abstract class
public interface MemManager {
  // Store a record and return a handle to it
  public MemHandle insert(byte[] info);

  // Release the space associated with a record
  public void release(MemHandle h);

  // Get back a copy of a stored record
  public byte[] getRecord(MemHandle h);
}

MemManager 抽象数据类型的用户通过参数 info 提供一个指针，指向用于存储或检索某条消息的空间。这类似于 C++ 的基本文件读写方法。其基本思想是客户端将消息交给内存管理器进行安全保管。内存管理器以 MemHandle 对象的形式返回该消息的 receipt 。客户端持有该 MemHandle ，直到希望取回消息为止。

insert 方法让客户告知内存管理器要存储消息的长度和 内容。 该 ADT 假定内存管理器会记住与给定句柄关联的消息长度， 因此 getRecord 方法不带长度参数，而是返回实际存储的 消息。 release 方法允许客户告知内存管理器释放存储给定消息的 空间。

当所有的插入和释放都遵循简单模式时——比如后请求先释放 （栈序），或先请求先释放（队列序）——内存管理相当容易。 我们关心的是一般情况：任意大小的块可能以任意顺序请求和 释放。 这就是所谓的 动态内存分配。 动态内存分配的一个例子是为编译器的运行时环境管理空闲存储， 比如 C++ 中系统级的 new 和 delete 操作。 另一个例子是多任务操作系统的内存管理。 此时，一个程序可能需要一定量的空间，内存管理器必须跟踪哪个 程序正在使用主存的哪个部分。 还有一个例子是磁盘驱动器的文件管理器。 磁盘文件被创建、扩充或删除时，文件管理器必须分配或释放磁盘 空间。

以这种方式管理的一块内存或磁盘空间有时被称为 堆。 这里"堆"一词的用法不同于通常用来实现优先队列的堆数据 结构。 这里的"堆"指的是由动态内存管理方案控制的内存。

在本章余下部分，我们首先研究动态内存管理技术。 然后解决当内存池中没有单个内存块大到足以满足给定请求时该怎么 办的问题。