垃圾收集(Garbage Collection) 通常被称为"GC”,常见的 GC 算法有 : 引用计数法、标记清除法、三色标记法、分代收集法。

引用计数法

引用计数法为每个对象维护一个整型的值,用于记录当前对象被引用的数量,当对象被引用时,此值+1,取消引用时,此值 -1。当计数器为0时,销毁对象。

优点

  • 回收垃圾速度快

  • 最大暂停时间短

    最大暂停时间 : 因执行 GC 而暂停执行程序的最长时间

缺点

  • 不能解决循环引用的问题,A对象引用了B对象,B对象也引用了A对象时。A与B的引用计数器永远不为0,永远不可以被回收。

  • 引用计数操作增加了内存与CPU消耗。

标记清除法

标记清除法分为两步:标记与清除

标记:从根节点开始,递归遍历所有对象,将能遍历到的对象打上标识。 清除:再次遍历堆,未标记的对象加入到空闲链表中,标记的对象则去除标记。

优点

  • 算法实现简单
  • 对象不被移动

缺点

  • 最大暂停时间太长
  • 清除后会产生大量内存碎片

三色标记法

三色标记法是对标记清除法的改进。是一种并行垃圾回收

过程:

  • 初始化,所有对象都是白色
  • 从根遍历(非递归),所有可达对象标记为灰色
  • 从灰色对象队列中取出对象,将其引用的对象标记为灰色,并将自己标记为黑色
  • 重复第三步,直到灰色队列为空,此时白色对象即为孤儿对象,进行回收

分代收集算法

分代GC将内存空间按”代(Generation)”分为几个部分(通常是两代,即Young Generation和Old Generation),并尽可能频繁地在年轻的一代执行GC,当年轻一代的内存空间不够时,将可达对象全部移到上一代,此时年轻代的内存空间为空闲空间,可用于分配新对象,这样更快并且通常也更有效率。当老一代GC不够用时,才执行全量GC。

通常大部分语言的运行时都会混合多种GC算法,比如Erlang的GC( 参考:深入了解Erlang 垃圾回收机制以及其重要性 )就混合了分代GC和引用计数,在进程堆内使用分代GC,对全局数据使用引用计数(即时释放内存)。