扫盲系列 - GC 算法
JVM 常见的 GC 算法： 标记清除算法，复制算法，标记整理算法，分代收集算法和火车算法
标记清除算法
从”GC Roots”集合开始，将内存整个遍历一次，保留所有可以被 GC Roots 直接或间接引用到的对象，而剩下的对象都当作垃圾对待并回收，过程分两步。
- Mark 标记阶段：找到内存中的所有 GC Root 对象，只要是和 GC Root 对象直接或者间接相连则标记为灰色（也就是存活对象），否则标记为黑色（也就是垃圾对象）。
- weep 清除阶段：当遍历完所有的 GC Root 之后，则将标记为垃圾的对象直接清除。
示意图如下
优缺点
- 优点:
- 基于最基础的可达性分析算法，是最基础的标记收集算法，后续的算法都是在此基础上对其不足改进的
- 不需要对对象进行移动，并且对不存活的对象进行处理，在存活对象较多的情况下极为有效，
- 缺点:
- 效率不高，标记和清除效率都不高
- 空间问题，产生大量内存碎片，这会导致分配大内存对象时，无法找到足够的内存。从而需要提前触发另外一次 GC 操作
应用场景
针对老年代的 CMS 收集器
复制算法
为了解决标记清除算法的效率问题。克服了句柄开销和解决了堆碎片问题。
算法思路
- 把内存划分两个大小相等的快，每次只使用一块
- 当该快内存使用完了，就将该内存中存活的对象复制到另外一块区域，然后使用这一块
- 把已使用的内存块一次性清理掉，然后重复步骤 2 操作。
示意图如下
优缺点
- 优点： 使得每次都针对半个区域进行回收。内存分配时候不必考虑碎片化等问题
- 缺点：
- 空间浪费，可用内存是原来的一般，太过浪费。不过可以改良，不按照1：1划分。
- 效率随存活对象的升高而降低，当对象存活率较高的时候，需要更多的复制操作，效率变低。后面的标记整理算法可以解决这个问题。
应用场景
现在商业 JVM 都是采用这种算法（通过改良缺点1）来回收新生代
如 Serial 收集器， ParNew 收集器， Parallel Scavenger 收集器，G1（从局部看）
HotSpot 虚拟机改良算法
HotSpot VM ， Sun JDK 和 OpenJDK 中所带的虚拟机，也是目前使用范围最广的 Java 虚拟机。
弱代理论
分代垃圾收集基于弱代理论（weak generation hypothesis），具体描述如下
- 大多数分配了内存的对象存活不会太长，出在年轻代就会死掉
- 很少有对象从年老代变成年轻代
其中 IMB 研究表明，98%对象都是朝生夕死，所以并不需要按照1：1 划分内存。
HotSpot VM 新生代内存布局和算法
- 将新生代内存分为一个较大的 Eden 区和两个较小 survivor 区，
- 每次使用 Eden 区和其中一个 survivor 区
- 当回收时，将 Eden 区和使用的 survivor 区中存活的对象复制到另一个 survivor 区
- 清空 Eden 区和之前使用的那个 Survivor 区
- 后面就使用 Eden 区和复制到的那一个 Survivor 区，重复步骤 3。 默认Eden : Survivor 是8：1 ，即每次可以使用的空间是90%，只有一块 Survivor 区被浪费
分配担保
如果另一块 Survivor 区域没有足够的空间存放上一次新生代存活下来的对象，这些对象将直接通过分配担保机制（Handle Promotion）进入年老代，若老年代也满了就会触发一次 full GC 。也就是新生代和老年代都会进行回收。
标记整理算法
需要先从根节点开始对所有可达对象做一次标记，之后，它并不简单地清理未标记的对象，而是将所有的存活对象压缩到内存的一端。最后，清理边界外所有的空间。因此标记压缩也分两步完成：
- Mark 标记阶段：找到内存中的所有 GC Root 对象，只要是和 GC Root 对象直接或者间接相连则标记为灰色（也就是存活对象），否则标记为黑色（也就是垃圾对象）。
- Compact 压缩阶段：将剩余存活对象按顺序压缩到内存的某一端。
算法思路
- 标记，和标记清除算法一致
- 整理，在回收不存活对象之后，会将所有存活对象往左端空闲 k 空间移动，并更新指针。
示意图如下
优缺点
- 优点：
- 不会像复制算法那样，效率随存活率升高而降低，
老年代的特点：对象存活率高，没有额外的空间可以分配担保，所以老年代不采用复制算法，而是采用标记整理算法 - 不会像标记清除算法那样，产生大量内存碎片，因为清除前，都做了整理，存活对象集中到了一侧。
- 不会像复制算法那样，效率随存活率升高而降低，
- 缺点： 除了像标记算法那样标记外，还得需要整理的过程，效率更低。
应用场景
很多垃圾收集器采用这种方式回收老年代。例如 Serial Old 收集器，G1(从整体上看)
分代收集算法
分代垃圾回收策略：基于这样一个事实，不同的对象生命周期不一样，因此不同生命周期对象应该采用不同的回收算法，以便提高回收率，所以就结合不同的收集算法处理不同的区域，
算法思路
基于前面说的弱代理论，根据对象存活周期的不同把内存划分几个区域，这样就可以根据各个年代的特点采用最适当的 GC 算法，一般把 Java 堆分为年轻代和老年代以及持久代
年轻代
所有新生对象首先放到年轻代（Young Generation）。年轻代的目标就是尽快的收集那些生命周期短的对象，每次 GC 都会有大量对象死去，只有少量存活，新生代发生 GC 叫 Minor GC ,这个频率比较高，不一定等到 eden 满时候才发生，所以可以采用 copy 算法。
老年代
- 新生代发生几次 GC 后仍旧存活下来的对象，会放入老年代 (Old Generation)，可以认为老年代中存放的都是一些生命周期比较长的对象
- 内存也比新生代大的很多（大概是2：1），当老年代内存满时候会触发 Minor GC ,即 full GC ，这个频率较低，老年代对象存活时间较长，存活率标记高
- 对象存活率高，没有额外的空间进行分配担保，可以使用标记整理或者标记清理算法
持久代
用于存放静态文件，如 Java 类，方法等，持久代对 GC 没有显著影响，但是有些应用可能动态生成或者调用一些 class 文件，例如 Hibernate 等，在这种时候需要设置一个较大的持久空间来存放这些运行中生成的类。即持久代(Permanent Generation)。
优缺点
- 优点： 可以根据不同的年代采用最合适的算法
- 缺点： 仍不能控制每次垃圾收集时间
应用场景
目前几乎所有的商业虚拟机的垃圾收集器都采用分代收集算法， 如 HotSpot 虚拟机上全部的垃圾收集器： Serial， ParlNew , Parallel Scavenge , Serial Old , Parallel Old , CMS , G1 等
GC log
新生代和老年代所打印的日志是有区别的。
- 新生代 GC：这一区域的 GC 叫作 Minor GC。因为 Java 对象大多都具备朝生夕灭的特性，所以 Minor GC 非常频繁，一般回收速度也比较快。
- 老年代 GC：发生在这一区域的 GC 也叫作 Major GC 或者 Full GC。当出现了 Major GC，经常会伴随至少一次的 Minor GC。
注意：在有些虚拟机实现中，Major GC 和 Full GC 还是有一些区别的。Major GC 只是代表回收老年代的内存，而 Full GC 则代表回收整个堆中的内存，也就是新生代 + 老年代。
火车算法
也叫列车算法，是一种更彻底的分区域处理收集算法，是对分代收集算法的一个补充。
算法思路
在火车算法中，内存被分为块，多个快组成一个集合，为了形象化，一个车厢代表一个快，一列火车代表一个集合，如下图：
火车和车厢都按照创建顺序标号，每个车厢大小相等，但是火车包含的车厢数不相等。
每节车厢有一个记忆集合，而整个火车的记忆集合是所有车厢的记忆集合的总和。
记忆集合由组成车厢对象的引用组成，这些引用来自同一个车厢中序号较高的车厢中对象，以及序号较高的对象。
垃圾收集以车厢为单位，整体流程如下
- 选择序号较小的火车
- 如果火车记忆集合为空，释放整列火车并终止，否则执行步骤3
- 选择火车中标号较小的车厢
- 对于车厢中记忆集合的每个元素。
- 如果它是被一个根引用的对象，那么将复制到一列新火车上
- 如果是一个被其他火车对象指向的对象，那么将它复制到指向它的火车上去
- 如果有一些对象已经保留，那么通过这些对象可以触及到的对象将会复制到同一火车上去
- 如果一个对象被来自多个火车上的对象引用，那么可以将它复制到任何一个火车上
这个步骤，有必要对受到影响的引用进行更新
- 释放车厢并终止。 收集的时候会删除一些空车厢和空车，并在需要的时候，创建一些车箱和火车。
优缺点
- 优点： 可以在成熟对象空间提供限定时间的渐进收集，而不需要每次都进行大区域的垃圾回收过程，即可以控制垃圾回收时间，在指定时间内进行小区域的回收
- 缺点： 实现比较复杂，如采用类似算法的 G1 收集器直到 JDK7 才实现，一些场景下性价比不高
应用场景
JDK7 后的 HotSpot VM 的 G1 收集器采用了类似算法，能建立可预测的停顿时间模型。
搬运地址：
Java虚拟机垃圾回收(一) 基础：回收哪些内存/对象 引用计数算法 可达性分析算法 finalize() 方法 HotSpot 实现分析
既已览卷至此，何不品评一二：