内存管理：追踪垃圾回收与三色标记法详解
内存管理：追踪垃圾回收与三色标记法详解
本文将深入探讨内存管理中的垃圾回收机制，重点介绍标记清除算法及其优化方案三色标记法。通过图文结合的方式，帮助读者理解垃圾回收算法的工作原理。
0x00 追踪垃圾回收
不同于引用计数，追踪垃圾回收从根节点开始，追踪可达对象。根节点包括全局变量和调用栈中的局部变量。最简单的算法形式是标记清除算法 (mark-and-sweep) ，这也是追踪垃圾回收的关键思想。
从根节点开始标记可从根节点传递访问到的对象，一旦标记完成，未标记的对象即为不可达的。因此我们可以安全地清除 (收集) 未标记的对象。
考虑以下示例，它最终形成一个引用循环：
假设程序在这一点上耗尽了内存（←），然后触发了 标记清除算法：
在这个例子中，局部变量 x 是根节点，我们从这里开始追踪（可达的对象用 ■ 标记）：
现在，垃圾收集器（GC）清理未标记的内存对象，并将它们释放以供以后重用。
0x01 标记清除算法的缺陷
虽然该算法可以处理引用循环，但它必须在进行垃圾回收时暂停整个程序的执行。程序的执行必须被挂起，因此用户可能会感受到程序的间歇性冻结。对比一下，回想一下引用计数可以立即（但以运行时开销为代价）释放不可达内存。我们能否克服这个问题？换句话说，我们能否在程序执行的同时，实时进行该算法？
0x02 标记清除算法：三色标记法（Tri-color）
我们将使用三种颜色来标记内存对象：
- 黑色：表示我们已经完成了对这个对象的调查，并确认它是可达的
- 灰色：表示我们已经确认这个对象是可达的，但需要进一步调查这个对象的出边
- 白色：表示这个对象目前还未确认为可达
算法（非正式描述）：
- 将根对象初始化为灰色，其他对象初始化为白色
- 重复以下步骤，直到没有灰色对象为止：选择一个灰色对象，并将其直接后继标记为灰色*， 然后将选定的对象标记为黑色
- 清除仍然保持白色的对象
让我们使用前面的例子来说明带三色标记和扫描的操作：
三色标记的关键在于它可以与程序执行同时进行。假设在这一点上（←）GC 在并发执行一段时间，它不必完成扫描。然后，程序恢复并继续执行，直到这一点（←）。GC 也继续执行，并标记所有可达的内存对象。
请注意，程序执行必须仔细决定对象的颜色（否则，GC 将无法工作）。例如，如果程序分配了一个新对象，并使其被一个黑色对象指向，那么它必须被标记为灰色。
0x03 可达 ≠ 将被使用
到目前为止，我们已经讨论了如何收集和释放不可达的内存对象。然而，请注意，即使一个对象是可达的，它可能在程序终止之前不再被使用。一般来说，准确预测一个对象是否会被使用是不可能的。因此，我们必须进行保守的估计，如果一个对象不可达，可以确保它在程序中不会再被使用。因此我们可以安全地释放它。