常见 GC 算法
| 名称 | 描述 | 优点 | 缺点 |
|---|---|---|---|
| 引用计数 | 根据对象自身的引用计数来回收，当引用计数归零时进行回收。 | 简单直接，回收速度快 | 需要额外的空间存放计数； 需要频繁更新计数； 无法处理循环引用的情况； |
| 标记清除 | 标记出所有不需要回收的对象，在标记完成后统一回收掉所有未被标记的对象。 | 简单直接，速度快 | 会造成不连续的内存空间（内存碎片） 不适合回收对象过多的场景 |
| 复制法 | 将内存分为大小相同的两块，每次使用其中的一块，当这一块的内存使用完后，将还存活的对象复制到另一块去，然后再把使用的空间一次清理掉 | 解决了内存碎片的问题 | 每次清除针对的都是整块内存，效率低于标记清除法； 有部分内存总是利用不到，资源浪费，移动存活对象比较耗时，并且如果存活对象较多的时候，需要担保机制确保复制区有足够的空间可完成复制； |
| 标记整理 | 标记过程同标记清除法，结束后将存活对象压缩至一端，然后清除边界外的内容。 | 解决了内存碎片的问题，也不像标记复制法那样需要担保机制，存活对象较多的场景也使适用； | 性能低，因为在移动对象的时候不仅需要移动对象还要维护对象的引用地址，可能需要对内存经过几次扫描才能完成； |
| 分代式 | 将对象根据存活时间的长短进行分类，存活时间小于某个值的为“年轻代”，存活时间大于某个值的为“老年代”，永远不会参与回收的对象为“永久代”。并根据分代假设（如果一个对象存活时间不长则倾向于被回收，如果一个对象已经存活很长时间则倾向于存活更长时间）对对象进行回收。 | STW 对用户代码影响大 |
Golang GC
Golang 使用的垃圾清理算法是“无分代”、“不整理”、“与用户代码并发执行”的三色标记清理算法。
为什么 Golang 不使用“顺序内存分配器”？
Go运行时的分配算法基于tcmalloc，基本上没有碎片问题，对对象进行整理不会带来实质性的性能提升。- 并且顺序内存分配器在多线程的场景下并不适用。
为什么 Golang 不使用“分代假设”？
- 分代假设的优点在于处理短时间存活的新创建对象，但是 Golang 会通过“逃逸分析”将大部分新生对象存储在栈上，所以分代假设在 Golang 上没有带来直接的优势；
- Go 的垃圾回收器与用户代码并发执行，这使得
STW的时间与对象的代际、对象的 size 没有关系。
三色标记原理
三色标记法将对象分为三类，并用不同的颜色相称：
- 白色对象（可能死亡）：未被回收器访问到的对象。在回收开始阶段，所有对象均为白色，当回收结束后，白色对象均不可达。
- 灰色对象（波面）：已被回收器访问到的对象，但回收器需要对其中的一个或多个指针进行扫描，因为他们可能还指向白色对象。
- 黑色对象（确定存活）：已被回收器访问到的对象，其中所有字段都已被扫描，黑色对象中任何一个指针都不可能直接指向白色对象。
具体的算法实现是维护一个“灰色对象队列”，从“根对象”开始进行“广度优先遍历”。其中根对象是一个集合，包括：
全局变量：在程序编译的时候就已经确定存在于整个生命周期的变量；
执行栈：每个
goroutine都包含自己的执行栈，这些执行栈上包含栈上的变量及指向分配的堆内存区块的指针；寄存器：寄存器的值可能表示一个指针，参与计算的这些指针可能指向某些赋值器分配的堆内存区块。
屏障机制
引入原因
Golang GC 是没有 STW (Stop The World) 的，它的垃圾回收器是与用户代码并发执行的。
但是这一机制会导致在下面的这个并发情况下，错误地回收了对象 B：
- 在垃圾回收进行到这样阶段时：灰色对象 A 引用了白色对象 B，黑色对象 C 没有引用白色对象 B；
- 用户代码移除了引用 $$A \rightarrow B$$，增加了引用 $$C \rightarrow B$$；
- 因为 C 已经被标记为黑色对象了，B 就将会一直被保持为白色对象直到扫描结束，从而被错误回收；
因为 GC 与用户代码是并行的，所以会破坏三色标记法在 STW 下运行的基本假设：
| 假设 | 节点性质 V | 入边性质 EN | 出边性质 EP |
|---|---|---|---|
| 黑色对象假设 B | 黑色对象一定是存活对象 | 一定存在一个黑色对象 | 只能引用灰色、黑色对象 |
| 灰色对象假设 G | 灰色对象一定是存活对象 | 一定存在一个黑色或灰色对象 | 🈚️无限制 |
| 白色对象假设 W | 结束时，一定为死亡对象 | 只能被灰色、白色对象引用 | 🈚️无限制 |
其中最重要的性质是 W-V，破坏这个性质会直接导致 GC 算法不可用。
用户代码的运行可能：
- 插入新的引用路径：破坏上面表格中的"B-EP"/“W-EN”/“W-V"三个性质；
- 删除已有的引用路径：破坏上面表格中的"B-V”/“B-EN”/“G-V”/“G-EN"四个性质；
所以 Golang 引入了屏障的概念，即：
- 在用户代码并行执行时，Hook 用户代码的一些操作，来实现存活对象不会被误清理的目的；
Dijkstra 屏障：插入路径
即在用户代码插入路径时执行一些操作：
- 如果新建一个路径 $$A \rightarrow B$$，则将 B 对象标记为灰色对象；
- 如果将路径 $$A \rightarrow C$$ 替换为 $$A \rightarrow B$$，则将 B 对象标记为灰色对象；
这一算法有以下缺点：
- 在插入屏障下的结果是必要条件，能够确保不被误删除，但会遗留未清理垃圾。
- 每次写入操作都需要执行额外代码会造成性能开销。Golang 在实现时实际只对堆区对象加入了写屏障，栈区代码会发生更改后被标记，在扫描结束后通过 STW 重新处理。
Yuasa 屏障：删除路径
即在用户代码删除路径时执行一些操作：
- 如果删除路径 $$A \rightarrow C$$，且 C 之前为白色，则 C 被标记为灰色；
- 如果将路径 $$A \rightarrow C$$ 替换为 $$A \rightarrow B$$，且 C 之前为白色，则 C 被标记为灰色；
删除路径并没有解决删除导致的破坏性质问题，反而是深化了这些被破坏的性质。这是因为删除屏障本质还是在解决插入路径遇到的问题，维持最重要的性质 W-V 的正确性。