常见GC算法

我总结了一下常见的 GC 算法。分别是：引用计数法、Mark-Sweep法、三色标记法、分代收集法。

 

1. 引用计数法

原理是在每个对象内部维护一个整数值，叫做这个对象的引用计数，当对象被引用时引用计数加一，当对象不被引用时引用计数减一。当引用计数为 0 时，自动销毁对象。

目前引用计数法主要用在 c++ 标准库的 std::shared_ptr 、微软的 COM 、Objective-C 和 PHP 中。

但是引用计数法有个缺陷就是不能解决循环引用的问题。循环引用是指对象 A 和对象 B 互相持有对方的引用。这样两个对象的引用计数都不是 0 ，因此永远不能被收集。

另外的缺陷是，每次对象的赋值都要将引用计数加一，增加了消耗。

这种GC算法把业务代码与GC算法耦合在一起，GC会导致业务代码执行性能下降，变量指向变动越频繁，GC占用性能越高。

 

2. Mark-Sweep法（标记清除法）

这个算法分为两步，标记和清除。

• 标记：从程序的根节点开始， 递归地遍历所有对象，将能遍历到的对象打上标记。
• 清除：讲所有未标记的的对象当作垃圾销毁。 

 

图片来自   

但是这个算法也有一个缺陷，就是人们常常说的 STW 问题（Stop The World）。因为算法在标记时必须暂停整个程序，否则其他线程的代码可能会改变对象状态，从而可能把不应该回收的对象当做垃圾收集掉。

当程序中的对象逐渐增多时，递归遍历整个对象树会消耗很多的时间，在大型程序中这个时间可能会是毫秒级别的。让所有的用户等待几百毫秒的 GC 时间这是不能容忍的。

golang 1.5以前使用的这个算法。

 

3. 三色标记法

三色标记法是传统 Mark-Sweep 的一个改进，它是一个并发的 GC 算法。

原理如下，

1. 首先创建三个集合：白、灰、黑。
2. 将所有对象放入白色集合中。
3. 然后从根节点开始遍历所有对象（注意这里并不递归遍历），把遍历到的对象从白色集合放入灰色集合。
4. 之后遍历灰色集合，将灰色对象引用的对象从白色集合放入灰色集合，之后将此灰色对象放入黑色集合
5. 重复 4 直到灰色中无任何对象
6. 通过write-barrier检测对象有变化，重复以上操作
7. 收集所有白色对象（垃圾） 

 

图片来自  

这个算法可以实现 "on-the-fly"，也就是在程序执行的同时进行收集，并不需要暂停整个程序（后面会讲具体GC与业务代码怎么并发执行的，其实还是会有短暂的STW的）。

但是也会有一个缺陷，三色标记法是增量GC算法，可能程序中的垃圾产生的速度会大于垃圾收集的速度，这样会导致程序中的垃圾越来越多无法被收集掉。

使用这种算法的是 Go 1.5、Go 1.6。

 

4. 分代收集

分代收集也是传统 Mark-Sweep 的一个改进。这个算法是基于一个经验：绝大多数对象的生命周期都很短。所以按照对象的生命周期长短来进行分代。

一般 GC 都会分三代，在 java 中称之为新生代（Young Generation）、年老代（Tenured Generation）和永久代（Permanent Generation）；在 .NET 中称之为第 0 代、第 1 代和第2代。

原理如下：

• 新对象放入第 0 代
• 当内存用量超过一个较小的阈值时，触发 0 代收集
• 第 0 代幸存的对象（未被收集）放入第 1 代
• 只有当内存用量超过一个较高的阈值时，才会触发 1 代收集
• 2 代同理

因为 0 代中的对象十分少，所以每次收集时遍历都会非常快（比 1 代收集快几个数量级）。只有内存消耗过于大的时候才会触发较慢的 1 代和 2 代收集。

因此，分代收集是目前比较好的垃圾回收方式。使用的语言（平台）有 jvm、.NET 。

 

golang的GC

root

首先标记root根对象，根对象的子对象也是存活的。

根对象包括：全局变量，各个G stack上的变量等。

 

标记

在之前的一文中，分析过span是内存管理的最小单位，所以猜测gc的粒度也是span。

bitmap

如图所示，通过gcmarkBits位图标记span的块是否被引用。对应内存分配中的bitmap区。

 

三色标记

• 灰色：对象已被标记，但这个对象包含的子对象未标记
• 黑色：对象已被标记，且这个对象包含的子对象也已标记，gcmarkBits对应的位为1（该对象不会在本次GC中被清理）
• 白色：对象未被标记，gcmarkBits对应的位为0（该对象将会在本次GC中被清理）

例如，当前内存中有A~F一共6个对象，根对象a,b本身为栈上分配的局部变量，根对象a、b分别引用了对象A、B, 而B对象又引用了对象D，则GC开始前各对象的状态如下图所示:

