常见的垃圾回收策略
引用计数算法 （Reference Counting）
引用计数算法是一种最简单的垃圾回收算法，它的基本思想是：给对象中添加一个引用计数字段，每当有一个地方引用它时，计数加 1；当引用失效时，计数减 1；当计数为 0 时，表示对象不再被使用，可以被回收。
优缺点
优点:
无需遍历
- 不需要从根节点遍历，相对容易查找
立即回收垃圾
- 每个对象始终知道自己的被引用次数，一旦引用计数为 0，就会立即将自身连接到空闲链表上，等待回收
最大限度地减少程序暂停时间
- 在 mutator 更新引用计数时，就会触发垃圾回收，不需要等到内存耗尽时才触发，因此不会出现程序暂停时间过长的情况
缺点:
- 无法解决循环引用问题
- 每次引用计数发生变化时都需要修改计数器，引起额外的开销
- 需要额外的空间存储计数器
追踪回收算法 （Tracing Garbage Collection）
追踪回收算法有三种策略:
- 标记-清除算法（Mark-Sweep）
- 标记-整理算法（Mark-Compact）
- 标记-复制算法（Mark-Copying）
注意
三种策略在执行时都需要 STW （stop the world）, 暂停程序运行
标记-清除算法（Mark-Sweep）
工作原理：
- 从根对象出发，递归遍历所有可达对象，将可达对象标记为存活对象
- 遍历堆中所有对象，将未标记的对象回收
优缺点
优点:
- 可以解决循环引用问题
- 不需要额外的空间存储计数器
缺点:
- 在清除阶段会产生大量的碎片，导致内存碎片化，可能会导致程序运行分配对象时找不到连续的内存空间而再次触发垃圾回收
- 执行效率不稳定
标记-复制算法（Mark-Copying）
工作原理：
- 从根对象出发，递归遍历所有可达对象，将可达对象标记为存活对象
- 将堆划分成两个相等的区域：使用区和未使用区
- 在程序运行时只将对象放到使用区，当使用区满时，执行垃圾回收，遍历使用区的所有对象，判断存活对象并将存活对象移动至未使用区，然后清空使用区。最后将本两块区域的角色进行交换，即未使用区变成使用区，使用区变成未使用区
优缺点
优点:
- 可以解决内存碎片化问题
- 每次执行垃圾回收都会将存活对象移动至未使用区，对象都是连续存放的
- 执行效率相对较高
- 由于只需要复制存活对象，清除未存活对象是批量操作，因此需要的时间相对较短，吞吐率更高
- 快速分配内存
- 由于内存是连续的，因此分配内存时只需要移动指针即可，相比其他算法使用的是空闲链表，连续内存分配效率更高
缺点:
- 空间利用率低
- 相同的内存空间下，只有一半的空间可以用来存放对象
- 递归效率低
- 由于需要递归遍历并复制所有可达对象，相比于迭代效率较低，且需要额外的栈开销，可能导致内存溢出
标记-整理算法（Mark-Compact）
工作原理：
- 从根对象出发，递归遍历所有可达对象，将可达对象标记为存活对象
- 将存活对象移动至堆的一端，然后清除未存活对象
优缺点
优点:
- 空间利用率高
- 相对于标记-复制算法来说空间利用率更高，不会浪费一半的空间
缺点:
- 执行效率较低
- 在将存活对象移动至堆的一端时，需要进行3次遍历操作，需要更多的时间, 当对象非常多时，暂停时间会比其他两种策略还要长
三种策略的比较
吞吐率: 标记-复制算法 > 标记-整理算法 > 标记-清除算法
内存利用率: 标记-整理算法 > 标记-清除算法 > 标记-复制算法
内存整齐度: 标记-整理算法 = 标记-复制算法 > 标记-清除算法
Golang 的垃圾回收
三色标记算法
三色标记算法改进了标记-清除算法，将标记-清除算法的两个阶段（标记和清除）分解为三个阶段（标记、标记终止和清除），减少了 STW 的时间。
三种对象
| 颜色 | 对象状态 | 描述 |
|---|---|---|
| 白色 | 未访问 | 对象未被访问, 可能是需要回收的对象 |
| 灰色 | 访问中 | 对象已被访问，但其子对象未被访问 |
| 黑色 | 访问完成 | 对象已被访问，且其子对象已被访问 |
最终回收的是白色的对象。
工作原理
- 在垃圾回收开始时将根对象标记为灰色
- 在灰色对象中选择一个对象标记为黑色，然后将其子对象标记为灰色
- 将黑色对象指向的所有白色对象标记为灰色
- 重复步骤2和3，直到没有灰色对象
- 清除所有白色对象
假如不 STW 会怎样？
实际上，如果正常按照三色标记法进行 STW 的话， STW 的时间仍旧比较长。但是如果不 STW，那么在标记和清除的过程中，程序可能会继续运行，这样可能会导致对象的状态发生变化，从而导致垃圾回收器无法正确标记对象的状态，最终导致回收错误。
如上图所示，假如遍历完 A 和 D 之后，在遍历到达 B 之前，若 D 添加了对 C 的引用， B 移除了 C 的引用， 则 C 将会在 GC 之后变为白色，会被垃圾回收。
屏障技术
为了解决上述问题， Golang 引入了屏障技术，通过屏障技术可以在对象状态发生变化时，通知垃圾回收器。
重要
若我们希望在并发或增量标记算法中保证标记的正确性，我们需要达成以下其中一种三色不变性：
- 强三色不变性：在标记阶段中，黑色对象不会指向白色对象
- 弱三色不变性：在标记阶段中，黑色对象指向的白色对象（G）必须包含一条灰色对象经过一个或多个白色对象后到达白色对象（G）的路径
如上图所示，假如 A 添加了对 D 的引用，则需要再 E 添加指向 D 的引用，这样才能保证弱三色不变性。
Golang 用到的屏障技术
- 插入屏障
- 删除屏障
插入屏障
在 Golang 中，当一个对象 A 添加了对另一个对象 B 的引用时，会在 A 的引用列表中插入一个 B 的引用，并且将 B 标记为灰色。
注意
插入屏障只会在堆内生效，不会在栈内生效，主要考虑到性能问题
如上图所示，在初始条件下（图1）， A 属于栈内数据，F 属于堆内数据，在图2 中同时往 A 添加 D 的引用， 往 F 添加 H 的引用。 H 由于插入屏障会变成灰色，而 D 由于不在堆内，不会变成灰色。当扫描完毕时，如图4 所示，H 会被标记为黑色，而 D 会被标记为白色。这时候会启动 STW 将栈内对象重新扫描一遍，将 D 标记为黑色。
删除屏障
在 Golang 中，当一个对象 A 删除了对另一个对象 B 的引用时，会在 A 的引用列表中删除一个 B 的引用，如果 B 是白色的，则将 B 标记为灰色。
之所以将白色的对象标记为灰色，是因为白色的对象后面可能还有其他对象引用，如果不标记为灰色，可能会导致后续的对象无法被扫描到。
混合写屏障
插入屏障和删除屏障有以下缺点：
- 插入屏障在扫描结束后还需要
STW一次，将栈内对象重新扫描一遍 - 删除屏障回收精度较低，在回收开始时需要
STW一次，将栈内对象重新扫描一遍, 记录初始快照，保护初始时刻所有存活的对象
为了解决上述问题， Golang 引入了混合写屏障，混合写屏障是插入屏障和删除屏障的结合，可以在对象状态发生变化时，通知垃圾回收器。
工作原理
- 在垃圾回收开始时将栈上的对象全部扫描并标记为黑色（不进行二次扫描）
- 在垃圾回收期间任何栈上创建的对象都会标记为黑色，避免了二次扫描
- 在垃圾回收期间删除任何的对象都会标记为灰色
- 在垃圾回收期间创建的任何对象都会标记为灰色