概述

垃圾回收（Garbage Collection），简称 GC，对于高级语言是有必需的，因为高级语言要更加关注的是业务，不能花太多精力去关注底层内存释放的问题。

v 1.3 的标记清除算法

标记清除算法，可以概括为以下 4 步骤，循环重复，直到 process 程序生命周期结束：

1. 暂停程序（不然期间会产生新的对象），从 main 根函数出发，找到可达对象和不可达对象。
2. 然后将可达对象变标记上。
3. 然后，清除未标记的对象。
4. 恢复程序运行。

缺点：

1. stw（stop the world）让程序暂停，会表现出卡顿现象，这个是最重要的问题
2. 标记步骤，需要扫描整个 heap（堆），耗费时间多
3. 清除数据，会产生 heap 碎片

在 go V1.3 之前使用的是这个算法。不过 go 做了点优化，为了缩短了 stw 的时间范围，将第三步和第四步骤做了替换。mark 标记完成后，就恢复程序的运行，清除工作和业务程序并行运行。

v 1.5 的三色标记算法

三色标记法有白、灰、黑三个颜色的列表。

1. 白色的列表代表没有被遍历到的，
2. 灰色代表正在被遍历的临时状态，
3. 黑色代表是遍历过的。

经过遍历后，最终只会剩下白色和黑色的两种，把白色的不可达对象给清除掉即可。

工作过程如下所示：

第一步，只要是新创建的对象，默认的颜色都是标记为"白色"。所以，以下的这些对象都会在白色列表中。

第二步，每次 GC 回收开始，首先遍历根节点，非递归，只遍历一次。把遍历到的对象从白色集合放入"灰色"集合。

如下图中，根结点遍历会操作，会遍历到对象 1 和对象 4。然后把着两个对象放到灰色标记表里。

第三步，开始遍历灰色集合，将灰色对象引用的对象从白色集合放入灰色集合中，之后将已经遍历完成的灰色对象放入黑色集合。

如上图所示，遍历灰色 对象 1 和灰色 对象 4，得到他们的引用 对象 2 和 对象 7，然后把 对象 2 和 对象 7 放到灰色列表里，对象 1 和对象 4 放到黑色列表里。

第四步，重复第三步，直到灰色中无任何对象。遍历灰色列表里的对象 2 和对象 7，把对象 2 的引用对象 3 变成灰色，然后对象 2 和对象 7 已经遍历完就变成黑色。

重复几次后，最终会得到如下所示的表

第五步：回收所有的白色标记表的对象 5 和对象 6. 也就是回收垃圾。

和普通标记清除算法比有什么不同点

三色标记法是一层层的开始标记，不是一次性全部标记

三色标记法，没有 stw，什么情况下会出现对象丢失？

如果此时 gc 执行到下图这个环节的时候，因为没有 stw，程序还在运行，如果发生以下两个动作

1. 白色对象被黑色对象 4引用
2. 灰色 对象 2 丢失了和该 白色对象3 的关系

此时因为灰色 对象 2 已经没有引用 对象 3 了，所以遍历 对象 2 的时候，没法找到 对象 3，对象 3 就会被当做垃圾误清除

强弱三色不变式，确保对象不丢失

1. 强三色不变式：允许黑色引用灰色（已经遍历了灰色，不会丢失灰色），不允许黑色引用白色（白色如果是上述的这个两个条件就会丢失，所以直接不允许），这样就会破坏上述中的条件 1
2. 弱三色不变式：允许黑色引用白色，但是，该白色的上游链中必须有一个灰色引用到，这样该灰色最终会遍历到这个白色。

屏障机制，确保不被误删除

插入屏障：

对象被引用的时候触发的机制，在 a 对象引用 b 对象的时候，b 对象被标记成灰色，满足了强三色不变式，这样就不存在黑色引用白色的了。

不足点是：因为这个插入屏障只有在写的堆上才有，栈（用于函数调用啥的）上的空间比较少，要求效率要高，出于效率的考虑，栈上没有这个机制。所以三色标记结束的时候，要 stw 来重新扫描栈，大约 10-100ms。

删除屏障：

被删除的对象，如果自身是灰色或者白色，那么被标记成灰色，满足弱三色不变公式。如下图中，对象 5 和对象 1 之间的引用关系被删除的话，这个时候对象 5 设置成灰色就好。

但是这操作的话有个问题，这个对象 5 其实已经是垃圾了，却还存在，只能等到下一轮 gc 的时候，才会被清除。虽然会有删除精度不高的问题，但是能确保不会被错删除

v 1.8 三色标记法+混合写屏障

混合写屏障，就是把删除和插入屏障放在一起，加上一个栈上的默认全部黑操作，整个过程不会有stw，具体操作：

1. GC 开始将栈上的对象可达结点全部扫描并标记为黑色 (之后不再进行第二次重复扫描，无需 STW)
2. GC 期间，任何在栈上创建的新对象，均为黑色，下一轮 gc 删除
3. 堆上被删除的对象标记为灰色
4. 堆上被添加的对象标记为灰色