堆管理

堆空间用于存放生命周期不稳定、或生存到被明确删除为止的数据对象。

存储管理器

存储管理器是分配/回收堆区空间的子系统。根据语言而定，比如C/C++需要手动回收空间，Java可以自动回收空间（垃圾收集）。

基本功能：

• 分配：为内存请求分配一段连续、适当大小的堆空间。首先从空闲的堆空间分配，如果不行则从操作系统中获取内存、增加堆空间。

• 回收：把被回收的空间返回空闲空间缓冲池，以满足其他内存需求。

评价存储管理器的特性：

• 空间效率：使程序需要的堆空间最小，即减少碎片

• 程序效率：运用内存系统的层次，使程序运行更快

• 低开销：使分配/收回内存的操作尽可能高效

程序中的局部性

程序具有高度的局部性

• 时间局部性：一个程序访问的存储位置很可能在一个很短的时间段内被再次访问

• 空间局部性：被访问过的存储位置的临近位置很可能在一个很短的时间段内被访问

局部性这一特性恰好可以充分利用计算机的层次存储结构。

堆空间的碎片问题

随着程序分配/回收内存，堆区逐渐被割裂成为若干空闲存储块（窗口）和已用存储块的交错。分配一块内存时，通常是把一个窗口的一部分分配出去，其余部分成为更小的块。回收时，被释放的存储块被放回缓冲池，通常需要把连续的窗口结合成为更大的窗口。

堆空间分配方法

• Best-fit：总是将请求的内存分配在满足请求的最小的窗口中。可以将大的窗口保留下来，应对更大的请求。

• First-fit：总是将对象放置在第一个能够容纳请求的窗口中，放置对象花费时间较少，但是总体性能比best-fit策略差。通常具有较好的数据局部性：同一时间段内生成的对象经常被分配在连续的空间内。

使用容器的堆管理方法

设定不同大小的块规格，相同的块放入同一容器。较小的（较常用的）尺寸设置较多的容器。分配方法：小尺寸的请求，直接在相应容器中找；大尺寸的请求，在适当的容器中寻找适当的空闲块；可能需要分割内存块，可能需要从荒野块中分割。（荒野块：可以扩展的内存块）

管理和结合空闲空间

当回收一个块时，可以把这个块和相邻的块结合起来，构成更大的块，有些管理方法不需要进行结合。

支持相邻块结合的数据结构：

• 边界标记：在每个存储块的两端，分别设置一个free/used位，并在相邻的位置上存放字节总数

• 双重链接的空闲块列表：列表的指针存放在空闲块中，用双向指针的方式记录了有哪些空闲块。

内存泄露(Memory leak)：未能删除不可能再被引用的数据

悬空指针引用(Dangling pointer)：引用已被删除的数据