乐趣区

关于java:现在已经卷到需要问三色标记了吗

jiezi

已经，我认为这些货色本人平时看看书就够了，属于那种花了半天精力总算搞明确了，而后过两天就天然遗记的货色。

后果，这都啥啊，啥是卡表，什么又是三色标记法，这些鬼问题都有人面试问，卷就完了。

援用计数 & 可达性剖析

要进行垃圾回收 GC，那么咱们首先就要决定到底怎么判断对象是否存活？一般来说有两种形式。

援用计数，给对象增加一个计数器，每当有中央援用它计数器就 +1，反之援用生效时就 -1，那么计数器值为 0 的对象就是能够回收的对象，然而有一个问题就是循环援用的话无奈解决。

对于当初的虚拟机来说，次要用的算法是 可达性剖析算法。

首先定义 GC ROOTS 根对象汇合，通过 GC ROOTS 向下搜寻，搜寻的过程走过的门路称作 援用链，如果某个对象到 GC ROOTS 没有任何援用链，那么就是对象不可达，是能够被回收的对象。

不可达对象须要进行两次标记，第一次发现没有援用链相连，会被第一次标记，如果须要执行 finalize()办法，之后这个对象会被放进队列中期待执行 finalize()，如果在 finalize()中胜利和援用链上的其余对象关联，就会被移出可回收对象汇合。（然而不倡议应用 finalize()办法）

分代收集

有了如何判断对象存活的根底，接下来的问题就是怎么进行垃圾收集 GC，当初商用的虚拟机基本上都是分代收集的实现，它的实现建设于两个假说：

  1. 绝大多数对象都是朝生夕死的
  2. 熬过越屡次垃圾回收的对象越难死亡

基于这两个假说，就产生了当初咱们常见的年老代和老年代。

因为分代了，所以 GC 也就分代了。

年老代用于寄存那些死的快的对象，年老代 GC 咱们称之为 MinorGC，每次年老代内存不够咱们就触发 MinorGC，当前还有存活的对象咱们就依据经验过 MinorGC 次数和动静年龄判断来决定是否降职老年代。

老年代则寄存老不死的对象，这里 GC 称之为 OldGC，当初也有很多人把他叫做 FullGC，实际上这并不精确，FullGC 应该泛指年老代和老年代的的 GC。

依照咱们上文所说的应用可达性剖析算法来判断对象的存活，那么如果咱们进行 MinorGC，会不会有对象被老年代援用着？进行 OldGC 会不会又有对象被年老代援用着？

如果是的话，那咱们进行 MinorGC 的时候不光要管 GC Roots，还有再去遍历老年代，这个性能问题就很大了。

因而，又来了一个假说。。。

跨代援用绝对于同代援用来说仅占极少数。

由此就产生了一个新的解决方案，咱们不必去扫描整个老年代了，只有在年老代建设一个数据结构，叫做记忆集 Remembered Set，他把老年代划分为 N 个区域，标记出哪个区域会存在跨代援用。

当前在进行 MinorGC 的时候，只有把这些蕴含了跨代援用的内存区域退出 GC Roots 一起扫描就行了。

卡表

说完这些，才到了第一个话题：卡表。

卡表实际上就是记忆集的一种实现形式，如果说记忆集是接口的话，那么卡表就是他的实现类。

对于 HotSpot 虚拟机来说，卡表的实现形式就是一个字节数组。

CARD_TABLE [this address >> 9] = 0;

这段代码代表着卡表标记的的逻辑。实际上卡表就是映射了一块块的内存地址，这些内存地址块称为 卡页，从代码能够看出每个卡页的大小就是 2^9=512 字节。

如果转换为 16 进制，数组的 0，1 号元素就映射为 0x0000～0x01FF(0-511)、0x0200～0x03FF(512-1023)内存地址的卡页。

只有一个卡页内的对象存在一个或者多个跨代对象指针，就将该地位的卡表数组元素批改为 1，示意这个地位为脏，没有则为 0。

在 GC 的时候，就间接把值为 1 对应的卡页对象指针退出 GC Roots 一起扫描即可。

有了卡表，咱们就不须要去在产生 MinorGC 的时候扫描整个老年代了，性能失去了极大的晋升。

卡表的问题

写屏障

卡表的数组元素要批改成 1，也就是脏的状态，对于 HotSpot 来说是通过写屏障来实现的，实际上就是在其余分代援用了以后分代的对象时候，在对援用进行赋值的时候进行更新，更新的形式相似 AOP 的切面思维。

void oop_field_store(oop* field, oop new_value) { 
// 援用字段赋值操作
*field = new_value;
// 写后屏障，在这里实现卡表状态更新 
post_write_barrier(field, new_value);
}

