JVM面试（五）垃圾回收机制和算法
概述
了解Java虚拟机的垃圾回收机制（Garbage Collection，简称GC），我们也要像其作者John McCarthy一样，思考一下三个问题：
- 哪些内存需要回收？
- 什么时候回收？
- 如何回收？
虽然经过半个世纪的发展，在今天，内存回收技术已经相当成熟了。一切都无需我们操作，这些机制就会自动化处理。
但是当我们要排查各种内存溢出、内存泄露问题是，或者是垃圾收集机制影响系统达到更高并发量的时候，我们就要对这些垃圾收集和内存分配有一定了解，并且对其进行监控和调节优化。
哪些对象需要回收
之前说过，垃圾回收主要处理的是堆区的对象，那么我们首先要确认的就是，哪些对象需要回收？ 或者通俗来讲， 哪些对象是存活？哪些已经死去？
引用计数法
最简单的算法，就是在对象中添加一个计数器，每当有一个地方引用他的时候，就给这个计数器+1 。当引用失效的时候，计数器就-1 。 当计数器为0的时候，就是这个对象没有被使用，等于已经死去，可以被回收。
它的原理挺简单的，判定效率也高，大多数情况下是一个不错的选择。 比如微软的COM技术，Python语言等都用这个计数算法进行内存管理。
但是Java领域中，主流的Java虚拟机都没有选择用这个引用计数法来管理内存，因为这个简单的算法要考虑很多例外情况，最知名的就是这个缺陷循环引用问题，而且这种情况再java中也是挺常见的。
举个栗子，当比如有两个对象，都有instance字段。A.instance = B；B.instance = A。 如果除了这两个，没有其他引用的话，这两个 对象的计数器都是1，但是永远无法被收回。
可达性分析算法
目前主流商用的程序语言（Java、C#）的内存管理子系统，都是通过可达性 分析（Reachability Analysis）算法来判断对象是否存活的。这个算法的基本思路就是通过称为“GC Roots”的根对象，从这些根节点开始，根据引用关系向下延伸，走过的路称为“引用链”。 而那些引用链不能触达的对象，也就是这个对象不可达，证明不再被使用，可以被回收。如下图：
可以作为GC Roots的对象有以下几种：
- 在虚拟机栈（栈帧中的本地变量表）中引用的对象，譬如各个线程被调用的方法堆栈中使用到的参数、局部变量、临时变量等。
- 在方法区中类静态属性引用的对象，譬如Java类的引用类型静态变量。
- 在方法区中常量引用的对象，譬如字符串常量池（String Table）里的引用。
- 在本地方法栈中JNI（即通常所说的Native方法）引用的对象。
- Java虚拟机内部的引用，如基本数据类型对应的Class对象，一些常驻的异常对象（比如NullPointExcepiton、OutOfMemoryError）等，还有系统类加载器。
- 所有被同步锁（synchronized关键字）持有的对象。
- 反映Java虚拟机内部情况的JMXBean、JVMTI中注册的回调、本地代码缓存等。
简洁概括为
- 虚拟机栈（栈帧中的本地变量表）中引⽤的对象。
- 方法区中类静态属性和常量引⽤的对象。
- 本地方法栈中JNI（即⼀般说的Native方法）引用对象。
- 常量池
- 锁对象
- 基本数据类型class对象，常驻异常对象
总结：与GC Roots无关的对象，可以被垃圾回收机制回收；存在循环引用的对象，如果不在GC Roots引用链中可以被回收， 可解决循环引用问题
下面我们来剖析一下这个算法，看到底是如何标记的。
三色标记法
上面说了，通过GC Roots来遍历可达对象，那么用什么来标记呢。 就是在遍历的过程中按照是否访问过该对象，区分为三种颜色。
白色：本对象没有访问过 （有可能是为垃圾对象）；（垃圾清扫前的对象）
灰色：本对象已经被访问过，且本对象的所有属性没有访问过；本对象所有属性都访问过后，本对象由灰色变为黑色。
（初始标记阶段后的GCRoot对象）
黑色：本对象已经被访问过，且本对象的所有属性都被访问过；(并发标记完成后)
如下图：
大致过程如下：
- 初始时，所有对象都在白色容器中；
- 当收集器在做初始标记的时候，会暂停所有的用户线程，标记GC Root关联的直接对象A和B；将其放⼊到灰色盒子中。
- 在并发标记阶段（用户线程与GC线程同时运行），将本对象引用的其他对象移动灰色容器中，如果该对象没有引用到其他对象或者其他对象已经标记过，则该对象放到黑色容器中。
- 重复以上这些操作，到灰色容器为空时，则停止。
- 结束后，如果在白色容器中仍然存在对象，则认为它们就是与GC Root没有直接关联，则认为就是为不可达对象，可以被垃圾回收线程清理。
多标-浮动垃圾
为了效率，标记算法在并发标记阶段，GC线程与用户线程是同时进行的，所以标记过程中，对象的引用也有可能产生变动。所以就可能会有多标和漏标的情况。
比如：标记过程中，本来这个对象C已经标记为灰色，突然用户线程已修改了其他对象对C对象的引用，导致这个对象变为垃圾对象。 但是现在已经在灰色容器中，那么本次回收的时候，就不会清理这个C对象。还有在并发清楚阶段也会产生。
把这种对象称之为“浮动垃圾”，只能在下一次GC回收的时候进行清理。
漏标
当遍历到C的时候，C对象已经标记为灰色，放到灰色容器中。
突然用户线程将C->E对象的引用断开，然后建立了B->E的引用。
但是这个时候B对象已经是黑色，不会再次遍历了，就会导致E对象会被GC线程清理掉，这个就是漏标问题
如图所示：
漏标问题会有两个条件：
- 在扫描灰色对象的所有链路的时候，突然删除之前拥有的白色对象
- 并且又至少被一个黑色对象引用
解决方法：
增量更新法，CMS收集器会用这个方法，当黑色对象关联该白色对象的时候，将这个黑色对象重新标记为灰色，那么就可以在下次扫描的时候重新扫描这个对象。 优点是保证不会漏掉，缺点是效率低下，因为还要扫描所有的黑色对象是否被重新标记为灰色。
原始快照，当灰色对象突然不关联这个白色对象的时候，也将这个白色对象标记为灰色，继续扫描这个对象。无论是有没有黑色对象引用，都会将其处理为灰色，最终本次GC的过程中被当成浮动垃圾，下次在进行清理。
什么时候回收？如何回收？
上面已经分析了垃圾对象如何区分，那什么时候回收这些对象，也是有算法来处理。 这就是大名鼎鼎的分代算法
分代算法
- 将Java堆区分为新生代和老年代两个区域
- 新生代又分为Eden区、form区和to区（也有说是两个Survivor区和一个Eden区，都一样）
- 对象创建的时候都是在Eden区中，当Eden区满了，就要进行一次YoungGC，也就是新生代的垃圾回收
- 将存活的对象移动到form区或者to区，也就是两个Survivor区中的某一个，然后清空Eden区。
- 并且每次YoungGC也会清理Survivor区，将存活的对象放到另一个，清理这个
- 两个Survivor区就这样循环使用。
- 对象在新生代每经历一次YoungGC，就把寿命+1，当寿命大于15的时候，则将对象放入老年代中。
- 如果老年代也满了，就进行一次FullGC
YoungGC
新⽣代GC （Minor GC），用的是标记复制算法，因为是要将对象移动到不同的区域中。
新生代分为⼀块较大Eden空间和两块较小的 Survivor空间，每次分配内存只使⽤Eden和其中⼀块Survivor。发生垃圾搜集时，将Eden和Survivor中仍然存活的对象⼀次性复制到另外⼀块Survivor空间上，然后直接清理掉Eden和已用过的那块Survivor空间。HotSpot虚拟机默认Eden和Survivor的大小比例是8∶1，也即每次新生代中可用内存空间为整个新生代容量的90%（Eden的80%加上⼀个Survivor的10%），只有⼀个Survivor空间，即10%的新生代是会 被“浪费”的。
还有一点：
这个标记复制算法要移动所有的存活对象，所以在清理阶段，会出发stop the world 暂停其他用户的所有线程，等到垃圾回收结束的时候，用户线程再继续执行。
如图：
FullGC
如果对象在新生代经历了15次YoungGC还是存活状态，那么就晋升到老年代。
当老年代满了，就会出发一次FullGC。
FullGC用的是标记清除算法，缺点是会产生内存碎片。
标记整理算法
还有一种标记整理算法，就是标记出来存活对象后，将其移动到一起，然后清除边界以外的所有对象。
虽然这种方法没有碎片产生了，但是整理过程中会移动内存地址，效率偏低。
