Garbage Collection

GC就是垃圾回收机制，对于高级语言来说是必须的，因为需要高度关注业务，而不是把精力放在管理垃圾上面

Gc 自动释放、垃圾回收、三色标记法、内存关机、STW（stop the world）

STW会暂停全部的线程，然后进行垃圾回收，这个会严重影响性能，发部分机器都在想方设法取消STW机制，虽然难以避免的会用到

Go之前的标记清除法

标记清除方法

假设是这样的场景

那么程序和对象的可达对象由1-2-3，4-7

（1）stw暂停所有的逻辑

（2）对所有的对象做标记

5 6就会被回收，

这个时候stw就停止了

这种标记法的缺点：

• STW stop the world让程序暂停，程序出现卡顿:star:最明显的缺点
• 标记需要扫描整个heap
• 清除数据会产生很多heap碎片

Go v1.5 三色标记法

传统的清除会暂停所有的程序，会使程序卡顿，等等很多缺点，因此go开发了新的内存管理的方法

三色标记法会有三个颜色 白色，灰色，黑色

只往下走一层，会把根节点保存到灰色中

然后让那个灰色标记表中的对象往下走，看看能找到哪些节点，把这些找到的节点放到灰色标记表中，然后再把对象1和4标记为黑色

这是一次循环

最终的目标是把灰色的搞没，然后把白色的回收

所以要一直重复上面的步骤，知道灰色标记表中没有任何对象

最后收集所有的白色对象（垃圾）

:star: 动态逐层分隔

如果三色标记过程不启动STW

上面的过程如果开启stw是会很麻烦的

（1）已经标记为灰色的对象2，有指针p指向白色的对象3

（2）在还没有扫描到对象2，已经标记为黑色的对象4创建指针q，指向对象3

（3余与此同时，对象2将指针p移除，对象3就被挂在了已经扫描完成的黑色的对象4下）

（4）正常执行算法逻辑，对象2，3，标记为黑色，而对象3，因为对象4已经不回再扫描，而是等待被回收清除

三色标记最不希望发生的事

• 一个白色对象被黑色兑现所引用
• 灰色对象与白色对象之间的可达关系被破坏

:exclamation: 这两个条件同时满足时，就会发生对象丢失的现象

如果不想让此类事件发生，最简单的方式就是STW:sweat:

强弱三色不变式

谷歌开发了两种不变式子

强三色不变式

强制性的不允许黑色对象引用白色对象

破坏条件1:一个白色对象被黑色对象引用（白色被挂在黑色下）

弱三色不变式

黑色对象可以引用白色对象，白色对象存在其他灰色对象的引用，或者可达它的链路上游存在灰色对象

破坏了条件2：灰色对象与它之间的可达关系的白色对象遭到破坏（灰色同时丢了该白色）

在三色标记中如果满足强/弱之一，即可保证对象不丢失，

通过屏障机制可以来完成强弱三色不变式

插写入屏障

屏障：额外的判断机制

类似于Hook钩子函数，回调，handler

屏障机制：

• 插入屏障——当一个对象被引用时，触发的机制
• 删除屏障——对象被删除时，触发的机制

插入屏障

具体操作：在A对象引用B对象的时候，B对象被标记为灰色（将B挂在A下游，B必须被标记为灰色）

满足：强三色不变式（不存在灰色对象引用白色对象的情况了，因为白色会强制编程灰色）

伪代码

添加下游对象（当前下游对象，新下游对象ptr）{
  //1
  标记灰色（新下游对象）
  //2
  当前下游对象slot=新下游对象
}

//场景 A.添加下游对象（nil，B） //A 之前没有下游，新添加一个下游对象B，B被标记为灰色 A.添加下游对象（C，B） //A将下游对象C更换为B，B被标记为灰色

插入屏障有一个弊端

会影响效率

栈和堆的区别

堆内存比较大，保存了对象。栈空间比较小，保存了函数，和运行时的东西对性能要求比较高

插入屏障为了不影响速度，不在栈上使用，所以栈不启用插入屏障，堆上会启用插入屏障

