GC 三色标记法

三色标记法的基本概念

1. 白色（White）：

   • 这些对象尚未被垃圾回收器检查过。
   • 在标记阶段结束时，所有白色对象都是不可达的，将被回收。

2. 灰色（Gray）：

   • 这些对象已经被检查，但它们的子对象尚未被检查。
   • 垃圾回收器会继续遍历这些对象的子对象。

3. 黑色（Black）：

   • 这些对象和它们的子对象都已被检查过。
   • 这些对象是可达的，不会被回收。

三色标记法的工作流程

三色标记法通常分为以下几个阶段：

1. 初始化：

   • 所有对象最初都是白色。
   • 根对象（Root objects，例如全局变量、堆栈变量等）被标记为灰色。

2. 标记阶段：

   • 垃圾回收器从根对象开始，将灰色对象的所有子对象标记为灰色，并将自己标记为黑色。
   • 重复这个过程，直到没有灰色对象为止。

3. 清除阶段：

   • 所有仍然是白色的对象都是不可达的，将被回收。

增量式标记和并发标记

Go 的垃圾回收器为了减少对应用程序的暂停时间，使用了增量式标记和并发标记技术。

• 增量式标记：

  • 标记阶段与应用程序的执行交替进行。每次垃圾回收器运行时只标记一小部分对象，这样可以减少单次垃圾回收对应用程序的影响。

• 并发标记：

  • 标记阶段与应用程序并发运行。垃圾回收器在后台标记对象，应用程序继续运行和分配内存。这种方式减少了全局暂停时间，提高了应用程序的响应性。

写屏障（Write Barrier）

在并发标记过程中，为了确保垃圾回收器在应用程序运行时能够正确标记对象，使用了写屏障机制。写屏障是一种在对象引用发生变化时触发的机制，用于维护三色不变性（tricolor invariants）。

• 维护三色不变性：写屏障保证在对象引用变化时，及时更新相应的颜色状态，确保没有未标记的可达对象被误回收。

示例

以下是一个简单示例，展示了三色标记法的基本思想：

package main

type Node struct {
    Value int
    Next  *Node
}

func main() {
    // 创建链表节点
    n1 := &Node{Value: 1}
    n2 := &Node{Value: 2}
    n3 := &Node{Value: 3}

    // 连接节点
    n1.Next = n2
    n2.Next = n3

    // 此时 n1, n2, n3 都是黑色（根对象及其可达对象）

    // 将 n2 的 Next 设置为 nil
    n2.Next = nil

    // 触发垃圾回收
    runtime.GC()

    // n3 是白色（不可达），将被回收
}

总结

三色标记法通过将对象分为白色、灰色和黑色三种颜色，并结合增量式和并发标记技术，有效地减少了垃圾回收对应用程序的暂停时间。写屏障机制确保在并发标记过程中，引用变化不会破坏标记过程的正确性，从而提高了垃圾回收器的效率和准确性。Go 语言通过这些技术，实现了高效的自动内存管理。