JVM学习-GC之追踪式垃圾收集算法基础

  学习JVM的垃圾回收，离不开的是 追踪式垃圾回收算法 ，现有的主流Java虚拟机都采用的是追踪式回收算法。对比于引用计数式垃圾收集， 追踪式垃圾回收算法都是采用的间接式的回收策略，也就是这种策略并非直接寻找垃圾本身，而是先寻找哪些对象存活，然后反过来判断其余所有的对象为垃圾对象 。追踪式回收算法本身包括 标记-清除(Mark-Sweep)、标记-复制(Mark-Copy)、标记-整理(Mark-Compact)这三种回收策略 ，在真正的回收器上，一定是根据对象的不同情况进行分区或者分代，针对不同的区域采取不同的回收策略，针对这些情况，有许多的相关基础概念展现出来。

追踪回收算法回收策略

追踪式回收算法本身包括标记-清除(Mark-Sweep)、标记-复制(Mark-Copy)、标记-整理(Mark-Compact)这三种回收策略，这三种策略都有一个共通之处，那就是 标记 (Mark)，关于这个标记的过程在上一篇文章( JVM学习-GC之判断对象存活 )有讲过，就是里面的可达性分析算法，本篇文章将不再做多余概述。

标记-清除(Mark-Sweep)算法

标记-清除(Mark-Sweep)算法是一种典型的非移动式回收算法，是所有追踪式回收算法的基础，其他的算法都是针对标记-清除(Mark-Sweep)算法的缺点改进而来。

原理

  在标记过程完成之后，将未标记的对象进行回收。

优缺点

  优点：

    1. 标记-清除(Mark-Sweep)算法的吞吐量（吞吐量就是处理器用于运行用户代码的时间与处理器总消耗时间的比值，吞吐量 = 运行用户代码时间 / (运行用户代码时间 + 运行垃圾收集时间)）较高；

    2. 标记-清除(Mark-Sweep)算法对空间的利用率比较高，既不需要像标记-复制(Mark-Copy)算法划出多余的空间来进行复制对象，也不需要像引用计数算法为每个对象设置引用计数器；

  缺点：

    1. 标记-清除(Mark-Sweep)算法的执行效率不太稳定；

    2. 标记-清除(Mark-Sweep)算法在清除的过程中会产生大量的碎片化空间，空间的碎片化太多，会导致程序在运行时分配对象的时候，无法找到足够大的连续空间，导致提前进行另一次垃圾收集；

标记-复制(Mark-Copy)算法

标记-复制(Mark-Copy)算法简称为复制算法，为了解决标记-清除(Mark-Sweep)算法面对大量可回收对象时，执行效率低的问题。

半区复制原理

  基本的复制回收器会将堆划分称为两个大小相等的半区，分别是来源空间和目标空间。每次在程序运行时，只用其中的来源空间来进行对象的内存分配，当来源空间的内存不足时，进行垃圾回收，交换两个半区的角色，然后将存活的对象移到另一个半区的一端，最后将垃圾回收的半区内存清零。

半区复制优缺点

  优点：

    1. 半区复制提升了垃圾回收的效率；

    2. 半区复制减少了碎片化空间的诞生；

  缺点：

    1. 半区复制将原来的可用内存减少了一半；

Appel式回收原理

  Appel式回收是针对标准ML提出的一种自适应分代策略，在ML语言中，一次回收完成通常只有不到2%的对象能够存活，Appel式回收正式针对这一种情况而设计的策略。 Appel式回收策略将空间分为三个：老年代、复制保留区、新生代，在HotSpot虚拟机中的实现中新生代收集器将新生代变成Eden空间，将复制保留区变成两块较小的Survivor空间，在程序运行中每次分配内存只使用Eden和其中一块Survivor空间，在发生垃圾收集时，将存活的对象复制到保留的那一块Survivor上，另外两块空间直接清零 （在HotSpot虚拟机中Eden和Survivor的比例为8:1）。

  当Survivor空间不足以容纳一次Minor GC之后，就需要依赖其他内存区域（大部分时候是老年代）进行分配担保，这些没有足够空间存放的对象直接进入其他区域。

Appel式回收优缺点

  优点：

    1. Appel式回收可以为复制保留区的大小进行动态调节；

  缺点：

    1. 必须要有其他空间进行空间担保；

标记-整理(Mark-Compact)算法

  在标记-清除(Mark-Sweep)算法这种非移动式回收算法中最大的问题就是会产生碎片化的空间，而标记-整理(Mark-Compact)算法正是为了降低内存碎片化提出来的解决策略。

