并行的新生代回收

CMS新生代回收相比串行新生代回收最大的优化是将串行算法升级为并行算法。

并行回收在CMS中被称为ParNew。从串行到并行需要考虑的问题是：如何让多个线程并行地执行任务？如果多个并行线程任务负载不均衡该如何处理？如何判断多个线程并行执行结束？

本篇仅讨论CMS如何将串行任务并行执行的问题，关于多线程任务负载均衡和任务结束的问题在后续讨论。

前面已经详细介绍过串行的复制算法，本文主要介绍两者的异同点。

类似于串行回收，ParNew也是在新生代内存不足时触发。回收算法的流程图也和串行回收的算法流程图类似，但ParNew采用了并行的实现，主要表现如下：

1）根处理并行化。

2）遍历对象使用深度遍历，并行处理。

3）引用支持并行。

4）弱根支持并行。

另外，需要注意对转移失败的处理，串行回收中如果发生转移失败，则会继续扫描和转移该对象的成员变量。ParNew转移失败，会把失败对象放入待遍历对象中，继续执行转移，但是并不会真的继续转移该对象（因为已经设置转移失败），也会继续扫描和转移该转移失败对象的成员变量。ParNew在转移失败发生之后，会把全局的标志位设置为true，自此以后转移的对象只能移到To空间，不会再晋升到老生代空间。ParNew的并行算法流程图如图4-5所示。

图4-5 新生代并行回收流程图

在对根进行并行处理时，可以根据根集合的特性选择不同的并行处理方式。简单地说，可以从指向新生代的位置来源进行划分。

1）从非堆空间指向新生代：典型的根集合有线程栈、元数据等，称为一般根集合。

2）从堆空间指向新生代：卡表保存了老生代到新生代的引用。

这样设计的原因主要是，一般根集合通常都比较小，且各个根集合的元素之间都很明确；而卡表覆盖的是整个老生代，老生代通常比较大，卡表的并行处理通常是划分为多个小空间进行处理，但是划分的小空间的起始地址通常不是一个完整对象的起始地址，所以需要额外处理，以确保每个小空间的处理都从第一个完整的对象开始。

一般根集合的并行处理

和串行标记相比，ParNew根集合并行化如何实现呢？

假设在垃圾回收时有N个根集合，有M个线程执行垃圾回收。当M大于等于N时，每个线程都可以单独处理一个根集合；当N大于M时，M个线程先从N个根集合中选择M个进行处理，当一个线程处理完一个根集合之后，再从剩余的NM个根集合中选择一个进行处理，直到N个根集合都处理完成。

从实现角度来看也比较简单。可以定义一个数组，长度为根集合的个数（此处为N），数组中的每个元素标记一个根集合是否被处理。每个线程都从数组中依次获取元素的状态，并尝试设置元素状态为已处理，如果能够获取并成功设置元素状态，则处理这个元素对应的根集合；如果获取到的元素状态为已经处理，则处理下一个根。注意，在这个过程中，获取和设置动作可能被M个线程同时执行，所以需要使用CAS原子性操作来保证有且仅有一个线程能成功设置状态。

在根集合的处理中，线程栈这个根集合处理稍有不同。线程栈并不像其他的根集合那样作为一个整体，被一个GC工作线程进行扫描和标记，而是把每一个线程的线程栈都作为一个根集合。这是因为在运行时线程数量可能比较多，且栈到堆的引用比较多，如果仅使用一个线程来处理，可能导致该GC工作线程处理根集合所需的时间长，这将导致后续处理时发生线程间任务的窃取概率很高。所以为了平衡线程间的待处理对象，可将每一个线程都作为一个根集合。在实现时，Java线程的数据内部有一个变量用于记录线程栈是否被M个线程之一的GC线程处理，修改变量也需要使用CAS指令。

老生代到新生代引用的并行处理

上面提到对于代际引用的并行处理方法是把老生代内存分成更小的块，然后让多个线程并行地处理。这样做遇到的第一个问题就是每个内存块的大小该怎么设置？内存块设置得太大，扫描效率可能高，但可能出现并行线程处理不均衡的现象；内存块设置得过小，可能导致并行线程处理边界时出现冲突，降低性能。JVM提供一个参数ParGCCardsPerStrideChunk（默认值为256，意思是每个线程一次处理256个卡块），让用户自己设置内存块的大小。内存块（称为chunk）大小可以通过公式计算得到，如果用户没有显式地设置参数，则使用默认参数。计算方式如下：

chunk = ParGCCardsPerStrideChunk×Card size = 256×512B = 128KB

