常见垃圾回收算法

1. 引用计数

优点：对象可以被很快回收，不会出现内存耗尽或达到某个阈值时才开始回收

缺点：1. 一些没有破坏性的操作，如只读操作也需要更新引用计数；

  1. 必须原子更新，不适用于多线程以及高并发
  2. 还有一个循环引用的问题，参考PHP解决循环引用

代表语言：php，python

2.标记-清扫

是一种间接的垃圾回收算法，不直接查找垃圾对象，而是通过活着的对象推断垃圾对象

优点：解决了引用计数的缺点

缺点：1. 可能产生内存碎片或空洞

  1. 需要STW

代表语言：Golang

3. 标记-压缩

分为两个阶段：标记、压缩。通过将分散的、活着的对象移动到更紧密的空间来解决碎片问题。

缺点：内存对象在内存的位置是随机的，这常常会破坏缓存的局部性，并且时常需要一些额外的空间来标记当前对象已经移动到了其它地方

4. 半空间复制

是一种空间换时间的算法，使用一半内存空间，保留另一半的内存空间用于快速压缩内存。

半空间复制的压缩性消除了内存碎片问题。半空间复制不分阶段，在扫描根对象时就可以直接压缩，每个扫描到的对象会从fromspace空间复制到topspace空间。一旦扫描完成就得到了一个压缩后的副本。

5. 分代GC

这个算法的重要前提是：死去的对象一般都是新创建不久的。按照对象生命周期长短划分不同的代空间，生命周期长的放入老年代，而短的放入新生代，不同代有不能的回收算法和回收频率。

缺点：没有办法及时回收老一代的对象，并且需要额外的开销引用和区分老对象。

代表语言：java

Golang垃圾回收

Golang使用了并发三色标记算法进行垃圾回收，实现简单。由于使用了现代内存分配算法TCMalloc，能够很好解决内存碎片的问题。

为什么不使用“引用计数”：由于引用计数固有的缺陷，不适合并发。

为什么不使用“标记压缩”和“半空间复制”：这两种都属于压缩算法，能够很好解决内存碎片问题。但是需要加锁，也不适合在并发程序中使用。

为什么不使用“分代GC”：分代GC的主要假设是大部分垃圾对象都是新创建的。但是由于编译器的优化，Go语言通过内存逃逸的机制将会继续使用的对象转移到了堆中，大部分生命周期很短的对象会在栈中，减弱了分代GC的优势。

垃圾回收流程

标记准备阶

需要STW

  1. 清扫上一阶段GC遗留的需要清扫的对象
  2. 重置各种状态、统计指标
  3. 启动专门用于标记的协程，为每个逻辑处理器P启动一个标记协程。Go语言规定后台标记协程消耗的CPU应该接近25%
  4. 统计需要扫描的任务数量
  5. 开启写屏障

并发标记阶段

之前写过一篇文章介绍了go语言的内存管理。提到span数据结构中维护了一个个内存块。由位图allocBits表示每个内存块的分配情况，gcmarkBits标记内存块被引用的情况：

allocBits和gcmarkBits数据结构是完全一样的，标记结束就是内存回收，回收时将allocBits指向gcmarkBits，则代表标记过的才是存活的，gcmarkBits则会在下次标记时重新分配内存，非常的巧妙！

三色标记法

前面介绍了对象标记状态的存储方式，还需要有一个标记队列来存放待标记的对象，可以简单想象成把对象从标记队列中取出，将对象的引用状态标记在span的gcmarkBits，把对象引用到的其他对象再放入队列中。

三色只是为了叙述上方便抽象出来的一种说法，实际上对象并没有颜色之分。这里的三色，对应了垃圾回收过程中对象的三种状态：

  • 灰色：对象还在标记队列中等待
  • 黑色：对象已被标记，gcmarkBits对应的位为1（该对象不会在本次GC中被清理）
  • 白色：对象未被标记，gcmarkBits对应的位为0（该对象将会在本次GC中被清理）

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

初始状态下所有对象都是白色的。

