Skip to Content
DocumentationJavaJava虚拟机HotSpot垃圾收集器理论基础

HotSpot垃圾收集算法基础

记忆集与卡表

根据前面的分代收集理论，我们提及过，为了解决分代引用的问题，引入了记忆集(Remember Set)的概念。

记忆集是一种记录从非收集区指向收集区的指针集合的抽象数据结构。如果不考虑成本的话，可以直接使用一个对象数组，来记录所有非收集区存在跨代引用的对象。 当然这种实现的复杂度很高，实际上在垃圾收集的场景中，我们一般只需要能做到可以定位到非收集区存在跨代引用的那一块区域即可(这里的区域指的是非收集区下的某一小块区域，并非整个收集区)。

一般情况下，根据记录的细粒度，可以有多种实现：

  • 精确到具体位置，这里记录的是一个寻址地址，通过该地址可以直接找到一个跨代指针
  • 精确到具体对象，每个对象内存在跨代指针
  • 精确到具体区域，区域内至少存在一个对象存在跨代指针，这种实现也被称之为卡表

HotSpot采用的卡表的形式。卡表最简单的形式就是采用字节数组，数组的每一个下标都对应一块区域，这个区域被称为卡页，比如：

CARD_TABLE[this.address >> 9] = 1;

通过上面代码可以看到，每个区域设定的区域大小为2^9B，也就是512KB。一个卡页的内存中通常包含不止一个对象，因此只要对应区域内存在有跨代指针的对象，数组元素下标就变成1。 后续在垃圾收集过程中，可以很方便的得出那些卡页存在跨代指针，把他们对应的对象加入到GC Roots即可

写屏障

现在我们已经知道了如何使用记忆集来缩减GC Roots扫描范围的问题，但是我们还需要知道记忆集是如何维护的。

卡表中的元素是如何变脏的很明确——有其他分代区的对象引用了当前区域的对象，对应的卡表元素就变脏，变脏的时间点发生在引用类型赋值的那个时刻。很明显，我们需要在这个时间点去维护卡表

  • 如果是解释执行，那相对好处理，虚拟机在每条字节码指令的执行周期内，都有介入空间
  • 如果是编译执行，经过即使编译处理后，代码已经是机器指令流了，这时候就需要在机器码阶段，对每一个赋值操作进行改动

在HotSpot内是通过写屏障的技术维护卡表状态的。写屏障可以看作是虚拟机在赋值操作层面的一个AOP切面，允许在赋值操作的前后提供一些额外操作。维护卡表的动作就可以认为是赋值操作的后置增强。

void oop_field_store(oop* field, oop new_value) {
    //引用字段赋值
    *field = new_value;
    //写后增强，完成卡表维护
    post_write_barrier(field, new_value);
}

并发收集可行性分析

当前主流垃圾收集器都是依赖的可达性分析算法来判断对象是否存活的，可达性分析算法理论上要求全过程都基于一个能保证一致性的快照中才能分析，这也就意味着需要冻结用户线程，以免其对对象的引用关系进行修改。 尽管GC Roots相比于整个Java堆来说是一小部分，但是当前继续遍历下去的时候，其花费的时间也就是用户线程停顿时间，必然会与Java堆的容量成正比关系。

那么想降低用户线程的停顿时间，必须明白为什么要在一个保证一致性的快照执行遍历，这里我们引入三色标记 来辅助推导： 按“是否访问过”这个条件，把对象标记成三种颜色：

  • 白色：表示对象没有被访问过。显然在开始阶段，所有对象都是白色，如果扫描分析完成后，对象还是白色，说明其是不可达对象
  • 灰色：表示对象被垃圾收集器访问过，但是这个对象至少还存在一个引用没有被扫描过。
  • 黑色：表示对象已经被访问过，且其关联所有引用都已经扫描过。当对象标记成黑色后，不会退化成灰色。

从这里我们可以很容易推导出：

  • 在扫描完成后，只应该存在黑色和白色对象
  • 黑色对象无法直接关联到白色对象，中间至少要存在一个灰色对象。

