1. 垃圾回收算法

1.1. 基础概念

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

（1） GC带来的优势：

  • 屏蔽内存回收细节，为用户屏蔽复杂的内存管理工作。

  • 以全局视野执行任务。

（2） GC带来的劣势：

  • 将释放内存的工作委托给垃圾回收模块，研发人员得到了减负，也失去了控制主权。

  • 增加了额外的成本，需要额外的状态信息用以存储全局的内存使用情况，且部分时间需要中断整个程序用以支持垃圾回收工作的执行。

1.2. 标记清扫

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

  • 标记：标记出当前还存活的对象

  • 清扫：清扫掉未被标记到的垃圾对象

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

1.3. 标记压缩

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

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

1.4. 半空间复制

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

  • 分配两片相等大小的空间，称为fromspace和tospace

  • 每轮只使用formspace空间，以GC作为分水岭划分轮次

  • GC时，将fromspace存活对象转移到tospace中，并以此为契机对空间进行压缩整合

  • GC后，交换fromspace和tospace，开启新的轮次

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

不足：比较浪费空间

1.5. 引用计数

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

  • 对象每被引用一次，计数器加1

  • 对象每被删除引用一次，计数器减1

  • GC时，把计数器等于0的对象删除

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

2. Golang中垃圾回收

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

2.1. 三色标记法

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

  • 对象分为三种颜色标记：黑、灰、白

  • 黑对象代表，对象自身存活，且其指向对象都已标记完成

  • 灰对象代表，对象自身存活，但其指向对象还未标记完成

  • 白对象代表，对象尚未被标记到，可能是垃圾对象

  • 标记开始前，将根对象（全局对象、栈上的局部变量等）置黑，将其所指向的对象置灰

  • 标记规则是，从灰对象触发，将其所指向的对象都置灰。所有指向对象都置灰后，当前灰对象置黑

  • 标记结束后，白色对象就是不可达对象，进行垃圾清扫

2.2. 并发垃圾回收

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删除。

3. 屏障机制

3.1. 强弱三色不变式

  • 强三色不变式：白色对象不能被黑色对象直接引用（直接破坏）

  • 弱三色不变式：白色对象可以被黑色对象引用，但要从某一个灰色对象出发仍然可以到达该白色对象

3.2. 插入写屏障

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

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

3.3. 删除写屏障

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

3.4. 混合写屏障

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

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

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

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

  • GC开始前，以栈为单位分批扫描，将栈中所有对象置黑

  • GC期间，栈上新创建对象直接置黑

  • 堆对象正常启用插入写屏障

  • 堆对象正常启用删除写屏障

参考链接

https://zhuanlan.zhihu.com/p/605315127