十四、垃圾回收相关算法
1、标记阶段—引用计数算法
标记阶段：判断对象是否存活
- 堆存放：几乎所有的Java对象实例，GC之前：区分对象是否存活。
- GC执行只回收死亡对象，释放其所占用的内存空间。
- 标记死亡对象：当一个对象不再被存活的对象引用时
两种方式：引用计数算法、可达性分析算法
引用计数算法：每个对象上保存整形的引用计数属性，有对象引用计数器+1，减少引用计数器-1。计数器为零时，进行垃圾回收。
优点：实现简单、垃圾对象易识别、判定效率高、回收没有延迟性
缺点：无法解决循环引用问题
代码测试证明 java不是使用的引用计数算法：
垃圾回收日志：Eden 区占用率为1% ，说明进行了垃圾回收（未用：引用计数）
2、标记阶段—可达性分析算法
可达性分析算法（根搜索算法、追踪性垃圾收集）：解决循环引用问题，防止内存溢出。
基本思路：
- 以根对象（GCRoots）为起始点，按照从上到下的方式搜索被根对象集合所连接的目标对象是否可达
- 使用可达性分析算法后，内存中存活的对象都被根对象集合直接或间接连接着，搜索所走过的路径称为引用链
- 如果目标对象没有与任何引用链相连，则是不可达的，意味着该对象已经死亡，可以标记为垃圾对象
（面试常问）GC Roots可以是哪些元素？
- 虚拟机栈中引用的对象，比如：各个线程被调用的方法中使用到的参数、局部变量等。
- 本地方法栈内 JNI（通常说的本地方法）引用的对象
- 方法区中类静态属性引用的对象（如今在堆中），比如：Java类的引用类型静态变量
- 方法区中常量引用的对象，比如：字符串常量池（StringTable）里的引用
- 所有被同步锁synchronized持有的对象
- Java虚拟机内部的引用：基本数据类型对应的class对象，一些常驻的异常对象，如nullpointerException，OOMerror，系统类加载器
- 反映java虚拟机内部情况的JMXBean、JVMTI中注册的回调、本地代码缓存等。
GC Roots 的总结：
- 堆空间外的一些结构，比如：虚拟机栈、本地方法栈、方法区、字符串常量池等地方对堆空间进行引用的，都可以作为GC Roots进行可达性分析
- 除了这些固定的GC Roots集合以外，根据用户所选用的垃圾收集器以及当前回收的内存区域不同，还可以有其他对象“临时性”地加入，共同构成完整GC Roots集合。比如：分代收集和局部回收（PartialGC）。
- 如果只针对 Java堆中某一块内存区域进行垃圾回收，必须要考虑这个区域的对象可能被其他区域对象所引用，这是需要一并将关联的区域对象加入GC Roots集合中去考虑，才能保证可达性分析的准确性。比如只回收新生代，那么老年代可能也有指向新生代的对象，那么老年代也要考虑加入GC Roots集合。
3、对象的 finalization机制
对象销毁前的回调函数：finalize()
Java语言提供了对象终止（finalization）机制来允许开发人员提供对象被销毁之前的自定义处理逻辑。当垃圾回收器发现没有引用指向一个对象，即：垃圾回收此对象之前，总会先调用这个对象的finalize()方法。finalize() 方法允许在子类中被重写，用于在对象被回收时进行资源释放。通常在这个方法中进行一些资源释放和清理的工作，比如关闭文件、套接字和数据库连接等。
由于finalize()方法的存在，虚拟机中的对象有三种可能状态：
- 可触及：从根节点开始，可以到达这个对象。
- 可复活：对象的所有引用都被释放，但是对象有可能在finalize()中复活。
- 不可触及的：对象的finalize()被调用，并且没有复活，那么就会进入不可触及状态。不可触及的对象不可能被复活，因为finalize()只会被调用一次。
finalize() 具体执行过程
1、 判定一个对象objA是否可回收，至少要经历两次标记过程，如果对象objA到GCRoots没有引用链，则进行第一次标记；
2、 进行筛选，判断此对象是否有必要执行finalize()方法；
- 如果对象objA没有重写finalize()方法，或者finalize()方法已经被虚拟机调用过，则虚拟机视为“没有必要执行”，objA被判定为不可触及的。
- 如果对象objA重写了finalize()方法，且还未执行过，那么objA会被插入到F-Queue队列中，由一个虚拟机自动创建的、低优先级的Finalizer线程触发其finalize()方法执行。
3、 finalize方法是对象逃脱死亡的最后机会，稍后GC会对F-queue队列中的对象进行第二次标记，如果A在finalize方法中与引用链上的任何一个对象建立了联系，那么在第二次标记时，A会被移除即将回收集合；
4、 之后，对象会再次出现没有引用存在的情况在这个情况下，finalize()方法不会被再次调用，对象会直接变成不可触及的状态，注：一个对象的finalize()方法只会被调用一次；
4、MAT 与 JProfiler的GC Roots溯源
MAT是Memory Analyzer的简称，是一款功能强大的Java堆内存分析器。用于查找内存泄露以及查看内存消耗情况，基于Eclipse开发的一款免费性能分析工具。
public class RefCountGC {
private byte[] bigSize = new byte[5 * 1024 * 1024]; // 5M
Object reference = null;
public static void main(String[] args) {
RefCountGC obj1 = new RefCountGC();
RefCountGC obj2 = new RefCountGC();
obj1.reference = obj2;
obj2.reference = obj1;
new Scanner(System.in).next(); // 第一次dump
obj1 = null;
obj2 = null;
System.gc();
new Scanner(System.in).next(); // 第二次dump
}
}
第一次dump时obj1和obj2都还没被GC
第二次dump之后只剩下main方法形参：
5、清除阶段：标记-清除算法
清除阶段：当成功区分出内存中存活对象和死亡对象后，GC接下来的任务是执行垃圾回收，释放掉无用对象所占用的内存空间，以便有足够的可用内存空间为新对象分配内存。目前在JVM中比较常见的三种垃圾收集算法：
- 标记-清除算法（Mark-Sweep）
- 复制算法（Copying）
- 标记-压缩算法（Mark-Compact）
其中标记-清除算法分为标记和清除两个阶段：
标记： 从引用根节点开始遍历，标记所有被引用的对象，一般是在对象Header中记录为可达对象，注意标记引用对象，不是垃圾对象。
清除： 对堆内存从头到尾进行线性的遍历，如果发现某个对象在其Header中没有标记为可达对象，则将其回收。
执行过程：
清除对象的方式：把需要清除的对象地址保存在空闲地址列表里。下次有新对象需要加载时，判断垃圾的位置空间是否够，如果够，就存放并覆盖原有地址内容。
内存的分配方式：
- 采用指针碰撞的方式进行内存分配：如果内存空间以规整和有序的方式分布，即已用和未用的内存都各自一边，彼此之间维系着一个记录下一次分配起始点的标记指针，当为新对象分配内存时只需要通过修改指针的偏移量将新对象分配在第一个空闲内存位置上，这种分配方式就叫做指针碰撞（Bump the Pointer）。
- 采用空闲列表分配内存，这种情况下内存是不规整的。虚拟机需要维护一个空闲列表。
标记-清除算法缺点：
1、 在进行GC时，需要停止整个应用程序，用户体验差，效率不高；
2、 清理出来的空闲内存不连续，产生内存碎片；
3、 需要维护一个空闲列表；
6、清除阶段：复制算法
将活着的内存空间分为两块，每次只使用其中一块，在垃圾回收时将正在使用的内存中的存活对象复制到未被使用的内存块中，之后清除正在使用的内存块中的所有对象，交换两个内存的角色，最后完成垃圾回收。
Eden区、from区、to区的使用的就是复制算法
优点：
- 没有标记和清除过程，实现简单，运行高效
- 复制过去以后保证空间的连续性，不会出现“碎片”问题。
缺点：
- 需要两倍内存空间
- 对于G1这种分拆成大量region的GC，复制而不是移动，意味着GC需要维护region之间对象引用关系，内存占用、时间开销都很大
综上：复制算法适合垃圾对象很多，存活对象很少的场景；例如：Young区的Survivor0和Survivor1区
7、清除阶段：标记-压缩算法（标记-整理 、Mark - Compact）
标记-清除算法：不适合老年代，会产生大量内存碎片。
复制算法：适合新生代，存活对象少，垃圾对象多。不适用于老年代，大量存活对象。
标记-压缩算法的执行流程（标记-清除-压缩）
1、 第一阶段和标记清除算法一样，从根节点开始标记所有被引用对象；
2、 第二阶段将所有的存活对象压缩到内存一端，按顺序排放之后，清理边界外所有空间；
3、 最终效果等同于标记清除算法执行完成后，再进行一次内存碎片整理与标记清除算法本质区别，标记清除算法是非移动式的算法，标记压缩是移动式的；
优点：
- 消除了标记-清除算法当中，内存区域分散的缺点，我们需要给新对象分配内存时，JVM只需要持有一个内存的起始地址即可。
- 消除了复制算法当中，内存减半的高额代价。
缺点：
- 从效率上来说，标记-整理算法要低于复制算法。
- 移动对象的同时，如果对象被其他对象引用，则还需要调整引用的地址。
- 移动过程中，需要全程暂停用户应用程序。即：STW
8、小结
对比三种清除阶段的算法（没有最好的算法，只有最合适的算法）
| Mark-Sweep 标记清除 | Mark-Compact 标记整理 | Copying 复制 | |
|---|---|---|---|
| 速度 | 中等 | 最慢 | 最快 |
| 空间开销 | 少（但会堆积碎片） | 少（不堆积碎片） | 通常需要活对象的2倍大小（不堆积碎片） |
| 移动对象 | 否 | 是 | 是 |
9、分代收集算法
不同生命周期的对象可以采取不同的收集方式，以便提高回收效率，几乎所有的GC都采用分代收集算法执行垃圾回收的。
年轻代（Young Gen）：
- 区域相对老年代较小，对象生命周期短、存活率低，回收频繁。
- 这种情况下使用复制算法，速度是最快的。复制算法的效率只和当前存活对象大小有关，因此很适用于年轻代的回收。而复制算法内存利用率不高的问题，通过hotspot中的两个survivor的设计得到缓解。
老年代（Tenured Gen）：
-
区域较大，对象生命周期长、存活率高，回收不及年轻代频繁。
-
这种情况存在大量存活率高的对象，复制算法明显变得不合适。一般是由标记-清除或者是标记-清除与标记-整理的混合实现。
-
Mark 阶段的开销与存活对象的数量成正比。
-
Sweep 阶段的开销与所管理区域的大小成正相关。
-
Compact阶段的开销与存活对象的数据成正比。
10、增量收集算法
现有的算法，在垃圾回收过程中，应用软件将处于一种Stop the World的状态。在Stop the World状态下，应用程序所有的线程都会挂起，暂停一切正常的工作，等待垃圾回收的完成。
如果垃圾回收时间过长，应用程序会被挂起很久，将严重影响用户体验或者系统的稳定性。为了解决这个问题，即对实时垃圾收集算法的研究直接导致了增量收集（Incremental Collecting）算法的诞生。
基本思想：
- 如果一次性将所有的垃圾进行处理，需要造成系统长时间的停顿，那么就可以让垃圾收集线程和应用程序线程交替执行。每次，垃圾收集线程只收集一小片区域的内存空间，接着切换到应用程序线程。依次反复，直到垃圾收集完成。
- 总的来说，增量收集算法的基础仍是传统的标记-清除和复制算法。增量收集算法通过对线程间冲突的妥善处理，允许垃圾收集线程以分阶段的方式完成标记、清理或复制工作。
增量收集算法的优缺点：
- 使用这种方式，由于在垃圾回收过程中，间断性地还执行了应用程序代码，所以能减少系统的停顿时间。
- 因为线程切换和上下文转换的消耗，会使得垃圾回收的总体成本上升，造成系统吞吐量的下降。
11、分区算法
一般来说，在相同条件下，堆空间越大，一次GC时所需要的时间就越长，有关GC产生的停顿也越长。
为了更好地控制GC产生的停顿时间，将一块大的内存区域分割成多个小块，根据目标的停顿时间，每次合理地回收若干个小区间，而不是整个堆空间，从而减少一次GC所产生的停顿。
分代算法将按照对象的生命周期长短划分成两个部分，分区算法将整个堆空间划分成连续的不同小区间。每一个小区间都独立使用，独立回收。这种算法的好处是可以控制一次回收多少个小区间。