此时，如果用户线程在扫描过程中是冻结的，那么最终扫描结果是肯定没问题的。

假设开始扫描时刻为T，此刻用户线程仍然是活动的，那么就有可能在T’修改对象的引用关系，其可能会导致如下后果：

  • 在原来白色对象上修改引用：由于此时当前对象还未访问，所以对最终扫描结果不会产生任何影响
  • 在原来灰色对象上修改：
    • 添加的引用对象是黑色或灰色，此时也不会产生影响，因为黑｜灰色对象已经完成扫描了
    • 删除的对象引用是黑色或灰色，此时需要考虑删除的对象引用，是否仅与当前灰色对象存在引用关系，如果是则会出现问题,原本T时刻应该是黑色的对象，实际变成了白色对象，残留在对中；如果不是则无影响
    • 修改的引用对象是白色：
      • 如果是添加引用操作，如果白色对象没有被其他任何灰色对象引用，那么在T时刻它本该最终属于白色对象，在这次操作后，属于黑色对象
      • 如果是删除引用操作，且删除的引用对象还有其他对象对其有引用关系，那么也不会影响结果。相反，如果目标白色对象仅与当前灰色对象有引用关系，那么就出现不一致了，T时刻本该最终属于黑色的对象结果最后被标记成了白色对象
  • 在原来黑色对象上修改：
    • 如果修改的引用对象是黑色｜灰色：
      • 添加黑｜灰色引用，不会有任何影响
      • 删除黑｜灰色引用，此时需要考虑删除的对象引用，是否仅与当前黑色对象存在引用关系，如果是则会出现问题,原本T时刻应该是黑色的对象，实际变成了白色对象，残留在对中；如果不是则无影响
    • 如果添加的引用对象是白色，就会出现问题，由于黑色标记不会退化成灰色，所以原本T时刻被标记成白色的对象会变成黑色

至此，我们总结出来了所有可能导致扫描结果与预期不一致的情况：

  1. 灰色对象上添加白色引用
  2. 灰色对象上删除了一个白色引用，且删除后白色引用没有其他对象与之关联
  3. 黑｜灰色对象上删除了黑｜灰色引用，且删除后的黑｜灰色引用没有其他对象与之关联
  4. 黑色对象上添加了白色引用

我们一条条分析：

  1. 灰色对象添加白色引用，可能会导致原本T时刻需要删除的白色对象，在T’时刻重新关联上，这个白色对象不应该被删除。但是我们不需要担心，因为当前对象是灰色，所以还会继续扫描下去，所以白色对象最终会变成黑色
  2. 删除后，可能会导致原来黑色的对象变成了白色，这样就可能出现问题，因为删除的对象还可能被其余黑色对象所关联
  3. 删除后，由于没有其他对象关联，所以理论上应该删除的对象最终不会被删除，这样会导致垃圾收集不完整，不过对于程序执行来说没有问题
  4. 黑色对象添加了白色引用，由于黑色对象不会变成灰色对象，所以最终新添加的白色对象会被删除，这样就会导致程序执行出现问题了

所以我们要重点关注2，4条，它们会导致我们程序运行不正常，我们再次对原操作进行分解，可以得到它是有两种基本条件构成的：

  1. 在黑色和白色对象之间，新增了至少一条引用路径
  2. 对于目标白色对象，删除了所有灰色对象指向他的直接引用或者间接

二者条件缺一不可，也就是说，只需破坏两个条件中的一个，我们就可以保证在并发扫描过程中，不会出现对象消失问题。也因此产生了两种解决方案：增量更新和原始快照

  • 增量更新：破坏的是第一个条件，在黑色和白色对象之间新增了引用关系时，记录引用关系，等并发扫描结束后完成更新。
  • 原始快照：破坏的是第二个条件，当灰色对象删除白色引用时，把灰色对象记录下来，在并发扫描结束后，将这些灰色对象作为根重新扫描一遍。
Last updated on