写屏障带来的问题就是额定的性能开销，不过这个问题不大，还能承受。

伪共享

另外存在的问题就是我之前文章写过的，伪共享问题（如果你不晓得什么是伪共享，请翻看我之前的文章）。

缓存行通常来说都是 64 字节，一个卡表元素 1 个字节，占用的卡页内存大小就是 64*512=32KB 的大小。

如果多线程刚好更新刚好处于这 32KB 范畴内的对象，那么就会对性能产生影响。

怎么解决伪共享问题？

JDK7 之后新增了一个参数-XX:+UseCondCardMark，他代表是否开启卡表更新的判断，没有被标记过才标记为脏。

if (CARD_TABLE [this address >> 9] != 0) 
      CARD_TABLE [this address >> 9] = 0;

三色标记法

卡表解决了跨代收集和根节点枚举的性能问题。而有了这些措施实际上枚举根节点这个过程造成的 STW 进展曾经属于可控范畴。

另外还存在一个问题就是接下来从 GC Roots 开始遍历，怎么能力高效的标记这些对象，这就是三色标记法的作用了。因为如果堆内的对象越多，那么显然标记产生的进展工夫就越长。

以当初咱们熟知的 CMS 或者 G1 来举例，GC 的前两个步骤如下：

  1. 初始标记：标记 GC ROOT 能关联到的对象，这一步须要 STW，然而进展的工夫很短。
  2. 并发标记：从 GCRoots 的间接关联对象开始遍历整个对象图的过程，这个工夫会比拟长，然而当初是能够和用户线程并发执行的，这个效率的问题就是三色标记关注的问题。

在三色标记法中，把从 GC Roots 开始遍历的对象标记为以下三种色彩：

  1. 红色，在刚开始遍历的时候，所有的对象都是红色的
  2. 灰色，被垃圾回收器扫描过，然而至多还有一个援用没有被扫描
  3. 彩色，被垃圾回收器扫描过，并且这个对象的援用也全副都被扫描过，是平安存活的对象

整个标记的过程如下，首先刚开始从 GC Roots 开始遍历的时候必定所有的对象都是红色的。

接着 A\G 对象被扫描到变成灰色，而后 A\G 对象的援用也都被扫描，A\G 对象变成彩色。

B\C 对象开始被扫描变成灰色，他们的援用也被扫描实现后本人也就都变成了彩色。

而后 D 对象也一样会经验从灰色到彩色的过程(偷点懒，省略一张无关紧要的过程图吧)

最初剩下的 E\F 节点就是能够被回收的对象了。

三色标记的问题

尽管三色标记法很高效，然而也会引申出其余的问题。

首先咱们上文说过并发标记的过程是不会 STW 的，就是你妈在打扫卫生，而你在旁边始终丢垃圾，这也没关系，大不了最初就是还有一些垃圾没扫洁净而已。

对于三色标记来说就是把应该要清理的对象标记成存活，这样本次 GC 就无奈清理这个对象，这个被称作为浮动垃圾，解决方案就是等下次 GC 的时候再清理，这次扫不洁净就等你妈下次打扫卫生的时候再清理就行了。

与此相反，如果把存活对象标记成须要清理，那么就有点麻烦了，这样你的程序就该出问题了。

所以通过钻研表明，只有同时满足两个条件才会产生这种对象隐没的问题：

  1. 插入了一条或者多条彩色到红色对象的援用
  2. 删除了全副从灰色到红色对象的援用

那么，针对这个问题也有两种解决方案：增量更新 和原始快照，如果对应到垃圾回收器的话，CMS 应用的是增量更新，而像 G1 则是应用原始快照。

思路就是既然要同时满足，那么我只须要毁坏其中一个条件那么不就能够了吗？

所以，先看下面咱们的例子中的一个场景，假如 A 扫描完，刚好 C 成为灰色，此时 C ->D 的援用删除，同时 A ->D 新增了援用（同时满足两个条件了吧），这样原本依照程序接下来 D 应该会变成彩色(彩色对象不应该被清理)，然而因为 C ->D 没有援用了，A 曾经成为了彩色对象，他不会再被从新扫描了，所以即使新增了 A ->D 的援用，D 也只能成为红色对象，最终被无情地清理。

增量更新解决方案就是，他会把这些新插入的援用记录下来，扫描完结之后，再以彩色对象为根从新扫描一次。这样看起来不就是增量更新吗？新插入的记录再扫一次！

原始快照则是去毁坏第二个条件，他把这个要删除的援用记录下来，扫描完结之后，以灰色对象为根从新扫描一次。所以就像是快照一样，不论你删没删，其实最终还是会依照之前的关系从新来一次。

退出移动版