Go语言中的三色标记原理

发布于 1周前 作者 yuanlaile 最后一次编辑是 5天前 来自 问答

Go语言中的三色标记原理是什么，我们首先看一张图，大概就会对 三色标记法有一个大致的了解 root.png 原理： 首先把所有的对象都放到白色的集合中

  • 从根节点开始遍历对象，遍历到的白色对象从白色集合中放到灰色集合中
  • 遍历灰色集合中的对象，把灰色对象引用的白色集合的对象放入到灰色集 合中，同时把遍历过的灰色集合中的对象放到黑色的集合中
  • 循环步骤 3，知道灰色集合中没有对象
  • 步骤 4 结束后，白色集合中的对象就是不可达对象，也就是垃圾，进行回
1 回复

在Go语言中，三色标记（Tri-color Marking）是一种用于垃圾收集（GC）中的常见算法，特别是在并发垃圾收集器中。该算法通过标记对象的方式，帮助确定哪些内存是存活（可达）的，哪些是可以回收的。三色标记将对象分为三种颜色：

  • 白色（White）：尚未被访问到的对象，垃圾收集器初始时认为所有对象都是白色的。
  • 灰色（Gray）：已经被访问到，但其引用的对象还未被访问的对象。灰色对象是后续遍历的起点。
  • 黑色（Black）：自身及引用的所有对象都已经被访问过的对象，即已完成扫描的对象。

基本流程

  1. 初始标记：所有对象均为白色，根集合（如全局变量、活跃线程的栈上引用等）中的对象被标记为灰色。
  2. 遍历灰色对象：
    • 将灰色对象标记为黑色。
    • 访问灰色对象引用的所有白色对象，并将它们标记为灰色。
    • 重复此过程，直到没有灰色对象为止。
  3. 垃圾回收：所有白色对象都是不可达的，可以被回收。

示例（伪代码）

由于Go语言的GC实现较为复杂且涉及到底层细节，这里提供一个简化的三色标记算法的伪代码示例：

type Color int

const (
    White Color = iota
    Gray
    Black
)

type Object struct {
    color   Color
    refs    []*Object // 指向其他对象的引用
    // 其他字段...
}

var (
    worklist []*Object // 灰色对象的工作列表
    roots    []*Object // 根集合中的对象
)

func markAndSweep() {
    // 初始化：所有对象为白色，根集合中的对象为灰色
    for _, root := range roots {
        root.color = Gray
        worklist = append(worklist, root)
    }

    // 遍历灰色对象
    for len(worklist) > 0 {
        obj := worklist[0]
        worklist = worklist[1:]

        if obj.color == Black {
            continue // 如果已经是黑色，跳过
        }

        obj.color = Black // 标记为黑色

        // 遍历所有引用
        for _, ref := range obj.refs {
            if ref.color == White {
                ref.color = Gray
                worklist = append(worklist, ref)
            }
        }
    }

    // 此时，所有白色对象都可以被回收
    // ... 回收白色对象的逻辑
}

请注意，上述代码是一个非常简化的示例，实际的Go语言垃圾收集器要复杂得多，涉及到并发执行、写屏障（Write Barrier）等技术来确保在并发环境中三色标记的正确性。

回到顶部