从C和C++内存管理来谈谈JVM的垃圾回收算法设计-下

从C和C++内存管理来谈谈JVM的垃圾回收算法设计-下

• 引言
• 基本概念
  • 对象
  • GC ROOTS
• 垃圾回收常见算法
  • 标记清除
    • 优缺点
  • 引用计数
    • 优缺点
  • 部分标记清除算法
    • 优缺点
  • 复制算法
    • 优缺点
    • 多空间复制算法
  • 标记整理(标记压缩)
    • 优缺点
• 分代设计
  • HotSpot具体实现
    • 跨代引用
    • 并发可行性
• 经典垃圾回收器
  • Serial新生代垃圾回收器
  • ParNew新生代垃圾回收器
  • Parallel Scavenge新生代垃圾回收器
  • Serial Old老年代垃圾回收器
  • Parallel Old老年代垃圾回收器
  • CMS老年代垃圾回收器
  • G1垃圾回收器
• 小结

引言

上一篇文章和大家介绍了C语言内存模型和malloc底层内存池实现。

本节和大家谈谈,如何在c语言内存模型和malloc的基础上尝试去设计一个隐式分配器,也就是能够自动释放不需要的块的垃圾收集器。

基本概念

再聊具体的垃圾回收算法前，我想先和大家聊聊一个垃圾回收器的设计需要涉及到哪些概念。

JAVA中的数据类型基本分为两类: 基本数据类型(不需要垃圾回收),引用类型(堆上分配,需要垃圾回收)。

对象

JAVA中每一个类最终会被编译成一个.class文件,类加载器定位,读取该文件到JVM中，按照指定class文件格式,挨个解析每个属性,将属性值放到内存中对应的class数据结构中:

/*
ClassFile {
    u4             magic;
    u2             minor_version;
    u2             major_version;
    u2             constant_pool_count;
    cp_info        constant_pool[constant_pool_count-1];
    u2             access_flags;
    u2             this_class;
    u2             super_class;
    u2             interfaces_count;
    u2             interfaces[interfaces_count];
    u2             fields_count;
    field_info     fields[fields_count];
    u2             methods_count;
    method_info    methods[methods_count];
    u2             attributes_count;
    attribute_info attributes[attributes_count];
}
*/
type ClassFile struct {
	magic      uint32
	minorVersion uint16
	majorVersion uint16
	constantPool ConstantPool
	accessFlags  uint16
	thisClass    uint16
	superClass   uint16
	interfaces   []uint16
	fields       []*MemberInfo
	methods      []*MemberInfo
	attributes   []AttributeInfo
}

我们如果想要new一个对象,也是先定位到该class在内存中对应的Class数据结构实例对象,然后根据里面存储的类元数据信息来新创建出一个对象:

type Object struct {
    //对象元数据指针
	class *Class
	//实例对象的变量槽
	data  []Slot 
}

type Slot struct {
    //基本数据类型的值
	num int32
	//引用类型的值
	ref *Object
}

//通过Class元数据信息创建出一个新的实例对象---此时还没有填充属性,只是单纯创建一个原始实例对象
func newObject(class *Class) *Object {
	return &Object{
		class: class,
		data:  newSlots(class.instanceSlotCount),
	}
}

上面给出了一个简单的模型实现，但是如果我们想要进行垃圾回收，那么必然还需要让每个对象提供相关用于垃圾回收的信息，这些信息可以存放在一个叫做对象头的地方,当然对象头可以分为两部分，一部分包含用于垃圾回收或者其他作用的信息，另一部分包含元数据指针。

此部分可以对照深入理解JVM第三版:

进行品读。

GC ROOTS

垃圾回收的执行通常是在方法执行的某个时间点发生的，那么该时间点哪些对象是一定不会被回收的呢 ？

• 全局性引用如常量引用或者类静态属性
• 局部性引用如当前执行方法中局部变量引用的对象,这些对象存放与当前活动栈帧的局部变量表和操作数栈中

这些对象一定不会被回收，所以这些对象构成的集合被称为根对象集合(ROOTS集合),因为垃圾回收器需要遍历这些对象的引用链找出当前所有的活动对象，因此该集合也被称为GC ROOTS。

