垃圾回收算法#

背景介绍#

垃圾回收（Garbage Collection，简称 GC）是一种内存管理策略，由垃圾收集器以及守护协程的方式在后台运作，按照既定的策略为用户回收那些不在被使用的对象，释放对应的内存空间。

（1） GC 带来的优势：

屏蔽内存回收细节，为用户屏蔽复杂的内存管理工作。
以全局视野执行任务。

（2） GC 带来的劣势：

将释放内存的工作委托给垃圾回收模块，研发人员得到了减负，也失去了控制主权。
增加了额外的成本，需要额外的状态信息用以存储全局的内存使用情况，且部分时间需要中断整个程序用以支持垃圾回收工作的执行。

标记清扫#

标记清扫（Mark-Sweep）算法，分两步走：

标记：标记出当前还存活的对象
清扫：清扫掉未被标记到的垃圾对象

不足：会产生内存碎片，如果由大对象需要分配内存，可能会因为内存空间无法化零而导致分配失败。

标记压缩#

标记压缩（Mark-Compact）算法，是在标记清扫算法的基础上做了升级，在第二步“清扫“的同时还会对存活对象进行压缩整合，使整体空间更为紧凑，从而解决内存碎片问题。

不足：实现会有很高的复杂度

半空间复制#

半空间复制（Semispace Copy）核心点：

分配两片相等大小的空间，称为 fromspace 和 tospace
每轮只使用 formspace 空间，以 GC 作为分水岭划分轮次
GC 时，将 fromspace 存活对象转移到 tospace 中，并以此为契机对空间进行压缩整合
GC 后，交换 fromspace 和 tospace，开启新的轮次

半空间复制算法应用了以空间换取时间的优化策略，解决了内存碎片的问题，降低了压缩空间的复杂度。

不足：比较浪费空间

引用计数#

引用计数（Reference Counting）算法核心点：

对象每被引用一次，计数器加 1
对象每被删除引用一次，计数器减 1
GC 时，把计数器等于 0 的对象删除

不足：无法解决循环引用和自引用问题

Golang 中垃圾回收#

Golang 在 1.8 版本之后，GC 策略矿建已经奠定，就是并发三色标记法 + 混合写屏障机制。

三色标记法#

Golang GC 用到的三色标记法属于标记清扫-算法的一种实现，核心点有：

对象分为三种颜色标记：黑、灰、白
黑对象代表，对象自身存活，且其指向对象都已标记完成
灰对象代表，对象自身存活，但其指向对象还未标记完成
白对象代表，对象尚未被标记到，可能是垃圾对象
标记开始前，将根对象（全局对象、栈上的局部变量等）置黑，将其所指向的对象置灰
标记规则是，从灰对象触发，将其所指向的对象都置灰。所有指向对象都置灰后，当前灰对象置黑
标记结束后，白色对象就是不可达对象，进行垃圾清扫

并发垃圾回收#

Golang1.5 版本是个分水岭，在此之前，GC 时需要停止全局的用户协程，专注完成 GC 工作后，再恢复用户协程。

在 1.5 版本之后，Golang 引入了并发垃圾回收机制，允许用户协程和后台的 GC 协程并发运行。

（1）Golang 并发垃圾回收可能存在漏标问题

漏标问题是指用户协程与 GC 协程并发执行的场景下，部分存活对象未被标记从而被误删的情况。

初始时刻，对象 B 持有对象 C 的引用
GC 协程下，对象 A 被扫描完成，置黑；此时对象 B 是灰色，还未完成扫描
用户协程下，对象 A 建立指向对象 C 的引用
用户协程下，对象 B 删除指向对象 C 的引用
GC 协程下，开始指向对对象 B 的扫描

由于 GC 协程在 B 删除 C 的引用后才开始扫描 B，因此无法到达 C，因为 A 已经被置黑，不会再重复扫描，因此从扫描结果看，C 是不可达的。

事实上 C 应该是被 A 引用的，而 GC 结束后因为 C 仍为白色，因此被 GC 误删

（2）Golang 并发垃圾回收可能存在多标问题

多标问题指的是在用户协程与 GC 协程并发执行的场景下，部分垃圾对象被误标记从而导致 GC 未按时将其回收的问题

初始时刻，对象 A 持有对象 B 的引用
GC 协程下，对象 A 被扫描完成，置黑；对象 B 被对象 A 引用，因此被置灰
用户协程下，对象 A 删除执行对象 B 的引用

在事实上，B 在被 A 删除引用后，已经称为垃圾对象，但由于其事先已被置灰，因此最终灰更新为黑色，不会被 GC 删除。

屏障机制#

强弱三色不变式#

强三色不变式：白色对象不能被黑色对象直接引用（直接破坏）
弱三色不变式：白色对象可以被黑色对象引用，但要从某一个灰色对象出发仍然可以到达该白色对象

插入写屏障#

屏障机制类似于一个回调保护机制，指的是在完成某个特定动作之前，会先完成屏障设置的内容。

插入写屏障的目标是实现强三色不变式，保证当一个黑色对象指向一个白色对象前，会触发屏障将白色对象置为灰色，再建立引用。

删除写屏障#

删除写屏障的目标是实现弱三色不变式，保证当一个白色对象即将被上游删除引用前，会触发屏障将其置灰，之后再删除上有指向其的引用。

混合写屏障#

屏障机制无法作用于栈对象

这是因为栈对象可能涉及频繁的轻量操作，倘若这些高频操作都需要-触发写屏障机制，那么所带来的成本将无法接收。

在这一背景下，单独看插入写屏障或删除写屏障，都无法真正解决漏标问题，除非我们引入额外的 Stop the wrold（STW）阶段，对栈对象的额处理进行兜底。

为了消除这个额外的 STW 成本，Golang1.8 引入了混合写屏障机制，可以视为糅合了插入写屏障和删除屏障的加强版，要点如下：

GC 开始前，以栈为单位分批扫描，将栈中所有对象置黑
GC 期间，栈上新创建对象直接置黑
堆对象正常启用插入写屏障
堆对象正常启用删除写屏障

Go 中的垃圾回收