垃圾回收算法——以Golang为例

常见垃圾回收机制分析以及Golang在GC方面的优化手段

垃圾回收算法——以Golang为例

垃圾回收机制在程序运行过程中显得必不可少。现如今人们已经开发出许多成熟的垃圾回收机制,它们被运用在不同的语言中,各自有各自的适用范围和好处。本文针对当前常见的几种垃圾回收机制进行简单的分析,并选择以当前新兴的Golang语言为例,由于Golang支持高并发处理,因此它的垃圾回收机制会变得更加复杂,因此本文也会对Golang高并发下的垃圾回收机制进行分析。

常见垃圾回收机制

目前常见的垃圾回收机制主要有三种,分别为引用计数算法、标记-清扫算法和三色标记算法。接下来对这三种算法做一下简单的介绍。

引用计数算法

引用计数法为每一个对象分配一个整数值,用于记录对象被引用的次数。每当有其他对象引用到此对象时,该整数值加一,而当其他对象不再引用时,该整数值减一。当系统检测出当前对象所分配的整数值降为0时,自动将其销毁。

这种做法实现逻辑简单,容易被理解。但是该算法最大的问题是循环引用的问题,有点类似于OS中的死锁。当两个对象同时引用了对方时,它们的引用计数都不会变为0,从而无法被垃圾回收机制回收。

以Java为例,考虑如下伪代码:

1
2
3
4
5
6
7
8
LoopObject objectA = new LoopObject();
LoopObject objectB = new LoopObject();
// A、B对象互相引入
objectA = objectB;
objectB = objectA;
// 回收
objectA = null;
objectB = null;

在以上情况中,执行objectA = null时,由于objectA正被objectB引用,引用计数不为0,因此无法被回收。同样,objectB = null也无法对B进行回收,造成了垃圾回收机制的异常。

标记-清扫算法

标记-清扫算法也是一种时间久远的回收算法,它在Golang1.5前曾经被使用过一段时间。与引用技术算法不同,执行回收之前,需要进行 ** 标记 *和 * 清扫 ** 两个部分。程序对目前所有存活的对象进行扫描,并将可以到达的对象标记为正常,而对于那些保持不可到达状态的对象,将其清扫并回收。

这种做法避免了引用计数算法中的因循环引用而不可回收的问题。垃圾处理机制以一种类似于树的结构,每一个对象看做一个节点,对象之间的引用看做是边。当从根节点完整遍历完树结构后,未能被遍历的对象就是需要被清楚的。这样,即使有循环引用,它们也会因为没有达到根节点的路径而被清除。

这种算法自然也有许多问题。最直接的就是性能问题,每次垃圾回收执行前都需要对树进行完整的遍历,需要花费大量的开销。另一个问题就是堆的碎片化问题,它是一种保守的内存分配机制,即不会改变已经分配且未被回收的内存,长时间运行后会导致堆内存碎片化。

三色标记算法

三色表计算法由Edsger W. Dijkstra 等大佬于1978年提出,它被应用于Golang1.5的垃圾回收机制。它将对象分为黑、白、灰三个集合,并遵循以下步骤——

(1) 首先将所有对象都存放在白色集合中
(2) 根节点进行遍历,将所有遍历到的对象存放进灰色集合。
(3) 遍历灰色集合,将其引用对象放入灰色队列,而自身标记为黑色。
(4) 重复步骤(3)直到灰色集合为空,此时白色集合中就是需要被回收的对象。

这种算法解决了前两种算法的部分问题,但是在Golang这种支持高并发的语言下,对象间的引用关系可能经常发生变化,可能会将对象放置在错误的集合中,还需要进一步改进。

Golang垃圾回收机制优化

Golang垃圾回收

在Golang1.5后,Golang的垃圾回收机制进行了大改,变为了三色标记算法,也终结了长期以来Golang垃圾回收的种种问题。官方文档中强调,他们GC是采用三色并发标记、混合写屏障以及非紧缩的。即他们在原先的三色标记算法中加入了并发处理的手段,同时将写屏障优化为混合写屏障。而非紧缩意味着在回收器处理过程中,依旧可以会出现堆空间碎片化的问题。

官方对于Golang垃圾回收机制的算法概括如下图所示:

由于Golang GC是一个相当宏大的讨论话题,它其中有着许多独特的特性,这里仅简单介绍它由写屏障过渡到混合写屏障的部分内容。