1. 初始状态下所有对象都是白色的。
2. 接着开始扫描根对象a、b; 由于根对象引用了对象A、B,那么A、B变为灰色对象，接下来就开始分析灰色对象，分析A时，A没有引用其他对象很快就转入黑色，B引用了D，则B转入黑色的同时还需要将D转为灰色，进行接下来的分析。
3. 灰色对象只有D，由于D没有引用其他对象，所以D转入黑色。标记过程结束
4. 最终，黑色的对象会被保留下来，白色对象会被回收掉。

STW

stop the world是gc的最大性能问题，对于gc而言，需要停止所有的内存变化，即停止所有的goroutine，等待gc结束之后才恢复。

 

go垃圾回收触发方式

• 阈值：默认内存扩大一倍，启动gc
• 定期：默认2min触发一次gc，src/runtime/proc.go:forcegcperiod
• 手动：runtime.gc()

 

GC流程

GO的GC是并行GC, 也就是GC的大部分处理和普通的go代码是同时运行的, 这让GO的GC流程比较复杂.

1. Stack scan：Collect pointers from globals and goroutine stacks。收集根对象（全局变量，和G stack），开启写屏障。全局变量、开启写屏障需要STW，G stack只需要停止该G就好，时间比较少。
2. Mark: Mark objects and follow pointers。标记所有根对象, 和根对象可以到达的所有对象不被回收。
3. Mark Termination: Rescan globals/changed stack, finish mark。重新扫描全局变量，和上一轮改变的stack（写屏障），完成标记工作。这个过程需要STW。
4. Sweep: 按标记结果清扫span

目前整个GC流程会进行两次STW(Stop The World), 第一次是Stack scan阶段, 第二次是Mark Termination阶段.

• 第一次STW会准备根对象的扫描, 启动写屏障(Write Barrier)和辅助GC(mutator assist).
• 第二次STW会重新扫描部分根对象, 禁用写屏障(Write Barrier)和辅助GC(mutator assist).

从1.8以后的golang将第一步的stop the world 也取消了，这又是一次优化； 1.9开始, 写屏障的实现使用了Hybrid Write Barrier, 大幅减少了第二次STW的时间.

写屏障

因为go支持并行GC, GC的扫描和go代码可以同时运行, 这样带来的问题是GC扫描的过程中go代码有可能改变了对象的依赖树。写屏障就是收集标记阶段对象依赖树修改记录的。

例如开始扫描时发现根对象A和B, B拥有C的指针。

1. GC先扫描A，A放入黑色
2. B把C的指针交给A
3. GC再扫描B，B放入黑色
4. C在白色，会回收；但是A其实引用了C。

为了避免这个问题, go在GC的标记阶段会启用写屏障(Write Barrier)。

启用了写屏障(Write Barrier)后，在GC第三轮rescan阶段，根据写屏障标记将C放入灰色，防止C丢失。

更多并发mark会导致的问题请看https://www.cnblogs.com/qqmomery/p/6661574.html?utm_source=tuicool&utm_medium=referral

 

golang的GC演变史

go 语言在 1.3 以前，使用的是比较蠢的传统 Mark-Sweep 算法。

1.3 版本进行了一下改进，把 Sweep 改为了并行操作。

1.5 版本进行了较大改进，使用了三色标记算法。go 1.5 在源码中的解释是“非分代的、非移动的、并发的、三色的标记清除垃圾收集器”。

从1.8以后的golang将第一步的stop the world 也取消了，这又是一次优化。

1.9开始, 写屏障的实现使用了Hybrid Write Barrier, 大幅减少了第二次STW的时间。

 

go 除了标准的三色收集以外，还有一个辅助回收功能，防止垃圾产生过快手机不过来的情况。这部分代码在  中。

但是 golang 并没有分代收集，所以对于巨量的小对象还是很苦手的，会导致整个 mark 过程十分长，在某些极端情况下，甚至会导致 GC 线程占据 50% 以上的 CPU。

因此，当程序由于高并发等原因造成大量小对象的gc问题时，最好可以使用  等对象池技术，避免大量小对象加大 GC 压力。

 

参考并引用自以下资料：

https://blog.csdn.net/erlib/article/details/51850912（为Go语言GC正名－20秒到100微妙的演变史）

https://www.cnblogs.com/diegodu/p/9150840.html（golang垃圾回收机制）

https://blog.csdn.net/liangzhiyang/article/details/52669851（golang的goroutine调度机制）

https://blog.csdn.net/bairongdong1/article/details/52216360（跟雨痕看go源码-并发清除与三色标记）

https://www.cnblogs.com/qqmomery/p/6661574.html?utm_source=tuicool&utm_medium=referral（垃圾回收算法-三色标记法）

https://www.jianshu.com/p/8b0c0f7772da（Go语言垃圾回收GC）