程序员真的有必要把GC算法好好过一遍，因为它是进大厂必备的

GC算法概述

最早的GC算法可以追溯到20世纪60年代，但到目前为止，GC的基本算法没有太多的创新，可以分为复制算法（Copying GC）、标记清除（MarkSweep GC）和标记压缩（Mark-Compact GC）。近些年推出的GC算法也都是在基础算法上针对一些场景进行优化，所以非常有必要理解基础的GC算法。

复制算法

复制算法是把堆空间分为两个部分，分别称为From Space（From空间）和To Space（To空间）。其中From空间用于应用的内存分配，To空间用于执行GC时活跃对象的转移。GC执行时From空间中的活跃对象都会转移到To空间中，GC完成后From和To交换，From空间中剩余尚未使用的空间继续用于应用的内存分配，To空间用于下一次GC活跃对象转移。下面通过示意图演示。假设对象标记如图2-4所示。

图2-4 复制算法执行前内存空间状态

复制算法执行之后，内存示意图如图2-5所示。

图2-5 复制算法执行后内存空间状态

复制算法的特点可以总结为：

1）复制完成后，To空间中的对象是按照堆空间的内存顺序分配的，也就是说复制完成后，To空间不存在内存碎片的问题。

2）复制完成后，From空间和To空间交换，应用程序新的对象都分配在From空间剩余的空间中（图2-5为了演示复制过程，没有将From和To交换）。

由于复制算法涉及对象的移动，因此必须存储对象移动前后的位置关系（确保对象只转移一次），在复制算法中当对象转移成功后，通常把转移后的地址保存在对象头中，当再次转移相同对象时可以通过对象头的信息获得转移后的对象，无须再次转移，这也意味着复制算法除了转移对象以外，还需要在原对象转移成功后在原对象的对象头中设置对象转移后的地址。可以想象，当多线程并行执行复制算法时，需要考虑同步，防止多个线程同时转移一个对象，通常使用无锁的原子指令来保证对象仅能成功转移一次。

复制算法通常只需要遍历From空间一次就可以完成所有活跃对象的转移，所以对象的标记和转移一次性完成。由于转移中需要遍历活跃对象的成员变量，因此算法实现中需要一个额外的数据结构保存待遍历的对象，当然这个额外的数据结构可以是队列或者栈。Cheney提出的复制算法借助To空间而不需要额外的数据结构，该算法在后面详细介绍。

另外，复制算法还有一个最大的问题：空间利用率不够高。如图2-4和图2-5所示，空间利用率只有50%。为了解决空间利用率的问题，JVM对复制算法进行了优化，设置了3个分区，分别是Eden、Survivor 0（简称S0）和Survivor 1（简称S1）。在新的优化实现中，Eden用于新对象的分配，S0和S1存储复制算法时标记活跃对象。这个优化的依据是，应用程序分配的对象很快就会死亡，在GC回收时活跃对象占比一般都很小，所以不需要将一半空间用于对象的转移，只需使用很少的空间用于对象的转移，S0和S1加起来通常小于整个空间的20%就能保存转移后的对象。下面演示一下新的优化算法的执行过程。

新分配的对象都放在Eden区，S0和S1分别是两个存活区。复制算法第一次执行前S0和S1都为空，在复制算法执行后，Eden和S0里面的活跃对象都放入S1区，如图2-6所示。

图2-6 复制算法第一次执行

回收后应用程序继续运行并产生垃圾，在复制算法第二次执行前Eden和S1都有活着的对象，在复制算法执行后，Eden和S1里面活着的对象都被放入S0区，如图2-7所示。

图2-7 复制算法第二次执行

虽然优化后的算法可以提高内存的利用率，但是带来了额外的复杂性。

例如，S0可能无法存储所有活跃对象的情况（这在标准的半代回收中不会出现，活跃对象不可能超过使用空间的最大值）。通常有两种方法处理S0溢出的情况：使用额外的预留空间保存溢出的对象，这部分空间需要预留；动态调整S0和S1的大小，保证S0和S1在GC执行时满足对象转移的需要，这意味着Eden、S0/S1的边界并不固定，在实现时需要额外处理。这两种方法在JVM中均有体现。另外JVM实现了分代算法，在某一个代中执行复制算法时，如果出现S0或S1溢出，则可以跨代使用其他代的内存。

标记清除算法

复制算法的空间利用率有限，但效率较高，并且GC执行过程包含了压缩，所以不存在内存碎片化问题。另外一种GC算法是标记清除，对于内存的管理可以使用链表的方式，当应用需要内存时从链表中获得一块空闲空间并使用，当GC执行时首先遍历整个空间中所有的活跃对象，然后再次遍历内存空间，将空间中所有非活跃对象释放并加入空闲链表中。以图2-4的内存状态为例，标记清除算法执行结束后的示意图如图2-8所示。

