深入理解 JVM 垃圾回收算法 - 标记整理算法

前文我们提到，可以有多种办法来提高标记-清理算法的垃圾回收效率，但内存碎片化却始终没有好的办法解决，这也是非移动式垃圾回收器共有的毛病：尽管堆中仍有可用空间，但内存管理器却无法找到一块连续的内存来满足较大对象的分配需求，或者需要花费较长时间才能找到合适的空闲空间。

对于小对象或者对象大小相差不大的程序，Allocator 可以仅在单个内存块中分配相同大小的对象，从而缓解内存碎片问题，比如前文提到的懒惰清理算法。但对于长期运行的程序，由于非移动式垃圾回收不会改变内存中对象的位置，久而久之，一定会出现碎片化问题，进而导致程序性能下降。

在接下来的两篇文章中，我们讨论两种对堆中存活对象进行整理 (compact) 以降低内存碎片的回收算法：整理算法和复制算法。其中，整理算法是把活的对象整理到相同区域的一端，而复制算法则是将存活对象从一个区域移动到另一个区域，比如新生代的 from 和 to 两个 survivor 半区。

什么是标记-整理算法

标记-整理算法的执行还是分为两个部分，首先是标记阶段，相关内容已经在前文讨论过；然后是整理阶段，移动存活对象位置，同时更新所有指向被移动对象的指针。

这类算法通常需要多次遍历堆空间，比如第一次遍历算出存活对象应当移动到哪个位置，接下来的遍历才会去移动对象。而不同的算法，堆的遍历次数、整理过程所遵循的顺序，对象的移动方式都有所不同，所以这些算法间的性能差异非常明显。

通常情况下，整理算法重排堆中对象时采用下述三种策略：

• 任意顺序(Arbitrary)：对象的移动方式与它们的原始排序顺序和引用关系无关，可以把对象移动到任意位置。其实现简单且执行快速，但这种整理方式可能会把原来相邻的对象分散到不同的高速缓存行或虚拟内存页，从而降低空间的局部性(locality)。

• 线性(Linearising)：将具有关联关系的对象排列在一起，比如具有引用关系的对象，或同一数据结构中的相邻对象。其最关键的问题是，很难评估将具有什么样关联关系的对象排在一起有更好的性能。所以，你几乎看不到使用这种策略实现的整理算法。

• 滑动(Sliding)：将存活对象滑动到堆的一端，挤出垃圾，保证原有顺序。由于它不改变对象的相对排列熟悉，不会影响赋值器的局部性，所以现代的标记-整理回收器均使用这一策略。

前文多次提到局部性，局部性原理指的是，对于应用程序来说，总是趋向于访问最近已经使用过的指令和数据，或者附近的指令和数据。从时间维度来看，刚刚访问的指令和数据，在不远的未来很有可能被再次访问；从空间维度来看，刚刚被访问的指令和数据，其附近的指令和数据在不远的未来很有可能被再次访问。

局部性原理在计算机领域应用非常广泛，比如计算机存储器的分级：离 CPU 越近的存储器，速度越快，因此寄存器的访问速度最快，其次是各种高速缓存，然后才是内存、磁盘等。CPU 正在访问的指令或数据往往会再次访问，所以在第一次访问后，会将其复制到高速缓存中，下次访问时就无需再次从内存中读取。

再比如，MySQL InnoDB 从磁盘读取数据时，并非按需读取，而是按页读取，一次至少读取一页数据，如果未来要读取的数据就在页中，就能够省去后续的磁盘 I/O。

整理算法的最大优势是可以有效减少内存碎片，但它也有不少限制：

• 采用任意策略的整理算法只能处理单一大小对象，或只能对不同大小的对象分别进行整理，这在下文介绍双指针算法时，会详细介绍；

• 整理过程需要两次甚至三次整堆遍历，这个在前面已经提到过；

• 对象头部可能需要一个额外的槽来保存迁移信息，这对通用内存管理器来说是一个显著的额外开销。

而为了最大限度地避免这些限制，前人发明了不同的整理算法，接下来简单介绍其中的几种。

双指针整理算法(Edward’s Two-finger compactions)

双指针算法是 Robert A.Saunders 在 1974 年提出的，它采用任意顺序策略，需要遍历两次堆空间，第一次遍历的目的是整理内存，即移动对象；第二次遍历的目的则是更新所有指向被移动对象的指针。

双指针算法的最佳适用场景为只包含固定大小对象的区域。其实现原理非常简单，大致的示意图如下所示，图中字母表示内存地址，数字为对象标识。

算法的第一次遍历(图 1.1-1.5)：

1. 在算法初始阶段，指针free指向区域开始，指针scan指向区域末尾，在第一次遍历过程中，指针free不断向前移动，指针scan不断向后移动；