存在于GC ROOTS集合中某个对象引用链上的对象被称为此刻的活动对象,而无法通过引用链找到的对象就被称为此刻的非活动对象,也就是垃圾对象。

垃圾回收常见算法

标记清除

标记清除算法分为两部分:

1. 标记: 通过遍历GC ROOTS引用链,标记出那些存活对象
2. 清除: 将垃圾对象占用空间加入空闲链表

1. 给每个对象头中添加一个存活标记位,遍历GC ROOTS引用链,给引用链上每个对象设置存活标记位为1
2. 清除阶段,遍历堆中所有对象,如果对象存活标记位为1,那么设置为0，然后继续遍历,否则将对象添加进空闲链表
3. 当分配新对象时,遍历空闲链表,优先分配垃圾对象占用的空间
4. 可以考虑在某个时机将内存上连续的垃圾对象占用的空间进行合并

分配的过程还可以再优先,假设空闲链表此刻情况如下:

假设此刻我们要分配20字节大小的空闲块，我们采用最佳适配原则，遍历一遍空闲链表，找到最接近当前要分配大小的空闲块，但是在空闲链表非常长的情况下，这样的遍历会导致很高的性能损耗。

此时，我们可以借鉴伙伴算法的思想，采用数组+链表的形式:

当我们需要分配大于4小于32大小的空闲块时，直接通过索引1定位到第二条空闲链表，然后遍历该链表看能否得到合适大小的空闲块。

如果发现空闲链表中两个相邻块地址相邻，可以合并这两个空闲块。

当分配时,没有合适小块，只能分配一个大块时，需要将大块划分为两个小块。

优缺点

优点:

• 实现简单
• 垃圾回收过程不移动对象

缺点:

• 碎片化
• 分配需要遍历空闲链表，耗时长

引用计数

每个对象头中腾出一块空间，用于存放计数器:0

• 创建新对象实例时,将对象的计数器设置为1
• 改变引用关系时,将引用前对象的计数器减去1,如果此时为0,那么将对象加入空闲链表(递归处理该对象的引用的子对象)，被引用的对象计数器加一

优缺点

优点:

• 垃圾可以在改变引用关系时就被检测出来,然后进行回收
• 当分配新对象时,直接查询空闲链表，如果其中没有空闲空间,那么不需要专门进行一波垃圾回收,而是直接抛出堆内存不足的异常，节省了遍历GC ROOTS的时间

缺点:

• 计数器增减过程繁多，改变一次引用都需要增减计数器,包括递归回收操作
• 计数器占据空间大，如果给计数器分配较小的位数，可能导致计数器溢出
• 循环引用无法回收

部分标记清除算法

引用计数法最大的麻烦处在于循环引用垃圾无法被回收，为了解决这个问题，我们可以使用引用计数配合标记清除来完成，具体思路如下:

针对可能存在循环引用的对象群使用标记清除算法,而对其他对象使用引用计数算法。

此时标记清除算法就是用来查找垃圾对象的了，那么如何实现呢?

核心思路如下:

• 当删除根对象到某个外部对象的引用时，如果此时该对象的计数器不为0 ,将对应的外部对象加入一个待选队列中，该队列中存放的都是有可能产生循环引用的垃圾对象，如果计数器为0，那么加入空闲链表。

• 当分配对象先尝试从空闲链表分配，如果空闲链表没有剩余空间，那么遍历候选队列，如果此时队列为空，说明堆内存已经满了，抛出异常
• 遍历候选队列，取出每个对象，将当前对象的引用的子对象的引用计数减一，然后进行递归处理，并做好标记，避免重复处理已经处理过的对象。

• 重新从A对象开始搜索，将计数器为0的垃圾对象进行回收

优缺点

部分标记清除能够很好解决循环引用垃圾的回收问题，但是从队列搜索对象的代价还是很大的，毕竟队列中记录的都是候选垃圾，所以要搜索的对象不在少数。

搜索对象也会导致垃圾回收的最大暂停时间变大，这抵消了引用计数的优点。

复制算法

最简单的复制算法思想如下:

• 将堆空间一分为二，一半为From空间,用于存放所有对象,一半To空间用于临时存放存活对象
• 遍历GC ROOTS引用链,将所有存活对象都复制到To空间保存