将整个堆空间划分成chunk以后，就可以建立M个线程与chunk之间的映射了，例如0号线程处理0，M，2M，…，1号线程处理1，M+1，2M+1，…，以此类推。

但是实际中还经常遇到这样的情况，有些chunk中包含的代际引用非常多，而有些chunk包含的代际引用比较少。为了让M个线程执行的任务尽可能地均衡，JVM增加了一层映射，称为条代（strip）。JVM中提供了一个额外的参数ParGCStridesPerThread（控制每个线程执行的strip数目），让所有的内存块均分到ParGCStridesPerThread×M个strip中。

默认情况下ParGCStridesPerThread是线程个数的2倍，即整体strip为2M，让chunk先映射到2M个strip中，然后再让M个线程执行2M个strip。chunk、strip和线程的映射关系如图4-6所示。

为什么采用两级映射，而不是直接把内存划分到2M个线程上呢？原因是防止过大的内存块中出现不均衡现象。例如在程序运行初期，整个老生代只有前面部分内存存在指向新生代的引用，按照这样的方式划分，可能只有一个或者两个线程非常忙碌地工作，其他线程都处于空闲状态。而按照现在的设计，则可以避免这种情况。

图4-6 老生代并行粒度划分示意图

内存按照chunk划分以后会带来另外一个问题，那就是一个对象可能跨越内存块。理论上来说，不同的内存块由不同的线程处理，对于跨越内存块的对象该如何处理？

在介绍如何处理跨内存块对象之前，先了解一下JVM中涉及的两类代际引用，一种是精确的引用，另一种是不精确的引用。这两种引用分别对应以下两种场景：

当老生代对象被修改时，JVM明确地知道哪一个成员变量被修改，所以在扫描时可以只扫描这个成员变量指向的新生代，这就是所谓的精确的引用。在JVM的GC阶段通常使用精确的引用来记录引用关系。

JVM内部还定义了非精确引用，主要是在通过写屏障往内存写对象时，统一将对象头对应的卡表设置为Dirty（这样设计主要是为了减少写屏障的执行，可以通过优化参数进一步要求在写之前判断是否已经设置过卡表）。在扫描时需要扫描整个对象的成员变量，并处理那些真正指向新生代的成员变量。这种扫描称为不精确的引用。

这两种不同的引用可以同时存在，但这会增加跨内存块处理的复杂性。

为了能准确地处理跨内存块的情况，ParNew设计了一个算法来计算待处理内存块的边界。

1）区间的头部。

如果内存块的头部刚好是对象的起始地址，则区间的头部为内存块的头部。

如果内存块的头部不是对象的起始地址，说明对象跨了至少两个区间，并且该内存块不包含对象的起始地址。简单的处理就是找到第一个需要处理的卡块对应的地址作为区间的头部（只要存在引用，无论是精确的引用还是不精确的引用都可以找到）。

2）区间的尾部则根据引用类型的不同采用不同的计算方式。

如果最后一个对象是非精确引用，并且不是数组对象，此时整个对象都需要处理，且可能需要跨内存块（需要找到对象的尾部），所以区间的尾部一般计算到对象的尾部，或者直到对象存在精确引用时停止。

如果对象是精确引用，或者是数据对象，或者不是对象类型（即基本类型），则区间的尾部直接设置为内存块的结束地址。

在遍历内存块时，会根据区间的情况及是精确引用还是不精确引用来处理（此处处理指的是根据引用，判断对象是活跃对象，需要转移对象还是晋升对象）。精确引用只处理对应的卡块，不精确引用将处理整个对象的所有成员变量。

并行遍历内存块时采用逆序遍历，从后向前逐一扫描对象。原因就是有精确引用和不精确引用。为了更快速地处理精确引用，如果是正序处理，从前向后，对于不精确引用处理比较简单，对象所有的成员变量都需要扫描。

到精确引用部分需要分成两种情况处理，若对象不包含不精确引用，则仅处理卡块；若对象是不精确引用，此时不精确引用处理需要处理整个后半部分（或者到达下一个精确引用的卡块）。而从后向前处理，逻辑更为简单。

卡表的竞争操作介绍

在对卡表的遍历过程中，Minor GC的执行过程还会存在多个线程同时更新卡表的动作。触发写同一卡块的主要原因是新生代中对象位置发生变化，但是老生代中的对象仍然存在对新生代的引用，此时需要更新卡表，保持代际引用的正确性。而多个线程按照内存块划分访问卡表，也会修改卡表（一般处理是先将卡表中的卡块设置为Clean），表示卡块已经遍历完成（MinorGC执行过程中新生代对象会晋升，意味着当前的卡块变成无效值，所以将卡块设置为Clean。如果不将卡块设置为Clean，则会导致大量的浮动垃圾）。

