深入研究虚拟机之垃圾收集(GC)算法实现

发表于2016-01-08
评论5 2.6k浏览

一、         What, Why

1.   GC是什么为什么需要GC

GC全写是Garbage Collection , 即垃圾回收。GC是一种自动内存管理机制。通常我们在需要时手动的分配内存,在不需要某块内存时再手动的释放内存,但是当系统足够复杂时判断某个内存区域是否需要释放是一件很麻烦的事情,必须小心的对待否则可能导致内存泄漏或者系统崩溃。自动内存管理机制可以自动的判断指定的内存区域是否需要被释放,安全的释放指定的内存区域,进而提高开发效率和提升系统的安全性,某些算法还可以提高系统运行性能

二、         讨论要点

这篇文章要讨论的并不是GC优化,而是GC算法的实现要解决的主要问题是如何选择和实现一个合适的GC算法中间涉及到一些有关性能的问题,因为有些GC算法本身就是基于性能的考虑设计的这里介绍的是GC算法的一些经典实现,同一种算法在实际应用中可能在实现上会有同,在有些情况下多种GC算法组合使用。

三、         算法分类

1.   引用计数GC和追踪式GC

引用计数GC

引用计数式GC通过额外的计数域来实时计算对单个对象的引用次数,当引用次数为0时回收对象。引用计数式GC是实时的。

 

追踪式GC:

追踪式GC算法在达到GC条件时通过扫描系统中是否有到对象的引用来判断对象是否存活,然后回收无用对象

2.   保守式(Conservative)GC和精确式GC

精确式GC

精确式GC是指回收过程中能准确的识别和回收每一个无用对象的GC方式,为了准确识别每一个对象的引用,通常要求一些额外的数据,这些数据通常对用户程序是透明的

 

保守式GC:

和精确式GC相反,保守式GC不能准确的识别每一个无用对象,但是能保证在不会错误的回收存活的对象的情况下回收一部分无用对象。保守式GC并不需要额外的数据来支持查找对对象的引用,它将所有内存数据假定为指针,通过一些条件来判定这个指针是否是一个合法的对象的引用

 

3.   搬迁式和非搬迁式

搬迁式GC:

搬迁式GCGC过程中需要移动对象内存位置,当然移动对象位置后需要将所有引用到这个对象的地方更新到新位置。

 

搬迁式GC:

搬迁式GC相反,GC过程中需要移动对象内存位置。

 

4.   实时和非实时GC

实时GC:

实时GC不需要停止用户程序执行的GC方式

 

非实时GC:

实时GC相反,实时GC执行过程中必须停止用户程序执行

 

5.   渐进和非渐近式GC

渐进GC:

和实时GC一样不需要中断用户程序运行,不同的地方在于渐进式GC不会在对象抛弃时立即回收占用的内存资源而是在达成GC条件时统一进行回收操作

 

四、         算法

1.    引用计数

1)   引用计数

引用计数算法是即时的,渐近的,对于交互式和实时系统比较友好,因为它几乎不会对用户程序造成明显的(注1)

 

分类:引用计数式,精确,实时,非搬迁式,渐近式

 

优点:

  • 引用计数方法是渐式的,它能及时释放无用的对象,将内存管理的的开销实时的分布在用户程序运行过程中

 

缺点:

  • 引用计数方法要求修改一个对象引用时必须调整旧对象的引用计数和新对象的引用计数,这些操作增加了指针复制的成本在总体开销上而言通常比追踪式GC要大
  •  引用计数要求额外的空间来保存计数值,通常要求框架和编译器支持
  • 实际应用中很多对象的生命周期很短,频繁的分配和释放导致内存碎片化严重。内存碎片意味着可用内存在总数量上足够但由于不连续因而实际上不可用,同时增加内存分配的时间
  • 引用计数算法最严重的问题是环形引用问题。

 

   图中Root对象是一个能被用户程序访问到的对象,比如栈上引用的对象。程序通过Root间接访问其它对象。

 

   对象A处在A->B->C->A的环中,因此Aa,b两个引用,当a引用断开时,A还有一个引用b,但是实际上A->B->C->A环已经无法被用户程序引用到了。如下图

 

 