• 清空From空间，然后交换From和To空间指针，交换后的的From空间中剩余的就是紧凑存放的存活对象了

优缺点

优点:

• 分配对象时，无需遍历空闲链表，因为空闲空间是一块连续的内存空间
• 不存在碎片化问题
• 有引用关系的对象复制过后被排列在了一起，可以提高高速缓存利用率

缺点:

• 堆空间利用率低
• 需要移动对象
• 复制对象时需要递归复制子对象,这个过程耗时长

多空间复制算法

简单的复制算法实现只能利用半个堆，如何优化呢？

例如: 把堆分成10份，其中2份作为From和To空间来执行复制算法，剩下8份执行标记清除算法。

这里举个例子，演示一下多空间复制算法的工作流程:

通过TO和FROM指针不断前移,将因标记清除算法产生的碎片空间进行整理，而原先整理好的空间又可能因为应用了标记清除算法而产生新的垃圾，就这样不断重复。

标记整理(标记压缩)

大致思路如下:

• 给每个对象的对象头中增加两个属性: mark 当前对象在GC后是否存活 ； forwad: 当前对象移动到哪个位置

• 遍历GC ROOTS，设置存活对象的mark标记位为true

• 遍历堆中所有对象，设置存活对象的forward指针，伪算法如下:

//scan是当前扫描的对象
//new_address堆空闲空间起始地址
scan=new_address=head_start
while(scan<head_end){
   //当前对象为存活对象
   if(scan.makr==true){
     scan.forward=new_address
     new_address+=scan.size
    } 
    //处理下一个对象 
   scan+=scan.size   
}   

• 更新对象之间的引用指针地址

• 移动对象到新的位置

优缺点

优点就是充分利用堆空间的同时又不产生内存碎片，缺点就是要实现前面的效果需要付出大量计算和时间资源。

分代设计

分代设计不属于某种具体垃圾回收算法的实现，而是考虑到不同对象生命周期长短的特点，应该“因材施教”。

我们在对象头中腾出一定空间用于存放对象的年龄，对象每熬过一次GC，对应年龄加一。

年龄小于指定阈值的对象被称为新生代对象，否则称为老年代对象。

新生代对象具有特点是生命周期短的特点，即每次GC后存活对象都是少数；老年代对象具有生命周期长的特点，因此老年代的GC频率应该偏低。

当新生代中的对象熬过指定次数GC后，年龄便会到达晋升老年代存放的的阈值，此时该对象会移动到老年代保存。

我们可以将不同类型的对象分区存放，将堆内存分为新生代区域和老年代区域，针对不同区域采用不同的GC算法实现:

• 考虑到新生代每次GC过后存活对象较少，又需要频繁的进行GC，因此适合采用标记复制算法，不适合采用标记清除是考虑到频繁GC会导致大量内存碎片产生。
• 传统的标记复制算法会导致一半的堆内存大小被浪费，这显然不太能够接受，但是结合新生代这个场景来看，每次存活的对象都很少，因此我们可以只划分出一小块空间来存放存活对象，这里直接给出深入理解JVM虚拟机第三版中的分代模型图:

新生代空间被划分为了生成空间,From空间和To空间三部分，每次new创建的对象保存在生成空间，经历了一次GC后，存活的对象，全部复制到To空间保存，然后交换From和To的指针。

如果From幸存空间大小不足以存放当前幸存对象，那么需要通过担保机制，直接将相关对象移动到老年代保存。

幸存空间通常只占有整个新生代大小10%左右,又因为只浪费其中一半的幸存空间，所以实际只浪费了5%的空间。

• 老年代每次GC后会存活较多的对象，因此更适合采用标记清除算法，但是一旦标记清除算法导致内存碎片产生过多，无法分配一个合适大小的块来存放新的对象了，此时需要采用标记整理算法去老年代内存空间进行整理。

分代设计中关于内存分配的常见基本策略如下:

• 对象优先分配在Eden，Eden空间不足引发minor gc
• 对象大小超过指定阈值时直接分配在老年代，避免在Eden和Survivor区域中进行复制
• 长期存活的对象进入老年代
• 幸存区空间不足以存放存活对象时，需要通过担保机制把幸存区无法容纳的对象直接送入老年代，之所以叫做担保是因为需要确认老年代有足够的剩余空间来存放这些存活对象，如果剩余空间不够，会引发一次FULL GC。

