GC垃圾回收机制设计原理

标记清除

1.3版本之前。大概分为两阶段:

标记阶段 - 从根对象出发标记堆中存活的对象

清除阶段 - 遍历堆中所有对象,回收未被标记的垃圾对象

1.0版本:是完全串行的,这两个阶段都在STW暂停范围之内

image-20211022124612807

1.1版本:在多核主机并行执行垃圾收集的标记和清除阶段

缺点:整个过程都需要 STW

三色标记

概述:

三色只是为了叙述上方便抽象出来的一种说法,实际上对象并没有颜色之分。这里的三色,对应了垃圾回收过程中对象的三种状态:

白色是要回收的,黑色是被引用的,灰色是对象还在标记队列中等待。当标记阶段结束之后,只有黑色存活对象和白色垃圾对象

1.5版本 实现了基于三色标记清扫和写屏障技术的并发垃圾收集器

垃圾收集器执行过程:

  1. 在垃圾收集器开始工作时,程序中不存在任何的黑色对象,垃圾收集的根对象会被标记成灰色。
  2. 垃圾收集器只会从灰色对象集合中取出对象开始扫描,从灰色对象的集合中选择一个灰色对象并将其标记成黑色,将该黑色对象指向的所有对象都标记成灰色,保证该对象和被该对象引用的对象都不会被回收。
  3. 重复上一步骤,当不存在灰色对象时,标记阶段就会结束。

缺点:三色标记清除算法本身是不可以并发或者增量执行的,它仍然需要 STW。

如果没有STW,在并发执行时,当以下两个条件同时被满足就会有对象丢失

  • 条件一:灰色对象失去了一个白色对象
  • 条件二:同时这个白色对象被黑色对象引用

因为是以上两个条件同时满足才会有对象丢失,所以只要破坏其中一个条件就行,对应两种方法:

强三色不变式:破坏条件二,强制性不允许黑色对象引用白色对象

弱三色不变式:破坏条件一,当白色对象存在其他灰色对象对它的引用,或者链路上游存在灰色对象,那么黑色对象才能引用该白色对象。如图:

黑色对象可以引用该白色对象

image-20211022183928149

黑色对象不能引用该白色对象

image-20211022184141010

屏障机制

屏障技术就是在并发或者增量标记过程中保证三色不变性的重要技术。

这里想要介绍的是 Go 语言中使用的两种写屏障技术:插入写屏障删除写屏障

插入写屏障

对象被引用时触发的机制

具体操作:在A对象引用B对象的时候,B对象被标记为灰色,满足了强三色不定式

注意:因为栈上的对象在垃圾收集中也会被认为是根对象,在栈上使用插入写屏障会大幅度增加写入指针的额外开销,影响性能。所以 Go 团队在实现上选择在栈上不触发插入写屏障,而是在标记完成后,暂停服务(STW),将栈上所有对象设为白色对象,重新从根对象遍历扫描,之后再回收白色垃圾对象

不足:结束时需要STW来重新扫描栈,大约需要10~100ms

删除写屏障

对象被删除时触发的机制

具体操作:当一个老对象的引用被删除时,如果该老对象是白色的,将其变为灰色。保证了弱三色不变性。老对象引用的下游对象一定可以被灰色对象引用。

如下图:

image-20211023220321882

此时B对象删除C对象的引用,触发删除写屏障机制

image-20211023220442328

C变成灰色,这样能保证插入时满足强三色不定式和弱三色不定式,如图

image-20211023220737189

不足: 回收精度低,一个对象的引用即使被删除了依然可以活过这一轮,在下一轮GC中被清理掉

混合写屏障

1.8版本 三色标记法+混合写屏障将垃圾收集的时间缩短至 0.5ms 以内,整体几乎不需要STW,效率高

具体操作:

  1. GC开始,优先扫描栈,将可达对象标记为黑色(之后不再进行第二次重复扫描,无需STW)

    注意:这里不是栈里所有的对象,而是从根节点开始扫描,可达的节点

  2. GC期间,任何在栈上创建的新对象,均为黑色

  3. 被删除的对象标记为灰色

  4. 被添加的对象标记为灰色

下一篇介绍go语言GC实现原理