标记-革除(mark and sweep)算法

这个是Go 1.3之前应用的垃圾回收算法。

咱们能够看下这个算法的流程：

  1. 暂停程序业务逻辑, 从根节点开始遍历内存对象，分类出可达和不可达的对象，而后做上标记。
  2. 开始标记，程序找出它所有可达的对象，并做上标记。
  3. 标记完了之后，而后开始革除未标记的对象。
  4. 进行暂停，让程序持续跑。而后循环反复这个过程，直到process程序生命周期完结。

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

三色并发标记法

Go语言从版本1.5开始引入了三色并发标记法，这是一种用于垃圾回收的技术。三色并发标记法的指标是尽可能减少垃圾回收对程序的进展工夫。上面是三色并发标记法的具体步骤：

咱们看下之前的三色并发标记法，假如有三个色彩的桶，红色，灰色，彩色。

  1. 所有的对象一开创立的时候都是放在白桶里。
  2. 从程序的根节点对象开始遍历根节点所援用的所有对象，遍历到的对象放进灰桶外面
  3. 遍历灰桶外面的所有对象，遍历到的新对象放进灰桶外面，同时将以后对象丢进黑桶里
  4. 反复3，始终到所有的对象都遍历完了。
  5. 这时候只有白桶和黑桶里有对象了，革除白桶外面残余的对象。

关键问题就是步骤3，如果遍历步骤3的时候不启动STW暂停程序，会有并发问题。

假如第N次遍历，此时A对象是灰色，B对象是彩色。A援用了C对象，此时C还是红色的。
因为程序是没有暂停的，程序执行了操作，A不再援用C对象，然而B又援用了C对象。
那么到了第N+1次遍历，就会呈现这样的状况，B援用了C，因为A不再援用C，C将永远留在白桶里，C最终要被革除掉。问题呈现了，B援用了C，然而C还是被革除了。

强三色不变性 — 彩色对象不会指向红色对象，只会指向灰色对象或者彩色对象；
弱三色不变性 — 彩色对象指向的红色对象必须蕴含一条从灰色对象经由多个红色对象的可达门路
遵循上述两个不变性中的任意一个，咱们都能保障垃圾收集算法的正确性。

独自应用插入屏障

原理就是下面的强三色不变性，要解决这个问题能够引入插入屏障,插入屏障意思就是黑桶外面的对象援用白桶外面的对象，那么这个对象将被强制放进灰桶。
毛病：完结时须要STW来从新扫描栈，标记栈上援用的红色对象的存活；

独自应用删除屏障

原理就是下面的弱三色不变性，就是A不再援用C时，C强制放到进灰桶。
毛病：这种形式的回收精度低，一个对象即便被删除了最初一个指向它的指针也仍旧能够活过这一轮，在下一轮GC中被清理掉。

栈的特殊性

插入屏障和删除屏障都不会在栈上应用，go是并发运行的，大部分的操作都产生在栈上，数十万goroutine的栈都进行屏障爱护会有十分大的性能开销。

插入屏障中，会标记栈中的色彩，然而栈中对象援用新对象不会更改援用对象的色彩。这样当全副三色标记扫描之后,栈上有可能仍然存在红色对象被援用的状况，所以须要STW，从新扫描一次栈上的对象，这个就是Go1.5采纳的计划。

删除屏障中，

各个版本的计划

Go1.3

一般的标记革除法， 整体过程须要STW，效率极低

Go1.5

三⾊标记法，堆空间启动写屏障，栈空间不启动，全副扫描之后，须要从新扫描⼀次栈(须要STW)， 效率一般.

Go1.8

三⾊标记法，混合写屏障机制，栈空间不启动，堆空间启动，整体过程⼏乎不须要STW，效率较⾼

  1. GC开始将栈上的对象全副扫描并标记为⿊⾊(之后不再进⾏第⼆次反复扫描，⽆需STW)
  2. GC期间，任何在栈上创立的新对象，均为⿊⾊。
  3. 被删除的对象标记为灰⾊。
  4. 被增加的对象标记为灰⾊。