之前的规则中,我们没有考虑对象被修改的问题。例如,我们在对对象A扫描完成后,突然加入了对象B作为对象A的引用。这样,我们对于对象A的扫描就是不完整的。或者说,垃圾回收机制可能永远都无法察觉到对象B,因此Golang在最新版本中加入了混合写屏障的机制。

之前的版本中,如果在扫描完对象A后,对象A又对对象B进行引用。而此时,若对象A抛弃,则会将对象B留入下一轮搜索中,不会一起被抛弃。在混合写屏障中,会同时标记写入对象的原指针和新指针。这样即使出现对象A被扫描后对象B由C -> B变为A -> B,对象B仍然会在垃圾回收机制遍历对象C的时候被遍历到。这一优化既能防止此类对象的漏查,最主要的是能够减少“三色标记法”中的标记时间,进一步提高垃圾回收器性能。

应用于高并发下的sync.Pool

尽管目前已经有了许多优秀的垃圾回收机制,但是在面对高并发问题时,依然不能避免回收异常或者性能降低等问题。在这种情况下,Golang传统的垃圾回收机制也很难正常运行。因此,在高并发下,Golang推荐使用sync.Pool来解决问题。

为了减少传统GC在高并发下的问题,可以采用对象重用的方式从而减缓垃圾回收机制的压力,sync.Pool就是这样一个对象池。作为一个封装的文件,它面向公众的主要方法为Put和Get,实现过程也相当简单,如下所示——

1
2
3
4
5
6
7
8
9
10
11
12
13
package main

import (
"fmt"
"sync"
)

func main() {
pool := new(sync.Pool)
pool.Put("test")
test := pool.Get()
fmt.Print(test)
}

上面这段代码首先创建了一个sync.Pool对象池,并向其中Put一个string类型的对象,再利用Put方法将对象取出。那么Golang是如何在高并发下利用该对象池做到高效的呢?

首先,这里简单介绍一下golang调度器的底层实现(G, M, P)。官方文档给出的介绍如下——

Runtime keeps track of each G and maps them onto Logical Processors,named P. P can be seen as a abstract resource or a context,which needs to be acquired,so that OS thread (called M,or Machine) can execute G .

简单说,G代表一段需要被执行的Go语言代码;M代表一个内核线程,P代表内核线程所需的上下文环境。当需要大量并发执行多段G时,sync.Pool为每个P分配了一个子池,其中每个子池都都维护一个私有对象和共享对象的列表。私有对象只能被其对应的P访问,而共享对象可以被其他P所访问。

在此基础上,在sync.Pool中,当某个P中需要获取对象时,需要遵循以下步骤——

(1) 尝试从P的私有对象列表中获取对象。
(2) 若私有对象中未能获取到,就去当前P下的共享对象列表中寻找。此时,从共享列表中获取对象已经不再安全,因此该过程需要加上互斥锁。
(3) 如果当前P下的共享对象列表仍无结果,则需在其他P子池中的共享对象列表进行搜索。
(4) 若还未搜索到,则确认该对象不存在,根据需要New一个新的对象或者返回空指针。

总体来说,sync.Pool减少了加锁的开销,即避免了同一个子池中私有对象的竞争,也增加了对象重用的机制,从而辅助减缓了高并发问题下垃圾回收机制的压力。

总结

本文主要分析了一些常见的垃圾回收机制,包括引用计数算法、标记清扫算法和三色标记算法,同时简单介绍了Golang语言不同版本下采用的垃圾回收机制。之后,又提到了当前Golang版本中对垃圾优化机制的两种优化手段,即混合写入屏障和sync.Pool,它们分别解决了三色-标记法中的标记遗漏现象以及高并发下的性能问题。今后我也会争取细致地研究Golang GC的内部实现代码,努力搞清其中的细节问题。

文章目录
  1. 1. 垃圾回收算法——以Golang为例
    1. 1.1. 常见垃圾回收机制
      1. 1.1.1. 引用计数算法
      2. 1.1.2. 标记-清扫算法
      3. 1.1.3. 三色标记算法
    2. 1.2. Golang垃圾回收机制优化
      1. 1.2.1. Golang垃圾回收
      2. 1.2.2. 应用于高并发下的sync.Pool
    3. 1.3. 总结