Go v1.3 标记—清楚(mark and sweep)方法
-
主要流程
- 暂停程序业务逻辑，找出可达对象和不可达对象；
- 开始标记，程序找出它所有可达的对象，并做上标记；
- 标记完了之后，然后开始清除未标记的对象；
- 停止暂停，让程序继续跑，然后循环重复这个过程，直到process程序声明周期结束；
-
标记清除整体逻辑
-
标记清除的缺点
- STW,stop the world ;让程序暂停，程序出现卡顿
- 标记需要扫描整个heap；
- 清楚数据会产生heap碎片；【如果地址不连续】
其中最大的问题还是因为STW太费时间，早期的探索是通过将sweep阶段移到STW之外，这确实是一种改善的方法，但是始终难以改变这种低级效能。所以需要尝试采用新的标记模式来代替清楚标记法(mark-sweep)—三色标记法。
Go V1.5 三色标记法
- 主要流程
主要的流程如下【广度优先搜索】：
- 只要是新创建的对象，默认的颜色都是标记为"白色"；
- 每次GC回收开始，然后从根节点开始遍历所有对象，把遍历到的对象从白色集合中放入"灰色"集合中；
- 遍历灰色集合，将灰色对象引用的对象从白色集合放入灰色集合，之后将原先的灰色对象放入黑色集合当中；
- 重复第三步，直到灰色中无任何对象；
- 回收所有白色标记表的对象，也就是回收垃圾；
三色标记过程无STW的问题
- 如果三色标记中不启动STW会怎么样？
简单来说，就是没有STW，那么如果对象2对对象3依赖的指针取消了，而对象四新建了一个对对象3的依赖，那么按照之前的原则，每次都是对灰色节点进行遍历，所以这个时候，无法将对象3标记为灰色，故会造成错误。
-
三色标记最不希望发生的事情
- 条件1:一个白色对象被黑色对象引用（白色挂在黑色下）
- 条件2:灰色对象与它之间的可达关系的白色对象遭到破坏(灰色同时丢了该白色)
以上两个条件同时满足就会发生对象的丢失。因此有必要使用STW，但是应当尽可能的提高GC效率，减少STW时间。
强弱三色不变式
-
强三色不变式
强制性的不允许黑色对象引用白色对象。
-
弱三色不变式
黑色对象可以引用白色对象，但是白色对象存在其他灰色对象对它的引用，或者可达它的链路上游存在灰色对象。
在三色标记中如果满足强/弱之一，即可保证对象不丢失。为了使用上面这种思想，引入了屏障。
插入写屏障
// 伪码
添加下游对象(当前下游对象slot,新下游对象ptr){// 1标记灰色(新下游对象)// 2当前下游对象slot = 新下游对象ptr
}
也就是说在堆上的对象才会启用插入屏障。在准备回收白色前，重新遍历扫描一边栈空间，此时加STW暂停保护栈，防止有外界干扰(有新的白色被黑色添加)
插入写屏障的不足就是在结束时需要用STW来重新扫描栈，大约需要10ms~100ms
// 伪代码
添加下游对象(当前下游对象slot,新下游对象ptr) 「
// 1
if (当前下游对象slot是灰色 || 当前下游对象slot是白色) {标记灰色(新下游对象ptr)
}
// 2
当前下游对象slot = 新下游对象ptr
Go V1.8的三色标记法+混合写屏障机制
//伪码
添加下游对象(当前下游对象slot,新下游对象ptr){// 1标记灰色(当前下游对象slot)// 2标记灰色(新下游对象)// 3当前下游对象slot = 新下游对象ptr
}
混合写屏障场景
场景1:对象被一个堆对象删除引用，成为栈对象的下游
// 伪代码
// 前提：堆对象->对象7 = 对象7；// 对象7 被 对象4 引用
栈对象1->对象7 = 堆对象7;// 将堆对象7挂载在 栈对象 下游
堆对象4->对象7 = null；//对象4 删除引用 对象7
对象4删除了对象7的引用关系，因为对象4是堆区，所以触发删除屏障，标记被删除的对象7为灰。【注意这个地方不能认为栈里面元素添加一个就直接标记为黑色，因为栈的区域不启用屏障】
场景2:对象被一个栈对象删除引用，成为另一个新建栈对象的下游
(1)、新创建一个对象9在栈上(因为是混合写屏障模式中，GC过程汇总任何在栈中新创建的对象均标记为黑色)
(2)、对象9添加下游引用栈堆对象3(直接添加，栈不启动屏障，无屏障效果)
(3)、对象2删除对象3的引用关系(直接删除，栈不启动写屏障，无屏障效果)
场景3:对象被一个堆对象删除引用，成为另一个堆对象的下游
//伪代码
堆对象10 -> 对象7 = 堆对象7; // 将堆对象7 挂在 堆对象10 下游
堆对象4 -> 对象7 = null; // 对象4 删除引用 对象7
(1)、堆对象10已经扫描标记为黑(黑色情况比较特殊，其他颜色暂不考虑)。
(2)、堆对象10添加下游引用堆对象7，触发屏障机制，被添加的对象标记为灰色，对象7变成灰色（对象6被保护）。
(3)、堆对象删除下游引用堆对象7，触发屏障机制，被删除的对象标记为灰色，对象7被标记为灰色。
场景4:对象从一个栈对象删除引用，成为另一个堆对象的下游
// 伪代码
栈对象1 -> 对象2 = null; // 对象1 删除引用 对象2
栈对象4 -> 对象2 = 栈对象2 // 对象4 添加栈对象2
堆对象 -> 对象7 = null; // 对象4 删除一个对象7
(1)、栈对象1删除对堆对象2的引用。(栈空间不触发写屏障)。
(2)、堆对象将之前引用对象7的关系，转移至对象2（对象4删除对象7的引用关系）。
(3)、对象4在删除的时候，触发写屏障，标记被删除对象7为灰色。保护对象7及其下游节点。
总结
Go V1.3 使用普通标记清除法，整体过程需要STW，效率极其低
Go V1.5 三色标记法，堆空间启动写屏障，栈空间不启动，全部扫描一次后，需要重新扫描一次栈（需要STW），效率极其普通
Go V1.8 三色标记法+混合写屏障机制，堆空间启动，栈空间不启动，整体过程几乎不需要STW，效率较高