接着开始扫描根对象a、b:

由于根对象引用了对象A、B,那么A、B变为灰色对象，接下来就开始分析灰色对象，分析A时，A没有引用其他对象很快就转入黑色，B引用了D，则B转入黑色的同时还需要将D转为灰色，进行接下来的分析。如下图所示：

img

上图中灰色对象只有D，由于D没有引用其他对象，所以D转入黑色。标记过程结束：

img

最终，黑色的对象会被保留下来，白色对象会被回收掉。

辅助标记

在并发标记阶段，扫描内存的同时用户协程也在不断分配内存，当用户协程的内存分配速度快到后台标记协程来不及扫描时，GC标记将永远不会结束，从而无法完成完整的GC周期，造成内存泄漏。

为了解决这样的问题，引入了辅助标记算法。由于用户协程被分配了超过限度的内存而不得不将其暂停并切换到辅助标记工作。

用户协程分配内存时，会检查是否已完成指定的扫描工作，如果没有，那么将停止工作协程，执行辅助标记协程。

屏障技术

辅助标记解决了垃圾回收正常结束与循环的问题，屏障技术解决更棘手的问题——准确性。

屏障技术的原则是在写入或删除对象时将可能活着的对象标记为灰色。

Dijkstra风格的插入屏障

如果目标对象的src为黑色，则将新引用的对象标记为灰色

Yuasa风格的删除屏障

在对象被解除引用后，立即将原引用对象标记为灰色

go1.8之后使用了混合写屏障技术

标记终止阶段

标记终止阶段的首要任务是计算下一次触发GC需要达到的堆目标，这叫做垃圾回收的调步算法。保证在GC结束后占用内存的大小刚好在目标内存的附近。

调步算法最重要的任务是估计出下一次触发GC的最佳时机

垃圾清扫阶段

程序中只有一个垃圾清扫协程，并与用户协程并行运行。

垃圾清扫采用了懒惰清扫策略当清扫协程被唤醒后，开始执行清扫，执行少量清扫工作后，通过Gosched函数让渡自己的执行权力，不需要一直执行。因此当触发下一阶段的垃圾回收后，可能有没有被清理的内存，需要先将它们清理完

清扫是以span为单位进行的，在清扫期间最重要的一步是将gcmarkBits位图赋值给allocBits位图。

如果标记后，gcmarkBits的全部bit位都为0，这时整个span将会被heap回收。

可以看出这种清扫方式并没有直接将内存释放到操作系统中，而是再次组织以便能够在下次分配时利用。

辅助清扫

由于清扫是懒惰形式清扫的，如果剩余未清扫的span太多，会大大拖后下一次GC的时间，因此使用了辅助清扫的手段。

go语言会在两个时机判断是否需要辅助清扫

  1. 向mcentrel申请内存时
  2. 大对象分配时

在这两个时机判断当前已经清扫的page数是否大于清理的目标page数，如果不是，则进行辅助清扫

系统驻留内存清除

在垃圾清扫阶段，只是将span归还给了heap，并没有直接归还给操作系统。

程序启动时就会启动一个清除协程，并且只有一个，清除策略是占用当前线程CPU%1的时间进行清除。

清除过程中以page为最小单位进行清除，有可能会一次释放n个连续的page。

垃圾回收的触发时机

  1. 定期触发：默认情况下最长2分钟触发一次，在src/runtime/proc.go:forcegcperiod变量声明

    // forcegcperiod is the maximum time in nanoseconds between garbage
// collections. If we go this long without a garbage collection, one
// is forced to run.
//
// This is a variable for testing purposes. It normally doesn't change.
var forcegcperiod int64 = 2 * 60 * 1e9

  2. 内存分配达到阈值

    每次内存分配时都会检查当前分配量是否已达到了阈值

    阈值 = 上次GC内存分配量 * 内存增长率

    内存增长率默认为100，即每当内存扩大一倍时启动GC

  3. 手动触发

    程序中直接使用runtime.GC()方法触发GC