所以在Minor GC执行过程中实际上存在两种修改卡表的操作，分别记为扫描和更新：扫描指的是把老生代作为根扫描活跃对象；更新指的是Minor GC过程中对象位置变化后仍然需要记录卡表的操作。一般来说，多个线程同时访问同一卡块时需要锁来保证操作的正确性，但是ParNew通过算法的设计来尽量避免锁的使用。下面通过一个例子来演示这个设计，假设堆空间如图4-7所示。

图4-7 多个线程访问同一卡块示意图

其中Thread1（线程1，简称T1）和Thread2（线程2，简称T2）分别根据内存块的区间执行扫描动作，假设T1在扫描过程中晋升了对象A，同时该对象仍然有指向新生代的引用对象B，并且晋升的对象A正好处于T2的扫描区间内，在扫描区间中有一个对象C指向了新生代的对象D。

线程T1和线程T2分别根据卡表的值执行扫描操作，在执行过程中需要修改卡块的值以避免重复操作。假设T1先执行，执行扫描时一般需要将卡块的值设置为Clean，从卡块中找到对象A，并且T1继续执行将对象晋升到对象A'处。由于A'有一个成员变量指向新生代中对象B（假设对象B已经转移完成），说明在下一次执行Minor GC时仍然需要把对象A'作为根，所以此处需要将对应的卡块设置为Dirty。另外，T2扫描对象C，并将卡块设置为Clean。

由于T1和T2同时写一个卡块（一个线程写卡块为Clean，一个线程写卡块为Dirty），从而产生了竞争。对于这样的竞争仅仅通过锁是无法保证正确性的。

假设T1先执行，将卡块设置为Dirty，表示该卡块对应的对象是下一次的Minor GC的根。接着T2执行，将卡块设置为Clean，表示该卡块对应的对象将会处理，T2在处理过程中先根据对象C转移对象D，假设对象D转移至老生代中，对于这种情况则不需要设置卡块；然后再处理对象A'，因为对象A'是晋升对象，其成员变量的遍历已经完成，不应该再次被处理，所以卡块保持Clean。但是卡块应该仍然为Dirty才能保证下一次Minor GC可以正确处理。

另外，在老生代的回收中，也会通过卡表记录对象的引用变化，并且在老生代的回收中也会处理和设置卡表。如果不正确地设置卡表将导致MinorGC的根丢失。

所以，此时就涉及在正确地处理卡表的同时保证效率的问题。下面来看看ParNew是如何实现的。首先定义以下几个状态。

1）prev_youngergen：上一次执行Minor GC后明确包含了老生代对象指向新生代对象的引用，是本次垃圾回收的根。

2）Dirty：上一次垃圾回收后，对象的成员被修改，该修改可能是识别为老生代到新生代的引用，或者老生代到老生代的引用，并且该引用尚未被老生代回收或新生代回收处理。

3）PreClean：老生代回收中通过处理卡表标记了修改的对象，但是修改对象仍然可能包含老生代到新生代的引用，所以引入一个不同于Dirty的状态（在后面介绍）。

4）cur_youngergen：本次执行Minor GC后明确存在老生代对象指向新生代对象的引用，是下一次垃圾回收的根。

5）
cur_youngergen_and_prev_nonclean_card：临时状态，表示当前卡块需要被扫描，又有下一次Minor GC的根，但是执行了更新尚未执行扫描，后面需要执行一次扫描。

卡表扫描和更新的流程分为两步，不同的操作根据不同的状态设置对应的卡块值。

线程扫描卡表时，先根据当前卡块的状态决定是否需要处理，如果卡表中的卡块为Clean，表示不需要处理，直接跳过卡块；如果卡表中的卡块不为Clean，表示需要处理，在处理之前先更新卡块。

1）当发现卡块的状态为prev_youngergen、Dirty和PreClean时，先把卡块设置为Clean。

2）当发现卡块的状态为
cur_youngergen_and_prev_nonclean_card时，说明本线程正在与别的线程竞争修改卡块，同时别的线程已经更新过卡块，且标注该卡块包含了下一次Minor GC的根，但是该卡块尚未完成扫描，所以执行扫描，并将卡块状态设置为cur_youngergen。

3）当卡块状态为cur_youngergen时，则无须进一步处理。

对应的状态机如图4-8所示。

图4-8 线程扫描卡表状态机

