14.2.1. 动态存储分配¶

为讨论动态存储分配，我们把内存看成单个数组，它被切分成一系列变长的块，其中一些是 空闲块，一些是 保留块 （即已分配的块）。空闲块链接在一起构成 空闲表，用于服务未来的 内存请求。下图展示了经过一系列内存分配和释放之后可能出现的情形。

内存管理器收到内存请求时，必须在 freelist 上找到一块足够大 的块来满足请求。 如果找不到这样的块，内存管理器只能求助于某种 失败策略（failure policy）， 例如 垃圾回收。

如果请求 \(m\) 个字的空间，而不存在大小恰好为 \(m\) 的块，就必须改用更大的块。此时的一种可能是把整个块都交给这次内存分配请求。当块只比请求略大时，这也许是可取的。因为保留一块小得对未来的内存请求毫无用处的碎块，可能并不值得。另一种做法是：对大小为 \(k\) （\(k > m\)）的空闲块，内存管理器可以保留最多 \(k - m\) 的空间形成新的空闲块，其余部分用于满足请求。

内存管理器可能受两种碎片之害。 外部碎片 是指一系列内存请求产生大量小块，没有一块能满足典型请求。 内部碎片 是指为 \(m\) 个字的请求分配了多于 \(m\) 个字，浪费了空闲存储。内部碎片与外部碎片的区别如下图所示。标着"External fragmentation"（外部碎片）的白色小块太小，无法满足典型的内存请求。标着"Internal fragmentation"（内部碎片）的灰色小块是作为其左侧灰色块的一部分分配的，但它实际上并不存储信息。

有些内存管理方案以内部碎片为代价换取内存管理的简便（也许还能减少外部碎片）。例如，以簇为单位分配文件空间的文件管理系统不会产生外部碎片。以内部碎片为代价简化内存管理的另一个例子是本章稍后描述的 伙伴法。

在 内存池 中搜索一块足以满足请求的块、并把剩余空间保留为空闲块的过程，称为 顺序适配 方法。