2.3.1　复制算法

复制算法是把堆空间分为两个部分，分别称为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空间而不需要额外的数据结构，该算法在第3章详细介绍。

另外，复制算法还有一个最大的问题：空间利用率不够高。如图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溢出，则可以跨代使用其他代的内存。