对象8就会被变成灰色

循环上述流程直到没有灰色节点

在准备回收白色之前，重新扫描一次栈空间（把栈上的黑色的全部置白，STW暂停保护栈区，然后stw开始清除），此时STW暂停保护栈，防止外界干扰（有新的白色被黑色添加）

插入写屏障的不足

结束时需要STW来重新扫描栈，大约需要10～100ms

删除写屏障

具体操作：被删除的对象如果自身为灰色或者白色，那么就会被标记为灰色

满足：弱三色不变式（保护灰色对象到白色对象的路径不回断）

// 为代码
添加下游对象（当前下游对象slot，新下游对象ptr）{
  // 1
  if(当前下游对象slot是灰色｜｜当前下游对象slot是白色){
    标记灰色（当前下游对象slot）
  }
  // 2
  当前下游对象slot = 新下游对象ptr
}

A.添加下游对象（B，nil）

A.添加下游对象（B,C）

例子：

初始状态

先遍历第一层

这个时候触发一个操作

触发删除写屏障

删除写屏障的不足

回收精度低：

​ 一个对象即使被删除了最后一个指向它的指针也依旧可以活过这一轮，在下一轮GC中被清理掉

满足弱三色不变式

Go v1.8混合写屏障机制

插入写屏障的不足：结束时需要STW重新来扫描栈，大约需要10～100ms

删除写屏障的不足：回收精度低，一个对象即使被删除自后自后一个指向它的指针也依旧可以活过下一轮，在下一轮GC中被清理掉

操作流程

1、GC开始将栈上的对象全部扫描并标记为黑色（之后不再进行第二次扫描，无需STW）

2、GC期间，任何在栈上创建的新对象，均为黑色

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

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

满足 变形的弱三色不变式（结合了插入、删除、写屏障的优点）

// 伪码
添加下游对象（当前下游对象slot，新下游对象ptr）{
  // 1
  标记灰色（当前下游对象slot）
  // 2
  标记灰色（新下游对象ptr）
  // 3
  当前下游对象slot = 新下游对象ptr
}

过程

（1）GC刚开始，默认都为白色

（2）将栈里面的全部变为黑

混合写屏障的使用场景

场景1

对象被一个堆对象删除引用，成为栈对象的下游

// 伪码
// 前提： 堆对象4>对象7 = 对象7；	//对象7 被对象4 引用（对象4指向对象7）
栈对象1->对象7 = 堆对象7； //将堆对象7 挂在 栈对象1 下游
堆对象4->对象7 = null；		//堆对象4 删除引用 对象7

1、从栈的根结点出发，把相关联的对象都标记为黑色，这一过程之后栈不再受到屏障保护，堆启动混合写流程

扫描堆中的对象

场景2 对象被一个栈对象删除引用，成为另一个栈对象的下游

// 伪码
new 栈对象9;
对象9->对象3->对象3;	//将栈对象3 挂在 栈对象9 下游
对象2->对象3 = null； //对象2 删除引用对象3

回收和程序执行的过程中是并行的

混合写屏障的目的就是为了不出发STW

场景3 对象被一个堆对象删除引用，成为另一个堆对象的下游

// 伪码
堆对象10->对象7 = 堆对象;	//将堆对象7 挂在 堆对象10 下游
堆对象4->对象7 = null;		// 对象4 删除引用 对象7


一开始就会把栈上的对象变成黑色

接下来再去扫描对象4和对象7

对象6和7可达，对象4是根对象，因此删除对象11，对象5，对象8

场景4 对象从一个栈对象删除引用，成为另一个堆对象的下游

// 伪码
栈对象1 -> 对象2 = null;		//对象1 删除引用 对象2
堆对象4 -> 对象2 = 栈对象2;	//对象4 添加 下游 栈对象2
堆对象4 -> 对象7 = null;		//对象4 删除引用 对象7

栈区不启用屏障，所以直接删

对象4是在堆里面

写屏障，一个对象如果被删除，那么这个对象会被标记为黑色