由于篇幅问题，本篇博客一共分为3小篇 一、什么是 GC ? 
Garbage CollectionC/C++oc/swift/java/python/php/golangvirtual machineruntime

Golang GC 的发展史

主要版本变化：

1.5 版本以及以后版本的GC 主要分为四个阶段，其中标记和清理都是并发执行的，但是标记阶段的前后需要使用STW来做GC的准备工作和栈的rescan（这也是1.8的优化点）。

1.8 版本引入混合屏障，最小化第一次STW，写入屏障和删除屏障各有优缺点，Dijkstra写入写屏障在标记开始时无需STW，可直接开始，并发进行，但结束时需要STW来重新扫描栈，标记栈上引用的白色对象的存活；Yuasa的删除写屏障则需要在GC开始时STW扫描堆栈来记录初始快照，这个过程会保护开始时刻的所有存活对象，但结束时无需STW。Go1.8版本引入的混合写屏障结合了Yuasa的删除写屏障和Dijkstra的写入写屏障，结合了两者的优点。

二、常见的 GC 算法

1. 引用计数法

Objective-CSwift
  • 优点：简单直接，回收速度快
  • 缺点：需要额外的空间存放计数，无法处理循环引用的情况；

2. 标记清除法

标记出所有不需要回收的对象，在标记完成后统一回收掉所有未被标记的对象。

  • 优点：简单直接，速度快，适合可回收对象不多的场景
  • 缺点：会造成不连续的内存空间（内存碎片），导致有大的对象创建的时候，明明内存中总内存是够的，但是空间不是连续的造成对象无法分配；

3. 复制法

复制法将内存分为大小相同的两块，每次使用其中的一块，当这一块的内存使用完后，将还存活的对象复制到另一块去，然后再把使用的空间一次清理掉。

  • 优点：解决了内存碎片的问题，每次清除针对的都是整块内存，但是因为移动对象需要耗费时间，效率低于标记清除法；
  • 缺点：有部分内存总是利用不到，资源浪费，移动存活对象比较耗时，并且如果存活对象较多的时候，需要担保机制确保复制区有足够的空间可完成复制；

4. 标记整理

标记过程同标记清除法，结束后将存活对象压缩至一端，然后清除边界外的内容。

  • 优点：解决了内存碎片的问题，也不像标记复制法那样需要担保机制，存活对象较多的场景也使适用；
  • 缺点：性能低，因为在移动对象的时候不仅需要移动对象还要维护对象的引用地址，可能需要对内存经过几次扫描才能完成；

5. 分代式

将对象根据存活时间的长短进行分类，存活时间小于某个值的为年轻代，存活时间大于某个值的为老年代，永远不会参与回收的对象为永久代。并根据分代假设（如果一个对象存活时间不长则倾向于被回收，如果一个对象已经存活很长时间则倾向于存活更长时间）对对象进行回收。

1. 三色标记法的原理

三色标记法将对象分为三类，并用不同的颜色相称：

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

标记过程如下：

  • 第一步：起初所有的对象都是白色的；
  • 第二步：从根对象出发扫描所有可达对象，标记为灰色，放入待处理队列；
  • 第三步：从待处理队列中取出灰色对象，将其引用的对象标记为灰色并放入待处理队列中，自身标记为黑色；
  • 重复第三步，直到待处理队列为空，此时白色对象即为不可达的“垃圾”，回收白色对象；

根对象在垃圾回收的术语中又叫做根集合，它是垃圾回收器在标记过程时最先检查的对象，包括：

  1. 全局变量：程序在编译期就能确定的那些存在于程序整个生命周期的变量。
  2. 执行栈：每个 goroutine 都包含自己的执行栈，这些执行栈上包含栈上的变量及指向分配的堆内存区块的指针。
  3. 寄存器：寄存器的值可能表示一个指针，参与计算的这些指针可能指向某些赋值器分配的堆内存区块。

2. 屏障机制

2.1 STW

Start/Stop The WorldStop The WorldStart The WorldSTW

2.2 No STW 存在的问题

假设下面的场景，已经被标记为灰色的对象2，未被标记的对象3被对象2用指针p引用；此时已经被标记为黑色的对象4创建指针q 指向未被标记的对象3，同时对象2将指针p移除；对象4已经被标记为黑色，对象3未被引用，对象2删除与对象3的引用，导致最后对象3被误清除；

  • 垃圾回收的原则是不应出现对象的丢失，也不应错误的回收还不需要回收的对象。如果同时满足下面两个条件会破坏回收器的正确性：

    • 条件 1: 赋值器修改对象图，导致某一黑色对象引用白色对象；（通俗的说就是A突然持有了B的指针，而B在并发标记的过程中已经被判定为白色对象要被清理掉的）
    • 条件 2: 从灰色对象出发，到达白色对象且未经访问过的路径被赋值器破坏；（通俗的说就是A持有B的指针，这个持有关系被释放）

  • 只要能够避免其中任何一个条件，则不会出现对象丢失的情况，因为：

    • 如果“条件 1”被避免，则所有白色对象均被灰色对象引用，没有白色对象会被遗漏；
    • 如果“条件 2”被避免，即便白色对象的指针被写入到黑色对象中，但从灰色对象出发，总存在一条没有访问过的路径，从而找到到达白色对象的路径，白色对象最终不会被遗漏。

可能的解决方法： 整个过程STW，浪费资源，且对用户程序影响较大，由此引入了屏障机制；

2.3 屏障机制

把回收器视为对象，把赋值器视为影响回收器这一对象的实际行为（即影响 GC 周期的长短），从而引入赋值器的颜色：

  • 黑色赋值器：已经由回收器扫描过，不会再次对其进行扫描。
  • 灰色赋值器：尚未被回收器扫描过或尽管已经扫描过，但仍需要重新扫描。

2.3.1 插入屏障（Dijkstra）- 灰色赋值器

写入前，对指针所要指向的对象进行着色，伪代码如下

// 灰色赋值器 Dijkstra 插入屏障
func DijkstraWritePointer(slot *unsafe.Pointer, ptr unsafe.Pointer) {
    shade(ptr) //先将新下游对象 ptr 标记为灰色
    *slot = ptr
}

//说明：
添加下游对象(当前下游对象slot, 新下游对象ptr) {   
  //step 1
  标记灰色(新下游对象ptr)   
  
  //step 2
  当前下游对象slot = 新下游对象ptr                    
}

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

避免条件1（ 赋值器修改对象图，导致某一黑色对象引用白色对象；）因为在对象A 引用对象B 的时候，B 对象被标记为灰色

Dijkstra 插入屏障的好处在于可以立刻开始并发标记。但存在两个缺点：

  • 由于 Dijkstra 插入屏障的“保守”，在一次回收过程中可能会残留一部分对象没有回收成功，只有在下一个回收过程中才会被回收；
  • 在标记阶段中，每次进行指针赋值操作时，都需要引入写屏障，这无疑会增加大量性能开销；为了避免造成性能问题，Go 团队在最终实现时，没有为所有栈上的指针写操作，启用写屏障，而是当发生栈上的写操作时，将栈标记为灰色，但此举产生了灰色赋值器，将会需要标记终止阶段 STW 时对这些栈进行重新扫描。