堆管理

堆是内存空间的一部分，它用来存储那些生命周期不确定，或者将生存到被程序显式地删除为止的数据。

虽然局部变量通常在它们所属的过程结束后就变得不可访问，但很多语言支持创建某种对象或者其他数据，它们的存在与否和创建它们的过程的活动无关。例如C++和Java都为程序员提供了new语句来创建这种对象。这样的对象存放在堆区。

存储管理器

存储管理器总是跟踪堆区中的空闲空间。它具有两个基本功能：

1. 分配。当程序为一个对象或者变量请求内存时，存储管理器产生一段连续的具有被请求大小的堆空间。（如果没有空间块可以分配，它试图从操作系统中获取连续的虚拟内存来增加堆区的存储空间）
2. 存储管理器把被回收的空间返还到空闲空间的缓冲池中，这样它可以复用该空间来满足其他的分配请求。（存储管理器通常不会将内存归还给操作系统）

存储管理器应该具有的特性：

1. 空间效率。
2. 程序效率。
3. 低开销。

一台计算机的存储层次结构

典型的大小		典型的访问时间
>2G	虚拟内存(磁盘)	3~15ms
256M~2G	物理内存	100~150ns
128K~~4M	二级高速缓存	40~60ns
16K~64K	二级高速缓存	5~10ns
32个机器字	寄存器	1ns

程序中的局部性

大部分程序表现出高度的局部性(locality)，也就是说程序的大部分运行时间花费在较小的一部分代码中，此时它们只涉及少部分数据。

1. 如果一个程序访问的存储位置很可能将在一个很短的时间段内被再次访问，我们就说这个程序具有时间局部性(temporal locality)。
2. 如果被访问过的存储位置的临近位置很可能在很短的时间段内被访问，我们就说这个程序具有空间局部性(spatial locality)。

局部性原理使得我们可以充分利用现代计算机的存储层次结构。将最常用的指令和数据放在快而小的存储中，而将其余部分放入慢而大的存储中，我们就可以显著地降低一个程序的平均存储访问时间。

碎片整理

在程序开始执行的时候，堆区就是一个连续的连续空闲空间单元。随着这个程序分配和回收存储工作的进行，空间被分割成若干空闲空间块和已用存储块，而空闲块不一定位于堆区的某个连续区域中。我们将空闲空间块称为hole。

对于每个回收请求，被释放的内存块被放回空闲空间的缓冲池中。我们把连续的窗口接合(coalesce)成为更大的窗口，否则窗口只会越来越小。如果我们不小心，空闲存储最终会变成碎片，即大量细小且不连续的窗口。

• best-fit

经验表明，使现实中的程序碎片最少的一个良好策略是将请求的存储分配在满足请求的最小可用窗口中，称为best-fit策略。这种策略趋于将大的窗口保留下来满足后续更大请求。

• first-fit

另一种策略称为first-fit策略。在这个策略中，对象被放置到第一个（即地址最低的）能够容纳请求对象的窗口中。这种策略放置对象时花费的时间较少，但是总体性能比best-fit要差。

• next-fit

虽然best-fit放置策略可以提高空间利用率，但从空间局部性角度考虑，它可能不是最好的。程序在同一时间分配的块通常具有类似的访问模式，并具有类似的生命周期。因此将它们放置在一起可以改善程序的空间局部性。对best-fit算法的有用改进之一是在找不到恰巧等于请求尺寸的存储块时，使用另一种对象放置方法。
在这种情况下，我们使用next-fit策略，只要刚刚分割过的存储块中还有足够的空间来容纳对象，我们就把这个对象放置在这个存储块中。next-fit策略还可以提高分配操作的速度。

• 管理和结合空闲空间

当一个对象通过手工方式回收时，存储管理器必须将该存储块设置为空闲的，以便它可以被再次分配。某些情况下，还可以将这个块和堆中的相邻块合并（接合）起来，构成一个更大的块。

（详见《编译原理》p297-297）

人工回收请求

人工回收的问题：

1. 内存泄漏(memory-leak)。
2. 悬空指针引用(dangling-pointer-dereference)。

编程规范和工具：

1. 对象所有者。
2. 引用计数。
3. 基于区域的分配方法。

(详见《编译原理》p297-209)

（END）