垃圾回收GC

现代语言中,大多数都实现了垃圾回收功能,不再需要开发者自己来释放无用的内存资源,大大提高了开发效率。

历史

1960 年前后诞生于 MIT 的 Lisp 语言是第一种高度依赖于动态内存分配技术的语言。Lisp 中几乎所有数据都以“表”的形式出现,而“表”所占用的空间则是在堆中动态分配得到的。 Lisp 语言先天就具有的动态内存管理特性要求Lisp 语言的设计者必须解决堆中每一个内存块的自动释放问题,否则,Lisp 程序员就必然被程序中不计其数的 free / delete 语句淹没,这直接导致了垃圾收集技术的诞生和发展。

在学校和工作中,我使用过c/c++这种需要开发者自己来维护内存,时时刻刻需要小心内存泄露的问题,也使用过pythongolangjs以及java这种不需要关系内存资源的释放,让自己更加专注于程序的设计和开发,但是也带来了性能的损耗。

垃圾回收GC并不是万能的,如果你接受了它的便利,那么你也需要接受GC带来的性能开销。

内存分配

内存分配大概分为三种:静态分配、局部分配以及动态分配。

1
2
3
4
5
6
7
8
9
静态分配( Static Allocation ):
静态变量和全局变量的分配形式。通常,它们无需释放和回收。

自动分配( Automatic Allocation ):
在栈中为局部变量分配内存的方法。栈中的内存可以随着代码块退出时的出栈操作被自动释放。

动态分配( Dynamic Allocation ):
在堆中动态分配内存空间以存储数据的方式。堆中的内存需要开发者自己来管理,谨慎对待每一个动态分配的对象,避免造成内存泄露。
在软件开发中,如果你懒得释放内存,那么你也需要一台类似的机器人——这其实就是一个由特定算法实现的垃圾收集器。

因此,垃圾回收的目的是回收动态分配的内存

垃圾回收GC

垃圾回收技术主要包括:引用计数、跟踪式以及分代。

引用计数

引用计数Reference Counting为每个内存对象维护一个引用计数器,

1
2
3
4
5
6
7
8
9
10
11
// 新的引用指向某对象时,该对象引用计数器加1
if add refrence:
counter +=1

// 对象的引用被销毁时,该对象引用计数器减1
if remove refrence:
counter -= 1

// 对象的计数器归零时,回收该对象所占用的内存资源
if counter == 0:
free object

每个计数器只记录了其对应对象的局部信息-被引用的次数,而没有全局的应用信息。

由于只维护局部信息,所以不需要扫描全局对象图就可以识别并释放死对象,但也因为缺乏全局对象图信息,所以无法处理循环引用的状况。

循环引用?

A引用B,B又引用了A,那么A和B引用计数器的值均为1,无法释放该资源。

1
2
A <- B
B <- A

优点 & 缺点

1
2
3
4
5
6
7
8
优点
- 每次创建和销毁都要更新引用计数值,会引起额外的开销
- 计数简单,只需要记录自身被引用次数
- 实时的垃圾回收,不会造成中断

缺点
- 无法处理循环引用
- 多线程对同一对象计数更新产设个竞争

Python使用了引用计数算法,为了解决循环引用的问题还设计了其他GC模块(标记清除分代收集)。
此外,Python为了解决引用技术的性能问题还引入了内存池机制。

跟踪式

跟踪式垃圾回收是比较常见的垃圾回收技术,主要原则是从程序栈的若干个根对象出发,构造一个可达链,对于那些不可达的内存对象,做回收。

如果一个内存对象有被程序中的至少一个变量引用(直接指向或间接指向),则认为该对象可达,否则认为该对象不可达,可以被垃圾回收。

标记清除

标记清除Mark-Sweep的基本思路是遍历以对象为节点、以引用为边构成的图,把所有可以访问到的对象打上标记,然后清扫一遍内存空间,把所有没标记的对象释放。