HotSpot具体实现

1. 根节点枚举: GC ROOTS枚举过程需要暂停用户线程,因此为了加快枚举过程，HotSpot采用了OopMap数据结构，在安全点生成对应的OopMap数据结构，该数据结构记录了当前线程的GC ROOTS集合。
2. 程序不是在执行的任何时刻都可以直接暂停进行垃圾回收的，而必须是执行到某个安全点处才可以暂停，进行垃圾回收，安全点设置要合理，不能太多也不能太少，通常在方法调用,循环跳转和异常跳转等指令处，会加上一个安全点指令。
3. 线程执行到安全点指令时，会检查对应的垃圾收集标志是否被设置了，如果被设置了，说明此刻垃圾收集线程已经发出了GC命令，正在等待所有用户线程主动暂停自己，那么当前用户线程就中断挂起。
4. 如果垃圾回收线程发出GC命令时，存在某些用户线程处于Sleep或者Block状态(也被称为处于安全区域)，那么当这些用户线程被唤醒时，不能直接运行用户程序，需要首先检查相关GC阻塞标志是否被撤销，如果还没撤销，说明当前垃圾回收阶段还处于STOP THE WORLD的阶段，那么当前用户线程中断挂起。

跨代引用

如果我们只是针对新生代进行垃圾回收,那么光光枚举GC ROOTS还不够，因为可能存在老年代中某个对象引用新生代中对象的事情发生，因此我们需要使用一种全局数据结构来指明当前老年代中存在哪些跨代引用，这种数据结构被称为记忆集。

通过一个对象指针数组记录全部含跨代引用对象的实现方案，记忆集数组的大小会随着跨代引用增加而变大，那么能不能进行优化呢?

我们可以把老年代划分为固定大小若干相等空间，这里将每个空间看做一个卡牌，然后使用一个位数组与每个卡片进行映射，如果该卡片空间内部存在跨代引用，那么设置对应位数组索引值为1即可:

此时，我们只需要用一个固定大小的字节数组就可以通过模糊的形式告诉垃圾回收器哪块卡片内部存在跨代引用，那么由垃圾回收器遍历该卡片内部的对象，找到存在跨代引用的对象，并加入GC ROOTS集合即可。

该实现方式在HotSpot中也被称为卡表。

为了在老年代对象产生跨代引用的时候，将其加入记忆集中，我们需要拦截所有引用类型字段赋值的过程，类似AOP，会在执行完赋值指令后，判断是否需要更新记忆集，该拦截过程被称为写屏障。

判断条件如下:

并发可行性

GC ROOTS枚举可以借助OopMap来加速完成，但是从GC ROOTS集合沿着引用链往下遍历的耗时则会根据堆内存活对象大小逐级递增。

能否加速遍历引用链的过程，或者说减少遍历引用链过程对用户线程的阻塞影响呢？

• 并发执行

让遍历引用链的过程和用户线程并发执行，并发执行是可以，但是这个过程中会存在一些问题:

• 用户线程通过改变引用关系，将存活对象变为了垃圾对象，但是因为之前已经标记过了，因此垃圾回收器不会将其视为垃圾对象
• 用户线程通过改变引用关系，创建新对象，新对象被当做垃圾对象回收掉

将原本存活的对象变为垃圾对象可以容忍，但是将存活对象视为垃圾对象回收是不可容忍的，因此我们必须解决后者。

为了解决这个问题，我们可以引入三色标记法，把遍历对象图过程中遇到的对象，按照是否访问过这个条件标记为三种不同的颜色:

• 白色: 没有被垃圾回收器访问过，代表不可达
• 黑色: 已经被垃圾回收器访问过,并且该对象直接引用的子对象也都被访问过了，因此垃圾回收器在此次垃圾回收过程中不会再访问该对象
• 灰色: 已经被垃圾回收器访问过，但是该对象直接引用的子对象至少存在一个还没有被扫描过，下次再遇到该对象时，垃圾回收器必须再次访问其子对象，直到确认全部扫描完毕，将其标记为黑色

