【go】三色标记-垃圾回收机制

垃圾回收原因 ：

垃圾回收是一种内存管理技术，它的主要目的是自动管理程序中的内存分配和释放，以减少内存泄漏和野指针等问题

赋值器与回收器：

赋值器（Mutator）是指程序中的执行部分，负责创建和操作对象。赋值器与垃圾回收器共同工作，赋值器负责创建和操作对象，而垃圾回收器则负责监视内存中的对象，标记不再使用的对象，然后释放它们所占用的内存空间。

垃圾回收基本过程 ：

1. 标记阶段：在这个阶段，垃圾回收器会遍历整个内存堆，标记所有仍然被引用的对象。通常，这个阶段会从根对象开始遍历，对于所有可达的对象，都会打上标记。

2. 清除阶段：在标记阶段结束之后，垃圾回收器会扫描整个内存堆，将所有未被标记的对象释放掉，以便后续的内存分配。这个阶段的操作通常是从堆的起始位置开始，对于每一个对象，都会检查它是否被标记，如果没有被标记，就将其释放掉。

3. 压缩阶段：在这个阶段，垃圾回收器会对内存堆进行整理，将所有存活的对象向一端移动，以便在后续的内存分配中可以更高效地利用内存空间。这个阶段通常只有在使用基于标记-整理（Mark-Compact）的垃圾回收算法时才会出现。

垃圾回收算法 ： 三色标记清扫

“三色标记清扫”（Tri-Color Mark and Sweep）的垃圾回收算法。该算法是一种基于标记-清除（Mark and Sweep）算法的改进版本，采用**三种不同的颜色（白色、灰色和黑色）**来表示对象的不同状态。

白色，灰色，黑色的含义：

• 白色对象（可能死亡）：未被回收器访问到的对象。在回收开始阶段，所有对象均为白色，当回收结束后，白色对象均不可达。
• 灰色对象（波面）：已被回收器访问到的对象，但回收器需要对其中的一个或多个指针进行扫描，因为他们可能还指向白色对象。
• 黑色对象（确定存活）：已被回收器访问到的对象，其中所有字段都已被扫描，黑色对象中任何一个指针都不可能直接指向白色对象。

基本过程：

1. 垃圾回收器首先将所有对象标记为白色，然后从根对象开始遍历程序中的所有对象，将可达对象标记为灰色。
2. 在遍历的过程中，如果发现某个对象的引用被清除或移动了，那么该对象被标记为白色。
3. 一旦所有可达对象都被标记为灰色，垃圾回收器将所有未被标记为灰色的对象标记为黑色，并释放所有标记为白色的对象的内存空间。

并行标记清理导致的问题 ：

用户态代码在回收过程中会并发的更新对象图，从而赋值器和回收器可能对对象图的结构产生不同的认知

垃圾回收的正确性保证

如何保证对象不缺失 ：

在三色标记过程中，对象如果要缺失，要同时满足以下两点：

1. 白色对象被黑色对象引用
2. 灰色对象与白色对象间的关系遭到破坏

所以GO语言引入两个原则， 弱三色不变式和强三色不变式

弱三色不变式

所有被黑色对象引用的白色对象，都有一条路径能够被灰色对象引用

强三色不变式

不存在黑色的子对象为白色

插入写屏障

又称增量更新屏障（incremental update）

思想：

插入屏障拦截将白色指针插入黑色对象的操作，标记其对应对象为灰色状态

缺点：

对栈上指针的写入添加写屏障的成本很高，所以Go选择仅对堆上的指针插入增加写屏障，这样就会出现在扫描结束后，栈上仍存在引用白色对象的情况，这时的栈是灰色的，不满足三色不变式，所以需要对栈进行重新扫描使其变黑，完成剩余对象的标记，这个过程需要STW

优点 ：

Dijkstra的插入写屏障在标记开始时无需STW，可直接开始，并发进行，但结束时需要STW来重新扫描栈

删除屏障

又称为基于起始快照的屏障（snapshot-at-the-beginning）

基本思想：

当删除引用时，被删除的对象是白色，则被标记成灰色

缺点 ：

• 一个对象被删除后，虽然可能没有其他存活对象引用它，但是仍然在本轮GC中存活，会降低回收精度，增加下轮GC成本
• 开始时STW扫描堆栈来记录初始快照

优点 ：

Yuasa的删除写屏障则需要在GC开始时STW扫描堆栈来记录初始快照，这个过程会保护开始时刻的所有存活对象，但结束时无需STW

混合屏障

Go1.8版本引入的混合写屏障结合了Yuasa的删除写屏障和Dijkstra的插入写屏障，结合了两者的优点

• GC刚开始的时候，将栈上所有可达对象全部标记为黑色
• GC期间，任何在栈上创建的对象，均为黑色
• 堆上被删除和新增的对象标记为灰色

优点：

避免了对栈re-scan的过程，极大的减少了STW的时间