图片已更新

首先要知道怎么标记垃圾(引用计数,根可达两种标记),再就是常用的垃圾回收算法(golang使用三色标记法,jvm使用分代回收法),然后关于写屏障有两种写屏障及过程(插入写屏障,删除写屏障),写屏障解决的问题(三色标记法错标或漏标问题)

1.垃圾定位算法

(1)引用计数法

通常C++通过指针引用计数来回收对象,但是这不能处理循环引用,原理是在每个对象内部维护一个引用计数,当对象被引用时引用计数加一,当对象不被引用时引用计数减一。当引用计数为 0 时,自动销毁对象。

(2)根可达算法

从GC Roots向下搜索,搜索所走过的路径称为引用链,当一个对象到GC Roots没有任何引用链(即GC Roots到对象不可达)时,则证明此对象是不可用的,向JAVA、Go这种带有GC功能的高级语言使用的都是这种定位算法

简单来讲,从根对象往下查找引用,可以查找到的引用标记成可达,直到算法结束之后,没有被标记的对象就是不可达的,就会被GC回收。

2.垃圾回收算法

(1)标记-清除

(2)复制

(3)标记-压缩

以上三种算法是传统的垃圾回收算法,第一种容易产生内存碎片,第二种不会生成内存碎片,但是由于是整块复制,所以STW较长,效率太低,第三种是前两种的结合

(4)分代模型

JVM做垃圾回收时常用的GC算法,分为年轻代和老年代,年轻代使用复制算法,老年代使用标记压缩或者标记清除。

在分代模型中,年轻代的回收算法有ParNew、Serial、Parallel Scavenge,老年代的回收算法有CMS、Serial Old、Parallel Old,年轻代和老年代的回收算法一定是成对出现的,常见的回收对是ParNew-CMS、Serial-Serial Old、Parallel Scavenge-Parallel Old(jdk1.8默认)

另外jdk1.8可以用上面的分代模型,也可以使用不分代模型,即G1、ZGC等

(5)三色标记法

三色标记法是传统 Mark-Sweep 的一个改进,它是一个并发的 GC 算法。其实大部分的工作还是在标记垃圾,基本原理基于根可达

golang使用三色标记法来标记垃圾并回收

步骤:

a. 首先初始状态下所有对象都是白色的

b.从根对象开始遍历所有对象,将遍历到的对象从白色集合方放到灰色集合

c.遍历灰色集合中的对象将灰色对象引用的对象从白色集合放到灰色集合里面,此灰色对象放进黑色集合

d.重复c直到灰色集合为空

e.通过写屏障检测对象发生变化,重复上面操作

f.收集所有白色对象(垃圾)

3.三色标记算法标记垃圾会产生的问题

A对象已经标记并且引用的对象B也已经被标记,所以A放到黑色集合里,B对象被标记但是C对象还没标记,所以B是灰色

(1)浮动垃圾

如果B到C的引用断开,那么B找不到引用会被标黑,此时C就成了浮动垃圾,这种情况不碍事,大不了下次GC再收集

(2)漏标或者错标或者称作悬挂指针

但是如果此时用户goroutine新建对象A对对象C的引用,也就是从已经被标记成黑色的对象新建了引用指向了白色对象,因为A已经标黑,此时C将作为白色不可达对象被收集,这就出大问题了,程序里面A对象还正在引用C对象,但是GC把C对象看成垃圾给回收了,造成空指针异常。

4.写屏障

为了解决漏标的问题,需要使用写屏障,原理就是当A对象被标黑,此时A又引用C,就把C变灰入队

写屏障一定是在进行内存写操作之前执行的。

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

Go 语言中使用两种写屏障技术,分别是 Dijkstra 提出的插入写屏障和 Yuasa 提出的删除写屏障。

(1)插入写屏障

# 伪代码
writePointer(slot, ptr):
    shade(ptr)
    *slot = ptr

上述插入写屏障的伪代码非常好理解,每当我们执行类似 *slot = ptr 的表达式时,我们会执行上述写屏障通过 shade 函数尝试改变指针的颜色。如果 ptr 指针是白色的,那么该函数会将该对象设置成灰色,其他情况则保持不变.

  1. 垃圾收集器将根对象指向 A 对象标记成黑色并将 A 对象指向的对象 B 标记成灰色;
  2. 用户程序修改 A 对象的指针,将原本指向 B 对象的指针指向 C 对象,这时触发写屏障将 C 对象标记成灰色;
  3. 垃圾收集器依次遍历程序中的其他灰色对象,将它们分别标记成黑色;

说人话,就是如果两个对象之间新建立引用,那么引用指向的对象就会被标记为灰色以满足强三色不变性,这是一种相对保守的屏障技术。

插入写屏障的缺点:

因为栈上的对象在垃圾收集中也会被认为是根对象,所以为了保证内存的安全,Dijkstra 必须为栈上的对象增加写屏障或者在标记阶段完成重新对栈上的对象进行扫描,这两种方法各有各的缺点,前者会大幅度增加写入指针的额外开销,后者重新扫描栈对象时需要暂停程序。

(2)删除写屏障

# 伪代码
writePointer(slot, ptr)
    shade(*slot)
    *slot = ptr

上述代码会在老对象的引用被删除时,将白色的老对象涂成灰色,这样删除写屏障就可以保证弱三色不变性,老对象引用的下游对象一定可以被灰色对象引用。

  1. 垃圾收集器将根对象指向 A 对象标记成黑色并将 A 对象指向的对象 B 标记成灰色;
  2. 用户程序将 A 对象原本指向 B 的指针指向 C,触发删除写屏障,但是因为 B 对象已经是灰色的,所以不做改变;
  3. 用户程序将 B 对象原本指向 C 的指针删除,触发删除写屏障,白色的 C 对象被涂成灰色
  4. 垃圾收集器依次遍历程序中的其他灰色对象,将它们分别标记成黑色;

说人话,如果一个灰色对象指向一个白色对象的引用被删除,那么在删除之前写屏障检测到内存变化,就会把这个白色对象标灰。

总结

Go的垃圾回收官方形容为 非分代 非紧缩 写屏障 并发标记清理

非分代是golang GC区别于JVM GC分代模型的特点;非紧缩意味着在回收垃圾的过程中,不需要像复制算法那样移动内存中的对象,这样避免STW过长;标记清理算法的字面解释,就是将可达的内存块进行标记mark,最后没有标记的不可达内存块将进行清理sweep;Golang中实现标记功能的算法就是三色标记法,Golang里面三色标记法会造成错标问题,使用写屏障来解决这种问题,而JVM里面的CMS和G1解决错标或者漏标问题的算法分别是Increment Update和SATB