这里我们主要来看一下将活动对象视为垃圾对象的操作:

用户程序和垃圾回收线程并发执行过程中，用户程序将B–>C变为了A–>C,但是由于A是黑色对象,那么A是不会再被访问的，那么意味着存活对象C将一直处于白色状态，最终会被垃圾回收器回收。

如果要导致存活对象被错误回收，需要满足两个条件:

• 用户程序插入了一条或者多条黑色对象到白色对象的新引用
• 用户程序同时删除了灰色对象到该白色对象的直接或者间接引用

要解决上面这个问题，我们只需要让其中任意一个条件不满足即可，有两种方式:

• 增量更新(破坏第一个条件): 当黑色对象插入了新的指向白色对象的引用时，通过写屏障将该插入的引用记录下来，在重新标记阶段，再将这些记录过的引用关系中的黑色对象为根,重新扫描一次。可以认为: 当黑色对象插入了指向白色对象的引用后,它就变回了灰色对象。
• 原始快照(破坏第二个条件): 当灰色对象要删除指向白色对象的引用关系时,利用写屏障将这个要删除的引用记录下来，在重新标记阶段，再将这些记录过的引用关系中的灰色对象为根,重新扫描一次。可以认为: 无论引用关系删除与否,都会按照刚刚开始扫描那一刻的对象图快照进行搜索。 (但是需要找额外的地方存放新创建的对象)

经典垃圾回收器

这里简单回顾一下深入理解JVM 虚拟机第三版书中列举的一些垃圾回收器。

Serial新生代垃圾回收器

serial重点是单线程,需要STOP THE WORLD。

• 单线程占用资源少，实现简单，但是GC过程需要暂停用户线程。

ParNew新生代垃圾回收器

• 采用多线程来回收新生代垃圾，但是回收过程仍然需要STOP THE WORLD，并且只有在多核或者超线程情况下，才有可能超越单线程工作效率。

Parallel Scavenge新生代垃圾回收器

Parallel Scavenge和ParNew一样，也是采用了标记复制算法，并且也是采用多线程收集模式。

Parallel Scavenge优于ParNew的地方在于，它可以通过参数调整来争取让程序吞吐量达到最高:

提供的相关参数主要控制垃圾回收花费时间不超过用户设置的值，或者垃圾回收时间占总时间比例不超过指定值。

并且相关参数还可以在运行中自适应调整。

Serial Old老年代垃圾回收器

• 单线程在目前多核环境下很难比的过那些多线程收集的垃圾回收器，并且老年代一般优先选用标记清除算法，然后将标记整理算法作为逃生门，在内存碎片过多的情况下，进行一波整理。
• 因此Serial Old垃圾收集器一般作为CMS收集器的逃生门方案。

Parallel Old老年代垃圾回收器

• 采用多线程，标记整理算法实现对老年代的收集
• 吞吐量优先

CMS老年代垃圾回收器

注重实现最短回收停顿时间，适合注重响应时间的应用程序，如: Web程序。

CMS采用并发的标记清除算法实现，实现步骤如下:

1. 初始标记: 需要暂停用户线程,利用OopMap快速得到GC ROOTS集合。
2. 并发标记: 和用户线程一起运行，遍历GC ROOTS引用链，标记所有存活对象，同时写屏障记录下其中引用变动
3. 重新标记: 暂停用户线程,重新遍历引用发生变动的对象集合
4. 并发清除: 和用户线程一起运行，清除掉已经确认的垃圾对象

垃圾回收线程能够和用户线程一起并发运行未必能够带来更好的效率，反而对于某些核数较少的机器而言，会因为频繁的上下文切换，降低运行效率。

并发标记和并发清理阶段，用户线程会不断产生新的垃圾对象，这些垃圾被称为浮动垃圾，CMS垃圾回收器无法在本次垃圾回收阶段回收掉这批浮动垃圾，因此并发回收过程中，需要预留一部分空间用作存放用户线程新对象的创建。

也就是说，如果老年代堆内存占用到达指定阈值，那么需要对老年代进行一次GC，从jdk 6起，该值被设置为92%，如果CMS运行期间，预留的内存无法满足新对象的分配，会触发"并发失败"，此时需要采用逃生门设计: 暂停用户线程，使用Serial old来重新进行老年代的收集。

