参考内容

发展历程

  • Go V1.3- 普通标记清除法，整体过程需要启动STW，效率极低。
  • Go V1.5- 三色标记法， 堆空间启动写屏障，栈空间不启动，全部扫描之后，需要重新扫描一次栈(需要STW)，效率普通
  • Go V1.8-三色标记法，混合写屏障机制，栈空间不启动，堆空间启动。整个过程几乎不需要STW，效率较高。

Mark and Sweep（Go V1.3）

执行流程

主要分为以下两个步骤：

  • Mark（需要进行 STW（stop the world））：暂停程序找到所有可达的对象，然后进行标记
  • Sweep 删除未被标记的对象。
  • 最后停止 STW，然后恢复正常运行。

img

img

优缺点

优点

  1. 简单，容易实现

缺点

  1. STW，让程序暂停，程序出现卡顿。
  2. 标记需要扫描整个 heap。
  3. 清除数据会产生 heap 碎片。

三色标记法（Go 1.5）

算法流程

  • 首先，先把所有的对象都标记为白色。（需要STW，否则会出现丢失数据的现象）
  • 然后从根节点开始遍历，把遍历到的节点从白色集合中转移到灰色集合。
  • 遍历灰色集合，将灰色集合引用的对象从白色集合转移到灰色集合中，然后灰色节点转移到黑色节点。重复第三步，直到灰色集合为空。
  • 删除所有白色节点。

如果不启动 STW 的情况：如果还没有扫描到对象2，但是对象4直接创建了 q 指针，并且移除了 p 指针，那么 对象3 就会无法被扫描到，从而被意外删除。
img

屏障机制

在三色标记法中，我们不希望以下情况出现：

  1. 一个白色对象被一个黑色对象引用。
  2. 灰色对象与它之间的可达关系的白色对象遭到破坏。

当以上两个条件同时满足时，就会出现数据丢失的情况。当然可以通过 STW 直接来解决这个问题，但是实际消耗过大，会很大的影响程序执行速度。因此采取了屏障机制。

  1. 强三色不变式：核心思想是直接破坏黑色对象直接引用白色对象。
    img

  2. 弱三色不变式：所有被黑色对象引用的白色对象都处于灰色保护状态。
    img

插入屏障机制

A 对象在引用 B 对象的时候，B 被标记为灰色。（将 B 挂在 A 的下游，B 必须被标记为灰色。）

为什么插入屏障机制只处理堆，而不是处理栈？
因为栈的生命周期十分明确且易于管理，只需要简单扫描一下根节点即可。

删除屏障机制

被删除的对象，如果自身为灰色或者为白色，那么都被标记为灰色。

但是被标记的灰色对象只能在下一次的 GC 中被回收，回收的精度低。
img

混合写屏障机制（Go V1.8）

  1. GC 开始将栈上的对象全部扫描并且标记为黑色（之后无需重复扫描，无需 STW）
  2. GC 期间，任何在栈上创建的对象都是黑色
  3. 被删除标记为灰色
  4. 被添加标记为黑色。

变色弱三色不变式
解决写屏障和删除写屏障的短板：

  • 插入写屏障：结束的需要 STW 来重新扫描栈，标记栈上引用的白色对象存活
  • 删除写屏障：回收精度低，GC开始时STW扫描堆栈来记录初始快照，这个过程会保护开始时刻的所有存活对象。