一文了解垃圾回收算法中的引用计数算法

本文介绍将简要介绍一种基本的回收算法：引用计数算法[Collins，1960]，英文名 reference counting。

引用计数方法非常简单。对象的存活性可以通过引用关系的创建和删除直接判定，从而无需向追踪式回收器那样先通过遍历堆找出所有的存活对象，然后再反向确定出未遍历到的垃圾对象。

引用计数算法基于计算对每个分配对象的指针引用数的想法。这是一种直接的方法，也恰好是自然增量的，因为它在整个程序中分配内存管理开销。

该算法依赖于一个非常简单的不变式：当且仅当指向某个对象的引用数量大于 0 时，该对象才有可能是存活的。

那么该算法是怎么运作的呢？

引用计数怎么运作？

在引用计数方法下，每个分配的对象都包含一个引用计数字段。

内存管理器负责维护不变量，即每个对象的引用计数始终等于对该对象的直接指针引用的数量，当创建或者删除某一对象的引用时增加或减少该对象的引用计数。

下面给出了该算法的基本版本：

• new 方法：用来创建一个对象，new() 分配一个新对象。为简洁起见，我们忽略了对象类型，假设所有对象的类型和大小都相同。
• delete 方法：实现引用计数的减少，当客户端程序不再需要对象时调用 ​​delete()​​
• update 方法：​​update()​​​ 是在系统中执行指针分配的唯一方法。实现对引用对象计数的增加，我们在删除之前递增，这正确处理了 ​​source == target​​ 的情况。

def new():
  obj = allocate_memory()
  obj.set_reference_count(1)
  return obj

def delete(obj):
  obj.decrement_reference_count()
  if obj.get_reference_count() == 0:
    for child in children(obj):
      delete(child)
    release_memory(obj)

def update(source, target):
  target.increment_reference_count()
  delete(source)
  source = target