Golang的垃圾回收与三色标记法

关键词: 垃圾回收 内存管理 自动释放 三色标记 STW

一 STW

​ STW就是Stop the world的缩写或者Start the world的缩写。指从stop到start这两个动作直接的时间间隔,即万物都静止。

​ STW在垃圾回收过程中保证了实现的正确性、防止了在垃圾回收过程中内存的无限增长等问题,从而停止赋值器对操作对象图的操作过程。

​ STW的时间会影响系统的性能,在这个过程中,用户的代码被停止运行和放缓运行。STW越长,对用户代码造成的影响越大(延迟)。

​ 在Go1.14之前,没有异步抢占。for {} 这样的goroutine进不去STW阶段,就会造成卡机等现象。Go 1.14 之后,这类 goroutine 能够被异步地抢占,从而使得进入 STW 的时间不会超过抢占信号触发的周期,程序也不会因为仅仅等待一个 goroutine 的停止而停顿在进入 STW 之前的操作上。

二 标记-清除(-Go1.3)

  • 标记(Mark phase)
    1. 暂停程序的业务逻辑;
    2. 从程序根节点开始遍历所有对象,并标记可达对象;
  • 清除(Sweep phase)
    1. 清理未被标记的可达对象
    2. 停止暂停,使程序继续运行;不断循环此过程,直到进程结束;
  • 过程

    垃圾清除-1.3

    在1.3版本进行优化,将停止STW时间与Sweep清除进行交换;

  • 标记清除的缺点
    1. 需要STW进行程序暂停,严重的影响程序的性能;
    2. 在进行标记时,需要扫描整个程序的栈和堆区;
    3. 在清理数据的时候会产生堆碎片;

三 三色标记法-插入写屏障/删除写屏障(Go1.5)

  • 三色阶段

    ​ 对象的三色抽象与波面(wavefront)推进,三色抽象式描述追踪式回收器的方法;波面,即黑色对象与白色对象的边界,灰色对象就是波面;可以理解为灰色对象就是在每次进行更新对象颜色的中间过程;

    • 白色标记表[可能死亡]

      白色标记表的存放的是白色对象,白色对象在一开始GC的过程中,会将所有对象全部存放到白色标记表中,最后回收的就是白色标记表中的白色对象,即死亡对象,该对象均不可达;

    • 灰色标记表[波面]

      灰色标记表中是存放正在或将要被访问到的可达对象;其灰色对象可能还存在白色对象的引用;(我理解就是类似算法中对图遍历,使用的就是广度优先遍历,其存放的就是当前可达的节点对象);

    • 黑色标记表[存活对象]

      被扫描过的灰色对象,就会被标记为黑色,存放到黑色标记表中,黑色对象中的任何指针都不可能指向白色对象引用;

  • 三色标记的处理流程
    1. 垃圾回收开始时,将程序所有对象,包括新创建的对象,全部标记为白色,并将白色对象放入到白色标记表集合中;

      GC阶段1

      程序节点关系

    2. 从根节点开始,遍历所有对象,将可达的对象,从白色集合放入到灰色集合中,并将该可达对象颜色置为灰色;

      灰色波面推进

    3. 遍历灰色对象集合,将灰色对象引用的白色对象从白色集合放到灰色集合中,并将并将这些白色对象置为灰色,同时将遍历过的灰色对象放到黑色对象集合中,将这些灰色对象置为黑色;

    4. 重复步骤3,直到灰色对象集合为空;

    5. 回收白色标记表中的白色对象,该对象均不可达;

  • 无STW三色标记出现的问题
    • 问题

      在三色并发过程中出现的问题,如果不使用STW,在垃圾回收阶段,如果某个白色对象的引用被黑色对象所指向,并且与此同时,白色对象与祖先节点没有灰色对象,那么白色对象就会被丢失;如果使用STW,则效果和标记清除无异;

    • 根源
      1. 白色对象被黑色对象所引用(即黑色对象有指向白色对象的指针);
      2. 灰色对象与白色对象之间的可达关系遭到破坏;

      在无STW的情况下,同时满足1、2的情况下,就会出现可达对象丢失情况;

  • 问题解决
    • 强三色不变式

      黑色对象的指针不能指向白色对象

      强三色不变性

    • 弱三色不变式

      所有被黑色对象所引用的白色对象,其祖先节点必有灰色对象;换句话说,总有一个链路能可达该白色对象;

      弱三色不变性

  • 屏障

    基于上面两种方式,得到了两种屏障机制:

    • 并发插入写屏障
      • 插入写屏障

        在进行对象引用时,被引用的对象被标记为灰色;

      • 满足

        强三色不变式(不存在黑色对象引用白色对象,被引用的白色对象变为灰色对象)

      • 发生区域

        发送在堆区,只在堆空间对象使用该屏障机制,在栈空间的对象操作中不使用(栈内存区容量小,并且要求调用速度快,函数调用时频繁弹出使用);

      • 存在短暂STW

        由于屏障只发生在堆区,如果存在栈区的对象引用,则会丢失,因此在三色标记扫描结束后,会对栈区重新进行三色标记扫描,启动暂时的STW,直到栈空间三色标记结束;

      • 案例分析

        1. 程序在开始进行GC时,先将所有的对象全部标记为白色,并将白色对象放到白色标记集合中;

          全对象标记

        2. 从根节点开始,遍历从根节点的可达对象,并将可达节点从白色集合移动到灰色集合 ,并将对象置为灰色;

          从根节点遍历

        3. 紧接着从灰色标记集合中继续遍历可达对象,并将灰色集合中的对象放入到黑色集合,同时将这些灰色对象的可达节点对象,标志为灰色,从白色标记集合中移动到灰色集合;

          继续遍历灰色对象可达节点

        4. 在此同时,由于程序的并发,代码中对堆区的对象4添加对象8、给栈区的对象1添加了对象9的引用,由于插入写屏障只发生在堆区,所以,直接将对象8标记为灰色,对象9不做任何处理;

          并发在堆区与栈区添加新对象引用

          并发在堆区与栈区添加新对象引用

          堆区被引用对象直接变灰色

        5. 继续重复步骤3,直到灰色标记集合为空;

        6. 由于在栈区添加了对象引用,并且插入屏障不会起作用,所以对栈区启动短暂的STW,重新对栈区的全部对象,进行三色标记,从而保证了新添加的对象不丢弃;

          栈区STW再三色标记

        7. 在STW中,将栈中的对象进行一次三色标记,直到没有灰色对象;

          STW三色标记

        8. 最后将堆区与栈区的白色对象全部清除;

          最后清除白色对象

    • 并发删除写屏障
      • 删除写屏障

        删除写屏障,判断的就是在删除对象时,不管是白色对象还是灰色对象,都将其置为灰色;

      • 满足

        弱三色不变性,保护了灰色对象到白色对象的路径不会断;

      • 弊端

        被删除的对象,在本次GC过程中,还是不会被清理,只有在下一轮GC才会被删除;这样的方式是一种低回收精度;

