Open xzhuz opened 4 years ago
https://hshanx.github.io/GlOx7ftC5/
困而学，学而知 好记性不如烂笔头
困而学，学而知
好记性不如烂笔头
在前面的引用计数法和可达性算法一文中，我们讲了一个引用要被回收需要达到的条件以及怎么判断一个引用是否要被回收。了解了这些知识，就到了今天要讲的垃圾收集算法。
垃圾收集算法分为几种：标记-清除、复制、标记-整理和分代收集算法。每个收集算法都不是独立存在的，一个收集算法在另一个收集算法也有引用到，比如分代收集算法的新生代就是使用的复制算法。话不多说，下面就来说说这几种垃圾收集算法吧。
分为两个标记和清除两个阶段：首先标记出所需要回收的对象，在标记完成后再回收所有被标记的对象。（标记过程可以参考引用计数法和可达性算法文中一节）。
标记-清除算法的优点就是简单，只需要将需要回收的对象标记出来，到了回收的时候，直接回收就是了。但是缺点也很明显：
为了解决标记-清除算法的缺点，出现了一个新的回收算法：复制算法。
回收算法主要的流程是：将可用的容量划分为大小相等的两块，每次只使用其中的一块。当这一块的内存用完了，就将还存活着的对象复制到另一块上面没然后在把已使用过的内存空间一次清理掉。
虽然这种收集算法能够解决内存碎片的问题，但是将内存缩为了原来的一半，代价有点高。这个算法也是后面要讲的分代收集算法的基础。
既然标记清除算法和复制算法有各种各样的缺点，那么中和一下这两个算法的优缺点，又有一个新的回收算法有闪亮登场了： 标记整理算法。
标记-整理算法的标记过程仍然与“标记-清除”算法一样，但是后续步骤不是直接对可回收对象进行清理，而是让所有存活的对象都向一段移动，然后直接清理掉端边界以外的内存。
在讲分代收集算法之前，我们先对上面讲到的几个算法作一个小总结。
标记清理和标记整理算法都是先对需要回收的对象进行标记，标记清理的后续操作是将标记的对象进行清除，而标记整理算法是将存活的对象都向一段移动，然后直接清理掉端边界以外的内存。复制算法是将内存划分为大小相等的两块，每次只使用其中一块，当启动一块使用完了，就换到另一块使用，把这一块清理掉。
标记清理算法的缺点很明显，很容易造成内存碎片，但贵在简单。复制算法的缺点也很明显，只使用其中一块内存，那就很浪费内存，但确是解决了内存碎片的问题。
上面的三个收集算法是下面要讲的这个垃圾收集算法基础。
分代收集算法就是根据对象存活周期的不同将内存划分为几块，一般是把Java堆分为新生代和老年代。
在新生代中，每次垃圾收集时都发现有大批对象死去，只有少量存活，那就算用复制算法。只需要付出少量存活对象的复制成本就可以完成收集。而老年代中因为对象存活率高，没有额外空间对它进行分配担保，就必须使用“标记-清理”或者“标记-整理”算法来进行回收。
由于目前的商业虚拟机几乎都是使用分代收集算法，所以我们就重点讲讲分代收集算法。
分代收集算法的思想是，将Java堆中的内存区域分为年轻代和老年代（Tenured Gen），如果再细分的话，年轻代有区分为： Eden区和Survivor区 。Survivor区又可以细分为From区和To区。如果要用的图形的方式表现出来，就如同下面的图示。
Eden 区, From space, To space。默认比例是8:1:1。
对象主要分配在新生代的Eden区上，如果启动了本地线程分配缓冲，将按线程有限的TLAB上分配。少数情况下也可能会直接分配在老年代中，分配规则并不是百分之百固定的，其细节取决于当前使用的哪一种垃圾收集器组合，还有虚拟机中与内存相关的参数的设置。
主要有下面几种普遍的分配策略
大多数情况下，对象在新生代Eden区中分配。当Eden区没有足够空间进行分配时，虚拟机将发起一次MinorGC。
MinorGC
虚拟机提供了-XX:+PrintGCDetails这个收集器日志参数，告诉虚拟机在发生垃圾收集行为时打印内存回收日志，并且在进程退出的时候输出当前的内存各区域分配情况。
-XX:+PrintGCDetails
新生代主要使用的复制算法。
所谓大对象是指，需要大量连续内存空间的Java对象。最典型的大对象就是那种很长的字符串以及数组。
虚拟机提供了一个-XX:PretenureSizeThreshold参数，令大于这个设置值的对象直接在老年代分配。这样做的目的是米边Eden区及两个Survivor区之间发生大量的内存复制（新生代采用复制算法收集内存）。
-XX:PretenureSizeThreshold
虚拟机为了识别哪些对象应该放在年轻代，哪些对象应该放在老年代。为了做到这一点，虚拟机给每个对象定义了一个对象年龄（Age）计数器。如果对象在Eden出生并经过第一次MinorGC后仍然存活，并且能被Survivor容纳的话，将被移动到Survivor空间中，并且对象年龄设为1。对象在Survivor区中每经历一次Minor GC，年龄就增加1，当它的年龄增加到一定程度（默认15），就将被晋升到老年代中。对象晋升老年代的年龄阈值，可以通过参数-XX:MaxTenuringThreshold设置。
-XX:MaxTenuringThreshold
老年代主要使用标记清除算法。
为了能更好适应不同程序的内存状况，虚拟机并不是永远地要求对象的年龄必须达到了MaxTenuringThreshold才能晋升老年代，如果在Survivor空间中相同年龄所有对象大小的总和大于Survivor空间一半，年龄大于或等于该年龄对象就可以直接进入老年代，无须等到MaxTenuringThreshold中要求的年龄。
MaxTenuringThreshold
新生代GC（MinorGC）：指发生在新生代的垃圾收集动作，因为Java对象大多都具备朝生夕灭的特性，所以MinorGC非常频繁，一般回收速度也比较快。
老年代GC（Major GC/Full GC)：指发生在老年代的GC，出现了Major GC，经常会伴随至少一次的MinorGC(但非绝对的，在Parallel Scavenge收集器的手机策略里就有直接进行Major GC的策略选择过程）。Major GC的速度一般会比MinorGC慢10倍以上。
需要注意的是，MinorGC是发生在新生代，FullGC是发生在老年代
在面试的时候，有一个知识点，就是什么时候会发生MinorGC？什么时候发生FullGC？这里我们也来说说吧。
什么时候触发MinorGC？
什么时候触发FullGC？
promotion failed
oncurrent mode failure
在说下面几个知识点之前，先来对分代收集算法做一个简单总结。
分代收集算法是根据对象的存活周期将内存空间分为了不同的空间，比如说年轻代和老年代。年轻代还可以细分为Eden区和Survivor区，Survivor区在细分又可以分为From区和To区。分代收集算法定义了一定的内存分配和回收策略：对象优先在Eden分配、大对象直接进入老年代以及长久存活的对象将进入老年代。这三个策略可以说是见名知意，这里不多做赘述。后面会讲一个空间分配担保，这个知识点也详细解释了这三个策略的原因。
然后就是MinorGC和FullGC，Minor GC发生在年轻代，Full GC 发生在老年代，这两个GC 有不同的触发条件，这里也不做赘述。
上面说到了分代收集算法的内存分配和回收策略，下面来讲讲这几个策略的具体原因。
在发生MinorGC 之前，虚拟机会先检查老年代最大可用的连续空间是否大于新生代所有对象总空间，如果这个条件成立，那么MinorGC可以确保是安全的，如果不成立，则虚拟机会查看HandlePromotionFailure设置值是否允许担保失败，如果允许，那么会继续检查老年代最大可用的连续空间是否大于历次晋升到老年代对象的平均大小，如果大于，则尝试着进行一次MinorGC，尽管这次MinorGC是有风险的：如果小于，或者HandlePromotionFailure设置不允许冒险，那么这时也要改为进行一次FullGC。
HandlePromotionFailure
下面解释一下“冒险”是冒了什么风险，前面提到过，新生代使用复制收集算法，但是为了内存利用率，只使用起一个Survivor空间来作为轮换备份，因此当出现大量对象在MinorGC后仍然存活的情况（最极端的情况就是内存回收或新生代的所有所有对象都存活），就需要老年代进行分配担保吗，把Survivor无法容纳的对象直接进入老年代。与生活中的贷款担保类似，老年代要进行这样的担保，前提是老年代本身还有容纳这些对象的剩余空间，一共有多少对象会活下来在实际完成内存回收之前是无法明确知道的，所以只好取之前每一次回收晋升到老年代对象容量的平均大小值作为经验值，与老年代的剩余空间进行比较，决定是否进行FullGC来让老年代腾出更多空间。
取平均值进行比较仍然是一种动态概率的手段，也就是说，如果某次MinorGC存活后的对象突增，远远高于平均值的话，依然会导致担保失败（Handle Promotion Failure）。
这里主要讲HotSpot虚拟机对于上面的收集算法的实现。
可作为GC Roots的节点主要在全局性的引用与执行上下文中，现在很多应用仅仅方法区就有数百兆，如果要逐个检查这里面的引用，那必然会消耗很多时间。
另外，可达性分析对执行时间的敏感还体现在GC停顿上，因为这项分析工作必须在一个能确保一致性的快照中进行-这里“一致性”的意思是指整个分析期间真个执行系统看起来就像被冻结在某个时间点上，不可能出现分析过程中对象引用关系还在不断变化的情况，该点不满足的话分析结果准确性就无法得到保证。这点导致GC进行时必须停顿所有Java执行线程（Sun将这件事情成为“Stop-The-World”）的其中一个重要原因，即使是在号称（几乎）不会发生停顿的CMS收集器中，枚举根节点时也是必须要停顿的。
Java虚拟机通过一组称为OopMap的数据结构来达到记录那些地方存放对象引用的目的，在类加载完成的时候，HotSpot就把对象内什么偏移量上是什么类型的数据计算出来，在JIT编译过程中，也会在特定的位置记录下栈和寄存器中那些位置是引用，这样，GC在扫描时就可以直接得知是什么信息了。
OopMap
特定的位置记录
在OopMap的协助下，HotSpot可以快速且准确地完成GC Roots枚举。但是如果引用引用关系变化，OopMap的也会相应变化，这样会造成很多空间浪费。
实际上，HotSpot没有为每条指令都生成OopMap，只是在特定的位置记录了这些信息，这些位置被称为安全点（safepoint），即程序执行时并非在所有的地方都停下来开始GC，只有在到达安全点时才能暂停。
安全点的选定不能太少导致GC等待时间太长，也不能太频繁导致过分增大运行时的负荷。
对于安全点，还需要考虑如何在GC发生时让所有线程都跑到最近的安全点上在停顿下来。这里有两种方案：
https://hshanx.github.io/GlOx7ftC5/
在前面的引用计数法和可达性算法一文中，我们讲了一个引用要被回收需要达到的条件以及怎么判断一个引用是否要被回收。了解了这些知识，就到了今天要讲的垃圾收集算法。
垃圾收集算法分为几种：标记-清除、复制、标记-整理和分代收集算法。每个收集算法都不是独立存在的，一个收集算法在另一个收集算法也有引用到，比如分代收集算法的新生代就是使用的复制算法。话不多说，下面就来说说这几种垃圾收集算法吧。
标记-清除算法
分为两个标记和清除两个阶段：首先标记出所需要回收的对象，在标记完成后再回收所有被标记的对象。（标记过程可以参考引用计数法和可达性算法文中一节）。
标记-清除算法的优点就是简单，只需要将需要回收的对象标记出来，到了回收的时候，直接回收就是了。但是缺点也很明显：
复制算法
为了解决标记-清除算法的缺点，出现了一个新的回收算法：复制算法。
回收算法主要的流程是：将可用的容量划分为大小相等的两块，每次只使用其中的一块。当这一块的内存用完了，就将还存活着的对象复制到另一块上面没然后在把已使用过的内存空间一次清理掉。
虽然这种收集算法能够解决内存碎片的问题，但是将内存缩为了原来的一半，代价有点高。这个算法也是后面要讲的分代收集算法的基础。
标记-整理算法
既然标记清除算法和复制算法有各种各样的缺点，那么中和一下这两个算法的优缺点，又有一个新的回收算法有闪亮登场了： 标记整理算法。
标记-整理算法的标记过程仍然与“标记-清除”算法一样，但是后续步骤不是直接对可回收对象进行清理，而是让所有存活的对象都向一段移动，然后直接清理掉端边界以外的内存。
简单总结
在讲分代收集算法之前，我们先对上面讲到的几个算法作一个小总结。
标记清理和标记整理算法都是先对需要回收的对象进行标记，标记清理的后续操作是将标记的对象进行清除，而标记整理算法是将存活的对象都向一段移动，然后直接清理掉端边界以外的内存。复制算法是将内存划分为大小相等的两块，每次只使用其中一块，当启动一块使用完了，就换到另一块使用，把这一块清理掉。
标记清理算法的缺点很明显，很容易造成内存碎片，但贵在简单。复制算法的缺点也很明显，只使用其中一块内存，那就很浪费内存，但确是解决了内存碎片的问题。
上面的三个收集算法是下面要讲的这个垃圾收集算法基础。
分代收集算法
分代收集算法就是根据对象存活周期的不同将内存划分为几块，一般是把Java堆分为新生代和老年代。
在新生代中，每次垃圾收集时都发现有大批对象死去，只有少量存活，那就算用复制算法。只需要付出少量存活对象的复制成本就可以完成收集。而老年代中因为对象存活率高，没有额外空间对它进行分配担保，就必须使用“标记-清理”或者“标记-整理”算法来进行回收。
由于目前的商业虚拟机几乎都是使用分代收集算法，所以我们就重点讲讲分代收集算法。
分代收集算法的思想是，将Java堆中的内存区域分为年轻代和老年代（Tenured Gen），如果再细分的话，年轻代有区分为： Eden区和Survivor区 。Survivor区又可以细分为From区和To区。如果要用的图形的方式表现出来，就如同下面的图示。
Eden 区, From space, To space。默认比例是8:1:1。
内存分配和回收策略
对象主要分配在新生代的Eden区上，如果启动了本地线程分配缓冲，将按线程有限的TLAB上分配。少数情况下也可能会直接分配在老年代中，分配规则并不是百分之百固定的，其细节取决于当前使用的哪一种垃圾收集器组合，还有虚拟机中与内存相关的参数的设置。
主要有下面几种普遍的分配策略
对象优先在Eden分配
大多数情况下，对象在新生代Eden区中分配。当Eden区没有足够空间进行分配时，虚拟机将发起一次
MinorGC。虚拟机提供了
-XX:+PrintGCDetails这个收集器日志参数，告诉虚拟机在发生垃圾收集行为时打印内存回收日志，并且在进程退出的时候输出当前的内存各区域分配情况。新生代主要使用的复制算法。
大对象直接进入老年代
所谓大对象是指，需要大量连续内存空间的Java对象。最典型的大对象就是那种很长的字符串以及数组。
虚拟机提供了一个
-XX:PretenureSizeThreshold参数，令大于这个设置值的对象直接在老年代分配。这样做的目的是米边Eden区及两个Survivor区之间发生大量的内存复制（新生代采用复制算法收集内存）。长久存活的对象将进入老年代
虚拟机为了识别哪些对象应该放在年轻代，哪些对象应该放在老年代。为了做到这一点，虚拟机给每个对象定义了一个对象年龄（Age）计数器。如果对象在Eden出生并经过第一次MinorGC后仍然存活，并且能被Survivor容纳的话，将被移动到Survivor空间中，并且对象年龄设为1。对象在Survivor区中每经历一次Minor GC，年龄就增加1，当它的年龄增加到一定程度（默认15），就将被晋升到老年代中。对象晋升老年代的年龄阈值，可以通过参数
-XX:MaxTenuringThreshold设置。老年代主要使用标记清除算法。
动态对象年龄判定
为了能更好适应不同程序的内存状况，虚拟机并不是永远地要求对象的年龄必须达到了
MaxTenuringThreshold才能晋升老年代，如果在Survivor空间中相同年龄所有对象大小的总和大于Survivor空间一半，年龄大于或等于该年龄对象就可以直接进入老年代，无须等到MaxTenuringThreshold中要求的年龄。MinorGC和FullGC
新生代GC（MinorGC）：指发生在新生代的垃圾收集动作，因为Java对象大多都具备朝生夕灭的特性，所以MinorGC非常频繁，一般回收速度也比较快。
老年代GC（Major GC/Full GC)：指发生在老年代的GC，出现了Major GC，经常会伴随至少一次的MinorGC(但非绝对的，在Parallel Scavenge收集器的手机策略里就有直接进行Major GC的策略选择过程）。Major GC的速度一般会比MinorGC慢10倍以上。
需要注意的是，MinorGC是发生在新生代，FullGC是发生在老年代
在面试的时候，有一个知识点，就是什么时候会发生MinorGC？什么时候发生FullGC？这里我们也来说说吧。
MinorGC和FullGC的触发条件
什么时候触发MinorGC？
什么时候触发FullGC？
promotion failed（在进行minorGC时，Survivor space放不下，分配担保时担保失败，对象只能放入老年代，然而此时老年代也放不下）,oncurrent mode failure（在进行GMS GC过程中同时有对象要放入老年代中，而此时老年代空间不足）。简单总结
在说下面几个知识点之前，先来对分代收集算法做一个简单总结。
分代收集算法是根据对象的存活周期将内存空间分为了不同的空间，比如说年轻代和老年代。年轻代还可以细分为Eden区和Survivor区，Survivor区在细分又可以分为From区和To区。分代收集算法定义了一定的内存分配和回收策略：对象优先在Eden分配、大对象直接进入老年代以及长久存活的对象将进入老年代。这三个策略可以说是见名知意，这里不多做赘述。后面会讲一个空间分配担保，这个知识点也详细解释了这三个策略的原因。
然后就是MinorGC和FullGC，Minor GC发生在年轻代，Full GC 发生在老年代，这两个GC 有不同的触发条件，这里也不做赘述。
上面说到了分代收集算法的内存分配和回收策略，下面来讲讲这几个策略的具体原因。
空间分配担保
在发生MinorGC 之前，虚拟机会先检查老年代最大可用的连续空间是否大于新生代所有对象总空间，如果这个条件成立，那么MinorGC可以确保是安全的，如果不成立，则虚拟机会查看
HandlePromotionFailure设置值是否允许担保失败，如果允许，那么会继续检查老年代最大可用的连续空间是否大于历次晋升到老年代对象的平均大小，如果大于，则尝试着进行一次MinorGC，尽管这次MinorGC是有风险的：如果小于，或者HandlePromotionFailure设置不允许冒险，那么这时也要改为进行一次FullGC。下面解释一下“冒险”是冒了什么风险，前面提到过，新生代使用复制收集算法，但是为了内存利用率，只使用起一个Survivor空间来作为轮换备份，因此当出现大量对象在MinorGC后仍然存活的情况（最极端的情况就是内存回收或新生代的所有所有对象都存活），就需要老年代进行分配担保吗，把Survivor无法容纳的对象直接进入老年代。与生活中的贷款担保类似，老年代要进行这样的担保，前提是老年代本身还有容纳这些对象的剩余空间，一共有多少对象会活下来在实际完成内存回收之前是无法明确知道的，所以只好取之前每一次回收晋升到老年代对象容量的平均大小值作为经验值，与老年代的剩余空间进行比较，决定是否进行FullGC来让老年代腾出更多空间。
取平均值进行比较仍然是一种动态概率的手段，也就是说，如果某次MinorGC存活后的对象突增，远远高于平均值的话，依然会导致担保失败（Handle Promotion Failure）。
HotSpot的算法实现
这里主要讲HotSpot虚拟机对于上面的收集算法的实现。
枚举根节点
可作为GC Roots的节点主要在全局性的引用与执行上下文中，现在很多应用仅仅方法区就有数百兆，如果要逐个检查这里面的引用，那必然会消耗很多时间。
另外，可达性分析对执行时间的敏感还体现在GC停顿上，因为这项分析工作必须在一个能确保一致性的快照中进行-这里“一致性”的意思是指整个分析期间真个执行系统看起来就像被冻结在某个时间点上，不可能出现分析过程中对象引用关系还在不断变化的情况，该点不满足的话分析结果准确性就无法得到保证。这点导致GC进行时必须停顿所有Java执行线程（Sun将这件事情成为“Stop-The-World”）的其中一个重要原因，即使是在号称（几乎）不会发生停顿的CMS收集器中，枚举根节点时也是必须要停顿的。
Java虚拟机通过一组称为
OopMap的数据结构来达到记录那些地方存放对象引用的目的，在类加载完成的时候，HotSpot就把对象内什么偏移量上是什么类型的数据计算出来，在JIT编译过程中，也会在特定的位置记录下栈和寄存器中那些位置是引用，这样，GC在扫描时就可以直接得知是什么信息了。安全点
在
OopMap的协助下，HotSpot可以快速且准确地完成GC Roots枚举。但是如果引用引用关系变化，OopMap的也会相应变化，这样会造成很多空间浪费。实际上，HotSpot没有为每条指令都生成OopMap，只是在特定的位置记录了这些信息，这些位置被称为安全点（safepoint），即程序执行时并非在所有的地方都停下来开始GC，只有在到达安全点时才能暂停。
安全点的选定不能太少导致GC等待时间太长，也不能太频繁导致过分增大运行时的负荷。
对于安全点，还需要考虑如何在GC发生时让所有线程都跑到最近的安全点上在停顿下来。这里有两种方案：