弱指针解决方案:

   弱指针算法使用两个计数域来计算对对象的引用,一个称为强引用,一个称为弱引用当强引用计数为0时对象不再可用。

 

Boost库中的SmartPtr按以下过程工作:

SharedPtr代表强指针,WeakPtr代表弱指针。

  • 当对象从强指针向强指针传播时,强引用计数增加
  • 当对象从强指针向弱指针传播时,弱引用计数增加
  • 当对象从弱指针向强指针传播时,如果强引用计数大于0那强引用计数增加,否则返回空。
  • 当对象从弱指针向弱指针传播时,如果强引用计数大于0,那么弱引用计数增加,否则返回空。
  • 当对象强引用为0时,如果弱引用为0则释放计数域,否则仅释放对象不释放计数域。
  •  当对象弱引用为0时,如果强引用为0则释放计数域,否则什么也不干。

 

 

   弱指针算法必须小心的维护弱引用,如果出现两个强互相引用,依然难以避免环形引用问题,虽然出现了一些自动避免环形引用的算法,但依然不完善,没有广泛的应用。

 

实际应用

Python

Boost SmartPtr

JavaScript

 

2.    追踪式GC

追踪式GC算法通过递归的检查对象的可达性来判断对象是否存活,进而回收无用内存。

 

追踪式的GC算法的关键在于准确并快速的找到所有可达对象,不可达的对象对于用户程序来说是不可见的,因此清扫阶段通常可以和用户程序并行执行。下面主要讨论了算法的标记阶段的实现

1)   标记清扫Mark-Sweep

标记清扫式GC算法是后面介绍的追踪式GC算法的基础它通过搜索整个系统中对对象的引用来检查对象的可达性,以确定对象是否需要回收。

 

分类:追踪式非实时,保守(非搬迁式)或者精确式(搬迁式) ,非渐进

 

优点:

  • 相对于引用计数算法,完全不必考虑环形引用问题。
  • 操纵指针时没有额外的开销
  • 与用户程序完全分离。

 

缺点:

  • 标记清扫算法是非实时的,它要求在垃圾收集器运行时暂停用户程序运行,这对于实时和交互式系统的影响非常大
  • 基本的标记清扫算法通常在回收内存时同时合并相邻空闲内存块,然而在系统运行一段时间后仍然难免会生成大量内存碎片,内存碎片意味着可用内存的数量上足够但实际上不可用,同时还会增加分配内存的时间,降低内存访问的效率
  • 保守式的标记清扫算法可能会将某些无用对象当做存活对象,导致内存泄露(注3)。

 

实现:

用户程序初始化向系统预申请一块内存,新的对象申请在此区域内分配, 用户程序不需要主动释放己分配的空间达到回收条件或者用户程序主动请求开始收内存。

 

标记清扫式GC算法(mark-sweep)分为两个阶段: 标记阶段 清扫阶段

 

标记阶段

根结点集合开始递归的标记所有可达对象

根结点集合通常包括所有的全局变量,静态变量以及栈(注2)。这些数据可以被用户程序直接或者间接引用到。

 

清扫阶段

遍历所有对象将没有标记为可达的对象回收,并清理标记位

 

标记前:

 

标记后:

 

保守式的标记清扫算法:

 

保守式的标记清扫算法缺少对象引用的内存信息(事实上它本身就为了这些Uncooperative Environment设计的),它假定所有根结点集合为指针,递归的将这些指针指向的内存堆区标记为可达,并将所有可达区域的内存数据假定为批针,重复上一步最终识别出不可达的内存区域,并将这些区域回收。

 

保守式的GC算法可能导致内存泄漏。由于保守式GC算法没有必需的GC信息,因此必须假设所有内存数据是一个指针,这很可能将一个非指针数据当作指针,比如将一个整型值当作一个指针,并且这个值碰巧在已经分配的堆区域地址范围内,这将会导致这部分内存被标记为可达,进而不能被回收。

 