四 混合写屏障机制(Go1.8)

  • 概述

    混合写屏障,综合了1.5GC方式中插入写屏障和删除写屏障的短板:

    插入写屏障: 只发生在堆区,对栈区的对象还有短暂的STW,完成对白色对象的清理;

    删除写屏障: 回收精度低,GC开始时STW扫描对栈区记录初始快照,这个过程会保护开始时刻存活的对象;

    混合写屏障,避免了对栈区的扫描与STW,极大了节省了STW的时间;

  • 混合写屏障规则
    • GC开始时,直接将栈上的对象全部置为黑色(不需要进行第二次重复扫描,减少STW时间)

    • 在GC期间,由于并发特性,任何在栈上产生的对象,全部置为黑色;

    • 被删除的对象,全部置为灰色;

    • 被添加的对象,全部置为灰色;

      注意: 为了保证运行效率,所有的屏障技术都不在栈上使用

  • 混合写屏障案例分析
    • 栈区引用堆区删除的对象
    • 栈区引用栈区删除的下游对象
    • 堆区引用了堆区删除的下游对象
    • 堆区引用栈区删除的对象

      分析方法同上,只要保证栈区不做任何屏障技术即可,堆区使用屏障技术;

五 总结

GoV1.3- 普通标记清除法,整体过程需要启动STW,效率极低。

GoV1.5- 三色标记法, 堆空间启动写屏障,栈空间不启动,全部扫描之后,需要重新扫描一次栈(需要STW),效率普通。

GoV1.8-三色标记法,混合写屏障机制, 栈空间不启动,堆空间启动。整个过程几乎不需要STW,效率较高。

六 观察GC的四种方式

  • 方式一:GODEBUG=gctrace=1
  • 方式二:go tool trace
  • 方式三:debug.ReadGCStats
  • 方式四: runtime.ReadMemStats
1
2
3
本文参考:
[作者: 刘丹冰 原文链接🔗]: https://www.kancloud.cn/aceld/golang/1958308#httpsimgkancloudcn452c452c55637b22078abad29786241d5000_1920x1080jpeghttpsimgkancloudcn42aa42aa1f73230061792851a43ce495acb6_1920x1080jpeg_370
[Go语言问题集]: https://www.bookstack.cn/read/qcrao-Go-Questions/spilt.1.GC-GC.md
本站总访问量 本站总访客数 本文总阅读量
载入天数...载入时分秒...