原理

  在标记之后，把所有标记的对象都移到内存空间的一端，然后直接把边界之外的内存清零。

优缺点

  优点：

    1. 减少了内存碎片化；

    1. 在对象大量存活的情况下，效率要高于复制算法；

  缺点：

    1. 整理(Compact)过程繁琐，在大多数算法下需要多次遍历内存，STW(Stop The World)时间比清理(Sweep)时间长；

关于标记-整理(Mark-Compact)算法吞吐量的个人理解：在算法上标记-整理(Mark-Compact)算法一般需要多次遍历堆的过程，所以标记-整理(Mark-Compact)算法上的吞吐量是不如标记-清除(Mark-Sweep)算法的吞吐量的，但是对于整个系统来说标记-清除(Mark-Sweep)算法是属于不移动回收算法，不移动回收算法有一个明显的缺点就是在分配内存时更加复杂，对于大量的碎片化空间就只能通过其他分配空间手段（比如：分区空闲分配链表）来解决，而分配内存是程序运行过程中最频繁的操作，所以在系统的吞吐量上标记-整理(Mark-Compact)算法上的吞吐量是优于标记-清除(Mark-Sweep)算法的吞吐量的。

三色算法

在标记过程中，三色算法是所有赋值器和回收器遵守的不变式。

三色算法原理

  在遍历对象图的过程中，回收器把是否访问过的对象根据“是否访问过”来把所有对象标记成三种颜色。

• 白色：对象尚未被回收器访问到，在回收周期的开始阶段，所有的对象都是白色，在回收周期结束的时候，所有白色对象都是不可达对象。
• 灰色：表示对象已经被回收器扫描过，但是对象上还有一个或者多个引用没有进行扫描。
• 黑色：对象已经被回收器扫描过，并且所有的引用已经被扫描。黑色对象永远不可能直接指向白色对象，也永远不会被回收器再次扫描，除非颜色变化。

  回收器从白色根节点出发，逐步把对象图的对象变成灰色再到黑色，当全部遍历完成后所有可达的节点变成黑色，不可达的节点依旧是白色。

对象丢失问题

  当在同时产生下面两个条件时，会产生对象丢失问题

• 赋值器插入了一条或者多条从黑色对象到白色对象的新引用 ；
• 赋值器删除了全部从灰色对象到该白色对象的直接或者间接引用 。

弱三色不变式和强三色不变式

弱三色不变式和强三色不变式是为了解决对象丢失的。

• 弱三色不变式：所有被黑色引用的白色对象都会被灰色保护（灰色保护：白色对象直接或间接被灰色对象引用）。弱三色不变式打破了对象丢失条件的条件二。
• 强三色不变式：不存在黑色对象指向白色对象的指针。强三色不变式打破了对象丢失条件的条件一。

并发时三色问题的解决方案

增量更新

  增量更新要破坏的是第一个条件，当黑色对象插入新的指向白色对象的引用关系的时候，就将这个新插入的引用记录下来，等并发扫描结束之后，再将这些记录过的引用关系中的黑色对象为根，重新扫描一次。

原始快照(SATB)

  原始快照(SATB)要破坏第二个条件，当灰色对象要删除指向白色对象的引用关系的时候，就要将这个要删除的引用记录下来，在并发扫描结束之后，再将这些引用记录过的引用关系中的灰色对象为根，重新扫描一次。

GC的实现方式

在追踪式垃圾收集算法里面最先开始的就是用可达性分析算法标记(Mark)对象，在可达性分析算法里面第一步就是确定根节点集合(Root Set)，而如何确定根节点集合(Root Set)，就影响了GC的实现方式。

保守式GC

  如果JVM选择不记录内存中每个数据的类型，那么JVM就无法区分内存里某个位置上的数据到底应该解读为引用类型还是其他数据类型。这种条件下，实现出来的GC就会是“保守式GC(Conservative GC)”。在进行GC的时候，JVM开始从一些已知位置（例如说JVM栈）开始扫描内存，扫描的时候每看到一个数字就看看它“像不像是一个指向GC堆中的指针”，判断的方式类似于上下边界的检查，对其检查等。

半保守式GC

  JVM可以选择在栈上不记录类型信息，而在对象上记录类型信息。这样的话，扫描栈的时候仍然会和保守式GC(Conservative GC)的过程一样，但扫描到GC堆内的对象时因为对象带有足够类型信息了，JVM就能够准确判断出在该对象内什么位置的数据是引用类型了。这种是“半保守式GC”，也称为“根上保守(ConserVative With Respect To The Roots)”。