保守式的GC不能确定一个内存上数据是否是一个指针,因此不能移动对象的位置。

 

实际应用

保守式标记清扫GC算法: Boehm-Demers-Weiser 算法

精确式标记清扫算法:UE3, UE4

 

2)   标记缩并Mark-Compaction

有些情况下内存管理的性能瓶颈在分配阶段,内存碎片增加了查找可用内存区域的开销,标记缩并算法是为了处理内存碎片问题而产生的。

 

分类:追踪式,非实时,精确式搬迁式,非渐进

 

优点:

  • 相比于基本的标记清扫算法,减少了内存碎片,提高了内存分配和访问效率。
  • 相比于节点复制算法,对内存需求更低。

 

缺点:

  • 需要移动对象位置,需要更新所有到对象的引用,因此需要更多的GC时间
  • 需要额外的空间保存缩并信息。
  • 需要精确的识别对象引用,因此需要编译器或者框架支持。

实现:

标记缩并式GC算法分为三个阶段:

标记阶段:

标记存活数据结构单元

缩并阶段:

移动对象并且合并空闲区块

更新阶段:

更新所有到存活数据的引用

 

双指针算法:

双指针算法要求每次分配的对象大小必需一样,但是并不需要额外的数据结构来保存节点信息

这个算法包括两个指针,执行过程如下。

(a)       Free指针从堆末尾查找空闲节点,Live指针从堆顶查找存活节点,

(b)      Live指针指向的存活节点复制到Free指针指向的空闲节点,将Free指针的地址写入Live指针指向的位置,

(c)       移动Free指针和Live指针,(b)直到Free指针和Live指针相遇。

 

(a)

(b)

(c)

(d)

 

迁移地址算法:

迁移地址算法适用于可变大小的内存分配但是它要求对象中包含一个记录对象新位置的字段 并且需要遍历三次堆

  • 第一堆头部开始遍历,计算到当前位置遇到的所有存活对象的大小(不包括当前对象),将值记入当前对象的新位置字段。同时将相邻的空闲字段合并成,以减少后面遍历的次数。
  • 第二次遍历所有的对象,将对其它对象的引用更新到新位置,新位置==当前位置+对象的新位置字段值。
  • 第三次移动所有对象到新位置,清除新位置字段的值,为下次收集做准备。

 

(1)GC

 

(2)计算新位置

 

(3)GC

 

 

3)   节点复制

节点复制GC通过将所有存活对象从一个区移动到另一个区来过滤存活对象。

 

分类:追踪式,非实时,精确式,搬迁式,非渐进

 

优点:

  • 和基本的标记清扫算法相比,节点复制算法的开销正比于存活数据的容量,而不是整个堆的大小
  • 减少了内存碎片,有更好的内存局部性
  • 新对象的分配更简洁高效,并且不需要维护空闲块的列表等辅助数据结构。
  • 在低对象存活率的环境中有更高的效率。

 

缺点:

  • 相比于标记缩并算法,需要双倍的内存。
  • 大型对象的复制消耗可能很大。

 

实现:

三色算法渐进式分代GC算法的基础。它将堆分为两个分区称为From区和To, 每次分配对象分配在From区中,当From区没有可用空间时开始GC,将存活对象从From区复制到To区中,交换From区和To区,新对象的分配只需要在From区已分配的大小加上新对象的大小。

 

三色法将所有对象定义为三种“颜色”:

黑色:表示当前对象已经被回收器扫描到,并且它的所有引用成员已经被加入到扫描列表中。

灰色:当前对象已经被加入到扫描列表中,但是还没有描到; 或者被用户程序修改, 由黑转灰。后一种情况主要出现在渐进式GC过程中

白色:没有扫描到的对象并且也不再队列中,也就是说还没有发现有到该对象的引用


