golang的垃圾回收机制使用三色标记法和混合屏障机制

声明：本文图片来自b站UP主刘丹冰Aceld的Golang中GC回收机制三色标记和混合写屏障

1、Go1.3之前 标记清除法（mark and sweep）

在GoV1.3中使用的是标记清除法，而这个方法也很简单。通过暂停程序，扫描程序的可达对象并标记，清除没被标记的对象，恢复程序。重点是暂停程序，STW（stop the world）和可达对象（对象可追溯到程序根节点）

image.png

  • 启动STW
  • 可达对象标记为红色
  • 清除非红色对象，即对象5和对象6
  • 结束STW，恢复程序

缺点：

  • STW（stop the world）：程序暂停会导致卡顿
  • 标记需要扫描整个heap
  • 清除数据会产生heap碎片

    2、Go1.5 三色标记法

    为了优化标记清除法，GoV1.5推出了三色标记法。它把对象划分为white白色标记区、grey灰色标记区、black黑色标记区，根据不同阶段分别进行标记，具体过程如下：

程序新创建的对象默认标记为白色并划分到白色标记表中
image.png

GC模块从程序根节点出发进行遍历，把对象1和对象4标记为灰色并划分到灰色标记表
image.png

接着对灰色标记表进行遍历，把可达对象2和可达对象7标记为灰色，划分到灰色标记表，原灰色对象1，对象4标记为黑色，划分到黑色标记表
image.png

重复上一步，直到灰色标记表中无对象
image.png

清除所有白色对象（对象5，对象6）
image.png

优点：

  • 动态分层标记，并非一次性扫描整个heap

缺点：

  • 假设无STW，并发情况下，GC模块还没遍历到对象2，此时对象4指向对象3，对象2删除与对象3的引用，扫描到对象2的时候因为对象3不是对象2的可达对象，因此不会被标记，而对象4已经遍历过了，最后会导致该对象3被误回收。因此依旧不能离开STW

image.png

3、强三色和弱三色不变式

虽然保护三色标记法最简单的方式是STW但为了提高GC效率，我们不能使用STW或尽可能减少STW时间，所以从无STW保护的三色标记法的缺点中可以推演出以下条件来保护：

强三色不变式：黑色对象不能指向白色对象，只能指向黑色对象或灰色对象
弱三色不变式：黑色对象可以指向白色对象，但白色对象的上游必须要有灰色对象

3.1 插入写屏障

为了满足强弱不变式，golang团队推出了屏障机制，其中使用插入写屏障完成强三色不变式。
插入写屏障：当一个对象被引用时触发且不在栈上使用
具体操作：当A对象引用B对象，B对象被标记为灰色

image.png

由于插入写屏障不在栈上使用，对象1指向了对象9，破坏了强三色不变式，所以在回收前，先启动STW，把栈上的对象重新标记为白色，并重新扫描进行标记
image.png
缺点：结束时需要STW来重新扫描栈

3.1 删除写屏障

满足弱三色不变式
删除写屏障： 当一个对象被删除时触发且会在栈上使用
具体操作：被删除的对象如果本身是白色或者灰色，则被标记为灰色
image.png
在这一轮扫描汇总，对象5，对象2，对象3最终都会被标记黑色，只能等到下一轮扫描才被回收。
缺点：回收精度低，扫描波面后退，下一轮GC才能回收上一轮删除的对象

4、Go1.8 混合屏障机制

简单地理解，混合屏障机制=插入写屏障+删除写屏障。
具体操作：

  • GC开始将栈上的所有对象全部扫描并标记为黑色（扫描栈需要STW，之后不再进行第二次扫描，无需STW）
  • GC期间，任何在栈上创建的新对象，均为黑色
  • 被删除的对象标记为灰色
  • 被添加的对象标记为灰色

栈上不启用屏障机制，把所有可达对象全部标记为黑色
image.png

场景一：对象被一个堆对象删除引用，成为栈对象的下游
image.png

场景二：对象被一个栈对象删除引用，成为另一个栈对象的下游
GC期间在栈上创建的新对象都被标记为黑色
image.png

场景三：对象被一个堆对象删除引用，成为另一个堆对象的下游
如果对象10是灰色，它的下游是被保护的，只有对象10是黑色才会出现特殊情况
image.png

场景四：对象被一个栈对象删除引用，成为一个堆对象的下游
image.png