垃圾回收

垃圾回收（Garbage Collection，简称GC）是编程语言中提供的自动的内存管理机制，自动释放不需要的对象，让出存储器资源，无需程序员手动执行。

版本1.3之前标记-清除（mark and sweep）算法

步骤：

• 标记（Mark phase）
• 清除（Sweep phase）

总体思想就是：暂停程序业务逻辑，找出不可达的对象，然后做上标记。第二步，回收标记好的对象。

1. mark and sweep算法在执行的时候，需要程序暂停！即STW(stop the world)。也就是说，这段时间程序会卡在哪儿。
   

2. 开始标记，程序找出它所有可达的对象，并做上标记。如下图所示：
   

3. 标记完了之后，然后开始清除未标记的对象，结果如下：
   

4. 停止暂停，让程序继续跑。然后循环重复这个过程，直到process程序生命周期结束。

标记-清除（mark and sweep）的缺点

• STW，stop the world；让程序暂停，程序出现卡顿（重要问题）
• 标记需要扫描整个heap
• 清除数据会产生heap碎片

版本1.3之前就是以上来实施的，流程为

版本1.3做了简单的优化，将STW提前，减少STW暂停的时间范围，如下所示

版本1.5的三色并发标记法

三色标记法 实际上就是通过三个阶段的标记来确定清楚的对象都有哪些。

具体步骤：

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

Go是如何解决标记-清除算法中的卡顿STW问题的呢？

没有STW的三色标记法

如果三色标记法，标记法过程中不使用STW将会发生什么呢？

1. 已经标记为灰色的对象2，有指针p指向白色的对象3
   
2. 在还没有扫描到对象2，已经标注为黑色的对象4，创建指针q，指向对象3
   
3. 于此同时对象2将指针p移除，对象3就被挂在了已经扫描完成的黑色的对象4下。
   
4. 正常执行算法逻辑，对象2，7标记为黑色，而对象3因为对象4已经不会再扫描，而等待被回收清除。
   
5. 对象3，这个被正常引用的对象，被无辜的清除掉了。

可以看出，有两个问题，在三色标记法是不希望被发生的

• 条件1：一个白色对象被黑色对象引用（白色被挂在黑色下）
• 条件2：灰色对象与它之间的可达关系的白色对象遭到破坏（灰色同时丢了该白色）

以上两个条件同时满足时，就会出现对象丢失现象。

为了防止这种现象的发生，最简单的方式就是STW，直接禁止掉其他用户程序对对象引用关系的干扰，但是STW的过程有明显的资源浪费，对所有的用户程序都有很大影响，如何能在保证对象不丢失的情况下合理的尽可能的提高GC效率，减少STW时间呢？

​ 答案就是, 那么我们只要使用一个机制,来破坏上面的两个条件就可以了.

屏障机制

破坏上面两个条件引出两种方式：

强-弱 三色不等式

• 强三色不等式

不存在黑色对象引用到白色对象的指针。

• 弱三色不等式

所有被黑色对象引用的白色对象都处于灰色保护状态

为了遵循上述的两个方式Go团队初步得到了如下具体的两种屏障方式“插入屏障”，“删除屏障”。

插入屏障

具体操作：在A对象应用B对象的时候，B对象被标记为灰色。（将B挂在A下游，B必须被标记为灰色）
满足：强三色不等式(不存在黑色对象引用白色对象的情况了，因为白色会强制变成灰色)

伪码如下:

添加下游对象(当前下游对象slot, 新下游对象ptr) {   
  //1
  标记灰色(新下游对象ptr)   

  //2
  当前下游对象slot = 新下游对象ptr                    
}

场景：

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

​这段伪码逻辑就是写屏障,我们知道,黑色对象的内存槽有两种位置, 栈和堆.栈空间的特点是容量小,但是要求相应速度快,因为函数调用弹出频繁使用, 所以“插入屏障”机制,在栈空间的对象操作中不使用,而仅仅使用在堆空间对象的操作中。

删除屏障

具体操作：被删除的对象，如果自身为灰色或白色，那么标记为灰色。
满足：弱三色不等式（保护灰色对象到白色对象的路径不会断）

伪代码：

添加下游对象(当前下游对象slot， 新下游对象ptr) {
  //1
  if (当前下游对象slot是灰色 || 当前下游对象slot是白色) {
          标记灰色(当前下游对象slot)     //slot为被删除对象， 标记为灰色
  }

  //2
  当前下游对象slot = 新下游对象ptr
}

场景：

A.添加下游对象(B, nil) //A对象，删除B对象的引用。 B被A删除，被标记为灰(如果B之前为白)
A.添加下游对象(B, C) //A对象，更换下游B变成C。 B被A删除，被标记为灰(如果B之前为白)

这种方式的回收精度低，一个对象即使被删除了最后一个指向它的指针也依旧可以活过这一轮，在下一轮GC中被清理掉。

版本1.8的混合写屏障（hybrid write barrier）机制

插入写屏障和删除写屏障的短板：

• 插入写屏障：结束时需要STW来重新扫描栈，标记栈上引用的白色对象的存活
• 删除写屏障：回收精度低，GC开始时STW扫描堆栈来记录初始快照，这个过程会保护开始时刻的所有存活对象。

1.8版本引入了混合写屏障机制，避免了对栈re-scan的过程，极大的减少了STW的时间。结合了两者的优点。

混合写屏障机制

具体操作：
1、GC开始将栈上可达的对象全部扫描并标记为黑色（之后不再进行第二次重复扫描，无需STW）
2、GC期间，任何在栈上创建的新对象，均为黑色
3、被删除的对象标记为灰色
4、被添加的对象标记为灰色

注意：3、4点是触发写屏障，而触发写屏障只发生在堆结构中。

伪代码：

添加下游对象(当前下游对象slot, 新下游对象ptr) {
      //1 
        标记灰色(当前下游对象slot)    //只要当前下游对象被移走，就标记灰色

      //2 
      标记灰色(新下游对象ptr)

      //3
      当前下游对象slot = 新下游对象ptr
}

文章参考：刘丹冰–《Go修养之路》