度优先遍历(对象间的引用关系让对象迁移到相邻的内存区域,可以获得良好的空间局部性

  • 递归的扫描所有根结点,将正在扫描的节点, From区复制到To区,在原位置上留下新地址,并标记为灰色。
  • 扫描这个节点中的所有引用,执行第一步,当这个节点扫描完成后,即所有引用到成员也已经标记为黑色,将该节点标记为黑色
  • 当所有根节点标记为黑色后,剩下的白色节点为可回收块仍然留在旧From中,整个From区将被回收,所有存活节点密集的分布在To区前部,To区的后部是空闲块,因此不需要维护空闲节点列表。
  • 交换FromTo区。

 

 

                              (1)                    (2)

 

          (3)                    (4)

 

          (5)               (6)

 

          (7)               (8)

          (9)

 

广度优先遍历

  • 将所有根节点加入扫描队列中同时将对象从From区移动到To 在原位置留下新位置的地址将对象标记为灰色。
  •  从队列头部第一个对象开始扫描,对它的成员进行以下操作:
   如果它是黑色,那么它已经扫描完成了,将当前扫描对象指向它的引用更新到新位置
   如果它是灰,那么它已经在To区中了,扫描它的成员,对它的所有成员执行第一步,再它的颜色转换为黑色。


  • 当队列头指针和尾指针相等时扫描完成。剩下的白色对象可回收仍然留在旧From区中,整个旧From区将被回收,所有存活节点紧密的分布在From前部,From的后部是连续的空闲块,因此不需要维护空闲节点列表。
  • 交换FromTo

 

4)   分代式GCGenerational Garbage Collection

在程序运行过程中,许多对象的生命周期是短暂的,分配不久即被抛弃。因此将内存回收的工作焦点集中在这些最有可能是垃圾的对象上,可以提高内存回收的效率,降低回收过程的开销,进而减少对用户程序的中断

 

分代式GC每次回收时通过扫描整个堆中的一部分而是不是全部来降低内存回收过程的开销。

 

分类:追踪式,非实时,精确式,搬迁式,非渐进

 

优点:

  • 只收集堆的一部分,减小了内存回收的开销,缩短了用户程序的中断时间
  • 和节点复制算法相比,只需要和需要回收分区一样大而不是和整个分配堆一样大的内存

缺点:

  • 系统需要根据对象的存活时间区分年老的对象和年轻的对象,因此需要额外的内存空间保存对象的年龄数据
  • 为了快速回收年轻分代,必须维护年轻分代的根结点集合。这需要使用拦截器实现,因而需要编译器支持。
  • 拦截器的使用增加了指针复制的开销。

 

实现:

分代式GC算法基于标记清扫算法或者节点复制算法。

 

分代式GC算法将堆按对象的存活时间分为两个或者更多个区域,称为分代,通过频繁的回收年轻分代来提高回收的效率

 

分代式GC算法中,新的对象总分配在年轻分代区域,当年轻分代填满时,扫描这个区域中的存活对象,增加它们的年龄,如果对象的年龄达到提升条件,那么将它复制到比当前分代年龄更大一级的分代中去。其它区域依次类推,年龄最高的分代回收时不移动存活对象,只回收无用对象。

 

下面描述的分代式GC算法是基于两个分代实现的,一个称为年老分代,一个称为年轻分代。

 

为了提高存活对象的回收效率,不必每次遍历整个堆来查找年轻分代的根集合,需要维护年轻分代的根结点集合,这个根结点集合称为记忆集记忆集包含了所有从这个分代区域外到这个分代区域内的所有对象的引用这些引用可能来源全局变量,栈,和年老分代。

 

年老分代到年轻分代的引用关系有两个来源,一个是在对象从年轻分代提升到年老分代的过程中被提升的对象引用到的未被提升的对象,另一个是用户程序运行时修改年老分代的成员变。前一种可以由回收器维护,后一种需要使用拦截器来维护

 

拦截器通常是一小段内联代码,在用户程序修改对象引用时执行一些特殊的操作以保证GC程序的正确执行。引用计数算法的计数更新操作也可以看作是一种拦截器。

 

拦截器分为两种,写拦截器和读拦截器,写拦截器保证了用户程序修改了对象引用时能将修改记录下来,比如放到记忆集中,以便后面重新扫描该对象。而读拦截器保证了用户程序访问到的对象都是可达的------如果对象还没有被标记为可达的,立即标记它。

 