当线程执行对象转移或者晋升时，如果发现卡块不包含下一次Minor GC的根，则不会进入卡块的处理过程中；如果卡块包含了下一次Minor GC的根，则进入卡表更新过程中。

1）当卡块状态为Clean时，则更新为cur_youngergen，表示卡块作为下一次垃圾回收的根。

2）当卡块状态为Dirty时，说明卡块包含了下一次Minor GC的根，并且该卡块尚未被处理，需要扫描，所以设置状态为

cur_youngergen_and_prev_nonclean_card。

3）当卡块状态为PreClean时，说明卡块包含了下一次Minor GC的根，并且该卡块待扫描，也设置卡块状态为

cur_youngergen_and_prev_nonclean_card。

4）当卡块状态为prev_youngergen时，说明卡块包含了下一次Minor GC的根，并且该卡块待扫描，所以卡块状态也设置为
cur_youngergen_and_prev_nonclean_card。

5）当卡块状态为cur_youngergen时，说明卡块扫描完成，直接作为下一次的根，直接保留状态cur_youngergen。

6）当卡块状态为
cur_youngergen_and_prev_nonclean_card时，说明卡块对应的内存待扫描，在扫描完成时会在另外的线程的卡表扫描结束直接更新状态，所以这里保持不变。

对应的状态机如图4-9所示。

图4-9 线程更新卡表状态机

在ParNew中对卡表扫描的流程图如图4-10所示。

图4-10 ParNew卡表扫描流程图

ParNew中更新卡表中对应卡块的流程图如图4-11所示。

图4-11 ParNew更新卡表流程图

并行复制算法对于卡表的处理带来了新的调整。上述过程以JDK 8代码为例进行说明，堆空间只包含了两个代。

　并行复制算法卡表设计

在JDK 7中还有持久代这个概念，相当于整个堆空间被划分为3个代。那么上述卡表的设计是否需要修改？更有甚者，如果堆空间被划分成更多代，在并行复制算法中卡表该如何设计？

一种简单的处理是针对多个代设计多个卡表，每个卡表维护一个代际之间的引用关系。这样的方式虽然简单，但是需要大量的卡表，存储成本高且实现逻辑也比较复杂。除此之外，还有一个问题，在分代垃圾回收中，针对多代内存回收，需要区别不同代内存对于增量对象的管理（包括对象的晋升和对象的修改），这就涉及并行卡表的扫描和更新问题。

针对这样的问题，一些学者探索出一种优化的方法，即使用一个卡表管理多个代际之间的引用，同时支持卡表并行扫描和更新。

专利中详细介绍了算法，这里简单地进行介绍。假设整个堆空间被划分为3个代，如图4-12所示。

图4-12 3个代的内存划分

当内存被划分成多个代时，需要多少个值记录卡表操作状态？以图4-12为例，整个堆被分成3个代，分别为新生代、中生代和老生代。中生代和老生代需要对应的卡表用于记录它们到新生代的引用，当然老生代的卡表也应该记录老生代到中生代的引用。假设发生以下场景：

1）发生新生代回收，设第一次卡表的操作状态为A，当垃圾回收完成后，如果老生代和中生代中存在对新生代的引用，则在卡表中记录操作状态为A，表示在下一次回收新生代时，操作状态为A的卡块都应该作为根。

2）接着发生一次中生代回收，如果垃圾回收完成后，老生代存在对中生代的引用，则需要在卡表中记录操作状态。但是这个操作状态和操作状态A并不相同，所以需要一个新的操作状态，假设为B。对于同一卡块，操作状态A和B可以共存吗？如果有冲突，该如何解决？统一设定为B。

3）接着又发生一次新生代回收，由于老生代中存在状态A和B，A和B都表示老生代可能存在对新生代的引用。当新的垃圾回收发生时，为了区别现在的操作和以前的操作，需要一个新的状态，记为C。在垃圾回收完成后，如果老生代和中生代中存在对新生代的引用，则在卡表中记录操作状态为C。

如果后续再发生新生代或者中生代垃圾回收，则可以重用状态A，用于区别当前的操作和以前的操作。当然从算法角度来说，还可以消除状态C的使用，那么为了区别不同的状态，可以在中生代的卡表使用状态B来区分操作状态，在老生代中使用状态A来区分操作状态。当然算法实现相对比较复杂。所以简单的结论就是：直接使用分代的个数作为卡表操作状态的个数。JVM的实现和专利的描述基本思路相同，在CMS并发回收器中使用3种操作状态（注意，这3种操作体现为3种不同的cur_youngergen_card即可）。

本文给大家讲解的内容是JVM垃圾回收器详解：并发标记清除回收，并行的新生代回收