2.1. 动态存储分配¶

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

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

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

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

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

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