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

本文介绍将简要介绍一种基本的回收算法：引用计数算法[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

无法解决循环引用

毫无疑问，引用计数的最大缺点是它无法回收循环存储。在简单引用计数方法下，双向链表或非简单图等循环数据结构无法有效回收，并且会泄漏内存。以下示例显示了该问题：

在 delete(A) 和 delete© 之后，我们最终得到了一个对象子图的不可访问但连接的组件，该组件无法从任何根访问，但由于非零引用，我们无法回收其节点。

幸运的是，所有其他垃圾收集技术（标记扫描、标记压缩、复制等）都可以轻松处理循环结构。这就是为什么使用引用计数作为主要垃圾收集机制的系统在堆耗尽后利用跟踪收集算法的情况并不少见。

引用计数算法的优缺点

引用计数的内存管理开销分摊在程序运行过程中，同时一旦某个对象成为垃圾对象就可以得到立刻回收。

而且该算法直接操作指针的来源与目标，因此其局部性不会比它所服务的应用程序差，且通常优于需要跟踪所有活动对象的跟踪 GC。该算法的优点如下：

• 响应性： 内存管理开销分布在整个程序中，与跟踪收集器相比，它通常会导致系统更加流畅和响应迅速。请注意，处理开销与最后一个指针指向的子图的大小相关，并且在某些情况下可能并不重要。
• 立即内存重用： 与跟踪收集器不同，在收集器执行之前，无法访问的内存保持未分配状态（通常在堆耗尽时）；引用计数方法允许立即重新使用丢弃的内存。这种立即重用可为缓存带来更好的时间局部性，从而减少页面错误。它还简化了资源清理，因为可以立即调用终结器，从而更快地释放系统资源。立即重用空间还可以进行优化，例如数据结构的就地更新。
• 易于实现： 就实现细节而言，基于引用计数的收集是最简单的垃圾回收机制。如果语言运行时不允许指针操作和/或程序员无法确定/操作对象根，则实现特别容易。
• 控制 vs 正确性：引用计数系统可以为程序员提供对对象分配和解除分配的完全控制。它可以允许程序员在其认为安全的地方优化引用计数开销。这确实带来了正确性挑战，并且需要更高的编码纪律。即使没有巧妙的优化，客户端程序的接口和引用计数方案之间也存在紧密耦合。它要求客户端正确调用增加/减少引用计数的操作。
• 空间开销： 每个对象承载引用计数字段的空间开销。理论上，对于非常小的对象，这可能相当于 50% 的开销。这种开销需要与内存单元的立即重用以及引用计数在收集期间不依赖于堆空间的事实相权衡。引用计数系统可以通过使用单个字节进行引用计数而不是使用全字来减少空间开销。这样的系统通过回退跟踪方案（如标记扫描）来增加引用计数，以收集具有最大引用计数（和循环引用）的对象。

缺点如下：

• 指针更新开销： 与指针更新是免费的跟踪方案不同，引用计数会带来很大的开销，因为每次指针更新都需要更新两个引用计数以保持程序的正确性。
• 原子化操作： 为了避免多线程竞争可能导致的对象释放过早，引用计数的增减操作记忆加载和存储指针的操作都必须是原子化的，而原子化的操作就需要解决很多线程竞争问题。
• 循环结构： 正如我们之前所讨论的，引用计数的最大缺点是它无法回收循环存储。在简单引用计数方法下，双向链表或非简单图等循环数据结构无法有效回收，并且会泄漏内存。

最坏情况下，某一个对象的引用计数可能等于堆中对象的总数，就导致引用计数所占的空间必须和某一个指针域大小相同，这一空间也会非常昂贵。

最后，引用计数算法仍有可能停顿的出现。当删除某一个大型结构根节点的最后一个引用时，该算法会递归的删除根节点的每一个子孙节点，线程安全的引用计数回收所导致的最大停顿时间可能会比追踪式回收器的长。

总结

引用计数就实现细节来说，是最简单的垃圾回收机制，因此在众多系统中得到广泛应用，包括如 Lisp、Awk、Perl 和 Python 等编程语言、部分应用程序如 Photoshop、Real Network的 Rhapsody 音乐服务，打印、扫描及文档管理系统）。

除了内存管理之外，引用计数还被广泛用作操作系统中的资源管理机制，用于管理文件、套接字等系统资源。

针对引用计数算法的两个问题：引用计数操作的开销问题和循环结构的循环引用问题，还有很多种提升方法。这一点下一篇文章再做介绍，感谢你能看到此处。

• Reference Counting - A Quick Primer on Garbage Collection Algorithms (educative.io)
• 垃圾回收算法手册：自动内存管理的艺术：第5章 引用计数