下载掌阅APP，畅读海量书库
立即打开
串行回收的实现以2.3.1节介绍的变异复制算法（见图2-6和图2-7）为基础，增加了分代处理。在引入分代之后，对回收算法做一些修改和优化。
新生代内存管理包含了内存的分配和回收，这与新生代内存布局密切相关。新生代被划分为3个空间：Eden、From和To空间。这3个空间的作用如下：
1）Eden：仅用于应用程序对象分配；GC工作线程不会在该空间进行对象分配。
2）From：用于GC工作线程在执行垃圾回收时，在前一轮垃圾回收后活跃对象的存储。在特殊情况下，From空间也可以用于应用程序对象的分配（这是JVM在实现对象分配时的一种优化），但GC工作线程不会在该空间进行对象分配。
3）To：用于在GC工作线程执行垃圾回收时，存储本轮垃圾回收过程中活跃的对象。垃圾回收过程将Eden空间和From空间中的活跃对象放入To空间。只有GC工作线程能在该空间进行对象分配，应用程序不能使用该空间进行对象分配。
串行回收使用单线程进行垃圾回收。Java语言支持多线程应用，应用分配对象的空间通常是Eden空间（此处暂不讨论JVM中From空间的优化使用），多个线程同时在一个空间中分配对象，需要设计高效的分配算法来提高应用程序的运行效率。新生代的高速分配算法实际上不仅包含在堆空间中进行对象分配，还包含对新生代堆空间进行垃圾回收后内存的再访问机制（主要指回收后访存的效率）。整体分配算法包含：高速无锁分配、加锁慢速分配、内存不足情况下的垃圾回收后再分配。JVM的内存分配流程图如图3-5所示。
图3-5 JVM内存分配流程示意图
设计3种分配方式的目的如下：
1）优先进行高速无锁分配，这是我们期望的情况，在这种场景中效率最高，具体内容在3.2.1节讨论。
2）当内存不足时，会在进行垃圾回收之后重用内存空间并再次进行分配，这将在3.2.2～3.2.6节讨论。
3）加锁的慢速分配是一个中间状态，主要用于解决：当Mutator直接在堆空间进行内存分配时需要互斥锁（同时也要保证多个Mutator之间竞争的公平性，防止某一个Mutator因为并发锁一直无法成功分配）；在整个JVM运行期间可能已经有其他Mutator因内存不足触发了垃圾回收，通常进行垃圾回收之后有大量可以使用的内存，在这种情况下，Mutator可以在加锁的情况下直接完成分配，该状态是设计和实现的一个优化点。
堆内存中供应用分配对象的空间只有一个（即Eden），而Mutator是多个同时执行，这意味着存在多个Mutator同时在Eden中分配对象的情况，因为Eden属于临界资源，在使用临界资源时需要互斥锁。使用互斥锁的结果就是多个Mutator需要按照内存分配请求的顺序串行执行，而这样的设计将导致Mutator的运行效率较低，所以JVM需要寻找一种高速的无锁内存分配方法来解决多个Mutator互斥访问Eden的问题。这种高速无锁分配在JVM中称为TLAB（Thread-Local-Allocation-Buffer），在其他资料中也称为TLS（Thread-Local-Storage）或者TLH（Thread-Local-Heap）。
TLAB的设计思路就是为每个Mutator分配一个专有的本地缓冲区，每个Mutator在对象分配的时候，优先从本地的缓冲区进行分配，只有在第一次从堆空间中初始化TLAB时才需要加锁分配，这样将大大减少多个Mutator之间分配时的互斥问题。多个Mutator使用TLAB的示意图如图3-6所示。
图3-6 多Mutator使用TLAB进行对象分配示意图
线程（Thread1和Thread2）分别从Eden中分配一个TLAB，Thread1和Thread2的内存分配都是从自己的TLAB中分配的。
虽然使用TLAB的分配方式能减少多个Mutator之间的互斥锁，但是也带来了设计上的复杂性。有两个需要特别注意的地方：
1）TLAB的大小。如果TLAB太小，那么缓冲区很快被填满，需要再次从堆空间请求一个新的TLAB。频繁地从堆空间请求TLAB将导致潜在的锁冲突，从而导致性能下降。如果TLAB过大，虽然不会导致频繁的锁冲突，但是可能导致TLAB一直填不满，存在潜在的空间浪费。
2）何时申请新的TLAB。简单的回答是在TLAB使用完了之后就申请一个新的TLAB。但是判断TLAB是否使用完毕并不容易，原因在于TLAB的大小是固定的，而应用中请求的对象大小并不固定，这就意味着TLAB通常无法完美地被使用完毕，在TLAB即将使用完毕的时候，剩余的大小并不固定。也就是说在TLAB即将用完的时候，需要一个机制判断是否需要申请新的TLAB。通过一个简单的示意图演示该问题，如图3-7所示。
图3-7 TLAB无法满足分配请求示意图
图3-7中演示了TLAB剩余的空间不满足Mutator新对象的分配场景，此时该如何处理？这就需要一个机制来判断是否申请新的TLAB。通常做法如下：
Mutator从堆空间直接分配TLAB并使用TLAB响应应用的分配，当TLAB满了以后，无须进行额外的处理。因为TLAB来自堆空间，在进行垃圾回收的时候会对堆空间进行回收，所以无须进行额外的处理。唯一需要额外处理的是在丢弃TLAB中尚未使用的空间时，需要给剩余空间填充一个垃圾对象（也称为Dummy对象），这样做的目的是保持堆的可解析性（Heap Parsability）。
多线程使用TLAB过程中TLAB满的例子如图3-8所示。假设有两个线程Thread1（简称T1）和Thread2（简称T2），它们都是应用程序线程，在运行时都需要一个TLAB，应用程序线程分配对象都在TLAB中，T1的TLAB在分配对象的时候，因为剩余空间不足以满足对象的大小，所以直接在堆空间Eden中直接分配；此时T1的TLAB仍然指向最初的TLAB；T2的第一个TLAB已经满了（或者说剩余空间比较少，填充Dummy对象之后满了），重新分配一个新的TLAB供新的分配。
图3-8 多线程使用TLAB过程中TLAB满的例子
在JVM的实现中，TLAB的初始大小可以通过参数（TLABSize）调整。另外，JVM也可以通过反馈机制动态调整TLAB的大小（如果允许动态调整TLAB的大小，则需要确保参数ResizeTLAB为true），从而在时间（加锁耗时）和空间（高速无锁分配、空间浪费）之间寻找一个平衡。在判断是否可以丢弃当前TLAB剩余空间的时候，当发现剩余空间小于TLAB的一定比例时，就认为浪费比较少了，可以直接丢弃（参数为TLABRefillWasteFraction，默认值为64，即剩余空间小于等于TLAB的1/64时可以丢弃）。
最后简单解释一下JVM中堆可解性的概念。在JVM运行过程中存在很多需要对堆空间进行遍历的情况，遍历时会从一个起始地址（假设起始地址为heap_start）遍历到终止地址（假设终止地址为heap_end）之间的内存空间。假设在遍历堆空间时进行一些额外的处理，其具体的工作由do_object处理（具体的处理省略）。一个典型的代码如下所示：
HeapWord* cur = heap_start;
while (cur < heap_end) { //遍历整个空间
object o = (object)cur;
do_object(o);
cur = cur + o->size(); //在这里需要空间里面的对象连续
//如果存在空洞，将在此处导致遍历错误
}
在遍历的时候要求堆空间中的对象是连续分配的，如果堆空间中存在空洞（hole），那么上述代码就不能正常工作（空洞会被转化为对象，导致内存访问错误）。所以在处理TLAB剩余空间的时候必须填充一个对象让上述代码能正常运行，这种机制称为堆可解析性（通常填充一个int[]的对象，这个对象是JVM内部产生的，读者可能遇到应用中根本没有分配int[]对象，但是在转存（dump）堆内存时看到很多int[]对象的情况，原因之一就是JVM在处理TLAB时填充了大量死亡的int[]对象）。
在讨论新生代垃圾回收之前，首先要解决的问题就是：谁能触发垃圾回收？何时触发垃圾回收？
从垃圾回收的角度来说，既可以进行主动回收，也可以进行被动回收。主动回收指的是GC工作线程发现内存不足时主动发起垃圾回收动作，被动回收指的是Mutator在对象分配的时候发现内存不足，由Mutator触发GC工作线程执行垃圾回收动作。主动进行回收需要额外的处理，判断何时启动垃圾回收，实现比较复杂；被动回收则非常简单。串行回收选择被动回收。
垃圾回收的执行可以由专门的GC工作线程来执行，也可以由Mutator来执行。通常来说，Mutator用于执行应用业务，如果把垃圾回收的工作放在Mutator中执行，会导致JVM设计的复杂性。使用专门的GC工作线程来执行垃圾回收工作的方法更为常见。GC工作线程执行垃圾回收时需要应用暂停（即STW），在JVM中最新的垃圾回收器实现或者增强中为了减少STW的时间，会把垃圾回收的一些任务放入Mutator中执行，也就是后面介绍的并发垃圾回收。
目前JVM中所有垃圾回收的触发机制有3种方式，即串行回收，并行回收和主动回收，如图3-9～图3-11所示。
图3-9 被动回收之串行回收
图3-9和图3-10演示的是被动回收。其中，图3-9中VMThread作为GC工作线程执行垃圾回收；图3-10中VMThread作为控制线程启动多个GC工作线程并行执行垃圾回收。图3-11演示的是主动回收。串行回收中Minor GC采用的是图3-9的触发机制方式，Parallel GC、ParNew、G1中Minor GC采用的是图3-10的触发机制方式，ZGC和Shenandoah采用的是图3-11的触发机制方式。
图3-10 被动回收之并行回收
图3-11 主动回收
在JVM的串行回收实现中，当Mutator发现无法为对象分配内存空间时
，就会请求GC工作线程执行垃圾回收。JVM中被动执行垃圾回收的流程如下：
1）Mutator发现内存空间不足，触发垃圾回收请求。
2）VMThread控制线程接受请求，暂停所有的Mutator，以便响应垃圾回收执行请求。
3）VMThread作为GC工作线程执行垃圾回收动作。
4）VMThread发现垃圾回收动作执行后会唤醒暂停执行的Mutator，Mutator恢复执行。
在2.3.1节中介绍了复制算法的思想，但并未涉及具体的实现。实现中通常要考虑更多的工作细节，比如该以什么样的顺序标记/复制对象？实现的性能如何？
Cheney在1970年提出的复制算法是最经典的算法，JVM中串行回收就是Cheney算法的变异实现（将新生代分为3个分区，且涉及对象晋升）。下面来演示一下串行回收中的复制算法。
假设初始状态如图3-12所示，对象都分配在Eden中，且因Mutator无法成功在Eden空间分配对象，触发了垃圾回收。为了演示简单，这里只画出了Eden和To空间，省略了From空间。
图3-12 堆空间初始状态
从根集合出发开始标记Eden空间中的活跃对象并将活跃对象复制到To空间中。这里假设只存在一个根，并且引用到对象A。根（Root）在Eden引用对象A，说明对象A活跃，将对象A复制到To空间的A'。A'和A有完全相同的数据，所以A'中的字段仍然指向Eden空间中的对象（A'和A相同的字段指向的对象也是完全相同的）。对象A被复制以后堆空间状态如图3-13所示，用 虚线 表示正在处理的对象。为了清晰地描述复制的过程，使用不同的颜色描述对象复制的状态，黑色表示对象已经处理完成，灰色表示对象正在处理，白色表示对象尚未被处理。
在To空间中有两个指针Scan和Free。其中Free表示To空间中后面的内存尚未使用，Scan表示To空间中标记/复制的对象位置。这两个指针用于模拟一个队列（queue），Scan指向队列头，Free指向队列尾。当A复制到To空间的A'后，To空间的Free指针随之增长，并且对象A'应该标记为灰色，表示待复制A'的成员变量。
图3-13 对象A复制以后的堆空间状态
当A被复制到To空间之后，需要把A'成员变量指向Eden空间中的活跃对象也复制到To空间中。在图3-13中，A'存在两个字段，分别指向B和D。A'中存在两个对象，在实现时应先处理哪一个对象？在JVM中使用一个oopmap来标记对象A'的内存布局，其中对象B和D在对象A'中的相对偏移位置都是固定的，假设A'中内存布局指向对象B的字段在前，指向对象D的字段在后。处理对象A'时，当从前向后处理字段时就会先处理对象B，当从后向前处理时就会先处理对象D（在JVM中存在两种顺序的处理方法）。通常是从前向后处理字段，这里也假设字段B先被处理。所以对象B将从Eden复制一份到To空间中，名字为B'，同时To空间中的Free指针也随之增长，B'也被标记为灰色。堆空间状态如图3-14所示。
图3-14 对象B复制以后堆空间的状态
对象B被复制完成后，继续处理A'中的下一个引用对象D，同样D也被复制到To空间中，名字为D'。
当对象D'被复制到To空间后，对象A'的所有成员变量都已经复制完成，所以颜色变成黑色。此时堆空间状态如图3-15所示。
还有一种情况，假设对象A'还有一个字段指向老生代中的对象F，对象F在A'遍历时该如何处理？简单的回答就是不做任何处理，因为对象F的位置不会发生变化，所以不需要任何额外处理。
图3-15 对象A完成复制后堆空间状态
由于对象A'的颜色变成黑色，意味着可以处理下一个对象B'。那么怎么知道该处理B'呢？这就要用到上面提到的Scan指针，当A'被处理完成后，Scan指针将向后移动，此时Scan指向的对象就是B'。按照同样的方法来处理对象B'。堆空间状态示意图如图3-16所示。
图3-16 移动Scan指针处理下一个对象
当B'被处理完成后也将变成黑色，同时Scan继续向后移动。此时Scan指向对象D'，所以开始标记/复制对象D'中的字段。D'中存在一个引用字段指向对象E，E也被复制到To空间中，名字为E'。同时To空间中的Free指针也随之增长，E'也被标记为灰色。堆空间状态如图3-17所示。
图3-17 复制对象E后堆状态示意图
同样地D'被处理完成，颜色变成黑色。继续处理E'。堆状态示意图如图3-18所示。
图3-18 对象D处理完成后堆状态示意图
因为E'不存在引用字段，所以不需要继续复制任何对象到To空间。此时Scan指针和Free指针重合，表示待标记/复制的对象全部完成，如图3-19所示。
图3-19 对象全部复制完成后堆状态示意图
此时所有活跃对象都从Eden空间复制到To空间中，Eden空间就可以被再次用于Mutator分配对象，所以Eden看起来就像被清空了一样，如图3-20所示。实际上为了确保效率，Eden空间不做任何额外的处理，新分配的对象直接覆盖原来的内存数据。
图3-20 重用Eden空间示意图
Cheney的复制算法实际上是一个宽度优先的遍历算法，该算法虽然使用了宽度优先，但并未真正消耗额外的空间，而是直接借助了To空间模拟了一个队列。所以这个算法非常适用于内存配置不高的场景，这也是串行回收中选择该算法的主要原因。
需要指出的是，JVM中除了串行回收之外，其他的垃圾回收器都未直接采用Cheney的复制算法，而是进行变形，引入了一个额外的标记栈辅助对象的标记过程。为什么其他垃圾回收器都不采用这个算法？最主要的原因是性能，该问题将在3.4节进一步讨论。
上一节介绍复制算法在引入分代后，需要对算法进行修改和优化。根据分代的思想，生命周期短的对象放在新生代中，生命周期长的对象放在老生代中。但是在分配对象时提到，新分配的对象都位于新生代的Eden空间。所以必须设计一个机制，让生命周期长的对象从新生代晋升到老生代中。准确地衡量对象生命周期长短并不容易，存活多长时间的对象才被认为是生命周期长的？很难给出一个准确的时间。另外，应用类型不同，对象生命周期长短的定义也会不同。所以在JVM中通过一个简单的方法来替代生命周期长短的判断，那就是对象晋升的阈值，当对象在经过一定次数的垃圾回收（指仅回收新生代的Minor GC）之后，仍然存活就被认为是生命周期长的对象，就会晋升到老生代中。当然这个方法也有一定的缺点，那就是对象晋升依赖于Minor GC的触发时机，以及晋升的阈值。为此，JVM定义了一个参数MaxTenuringThreshold，让使用者根据应用的特性手动地调整对象晋升的时机
。在引入分代之后，回收算法的示意图如图3-21所示。
图3-21 分代后的复制算法第一次执行GC示意图
在第一次Minor GC执行时，对象从Eden转移到To空间或者晋升到Old空间，在Minor GC执行结束时，From和To进行交换（To永远作为Minor GC执行时对象的转移目的空间）。
在第二次Minor GC执行时，对象从Eden和From转移到To空间或者晋升到Old空间，如图3-22所示。假设Mutator直接在Old中分配了对象，并且在Minor GC执行时晋升了一些对象，为了提高Minor GC执行的效率，会维持一个代际引用（如图3-22中的卡表所示），所以当老生代新增对象时需要判断是否要维护卡表。
图3-22 分代后的复制算法第二次GC执行示意图
分代回收如何判断所有对象是否遍历完毕？
在串行回收中，使用的是宽度优先遍历，本质上使用队列来保持尚未标记完成的对象，当队列中不包含对象时，标记就完成了。只是在实现中重用了Survivor分区的空间，并没有为队列分配额外的内存。由于涉及分代，在处理时不仅要处理Survivor分区中新增的对象，同样还要处理晋升到老生代的对象。老生代的处理稍有一些不同，老生代的循环终结条件也是新生代的新增区域不再变化。除此以外，晋升到老生代的对象涉及更新卡表（维护跨代的引用关系）。
在分代回收中还需要额外处理Minor GC中对象晋升失败的情况。晋升失败指的是Minor GC向老生代中晋升对象，但是老生代没有足够的空间存储晋升的对象。晋升失败处理相对来说是一件比较麻烦的事情，通常来说，晋升失败并不撤回已经晋升成功的对象，仅仅针对晋升失败的对象做引用恢复处理（此时晋升失败的对象变成了死对象），然后整个GC继续执行。Minor GC过程发生晋升失败，一般都会在GC结束后触发更费时的垃圾回收动作（如Full GC）。
在分代算法中，位于不同代之间的对象可能存在相互引用。在应用初始运行时，对象都位于新生代，对象之间的引用关系都在新生代中。但是当对象晋升到老生代后，此时就存在新生代中的对象引用老生代的对象，同时老生代对象引用新生代对象的情况。在对新生代进行垃圾回收时，第一步需要做的就是识别新生代中的活跃对象。由于代际之间存在相互引用的情况，按照常规的思路，需要对整个内存空间进行标记才能准确地识别内存中的活跃对象。在对整个空间标记完成之后，再对新生代的空间进行回收。为了回收部分空间，对整个空间进行标记存在大量的浪费。为了解决这个问题，分代设计中引入了一个概念，称为“引用集”。引用集主要记录从老生代到新生代的对象引用关系，用于加速Minor GC时对象的标记。在对新生代进行标记时，把引用集作为新生代的根，从引用集找到的对象都认为是活跃的，这样就不用标记整个内存空间。
注意
在目前的设计和实现中，所有的垃圾回收器都只有老生代到新生代的引用，原因在于回收老生代时要么同时回收新生代，要么要求先回收新生代再回收老生代。对于这两种设计来说，都不需要额外记录新生代到老生代的引用。在同时回收新生代和老生代时，需要对整个内存空间进行标记，所以无须进行额外的记录；在回收老生代时首先进行一次新生代的回收，可以直接把新生代回收之后的对象作为老生代的根，所以也无须额外的记录。不记录新生代到老生代的引用的主要原因是：新生代发生垃圾回收的频次较高，对象的位置变化频繁，这样的变化会导致引用集的设计非常复杂。
当然，使用引用集的方法可能会导致一部分浮动垃圾无法回收。例如老生代的对象实际上已经死亡，若对象仍然引用到新生代，引用集仍然会把这些死亡对象作为新生代的根，而把死亡对象作为根会导致浮动垃圾。注意，老生代中死亡的对象只有在老生代发生垃圾回收之后才能被识别出来，只有识别之后才可能更新引用集。
应该设计什么样的数据结构来存储引用关系及何时记录引用关系？引用关系的记录大体可以分为以下两种方式。
（1）在引用对象处记录引用关系
因为引用对象在一个时刻只能指向一个被引用对象，所以这个引用关系只需要记录一次。老生代中的对象只有在发生了老生代回收后位置才可能发生变化，在新生代回收时老生代中的对象位置不会变化，所以可以通过老生代中的对象关联一个数据结构来记录引用关系。例如在实现时，可以直接分配一个数组，数组的下标是老生代中对象的地址，数组元素对应的值为引用新生代对象的地址，如图3-23所示。
图3-23 数组记录引用关系
这样的实现有一个小小的缺点：数组比较大（记录完整的对象地址），导致空间消耗大。另外，在实际运行过程中，数组的大多数元素都未使用，是一个非常稀疏的数组。所以一个优化方法是采用压缩方式存储数组。通常把一段内存空间视为一个管理单元（简称为卡块），如果管理单元中有任何一个对象存在指向新生代的引用，那么就认为该单元中所有的对象都有可能存在指向新生代的引用，在处理引用时，再把该单元中所有的对象一一取出，并判断是否存在指向新生代的引用，如果存在则进行标记，如果不存在则直接跳过对象。这是一种典型的时间换空间的做法。这种技术被称为卡表。使用卡表时需要考虑两个问题：
1）卡表的大小是一个值得关注的问题。
2）存储不能以对象为单位进行管理，因为对象的大小都不相同。所以使用两个压缩表，一个记录引用，一个记录对象的起始位置。
使用卡表存储引用关系的示意图如图3-24所示。
图3-24 使用卡表存储引用关系
使用卡表还需要解决另外一个问题——如何访问对象？访问对象时总是需要知道对象的起始地址才能读取对象，然而卡表和对象的起始地址没有任何关系，所以需要一个额外的数据结构记录每个卡块中第一个对象的位置（这个值是第一个对象起始地址和卡块起始地址的偏移量），这个数据结构在JVM中被称为BOT（Block-Offset-Table），这样就能正确地访问卡表的对象了。但是有一个特殊的场景，需要对BOT信息进行额外处理，就是大对象的处理。一个大对象会占用多个连续的卡块，要找到超大对象的起始地址，可以在BOT中记录一个负值表示对象起始地址在前一个卡块中，这样通过BOT的配合总能找到对象的起始地址。这个方案针对超大对象可能不够优化，需要连续访问多个BOT表，不断地往前追溯。一个可能的优化是在BOT表中直接记录一个目标位置的负值，然后就可以通过该负值直接跳到目标位置的卡块中，从而减少了追捕回溯的性能。大对象回溯示意图如图3-25所示，其中用 x 表示当前修改位置和对象头所在位置的偏移距离。
图3-25 大对象BOT回溯示意图
实现中还需要考虑一些细节，例如对象超级大，图3-25中的BOT存储的值 -x 超过了BOT一个元素的表示范围，此时需要设计一个合理的编码方式记录 -x 。JVM也是类似的实现，具体的编码规则不再展开介绍。
（2）在被引用对象处记录引用关系
因为多个对象可以同时指向同一个引用对象，所以在这种方法中需要记录多个引用者。回收时只需要简单处理自己对象存储的引用关系，如图3-26所示。
图3-26 在被引用者处记录引用者信息
在串行回收中通过写屏障技术来记录引用关系。写屏障指的是在堆空间中写对象时，额外插入一段代码。除了写屏障以外，还有读屏障、比较屏障等概念。由于卡表记录的是代际引用，代际引用关系变化发生在Minor GC或者Mutator执行过程中，如果对象发生了晋升、转移或者引用关系修改，也就意味着发生了对象写操作，就可以通过写屏障技术将引用关系记录在卡表中。
串行回收中通过卡表管理引用关系，主要原因是：在堆设计时地址连续、边界固定，非常适用于使用卡表快速判断是否需要写屏障。由于记录引用关系需要屏障技术，这意味着需要存储成本以及执行成本，因此很有必要确定哪些情况需要使用卡表来记录引用关系。对象修改前后引用关系是否需要记录的情况如表3-2所示。
表3-2 对象修改前后引用关系是否需要记录的情况
在JVM的实现中，对于卡表的处理涉及读、标记、写。处理方式是：先找到卡表中存在引用标记的卡块，对该卡块进行清除，然后对卡块关联的对象进行遍历，判断对象是否存在指向新生代的引用，如果存在，则进行标记、转移，如果不存在则跳过。当对象转移后，把原来的引用地址更新为新的地址，在更新成功后，再次判断是否需要记录引用关系，如果需要则再次对引用集进行更新。当对象晋升到老生代时，晋升的对象会再次被扫描，相当于认为这些对象存在代际之间的引用关系。