具体过程分两步:

  • 从根(Root)开始遍历,被根引用了的对象标记为非垃圾对象,非垃圾对象引用的对象同样标记为非垃圾对象,以此递归直到标记完所有对象;
  • 再次从根节点开始,对已被标记为垃圾的对象清除释放。

如图,红色代表垃圾对象,黄色代表非垃圾对象,绿色代表未使用空间。

缺点:内存碎片

由于标记清除不需要移动对象的位置,直接回收垃圾对象必然会造成内存碎片

标记复制

标记复制 Mark-Copy只需要对对象进行一次遍历。

它的基本思想是利用空间换时间,从根开始开始遍历对象,如果对象仍然存在引用,就把它复制到新的内存空间中,一次遍历结束之后,所有存在于新空间的对象就是所有的非垃圾对象,可直接释放掉原有内存空间,不会造成内存碎片。

如图,红色代表垃圾对象,黄色代表非垃圾对象,绿色代表未使用空间。

缺点:浪费内存

标记复制更快速但是需要额外开辟一块用来复制的内存,对垃圾比例较大的情况占优势。

此外,内存空间切换过程中需要暂停程序运行(也就是常说GC停顿)。

标记压缩

标记压缩Mark-Compact是在标记清除算法的基础之上增加对象的移动,从而解决内存碎片的问题。

在压缩阶段,由于要移动可达对象,那么需要考虑移动对象时的顺序,一般分为下面三种:

  • 任意顺序 - 即不考虑原先对象的排列顺序,也不考虑对象间的引用关系,随意的移动可达对象,这样可能会有内存访问的局部性问题。

  • 线性顺序 - 在重新排列对象时,会考虑对象间的引用关系,比如A对象引用了B对象,那么就会尽可能的将A,B对象排列在一起。

  • 滑动顺序 - 顾名思义,就是在重新排列对象时,将对象按照原先堆内存中的排列顺序滑动到堆的一端。

现在大多数的垃圾收集算法都是按照任意顺序或滑动顺序去实现的(由于线性顺序需要考虑对象的引用关系所以实现复杂)。

Two-Finger 算法数据移动过程类似快排,分别用两个指针指向内存的两端,分别向中心移动。如果右侧指针遇到垃圾数据直接回收,否则,移动左侧指针直到遇到可替换垃圾对象,然后替换左右指针的对象。

缺点:移动对象的代价

为了避免内存碎片,移动对象需要遍历整个内存空间,还需要暂停程序更换映射地址空间。

分代回收

分代回收是根据对象的存活周期的不同将内存划分为几块。一般把java堆分为新生代和老年代,这样就可以根据各个年代的特点采用最适当的收集算法。

年轻代垃圾回收

年轻代回收特点:

  • 新对象的内存分配都是先在Eden区域中进行的;
  • 当Eden区域的空间不足于分配新对象时,就会触发年轻代上的垃圾回收minor gc(minor garbage collection);
  • 每个对象都有一个年龄,代表对象经历过的minor gc的次数;
  • 当触发minor gc后,所有存活的对象都会被拷贝到一个新的survivor区域,并且年龄增加1;当对象的年龄足够大,它会从survivor内存区域升级到老年代中。

年老代垃圾回收

当老年代内存区域(图中Tenured)无法容纳新对象时,这时候就会触发老年代的垃圾回收major gc(major garbage collection”)。

垃圾回收算法PSCMS

常用的垃圾回收算法有Parallel Scavenge(PS)Concurrent Mark Sweep(CMS),它们的不同之处体现在年老代的垃圾回收过程中,而年轻代的垃圾回收过程在这两种垃圾回收器中基本上是一致的。PS在执行垃圾回收时使用了多线程来一起进行垃圾回收,这样可以提高垃圾回收的效率,CMS在进行垃圾回收时,应用程序可以同时运行。

