首页 计算机科学 GO

# go gc

GoV1.3- 普通标记清除法，整体过程需要启动 STW，效率极低。

GoV1.5- 三色标记法， 堆空间启动写屏障，栈空间不启动，全部扫描之后，需要重新扫描一次栈 (需要 STW)，效率普通

GoV1.8 - 三色标记法，混合写屏障机制， 栈空间不启动，堆空间启动。整个过程几乎不需要 STW，效率较高。

# 标记清除

第一步，暂停程序业务逻辑，分类出可达和不可达的对象，然后做上标记。

第二步，开始标记，程序找出它所有可达的对象，并做上标记。

第三步，标记完了之后，然后开始清除未标记的对象。

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

mark and sweep 算法在执行的时候，需要程序暂停！即 STW(stop the world) ，STW 的过程中，CPU 不执行用户代码，全部用于垃圾回收，这个过程的影响很大，所以 STW 也是一些回收机制最大的难题和希望优化的点。所以在执行第三步的这段时间，程序会暂定停止任何工作，卡在那等待回收执行完毕。

标记清除问题

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

# 三色标记法

Golang 中的垃圾回收主要应用三色标记法，GC 过程和其他用户 goroutine 可并发运行，但需要一定时间的 STW (stop the world)，所谓三色标记法实际上就是通过三个阶段的标记来确定清除的对象都有哪些。

第一步，每次新创建的对象，默认的颜色都是标记为 “白色”，如图所示。

img

第二步，每次 GC 回收开始，会从根节点开始遍历所有对象，经过一次遍历，把遍历到的对象从白色集合放入 “灰色” 集合如图所示。

img

第三步，遍历灰色集合，将灰色对象引用的对象从白色集合放入灰色集合，之后将此灰色对象放入黑色集合，如图所示。

img

第四步，重复第三步，直到灰色中无任何对象，如图所示。
img

51-GC9.jpeg

第五步：回收所有的白色标记表的对象。也就是回收垃圾，如图所示。

img

剩下的就是全部依赖的黑色对象。

以上便是 三色并发标记法 ，不难看出，不过这种三色标记法仍然需要 STW，才能保证 GC 过程中的数据安全。

如果没有 STW ，会发生以下事情

  1. 一个白色对象被黑色对象引用
  2. 灰色对象与它之间的可达关系的白色对象遭到破坏

当两个事件都发生了之后，就会造成不是垃圾的对象被回收了。

# 屏障机制

# 强三色不变式

强制性的不允许黑色对象引用白色对象，这样就不会出现有白色对象被误删的情况。

img

# 弱三色不变式

黑色对象可以引用白色对象，但是这个白色对象的链路上游存在灰色对象。

img

# 插入屏障

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

满足: 强三色不变式. (不存在黑色对象引用白色对象的情况了， 因为白色会强制变成灰色)

func 添加下游对象(当前下游对象slot, 新下游对象ptr) {   
  //1
  标记灰色(新下游对象ptr)   
  
  //2
  当前下游对象slot = 新下游对象ptr                   
}
// 场景
A.添加下游对象(nil, B)   //A 之前没有下游， 新添加一个下游对象 B， B 被标记为灰色
A.添加下游对象(C, B)     //A 将下游对象 C 更换为 B，  B 被标记为灰色
“插入屏障” 机制，在栈空间的对象操作中不使用。而仅仅使用在堆空间对象的操作中。栈的操作比较频繁，如果开启栈的插入屏障对系统的性能损耗比较高。
模拟整个一个详细的过程：
img
img
img
img
img
img
如果栈不添加插入屏障，当全部三色标记扫描之后，栈上有可能依然存在白色对象被引用的情况 (如上图的对象 9). 所以要对栈重新进行三色标记扫描，但这次为了对象不丢失，要对本次标记扫描启动 STW 暂停。直到栈空间的三色标记结束.
img
img
img
最后将栈和堆空间 扫描剩余的全部 白色节点清除。这次 STW 大约的时间在 10~100ms 间.
img
# 删除屏障
具体操作：被删除的对象，如果自身为灰色或者白色，那么被标记为灰色。
满足: 弱三色不变式. (保护灰色对象到白色对象的路径不会断)
伪代码：
func 添加下游对象(当前下游对象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 之前为白)
流程：
img
img
img
img
img
img
img
这种方式的回收精度低，一个对象即使被删除了最后一个指向它的指针也依旧可以活过这一轮，在下一轮 GC 中被清理掉。
插入写屏障和删除写屏障的短板：
  • 插入写屏障：结束时需要 STW 来重新扫描栈，标记栈上引用的白色对象的存活；
  • 删除写屏障：回收精度低，GC 开始时 STW 扫描堆栈来记录初始快照，这个过程会保护开始时刻的所有存活对象。
# 混合写屏障
Go V1.8 版本引入了混合写屏障机制（hybrid write barrier），避免了对栈 re-scan 的过程，极大的减少了 STW 的时间。结合了两者的优点。
具体操作:
1、GC 开始将栈上的对象全部扫描并标记为黑色 (之后不再进行第二次重复扫描，无需 STW)，
2、GC 期间，任何在栈上创建的新对象，均为黑色。
3、被删除的对象标记为灰色。
4、被添加的对象标记为灰色。
满足：变形的弱三色不变式.
伪代码：
func 添加下游对象(当前下游对象slot, 新下游对象ptr) {
    //1 
        标记灰色(当前下游对象slot)    // 只要当前下游对象被移走，就标记灰色
    
    //2 
    标记灰色(新下游对象ptr)
        
    //3
    当前下游对象slot = 新下游对象ptr
}
这里我们注意， 屏障技术是不在栈上应用的，因为要保证栈的运行效率。
# 混合写屏障场景
GC 开始：扫描栈区，将可达对象全部标记为黑
img
img
场景一： 对象被一个堆对象删除引用，成为栈对象的下游
伪代码
// 前提：堆对象 4-> 对象 7 = 对象 7；  // 对象 7 被 对象 4 引用
栈对象1->对象7 = 堆对象7；  // 将堆对象 7 挂在 栈对象 1 下游
堆对象4->对象7 = null；    // 对象 4 删除引用 对象 7
img
img
场景二： 对象被一个栈对象删除引用，成为另一个栈对象的下游
伪代码
new 栈对象9；
对象8->对象3 = 对象3；      // 将栈对象 3 挂在 栈对象 9 下游
对象2->对象3 = null；      // 对象 2 删除引用 对象 3
img
img
img
场景三：对象被一个堆对象删除引用，成为另一个堆对象的下游
伪代码
堆对象10->对象7 = 堆对象7；       // 将堆对象 7 挂在 堆对象 10 下游
堆对象4->对象7 = null；         // 对象 4 删除引用 对象 7
img
img
img
场景四：对象从一个栈对象删除引用，成为另一个堆对象的下游
伪代码
堆对象10->对象7 = 堆对象7；       // 将堆对象 7 挂在 堆对象 10 下游
堆对象4->对象7 = null；         // 对象 4 删除引用 对象 7
img
img
img
Golang 中的混合写屏障满足 弱三色不变式 ，结合了删除写屏障和插入写屏障的优点，只需要在开始时并发扫描各个 goroutine 的栈，使其变黑并一直保持，这个过程不需要 STW，而标记结束后，因为栈在扫描后始终是黑色的，也无需再进行 re-scan 操作了，减少了 STW 的时间。
 更新于 
-->