共计 5966 个字符,预计需要花费 15 分钟才能阅读完成。
本文比照了四种语言在垃圾回收方面的实现,其指标都是雷同的,即心愿做到精确又高效的辨认和清理内存中的垃圾对象,不同语言之间在实现思路上有相似之处,又各自有不同的侧重点。
常见的垃圾回收算法
援用计数
给每个对象构造体附加一个援用计数的属性,当对象被赋值或援用时会减少援用计数,当对象销毁时缩小援用计数,当援用计数变为 0 时回收。
- 长处:实现简略,性能良好
- 毛病:无奈辨认循环援用的状况
- 代表语言:Python、PHP
标记 - 革除
从内存中一组 root object 根对象开始向下遍历并标记所有可能拜访到的对象,即 可达对象 ,相同没有被标记的对象即为 不可达对象,标记实现后将不可达对象革除。
- 长处:能够解决循环援用问题
- 毛病:须要 STW (Stop The World)暂停程序的执行,有性能损耗,这也是大部分标记革除类算法都在试图优化的中央。
- 代表语言:Go 的三色标记法是标记革除的变体;Python 和 PHP 也都有各自的标记革除变体实现,次要为了解决循环援用的问题。
分代回收
针对对象的生命周期长短不同将其划分到不同代,如年老代,老年代等;不同代采纳不同回收策略,例如年老代的对象可能刚调配不久就不再应用应该能够被回收,所以年老代触发 GC 较为高频,老年代的对象可能有历久弥坚的个性,始终存活到最初,所以触发 GC 较为低频。总的来说分代回收针对不同特点的数据启用不同策略,缩短 GC 工夫。
- 长处:缩小 STW 工夫,性能较稳固
- 毛病:实现逻辑较简单
- 代表语言:Java 是典型的分代回收的例子;Python 应用简化的分代回收策略来晋升回收效率
复制回收
将内存分为两块,每次只应用其中一块。垃圾回收时,将存活对象从一个块复制到另一个块,而后革除未复制的块。
- 长处:能够疾速回收对象,且没有内存碎片
- 毛病:须要额定的内存空间,复制对象时开销较大
- 代表语言:Lisp、Smalltalk
Python 的垃圾回收
不同的 Python 解释器实现有不同的垃圾回收形式,在 CPython 中以援用计数为主,附加标记革除的变体解决循环援用问题,另外附加分代回收进步垃圾回收的执行效率。
以援用计数为主:对象链表 refchain 和对象的援用计数 ob_refcnt
Python 中应用 refchain 双向循环链表保护所有对象,在对象的构造体中,ob_refcnt 是援用计数器
Python 对象的构造示意:
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ \
| *_gc_next | |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ | PyGC_Head
| *_gc_prev | |
object -----> +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ /
| ob_refcnt | \
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ | PyObject_HEAD
| *ob_type | |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ /
| ... |
应用标记革除的变体解决循环援用问题
循环援用只可能产生在容器类对象中,如 list、set、dict、类实例等,为了辨认并解决循环援用,Python 保护了两个双向链表,一个蕴含所有要扫描的对象 Objects to Scan,另一个蕴含临时无法访问的对象 Unreachable。
Python 中循环援用例子
>>> import gc
>>> class Link:
... def __init__(self, next_link=None):
... self.next_link = next_link
>>> link_3 = Link()
>>> link_2 = Link(link_3)
>>> link_1 = Link(link_2)
>>> link_3.next_link = link_1
>>> A = link_1
>>> del link_1, link_2, link_3
>>> link_4 = Link()
>>> link_4.next_link = link_4
>>> del link_4
# Collect the unreachable Link object (and its .__dict__ dict).
>>> gc.collect()
2
上述代码示意图如下:
两个链表如图所示,其中每个对象的 ref_count 是对象真正的援用计数,gc_ref 的值与 ref_count 雷同,用于辅助 GC 应用,目标是为了在 GC 时批改而不影响本来的援用计数。
当 GC 开始时将 Object to Scan 链表中所有对象的 gc_ref 减 1,这一步能够打消容器对象之间的援用。
如果此时 gc_ref>0,阐明还有容器对象之外的援用指向这个对象,即该对象是可拜访的。可拜访对象援用的对象也被视为是可拜访对象,而其余 gc_ref=0 的对象被挪动到 Unreachable 链表中
再次扫描整个链表,将所有可达对象从新移回 Objects to Scan 链表,而最终的 Unreachable 链表中的对象就是真正不可达对象,须要被回收。
应用分代回收晋升效率
为了限度每次垃圾收集所破费的工夫,Python 应用分代回收的思维晋升效率。分代回收假如大多数对象的寿命都很短,因而会在创立后不久就被收集。事实上大部分的程序十分合乎这一假如,许多长期对象的创立和销毁速度十分快。而对象越老,它变成不可拜访的可能性就越小。
Python 将所有容器对象都划分到三个代:0 代,1 代,2 代,如果对象在其所在的代的 GC 中存活下来,它将被挪动到下一个代。采纳分代回收机制,依据对象存活工夫的不同来辨别扫描的频次和机会,能够进步垃圾回收的效率。
那么应该在何时启动某一代的 GC 呢,gc.get_threshold
能够查看三个代垃圾回收的触发阈值:
>>> import gc
>>> gc.get_threshold()
(700, 10, 10)
# 另外 gc.set_threshold 能够设置阈值
三个阈值别离示意 GC 触发机会:
- 0 代:如果 0 代中对象数量达到 700 个则触发一次。
- 1 代:如果 0 代被扫描 10 次,则触发一次。
- 2 代:只有当
long_lived_pending / long_lived_total
大于 25% 时才会触发
PHP 的垃圾回收
PHP 的垃圾回收跟 Python 非常相似,都是应用援用计数联合标记革除的变体解决循环援用。
PHP 对象构造和援用计数
PHP 中的对象构造体中有一个 gc.refcount 属性示意援用计数,上面是一个 PHP 循环援用的例子:
$a = [1];
$a[] = &$a;
unset($a);
unset 掉 $a 之后:
遍历对象链表标记不可达对象
PHP 将可能存在循环援用的容器类对象放入一个 GC 缓冲链表,当缓冲链表中对象数量达到 10000 个则会触发一次 GC,步骤如下:
- 从 GC 缓冲链表头开始进行深度优先遍历,标记为 GC_GREY 灰色,并将援用计数减 1
-
再次遍历缓冲区链表,考查对象的援用计数是否为 0:
- 为 0,表明其是一个不可达对象,标记为 GC_WHITE 红色。
- 不为 0,表明还存在链表之外的援用,其是一个可达对象,标记为 GC_BLACK,并将援用计数加 1 复原。
- 最初遍历缓冲链表,将所有 GC_WHITE 红色对象移除。
Java 的垃圾回收
Java 采纳可达性剖析附加分代回收实现 GC。
GC root 和可达性剖析
GC root 指的是一组根对象 root object,这些对象被认为是内存中的起始点,它们间接或间接地援用了应用程序中的其余对象,因而,从这组根对象登程,能够通过一系列的援用关系遍历到所有可达的对象,而不可达的对象将被标记为垃圾并被回收。
GC Root 具体指的是:
- 虚拟机栈中的援用的对象
- 办法区中的类动态属性援用的对象
- 办法区中的常量援用的对象
- 本地办法栈中 JNI(Native 办法)的援用的对象
分代回收
内存划分为年老代和老年代,年老代分为 eden 区和 survivor0 survivor1 区。在年老代外部挪动采纳的是复制回收算法,即在 survivor0 和 survivor1 之间搬运。
Young GC
对象先在 Eden 区调配,当 Eden 满时触发 Young GC
当 Eden 满时,将存活的对象放入 S0,并将每个对象的年龄加一。
当 S0 满,将存活的对象放入 S1,对象年龄再加一。
S1 也满,则在挪动到 S0,对象年龄再加一,直到对象年龄达到 15 时,存活对象移入老年代
Full GC
老年代 FullGC 在多个状况下都会被触发:
- 产生 Young GC 之前进行查看,如果“老年代可用的间断内存空间”<“新生代历次 Young GC 后升入老年代的对象总和的均匀大小”,阐明本次 Young GC 后可能升入老年代的对象大小,可能超过了老年代以后可用内存空间,此时会触发 FullGC。
- 当老年代没有足够空间寄存对象时,会触发一次 FullGC。
- 如果元空间区域的内存达到了所设定的阈值 -XX:MetaspaceSize=,也会触发 FullGC
常见 Java 垃圾回收器
Serial Garbage Collector:单线程 GC
Parallel Garbage Collector:多线程 GC
CMS Garbage Collector:多线程 GC
G1 Garbage Collector:jdk7 引进的 GC,多线程,高并发,低暂停,逐渐取代 CMS GC
Go 垃圾回收
Go 采纳标记革除法的变体 - 三色标记法,附加混合写屏障实现垃圾回收。上面介绍 Go 不同版本从最开始的标记革除开始,逐渐演化成当初的三色标记加混合写屏障。
Go v1.3 之前标记革除
跟传统标记革除相似,从根对象遍历,标记出可达和不可达对象,将不可达对象革除,但整个过程须要 STW,性能不高。
Go v1.5 带 STW 的三色并发标记法
三色标记法,此时仍旧须要 STW
将所有对象演绎成三种色彩,三色概念的形象如下:
- 红色:可能是垃圾的对象
- 灰色:存活对象,但子对象待考查
- 彩色:存活对象
上面形容 GC 的过程
- 一开始将所有对象视为红色
- 从根对象开始考查可达对象,将可达对象自身记为灰色
- 遍历灰色汇合,将灰色对象自身记为彩色,并将其子对象记为灰色
- 反复第 3 步,直到灰色汇合没有对象,此时所有的彩色对象为存活对象,红色对象为垃圾对象要清理。
一开始所有对象都是红色
从根对象开始考查,将第一个对象记为灰色
之后遍历灰色汇合,将灰色对象记为彩色,并将其子对象记为灰色
反复上述步骤,直到灰色汇合清空,此时彩色对象就是存活对象,红色对象就是垃圾对象。
须要指出这个版本的三色标记还是须要 STW 的,即仍旧存在性能问题。
如果不应用 STW 会呈现什么状况
不应用 STW 就表明在标记对象的同时程序还在运行,程序有可能会批改对象的援用关系,这可能会导致对象被谬误的回收。
如图对象 3 本来在对象 2 的援用下,此时对象 2 是灰色,对象 3 是红色。
因为没有 STW 程序还在运行,程序让彩色对象 4 援用了红色对象 3,并且灰色对象 2 移除了红色对象 3。
这样就会导致当再次遍历灰色对象汇合时,将对象 2 挪动到彩色汇合之后,因为对象 2 不再持有对象 3 的援用,所以不会再考查对象 3,同时因为对象 4 曾经是彩色的考查过的对象,也不会再次考查对象 3,后果就是对象 3 被记为红色,最终被谬误地回收掉。
强弱三色不变性
如果既不想要 STW,又想确保不丢对象,就须要毁坏对象失落的前提条件。通过总结上述失落对象的过程能够发现,对象失落的前提条件有两个:
- 彩色对象援用了一个红色对象,即上图中黑 4 援用白 3
- 灰色对象与红色对象之间的援用关系受到毁坏,即上图中灰 2 移除掉白 3 的援用
如果同时满足上述两个条件,就可能会产生对象失落。那么如果不想产生对象失落,就能够毁坏掉这两个条件其一即可。
如此引出强弱三色不变性:
-
强三色不变性:彩色对象不能够指向红色对象,只能够指向灰色对象或者彩色对象;
-
弱三色不变性:彩色对象指向的红色对象必须蕴含一条从灰色对象经由多个红色对象的可达门路
插入屏障和删除屏障
基于上述两个准则衍生出两种屏障形式,插入屏障和删除屏障。
插入屏障
当 A 对象援用 B 对象时,将 B 对象被标记为灰色,使满足强三色不变性。
插入屏障的毛病:最初须要对栈空间进行 STW 从而二次扫描。这是因为因为栈空间应用频繁,插入屏障不在栈中应用,即如果在栈空间生成一个对象,新对象是一个红色对象。最终在革除垃圾对象前须要对栈空间进行一次 STW,从新执行一遍三色标记的流程,防止将新的红色对象谬误删除。
删除屏障
被删除援用的对象如果是红色,则标记为灰色,使满足弱三色不变性。
删除屏障的毛病:整体开始前须要对栈空间 STW,还是有损耗
Go v1.8 混合写屏障
混合写屏障综合了插入屏障和删除屏障,做到不丢对象又不须要 STW。(严格来说只在标记栈上对象时须要很短的 STW,除此之外不再须要 STW)
具体准则如下:
- GC 开始时将栈上对象全副扫描并记为彩色,这样就不须要最初的 STW 二次扫描了
- GC 期间,任何在栈上创立的新对象均标记为彩色
- 被删除的对象记为灰色
- 被插入的对象记为灰色
实际上是满足了弱三色不变性,即当对象有变动时将对象变为灰色,让该灰色及其之后的对象留有被扫描的机会。
如此一来基于上述准则,无论增加对象还是移除对象援用,都不会呈现丢对象的状况,也不须要长时间 STW。
总结
编程语言提供垃圾回收的目标是简化内存操作,防止内促泄露,加重开发者的老本,既然目标是统一的,面临的问题也是相似的,大抵上分为如何找到垃圾,如何革除垃圾两局部,而解决形式基本上是在几种惯例伎俩的根底上做衡量和取舍。
参考
Python 内存治理 & 垃圾回收原理:https://www.bilibili.com/video/BV1F54114761/
Python Developer’s Guide:https://devguide.python.org/internals/garbage-collector/
PHP 垃圾回收:https://www.kancloud.cn/nickbai/php7/363305
Java Young GC 和 Full GC:https://www.cnblogs.com/klvchen/articles/11758324.html
Java 垃圾回收算法及具体过程:https://xie.infoq.cn/article/9d4830f6c0c1e2df0753f9858
Python 和 Golang 的垃圾回收:https://www.yance.wiki/gc_go_py
混合写屏障:https://liqingqiya.github.io/golang/gc/ 垃圾回收 / 写屏障 /2020/07/24/gc5.html
三色标记混合写屏障:https://www.yuque.com/aceld/golang/zhzanb
本文由 mdnice 多平台公布