常见的 GC 算法

引用计数

每个对象分别引用一个计数器 count,被引用则 count + 1,被释放则 count - 1,当 count0 时,该对象可以被清除

缺点是对象之间存在循环引用的问题

标记-清除算法

基于追踪的垃圾回收算法

算法分为两部分:标记(mark),清除(sweep)

  1. root 开始遍历,将所有访问到的对象都标记为可达对象

image

  1. 清除不可达对象

进行以上两个过程需要 stop the world,代码的执行会被暂停,保证在清除过程中内存的状态不变,这个过程又被称作 STW,可见 STW 所用时间将直接决定 GC 性能,优点是解决了 引用计数 问题,确定是需要 STW

三色标记算法

白色集合: 初始状态,全部的对象,其中部分可以被回收。
灰色集合: root 中直接引用的对象,可能引用白色对象,不能被回收,会被移动到黑色集合。
黑色集合: 其中的对象 不引用 白色集合中的对象。

清理过程
  1. 初始状态下对象都在白色集合
  2. 将被 root 直接引用的对象移动到灰色集合
  3. 从灰色集合中取出一个对象,将其放入黑色集合,将其子对象放入灰色集合,重复以上过程,直至灰色集合为空

此时黑色集合包含被直接(或间接)引用的对象,白色集合包含未被引用的对象

  1. 将白色集合的对象全部清除

三色标记法与标记-清除算法相比,优越性体现在哪?

三色标记法只需要保证 灰色集合为空,黑色不引用白色对象 的条件,那么白色对象就可以被释放

三色标记的目的,主要是用来做增量垃圾回收,如果只有两种状态,那么标记和清除不能被打断,期间用户程序不能执行。

而使用三色标记,即使在标记过程中对象的引用发生了变化,只要满足黑色不引用白色这个约束条件,垃圾回收器就可以继续工作,将整个回收过程打散,每次回收一部分,实现真正的增量回收。

但并发执行存在一个问题:

image

A为根对象,GC遍历到A,A变黑,B变灰,这时用户程序将A->B 的引用改为 A -> C 的引用,GC遍历到B,B没有引用,B变黑,灰集合为空,C被错误地释放。

为了解决并发带来地引用修改的问题, Go 引用了写屏障,GC开始之后可以感知内存的引用变化,如果黑色对象A引用了白色对象C,那么C变为灰色,如果新创建了对象,那么直接移入黑色,等待下一次处理

https://blog.wangriyu.wang/2019/04-Golang-GC.html#
https://making.pusher.com/golangs-real-time-gc-in-theory-and-practice/