图2-8 标记清除算法执行结束后的内存示意图

标记清除算法的内存使用率相对来说较高，但是还有一些具体情况需要进一步分析。由于标记清除算法使用链表的方式分配内存，因此需要考虑分配的效率及内存分配时内存碎片化的情况。具体来说，空间链表中存放尚未使用或者已经释放的内存块，这些内存块的大小并不相同。从空闲链表中请求内存块时，需要遍历链表找到一个内存块。另外，由于链表中内存块大小不相同，因此可能没有和请求大小一样的内存块，此时需要找到一个比请求内存大的内存块才能满足应用的需要，这就需要额外的控制策略，是找到一个和请求内存尽可能接近（best-fit）的内存块，还是找一个最大（worstfit）的内存块，或者是第一个满足需求（first-fit）的内存块？不同策略导致分配时的碎片化情况有所不同。

除了考虑分配效率和分配时内存碎片化的情况，还需要考虑回收的情况。特别是回收时空闲内存的合并，是否允许相邻的空间内存块合并？合并需要花费额外的时间，同时也会影响内存的碎片化。

在JVM中并发标记清除采用了该算法，为提高分配效率使用了多条链表及树形链表，分配策略使用best-fit方法，回收时提供了5种策略并辅以预测模型控制空闲内存块的合并。更多细节参考第4章。

标记压缩算法

标记清除算法的内存利用率虽然比较高，但是有一个重要的缺点：内存碎片化严重。内存碎片化可能会导致无法满足应用大内存块的需求。另外一种GC算法是标记压缩算法，其本质是就地压缩内存空间，而不是像复制算法那样需要一个额外的空间。算法可以分为以下4步：

1）遍历内存空间，标记内存空间的活跃对象。

2）遍历内存空间，计算所有活跃对象压缩后的位置，“压缩后”是指如果遇到死亡对象，则直接将其覆盖。

3）遍历内存空间，更新所有活跃对象成员变量压缩后的位置。

4）遍历内存空间，移动所有活跃对象到第二步计算好的位置，此时由于对象内部的成员变量已经完成更新，因此移动对象后所有的引用关系都是正确的。

在一些实现中，第二步和第三步可以借助额外的数据结构合并成一步。

总体来说，标记压缩算法需要遍历3～4次内存空间，虽然内存利用率更高，并且GC执行后不存在内存碎片的问题，但是因为多次遍历内存空间，故算法的执行效率不高。

仍然以图2-4的内存状态为例，标记压缩算法执行结束后的示意图如图2-9所示。

图2-9 标记压缩算法执行后内存示意图

由于标记压缩算法执行效率不高，因此通常作为GC的兜底算法。标记压缩在JVM中也有多种实现，分别是串行实现、并行实现。在第3～5章中都会介绍标记压缩算法。

分代回收

3种GC算法各有优缺点，实际中需要根据需求选择不同的实现。除此以外还可以将内存空间划分成多个区域，每个区域采用一种或者多种算法协调管理。这个思路来自人们对应用程序运行时的观察和分析。根据研究发现，大多数应用运行时分配的内存很快会被使用，然后就释放，这意味着为这样的对象划分一块内存空间，然后使用复制算法效率会很高，因为对象的生命周期很短，在GC执行时大多数对象都已经死亡，只需要标记/复制少量的对象就可以完成内存回收。现代垃圾回收实现中都会根据对象的生命周期划分将内存划分成多个代进行管理，最常见的是将内存划分为两个代：新生代和老生代，其中新生代主要用于应用程序对象的分配，一般采用复制算法进行管理；老生代存储新生代执行GC后仍然存活的对象，一般采用标记清除算法管理。

基于对象生命周期管理，有弱分代理论假设和强分代理论假设两种：

1）弱分代理论假设：假定对象分配内存后很快使用，并且使用后很快就不再使用（内存可以释放）。

2）强分代理论假设：假定对象长期存活后，未来此类对象还将长期存活。

基于弱分代理论将内存管理划分成多个空间进行管理，基于强分代理论可以优化GC执行的效率，不回收识别的长期存活对象，从而加快GC的执行效率。

值得一提的是，目前弱分代理论在高级语言中普遍得到证实和认可，但是对于强分代理论只在一些场景中适用。目前弱分代理论和强分代理论在JVM中均有体现。

虽然分代回收的思想非常简单，但实现中有许多细节需要考虑，例如在内存分代以后，分代边界是否可以调整？以内存划分为两个代为例，最简单的实现是边界固定，如图2-10所示。