关于golang:Go学习笔记GC回收机制

V1.3 前 - 标记革除法

mark and sweep

GoV1.3 之前的标记革除：mark and sweep

1. 暂停程序业务逻辑STW(stop the world), 分类出可达和不可达的对象，而后做上标记。
2. 程序找出它所有可达的对象，并做上标记。
3. 革除未标记的对象。（对象 5，6 不可达，被 GC 革除）
4. 进行暂停，让程序持续跑。而后循环反复这个过程，直到 process 程序生命周期完结。

留神：mark and sweep 算法在执行的时候，须要程序暂停！即 STW(stop the world)，STW 的过程中，CPU 不执行用户代码，全副用于垃圾回收，这个过程的影响很大，所以 STW 也是一些回收机制最大的难题和心愿优化的点。所以在执行第三步的这段时间，程序会暂定进行任何工作，卡在那期待回收执行结束。

mark and sweep 的毛病：

1. STW，stop the world；让程序暂停，程序呈现卡顿 (重要)；
2. 标记须要扫描整个 heap（堆）；
3. 革除数据会产生 heap 碎片。

V1.3 STW 步骤提前

STW 的步骤提前了一步，因为在 Sweep 革除的时候，能够不须要 STW 进行，因为这些对象曾经是不可达对象了，不会呈现回收写抵触等问题。

然而无论怎么优化，Go V1.3 都面临这个一个重要问题，就是mark-and-sweep 算法会暂停整个程序。

V1.5 三色标记法

1. 每次新创建的对象，默认的色彩都是标记为“红色”
2. 每次 GC 回收开始, 会从根节点开始遍历所有对象，把遍历到的对象从红色汇合放入“灰色”汇合
3. 遍历灰色汇合，将灰色对象援用的对象从红色汇合放入灰色汇合，之后将此灰色对象放入彩色汇合
4. 反复 第三步, 直到灰色中无任何对象
5. 回收所有的红色标记表的对象. 也就是回收垃圾

没有 STW 的三色标记法

在还没有扫描到对象 2 的时候，如果对象 4 指向对象 3，同时对象 2 指针 p 移除，会导致对象 3 被误杀。

对象失落

• 条件 1: 一个红色对象被彩色对象援用(红色被挂在彩色下)
• 条件 2: 灰色对象与它之间的可达关系的红色对象受到毁坏(灰色同时丢了该红色)

当以上两个条件同时满足时，就会呈现对象失落景象!

强弱三色不变式

GC 回收器满足上面两种状况之一时，即可保对象不失落。这两种形式就是“强三色不变式”和“弱三色不变式”。

• 强三色不变式：不存在彩色对象援用到红色对象的指针。
• 弱三色不变式：所有被彩色对象援用的红色对象都处于灰色爱护状态。

插入屏障

具体操作：在 A 对象援用 B 对象的时候，B 对象被标记为灰色。(将 B 挂在 A 上游，B 必须被标记为灰色)

满足 ： 强三色不变式. (不存在彩色对象援用红色对象的状况了，因为红色会强制变成灰色)

插入屏障机制，在 栈空间的对象操作中不应用，仅仅应用在堆空间对象的操作中。

解决流程：

1. 程序创立，对象全副标记为红色，放入红色汇合中
2. 遍历 Root Set(只遍历一次)，失去灰色节点
3. 遍历灰色标记表，将可达对象标记为灰色，遍历后的灰色对象标记为彩色
4. 此时对象 4 增加对象 8（堆区：触发插入屏障），对象 1 增加对象 9（不触发）
5. 因为插入写屏障，对象 8 变为灰色，对象 9 仍为红色

6. 持续循环上述流程进行三色标记，直到没有灰色节点
7. 在筹备回收红色节点前，从新遍历扫描一次栈空间，此时加 STW 暂停爱护栈，避免外界烦扰（有新的红色被彩色增加）
8. 在 STW 中，将占中的对象进行三色标记，直到没有灰色节点
9. 进行 STW
10. 革除红色

有余：完结时须要 STW 来从新扫描，大概须要 10~100ms

删除屏障

具体操作: 被删除的对象，如果本身为灰色或者红色，那么被标记为灰色。

满足 : 弱三色不变式. (爱护灰色对象到红色对象的门路不会断)

解决流程：

1. 程序创立，对象全副标记为红色，放入红色汇合中
2. 遍历 Root Set(只遍历一次)，失去灰色节点
3. 对象 1 删除对象 5，触发删除写屏障，对象 5 标记为灰色
4. 循环进行三色标记，直到没有灰色节点
5. 革除红色

毛病：回收精度低，一个对象即便被删除了最初一个指向它的指针也仍旧能够活过这一轮，在下一轮 GC 中被清理掉。

V1.8 三色标记法 + 混合写屏障

混合写屏障

具体操作:

1、GC 开始将栈上的对象全副扫描并标记为彩色(之后不再进行第二次反复扫描，无需 STW)，

2、GC 期间，任何在栈上创立的新对象，均为彩色。

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

4、被增加的对象标记为灰色。

满足 : 变形的 弱三色不变式

典型场景

场景一：对象被一个堆对象删除援用，成为栈对象的上游

// 前提：堆对象 4 -> 对象 7 = 对象 7；// 对象 7 被 对象 4 援用
栈对象 1 -> 对象 7 = 堆对象 7；// 将堆对象 7 挂在 栈对象 1 上游
堆对象 4 -> 对象 7 = null；// 对象 4 删除援用 对象 7 

场景二：对象被一个栈对象删除援用，成为另一个栈对象的上游

new 栈对象 9；对象 8 -> 对象 3 = 对象 3；// 将栈对象 3 挂在 栈对象 9 上游
对象 2 -> 对象 3 = null；// 对象 2 删除援用 对象 3 

场景三：对象被一个堆对象删除援用，成为另一个堆对象的上游

堆对象 10-> 对象 7 = 堆对象 7；// 将堆对象 7 挂在 堆对象 10 上游
堆对象 4 -> 对象 7 = null；// 对象 4 删除援用 对象 7 

场景四：对象从一个栈对象删除援用，成为另一个堆对象的上游

堆对象 10-> 对象 7 = 堆对象 7；// 将堆对象 7 挂在 堆对象 10 上游
堆对象 4 -> 对象 7 = null；// 对象 4 删除援用 对象 7 

Golang 中的混合写屏障满足 弱三色不变式，联合了删除写屏障和插入写屏障的长处，只须要在开始时并发扫描各个 goroutine 的栈，使其变黑并始终放弃，这个过程不须要 STW，而标记完结后，因为栈在扫描后始终是彩色的，也无需再进行 re-scan 操作了，缩小了 STW 的工夫。

总结

• GoV1.3- 一般标记革除法，整体过程须要启动 STW，效率极低。
• GoV1.5- 三色标记法，堆空间启动写屏障，栈空间不启动，全副扫描之后，须要从新扫描一次栈(须要 STW)，效率一般
• GoV1.8- 三色标记法，混合写屏障机制，栈空间不启动，堆空间启动。整个过程简直不须要 STW，效率较高。

Reference

Golang 涵养之路