在年轻代中,每次垃圾收集时都发现有大批对象死去,只有少量存活,那就选用复制算法,只需要付出少量存活对象的复制成本就可以完成收集。而老年代中因为对象存活率高、没有额外空间对他进行分配担保,就必须使用“标记-整理”算法进行回收。

Parallel Scavenge

PS垃圾回收是由标记清除标记压缩算法组成。

标记清除算法的一个缺陷就是它会引起内存碎片问题。继而有可能会引发连续的major gc。假设当前存在的内存碎片有10M,但最大的内存碎片只能容纳2M的对象,这个时候如果有一个3M的对象从Survivor区域升级到Tenured区域,那Tenured区域也没有办法存放这个3M的对象。结果就是不断的触发major gc,直到Out of Memory。所以,PS垃圾回收器在清除非可达对象后,还会进行一次compact,来消除内存碎片。

Concurrent Mark Sweep

CMS在进行垃圾收集时,应用程序是可以并行运行的,因此,它减少了垃圾收集时暂停应用程序的时间。
垃圾回收的四个阶段如下,

1
2
3
4
5
6
7
8
9
10
11
12
1. Initial Mark阶段
程序暂停运行`Stop-The-Word`,标记到根对象的第一层孩子节点即停止 ,然后程序恢复运行。由于只标记一层节点,所以暂停时间很短。

2. Concurrent Mark阶段
以Initial Mark阶段标记的节点为根对象,重新开始标记Tenured区域中的可达对象(不需要暂停应用程序,因此称为"Concurrent Mark")。
由于CMS垃圾回收器和应用程序同时运行,Concurrent Mark阶段它并不保证在Tenured区域的可达对象都被标记了(分配新对象)。

3. Remark阶段
暂停应用程序,确保所有的可达对象都被标记(Concurrent Mark阶段未标记的,`可多线程标记`)。

4. Concurrent Sweep阶段
恢复应用程序的执行,执行sweep来清除所有非可达对象所占用的内存空间。

PS相比,CS垃圾回收算法可以减少程序暂停的时间。

Garbage First

CMS垃圾收集器虽然减少了暂停应用程序的运行时间,但是由于它没有Compact阶段,它还是存在着内存碎片问题。于是,为了去除内存碎片问题,同时又保留CMS垃圾收集器低暂停时间的优点,JAVA7发布了一个新的垃圾收集器 - G1垃圾收集器。

G1垃圾收集器和CMS垃圾收集器有几点不同,最大的不同是内存的组织方式变了。Eden,Survivor和Tenured等内存区域不再是连续的了,而是变成了一个个大小一样的region - 每个region从1M到32M不等。

G1垃圾回收的四个阶段如下,

1
2
3
4
5
6
7
8
9
10
11
12
13
1. Initial Mark阶段
同CMS垃圾收集器的Initial Mark阶段一样,程序暂停运行`Stop-The-Word`,标记到根对象的第一层孩子节点即停止 ,然后程序恢复运行。
由于只标记一层节点。但它不会单独暂停应用程序的执行,而是在G1触发minor gc是发生。

2. Concurrent Mark阶段
同CMS垃圾收集器的Concurrent Mark阶段一样,重新开始标记Tenured区域中的可达对象(不需要暂停应用程序)。
但G1还会回收掉Tenured region中对象的存活率很小或者基本没有对象存活的内存区域(不需要等待clean up阶段,因此成为Garbage First),并计算每个 region的对象存活率以供clean up阶段使用 。

3. Remark阶段
同CMS垃圾收集器的Remark阶段一样, 但G1采用一种叫做SATB(snapshot-at-the-begining)的算法能够在Remark阶段更快的标记可达对象。

4. Clean up/Copy阶段
与CMS中不同,它有一个Clean up/Copy阶段,在minor gc发生的同时G1会挑选出那些对象存活率低的region进行回收。

由于Initial Mark阶段和Clean up/Copy阶段都是跟minor gc同时发生的,相比于CMS,G1暂停应用程序的时间更少,从而提高了垃圾回收的效率。