2. 指针free不断向前移动，直到遇到一个空闲位置，指针scan不断向后移动，直到遇到一个存活对象；

3. 当指针free和指针scan分别指向空闲位置和存活对象时，准备将 scan 指向的对象移动到 free 的位置；

4. 将 scan 指向的对象移动到 free 的位置，scan 指向的位置记录下原对象移动到了哪里(图中为 B 位置)，并将这块内存标记为空闲；

5. 当 指针free和指针scan发生交错，遍历结束。

算法的第二次遍历：

1. 初始化时，指针scan指向区域的起始位置；

2. 然后开始遍历，如果指针scan指向的对象中包含指向空闲位置的指针 p，则 p 指向的内存块中必定记录着对象移动后的地址，然后将 p 指向这个地址。比如，图中对象 3 有一个指针指向对象 4，对象 4 移动后，其原来的内存块 F 中记录着其移动后的地址 B，那么需要将这个指针修改为指向 B；

3. 继续遍历，直到指针scan指向的位置为空闲内存，遍历结束。

双指针算法的优势是实现简单且执行速度快，但它打乱了堆中对象的原有顺序，这会破坏程序局部性，而且还对分配内存大小有严格限制，所以其应用范围有限。

这也算是采用任意顺序策略的整理算法的通病，可以想象一下，如果对象大小不固定，遍历存活对象并找到合适大小的空闲内存，该如何遍历堆，又会遍历多少次？到这儿也就能够理解为什么采用任意顺序策略的整理算法只能处理单一大小对象，或只能对不同大小的对象分别进行整理的原因了。

Lisp 2 算法(Lisp 2 collector)

Lisp 2 算法是一种广泛使用的滑动回收算法，与双指针算法不同，它需要在每个对象头部增加一个额外的槽来保存转发地址(forwarding address)，即对象移动的目标地址，除此之外，它需要三次堆遍历，但每次遍历要做的工作相较于其他算法并不多。

使用滑动算法整理前后的内存对比示意图如下所示，即把所有存活对象按照顺序依次移动到内存的一端，就好似依次滑动过去一样。

Lisp 2 算法需要三次堆遍历，我们依次讨论。在标记结束之后的第一次堆遍历过程中，回收器将会计算出每个存活对象的最终地址(转发地址)，并保存在对象的forwarding address域中，其示意图如下：

1. 在初始状态，指针free和指针scan都在起始位置；

2. 指针scan向前遍历，直到遇到存活对象，然后将 free 指向的地址写入对象 1 的forwarding address域；

3. 指针free和指针scan均向前移动 size(对象1) 步；

4. 指针scan继续向前移动，直到下一个存活对象，然后重复步骤 2 和步骤 3，直到指针scan跑到堆的末端。

接着进行第二次堆遍历过程中，回收器将使用对象头中forwarding address域记录的转发地址来更新 GC Roots 以及被标记对象的引用，该操作确保它们指向对象的新位置。

最后是第三次遍历，将每个存活对象移动到其新的目标位置。

Lisp 2 算法的实践过程中，通常会把整个堆空间划分为多个内存块，这样多个内存块里面可以同时并发执行；并且在相邻内存块上使用不同的滑动方向，这样可以产生较大的对象“聚集”，进而产生更大的空闲内存间隙，如下图所示。

Lisp 2 算法相比于其他算法的最大优点是堆空间利用率高，但缺点也很明显，堆遍历次数多。

其它

Lisp2 算法的最大缺点是需要三次堆遍历，后来，出现了多种只需要两次堆遍历的滑动回收算法，其中最出名的是引线整理算法(Threaded compaction algorithms)和*单次遍历算法(One pass algorithms)*。其中引线算法的实现有多个版本，限制最少的版本是 Jonkers 实现的算法。

引线整理算法和单次遍历算法相较于前面的双指针算法和 Lisp2 算法，更复杂，也更加晦涩难懂，每一种算法想要说明白都够写几千字了。因此，在这儿就不继续下去了。

如果只是想简单的了解这两种算法，可以阅读「垃圾回收算法手册」的第 3.4 和 3.5 小节。

如果想要更深入的了解，其实还挺麻烦的，因为关于这两种算法实现的中文资料并不多，但可以用算法的英文名称去搜搜看，如果懒得去搜，就看看这个：Algorithms for Dynamic Memory Management 吧。

而关于引线整理算法实现的中文资料，只找到这篇：Threaded Compaction算法——Jonker算法，写得挺好的，如果是我来写，最多也就这个程度了。如果链接失效，可以访问这个备用地址。

深入理解 JVM 系列的第 12 篇，完整目录请移步：深入理解JVM系列文章目录

封面图：Shawn Ang

参考资料

垃圾回收算法手册：自动内存管理的艺术

Threaded Compaction算法——Jonker算法