如果是因为内存碎片过多，导致无法找到足够大的内存空间来分配新对象，那么会触发一次FULL GC，默认会在进行FULL GC前，先对老年代进行一次碎片整理。

G1垃圾回收器

将堆划分为内存大小相同的连续区域(Region)，每个独立的区域都可以扮演新生代的Eden空间，Survivor空间，或者老年代空间，G1会根据Region扮演的不同角色采用不同的策略去处理。

上面展示的是将Eden中幸存的对象复制到幸存区中。

G1将Region作为回收的最小单元，每次回收的内存空间都是Region的整数倍大小，G1通过跟踪各个Region里面的垃圾收集价值，在后台维护一个优先级列表，每次根据用户设定的允许收集停顿时间，优先处理那些回收价值最大的Region。

对于大对象的存储，Region采用了一类特殊的Humongous区域,只要某个对象大小超过单个Region容量一半，就认为该对象为大对象。G1大部分行为都会将Humongous Region当做老年代来看待。

G1通过化整为零的方法在解决跨代引用方面到变得复杂了起来，G1通过在每个Region上都维护一个记忆集，来记录下别的Region指向自己的指针，并标记这些指针分别在哪些卡页范围内，通过一个双向卡表结构，不仅记录谁指向我，也记录了我指向谁。由于每个Region都需要维护一个记忆集，此时G1收集器就需要耗费整个堆内存约10%-20%的额外内存来存放这些信息。

CMS采用增量更新的算法来实现垃圾回收线程和用户线程的并发可达性，和G1则采用原始快照算法来实现，为了存储并发执行过程中程序新创建的对象，G1为每个Region腾出一部分空间用于存放并发回收过程中新对象的分配。

与CSM并发失败导致FULL GC类似，如果G1的内存回收速度赶不上内存分配速度,G1也会产生FULL GC,从而产生长时间的STOP THE WORLD。

G1是如何计算得出某个Region的回收优先级的呢?

• 简单来说是通过记录每个Region的回收耗时，每个Region记忆集中的脏卡数量等各个可测量步骤的花费成本，最终计算出一个Region的回收优先级。（这部分说的过于简化，感兴趣大家可以自行研究一下）

G1工作流程:

• 初始标记: 标记GC ROOTS直接关联的对象
• 并发标记: 遍历GC ROOTS引用链，标记所有可达对象，利用写屏障记录下所有发生引用变动的对象到STAB队列中
• 最终标记: 处理STAB队列中发送引用变动的对象
• 筛选回收: 更新Region统计数据，对各个Region按照回收价值排序，根据用户所期望的停顿时间制定回收计划，然后选择任意多个Region构成回收集，然后把决定回收的那一部分Region的存活对象复制到空的Region中，再清理掉整个旧的Region全部空间。

G1小结:

G1可以面向堆内存任何部分来组成回收集进行回收，衡量标准不再是它属于哪个分代，而是哪块内存中存放的垃圾数量最多，回收效益最大，这就是G1收集器的Mixed GC模式

G1虽然仍然保留新生代和老年代的概念,但新生代和老年代不再固定，他们都是一系列区域的动态集合，G1收集器能够建立可预测的停顿时间模型，是因为他将Region作为单次回收的最小单元，即每次回收到的内存空间都是Region大小的整数倍，这样可以避免在整个java堆中进行全区域的垃圾收集。

G1会去跟踪各个region里面的垃圾堆积的价值大小，价值即回收所获得的空间大小及回收需要的时间的经验值，然后在后台维护一个优先级列表，每次根据用户设定的收集停顿时间来优先处理回收价值收益最大的那些region

在决定进行回收的时候，g1会对region按照回收价值和成本排序，根据用户期望的停顿时间来指定回收计划，可以自由选择任意多个region组成回收集，然后把决定回收的那一部分region的存活对象复制到空的.region中，再清理掉整个旧的region的全部空间。

G1垃圾收集器

小结

本文涉及的垃圾回收算法主要参考深入理解JVM第三版和垃圾回收算法设计与实现一书。

本文只涉及到垃圾回收中最经典，理解难度偏易的处理方法，更多复杂算法可以参考相关经典书籍和论文。