拦截器会增加指针复制的开销和增大代码生成结果,在实际应用中对象的写访问操作比对象的读访问操作少得多,所以基于写拦截器的的GC算法更通用。

 

分代式GC算法的标记流程如下,假设每次GC提升存活对象

  •  从全局变量和栈上的引用查找存活对象
  • 黑色引用即为年轻分代的根节点集合
        
  • 每次GC只扫描年轻分代区域由年轻分代指向年轻分代之外的引用不计算
       
  • 年老分代满时需要进行一次Full GC, 完全扫描整个堆
     
  • 清理堆中所有无用内存

 

实际应用Java, Ruby

5)   GC

渐进式GC要解决的问题是如何缩短自动内存管理引起的中断,以降低对实时系统的影响

渐进式GC算法基于分代式GC算法,它的核心在于用户程序运行过程维护年轻分代的根结点集合。

 

分类:追踪式,非实时,精确式,搬迁式渐进

 

优点:

  • 可以和用户程序并行执行对于对用户程序影响非常小

 

缺点:

  • 需要编译器支持

 

实现:

渐进式GC内存回收过程中标记阶段分为多段执行减小用户程序的中断时间

 

在标记过程中,当用户程序修改了对象的引用关系时,GC程序必须知道哪个对象被修改了,以便后面重新标记这个对象。

 

基于记忆集的渐进式GC算法

 

记忆集算法需要额外的空间来保存被引用的年轻分代的对象集合,当有重复对象加入记忆集时记忆集可能会变的很大,而使用额外的字段标记对象是否加入了记忆集的则需要对象保留额外的字段来标记这个对象是否已经加入了记忆集,并且最后需要重新扫描整个堆。

 

其工作流程如下:


  •  P已经被扫描并标记为黑,正在扫描K->L

  • 用户程序修改了P拦截器P标记由黑转灰,并放入到记忆集末尾(5)

  • 当扫描到记忆集的末尾时重新扫描P

  • 当扫描指针指向记忆集结尾时,GC过程结束

 

 

卡表法:

 

卡表法将年老分代分为多个小分区,每个小分区对应一个标记位小分区中对象被修改时,更新该分区对应的标记位,在扫描结束时重新扫描所有标记位,查找所有被更新的标记位对应的小分区,重新扫描这些小分区内的所有对象。

 

B.ptrI.ptr被修改,导致Mark1Mark6更新,最终B, G, I被重新扫描。

 

实际应用:JavaRuby

 

 

 

五、         参考文档

 

Garbage Collection in an Uncooperative Environment. Hans-Juergen Boehm .

http://www.hboehm.info/gc/.   Hans-Juergen Boehm

http://www.oracle.com/technetwork/articles/java/index-jsp-140228.html

http://www.zhihu.com

http://www.stackoverflow.com

http://www.boost.org/doc/libs/1_60_0/libs/smart_ptr/smart_ptr.htm

六、          备注

1:引用计数算未能在某些极端情况下也可能会导致长时间的停顿,比如一个很长的单链引用。

2:在一些标记清扫算法通常还包括寄存器中的数据。

3保守式标记清扫算法中的内存泄露是非递增的。

4基于记忆集的算法通常会将C放入记忆集,表示C被外部对象引用,是当前分代的根结点之一,而卡表法A对应的小分区标记位置位,表示分区被修改过(Dirty)。

5:有些算法在对象中保留一个字段来标记对象是否已经在记忆集中了,以保证对象不会被重复加入到记忆集中, 当然最终需要重新扫描整个记忆集来识别这些灰色对象。

6拦截器的开销均匀的分布在用户程序运行过程中,通过某些条件可以将这种影响降低到最低比如大部分时候对象的操作都在栈上,而栈必定是根集合的一部分因此过滤对栈上数据的拦截可以极大的降低拦截器的开销,这对编译器是很容易实现的,或者只对分布在年老分区内的对象修改时进行拦截。

7:不包括栈上引用的对象。

 

 

如社区发表内容存在侵权行为,您可以点击这里查看侵权投诉指引