• 2

  • 481

  • 收藏

GO-Garbage Collection gc

3星期前

可以参考文档 zhuanlan.zhihu.com/p/77943973

Mark & Sweep

现代高级编程语言管理内存的方式分为两种:自动和手动,像 C、C++ 等编程语言使用手动管理内存的方式,工程师编写代码过程中需要主动申请或者释放内存;而 PHP、Java 和 Go 等语言使用自动的内存管理系统,有内存分配器和垃圾收集器来代为分配和回收内存,其中垃圾收集器就是我们常说的 GC。主流的垃圾回收算法:

  • 引用计数
  • 追踪式垃圾回收

Go 现在用的三色标记法就属于追踪式垃圾回收算法的一种。

大概原理就是一层一层去差没有追踪到的就是垃圾

STW

  • stop the world, GC 的一些阶段需要停止所有的 mutator 以确定当前的引用关系。
  • 这便是很多人对 GC 担心的来源,这也是 GC 算法优化的重点。

Root

  • 根对象是 mutator 不需要通过其他对象就可以直接访问到的对象。
    • 比如全局对象,栈对象中的数据等。
  • 通过Root对象。可以追踪到其他存活的对象。

Mark Sweep 两个阶段:标记(Mark)和 清除(Sweep)两个阶段,所以也叫

追踪式算法

这个算法就是严格按照追踪式算法的思路来实现的:

  • Stop the World 暂停程序
  • Mark:通过 Root 和 Root 直接间接访问到的对象, 来寻找所有可达的对象,并进行标记。
  • Sweep:对堆对象迭代,已标记的对象置位标记。所有未标记的对象加入freelist, 可用于再分配。
  • Start the Wrold 恢复程序

这个算法最大的问题是 GC 执行期间需要把整个程序完全暂停,朴素的 Mark Sweep 是整体 STW,并且分配速度慢,内存碎片率高。

标记过程需的要 STW,因为对象引用关系如果在标记阶段做了修改,会影响标记结果的正确性。

并发 GC 分为两层含义:

  • 每个 mark 或 sweep 本身是多个线程(协程)执行的(concurrent)
  • mutator(应用程序) 和 collector(垃圾回收器) 同时运行(background)

concurrent 这一层是比较好实现的, GC 时整体进行STW,那么对象引用关系不会再改变,对 mark 或者sweep 任务进行分块,就能多个线程(协程) conncurrent 执行任务 mark 或 sweep。

而对于 backgroud 这一层, 也就是说 mutator 和 mark,sweep 同时运行,则相对复杂。

  • 1.3以前的版本使用标记-清扫的方式,整个过程都需要 STW。
  • 1.3版本分离了标记和清扫的操作,标记过程STW,清扫过程并发执行。

1.3版本

backgroup sweep 是比较容易实现的,因为 mark 后,引用关系全部确定了, 哪些对象是存活,哪些是要被 sweep 是已知的,sweep 的是不再引用的对象(绿色的)。sweep 结束前,这些对象不会再被分配到,所以 sweep 和 mutator 运行共存。无论全局还是栈不可能能访问的到这些对象,可以安全清理。

1.5版本

1.5版本在标记过程中使用三色标记法。标记和清扫都并发执行的,但标记阶段的前后需要 STW 一定时间来做 GC 的准备工作和栈的re-scan。

为什么需要一段时间?

Tri-color Mark & Sweep

三色标记是对标记清除法的改进,标记清除法在整个执行时要求长时间 STW,Go 从1.5版本开始改为三色标记法, 初始将所有内存标记为白色, 然后将 roots 加入待扫描队列(进入队列即被视为变成灰色), 然后使用并发 goroutine 扫描队列中的指针,如果指针还引用了其他指针,那么被引用的也进入队列,被扫描的对象视为黑色。

白色对象:潜在的垃圾,其内存可能会被垃圾收集器回收。 黑色对象:活跃的对象,包括不存在任何引用外部指针的对象以及从根对象可达的对象,垃圾回收器不会扫描这些对象的子对象。 灰色对象 :活跃的对象,因为存在指向白色对象的外部指针,垃圾收集器会扫描这些对象的子对象。

Tri-color Marking

垃圾收集器从 root 开始然后跟随指针递归整个内存空间。分配于 noscan 的 span 的对象, 不会进行扫描。然而,此过程不是由同一个 goroutine 完成的,每个指针都排队在工作池中 然后,先看到的被标记为工作协程的后台协程从该池中出队,扫描对象,然后将在其中找到的指针排入队列。

Tri-color Coloring

染色流程:

  • step1 一开始所有对象被认为是白色
  • step2 根节点(stacks,heap,global variables)被染色为灰色
  • 一旦主流程走完,gc 会:
  • step3 选一个灰色对象,标记为黑色
  • step4 遍历这个对象的所有指针,标记所有其引用的对象为灰色
  • 最终直到所有对象需要被染色。

step1

step2

step3

step4

标记结束后

黑色对象是内存中正在使用的对象,而白色对象是要收集的对象。由于struct2的实例是在匿名函数中创建的,并且无法从堆栈访问,因此它保持为白色,可以清除。

颜色在内部实现原理:

每个 span 中有一个名为 gcmarkBits 的位图属性,该属性跟踪扫描,并将相应的位设置为1。

Write Barrier

1.5版本在标记过程中使用三色标记法。回收过程主要有四个阶段,其中,标记和清扫都并发执行的,但标记阶段的前后需要 STW 一定时间来做GC 的准备工作和栈的 re-scan。

使用并发的垃圾回收,也就是多个 Mutator 与 Mark 并发执行,想要在并发或者增量的标记算法中保证正确性,我们需要达成以下两种三色不变性(Tri-color invariant)中的任意一种:

  • 强三色不变性:黑色对象不会指向白色对象,只会指向灰色对象或者黑色对象。
  • 弱三色不变性 :黑色对象指向的白色对象必须包含一条从灰色对象经由多个白色对象的可达路径。

可以看出,一个白色对象被黑色对象引用,是注定无法通过这个黑色对象来保证自身存活的,与此同时,如果所有能到达它的灰色对象与它之间的可达关系全部遭到破坏,那么这个白色对象必然会被视为垃圾清除掉。 故当上述两个条件同时满足时,就会出现对象丢失的问题。如果这个白色对象下游还引用了其他对象,并且这条路径是指向下游对象的唯一路径,那么他们也是必死无疑的。

为了防止这种现象的发生,最简单的方式就是 STW,直接禁止掉其他用户程序对对象引用关系的干扰,但是 STW 的过程有明显的资源浪费,对所有的用户程序都有很大影响,如何能在保证对象不丢失的情况下合理的尽可能的提高 GC 效率,减少 STW 时间呢?

Stop The World

免责声明:文章版权归原作者所有,其内容与观点不代表Unitimes立场,亦不构成任何投资意见或建议。

php

481

相关文章推荐

未登录头像

暂无评论