标记-清除法

标记-清除法(Mark-Sweep)是一种基于追踪回收(tracing GC)技术的垃圾回收算法。它分为两个阶段:

mark-and-sweep.gif

标记-清除法的缺点是回收期间会 STW(Stop The World)。


三色标记法

针对原生标记-清除法标记过程会 STW 的缺点,三色标记法(Tri-Color Marking)改进了标记方案。三色标记法将所有对象分成三类:

三色标记法的过程如下:

因为黑色对象不会引用任何白色对象,所以可以在处理完灰色对象之后,立即回收白色对象。此算法的最大特点是标记过程可以与用户程序并行运行(需要其它技术追踪标记过程中的对象引用变更)

tri-color-marking.gif


GC in Go

Golang GC 使用的是三色标记法方案,并且支持并行 GC,即用户程序可以与 GC 任务同时运行。其过程如下:

  1. Mark

    1. Mark Prepare:初始化 GC 任务,包括开启写屏障(Write Barrier)和辅助 GC(mutator assist)、统计 root object 数量等,这个过程会 STW
    2. GC Drains:扫描所有 root object,包括全局指针、Goroutine 栈上的指针,将其放到灰色队列,然后循环处理灰色队列中的对象,直到灰色队列为空,这个过程会在后台并行执行
  2. Mark Termination

    标记过程完成后,re-scan 全局指针和栈。因为标记过程和用户程序并行执行,所以需要通过写屏障(Write Barrier)来记录标记过程中的对象分配和指针赋值,然后 re-scan,这个过程也会 STW

  3. Sweep

    回收所有白色对象,这个过程会并行执行

  4. Sweep Termination

    清扫未清扫的 span注释1,只有在上一轮 GC 的清扫工作完成后,才能开启下一轮 GC

go-gc-phases.png


注释

注释1:

为了解决内存碎片的问题。Go 将内存块分成大小不同的 67 种,然后把这 67 种大内存块逐个拆分成小块,每个小块是一个 span。分配内存时,根据对象的大小选择长度相近的 span。这样就解决了内存碎片问题


原文地址

https://wudaijun.com/2017/12/gc-study/