一张图了解三色标记法



三色标记法是传统 Mark-Sweep 的一个改进,它是一个并发的 GC 算法。
原理如下,

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

这个算法可以实现 “on-the-fly”,也就是在程序执行的同时进行收集,并不需要暂停整个程序。
但是也会有一个缺陷,可能程序中的垃圾产生的速度会大于垃圾收集的速度,这样会导致程序中的垃圾越来越多无法被收集掉。