准确式GC

  “准确式GC”所谓的准确，关键就是“类型”，也就是说给定某个位置上的某块数据，要能知道它的准确类型是什么，这样才可以合理地解读数据的含义； GC所关心的含义就是“这块数据是不是指针”，这块数据不仅仅是GC堆内对象上的数据，包括活动记录（栈+寄存器）里的数据 。

分代收集理论相关

追踪式垃圾收集算法在少量垃圾回收的时候效率非常高效，特别是复制回收算法。但是长寿对象的存在会影响到回收回收的效率，这个时候就通过分区，使长寿的数据都堆积在一边，这样对年轻的数据使用复制回收算法就可以大大提升效率。在真实的商用垃圾回收大部分都采用了分代理论，哪怕G1回收器作为全区域回收器，在区域里面依旧用到了分代概念。

分代收集理论

分代收集理论建立在两个分代假说之上：

• 弱分代假说： 大多数对象都是朝生夕灭的 。这个假说已经在不同的编程语言和编程范式中得到证实；
• 强分代假说： 越长寿的对象越不容易死亡 。这个假说证据稍显不足，但是却依旧给大对象回收处理有一定的意义。

  这两个假说共同奠定了多款常用的垃圾收集器的一致设计原则：收集器应该将堆划分出不同区域，然后将回收对象依据年龄分配到不同的区域之中。

  除此之外新生代对象完全可以由老年代对象引用，如果产生这种引用，就需要遍历整个老年代来确定可达性分析的准确性，这样对内存回收带来极大的性能负担，所以引出了另一条假说

• 跨代引用假说： 跨代引用对比与同代引用来说仅占极少数 。

记忆集(Remembered Set)和卡表(Card Table)

  对于跨代引用来说，目前解决的方式就是记忆集和卡表。记忆集(Remembered Set)是一种抽象概念，而卡表(Card Table)可以是记忆集(Remembered Set)的一种实现方式。

  记忆集(Remembered Set)是在实现部分垃圾收集(partial GC)时 用于记录从非收集部分指向收集部分的指针的集合的抽象数据结构 。

  1. 记录精度（其实无论是remembered set还是card table，记录精度都有很大的选择余地）：

• 字粒度：每个记录精确到一个机器字(Word)。该字包含有跨代指针。
• 对象粒度：每个记录精确到一个对象。该对象里有字段含有跨代指针。
• 卡(card)粒度：每个记录精确到一大块内存区域。该区域内有对象含有跨代指针。

  (还有许多类型的颗粒度，可以自己想象)

  2. 数据结构

  记忆集(Remembered Set)：使用指针（对象指针或者字指针）的数据来实现，例如

struct RememberedSet {  
  Object* data[MAX_REMEMBEREDSET_SIZE];  
}; 
复制代码

卡表(Card Table)：使用字节数组来实现卡(card)的记录，每个卡(card)对应该数组里的一个bit或一个byte，例如

struct CardTable {  
  byte table[MAX_CARDTABLE_SIZE];  
};  
复制代码

字节数组卡表的每一个元素都对应着其标识的内存区域中一块特定大小的内存块，这个内存块被称作“卡页”(Card Page)，一般来说卡页大小都是以2的N次幂的字节数。一个卡页的内存中通常不止包含一个对象，只要卡页中有一个或者多个对象的字段存在着跨代指针，那就将对应的卡表的数组元素的标识变成1，称为这个元素变脏，没有则标识为0。在垃圾收集过程中只要筛选出来变脏的元素，把变脏的元素加入根节点集合(Root Set)一并扫描。

对象的年龄

在JVM的HotSpot虚拟机中，对象的年龄放置在对象头中，每当对象经历熬过一次回收，年龄加一，最大15。

对象分配规则和晋升老年代规则：

1. 对象优先在Eden分配
2. 大对象直接进入老年代
3. 长期存活对象进入老年代
4. 动态对象年龄判断（ 虚拟机并不是总是要求对象年龄需要达到规定的晋升年龄(MaxTenuringThreshold)才能晋升到老年代的，如果在Survivor空间中相同年龄所有对象大小的总和大于Survivor空间的一半，年龄大于或等于该年龄的对象就可以直接进入老年代，无须等到MaxTenuringThreshold中要求的年龄 ）
5. 空间分配担保

本文采用《深入理解Java虚拟机》和《The Garbage Collection Handbook》以及RednaxelaFX大佬的文章进行参考以及学习