垃圾回收相关算法

1.标记阶段

1.1 引用计数算法（HotSpot并没使用）

1.1.1 实现原理

每个对象保存一个整型的引用计数器属性，用来记录对象被引用的情况，当引用计数器值为0的时候，可进行回收该对象

1.1.2 优缺点

优点：
	实现简单，垃圾对象便于识别，判定效率高，回收没有延时
缺点：
	需要引用计数器，增加空间开销
	维护引用计数器，增加时间开销
	无法处理循环引用（最关键）

1.1.3 循环引用

S引用A，A引用B，B引用C，C引用A。当S置为null的时候，其他三个已经可以回收，但是引用计数器都是1

1.1.4 Python如何解决循环引用

1、手动解除，在合适的时候手动解除引用
2、使用弱引用weakref

1.2 可达性分析算法

1.2.1 实现原理

是以根对象集合（GC Roots）为起点，由上至下进行搜索，判断目标对象是否可达，搜索走过的路径称为引用链，如果没有任何引用链，则证明是垃圾对象

1.2.2 GC Roots

1.虚拟机栈中引用的对象，比如各个线程被调用的方法中使用到的参数，局部变量等
2.本地方法栈内JNI（通常说的本地方法）引用的对象
3.方法区中静态属性引用的对象，比如Java类的引用类型静态变量
4.方法区中常量引用的对象，比如串池里的引用
5.所有被同步锁synchronized持有的对象
6.Java虚拟机内部的引用，基本数据类型对应的class对象，一些常驻的异常对象，如nullpointerException，OOMerror，系统类加载器
7.反映java虚拟机内部情况的JMXBean,JVMTI中注册的回调，本地代码缓存等
8.除了固定的GC Roots集合之外，根据用户选择的垃圾收集器以及当前回收的内存区域不同，还可以有其他对象临时性的加入，共同构成完整GCRoots集合，比如分代收集和局部回收（面试加分项）

1.2.3 注意事项

如果使用可达性分析算法。分析工作必须在一个能保障一致性的快照中进行，这也是导致GC进行时必须发生STW（stop the word的重要原因）

2.对象的finalization机制

2.1 finalization简介

1.Java语言提供了对象终止finaliztion机制来允许开发人员提供对象被销毁之前的自定义处理逻辑
2.当垃圾回收器发现没有引用指向一个对象，即垃圾回收此对象之前，总会先调用这个对象的finalize（）方法
3.finalize（）方法允许在子类中被重写，用于在对象被回收时进行资源释放，通常在这个方法中进行一些资源释放和清理的工作，比如关闭文件，套接字和数据库链接等

永远不要主动调用某个对象的fianlize（）方法，应该交给垃圾回收机制调用，原因如下：
1.fianlize有可能导致对象复活
2.fianlize方法执行时间是没有保障的，它完全由GC线程决定，在极端情况下，若不发生GC，则fianlize方法没有机会执行
3.一个糟糕的fianlize方法会严重影响GC性能

2.2 虚拟机对象三种状态

由于fianlize方法的存在，虚拟机中的对象一般处于三种可能的状态
1.可触及的。从根节点开始，可以到达这个对象
2.可复活的。对象的所有引用都被释放了，但是对象有可能在finalize（）中复活
3.不可触及的。对象的finalize（）被调用，并且没有复活，那么就会进入不可触及状态。不可触及的对象不可能被复活，因为finalize（）只会被调用一次

ps：只有对象再不可触及时才可以被回收

2.2.1 回收过程

判断一个对象ObjA是否可以被回收，至少需要经历两次标记过程:
1.如果对象到GCRoots没有引用链，则进行第一次标记
2.进行筛选，判断此对象是否有必要执行finalize（）方法
	2.1如果对象A没有重写finalize方法，或者finalize方法已经被虚拟机调用过，则虚拟机视为没有必要执行，对象A被判定为不可触及的
	2.2如果对象A重写finalize（）方法，且还未执行过，那么A会被插入到F-queue队列中，有一个虚拟机自动创建的，低优先级的Finalizer线程触发其finalize（）方法执行
	2.3finalize方法是对象逃脱死亡的最后机会，稍后GC会对F-queue队列中的对象进行第二次标记，如果A在finalize方法中与引用链上的任何一个对象建立了联系，那么在第二次标记时，A会被移除即将回收集合。之后，对象会再次出现没有引用存在的情况下，finalize方法不会再被调用，对象直接变为不可触及状态

3.清除阶段

目前在JVM中比较常见的三种垃圾收集算法是：
1.标记-清除算法（Mark-Sweep）
2.复制算法（Copying）
3.标记-压缩算法（Mark-Compact）

3.1 标记-清除算法（Mark-Sweep）

3.1.1 执行过程

1.标记：
从引用根节点开始遍历，标记所有被引用的对象，一般是在对象Header中记录为可达对象
注意，注意标记引用对象，不是垃圾对象，标记信息放在对象头里
2.清除：
对堆内存从头到尾进行线性的遍历，如果发现某个对象在其Header中没有标记为可达对象，则将其回收

3.1.2 缺点

1.效率不高
2.在GC时，需要发生STW，用户体验差
3.产生内存碎片，需要维护空闲列表

3.1.3 何为清除

所谓的清除并不是真的置空，而是把需要清除的对象地址保存在空闲的地址列表里，下次有新对象需要加载时，判断垃圾的位置空间是否够，如果够就存放。
ps：电脑删除的文件可以恢复就是这个道理

3.2 复制算法（Copying）

3.2.1 核心思想

将或者的内存空间分为两块，每次使用其中一块。在垃圾回收时，将正在使用的内存中的存活的对象复制到未被使用的内存块中，之后清除正在使用的内存块中的所有的对象，交换两个内存的角色，最后完成垃圾回收

3.2.2 优点

1.没有标记和清除的过程，实现简单高效
2.复制过去以后的保证空间的连续性，不会出现碎片的问题

3.2.3 缺点

1.需要两倍的内存空间
2.对于G1这种拆分为大量region的GC，复制而不是移动，意味着GC需要维护region之间的引用关系，不管是内存占用或者时间开销也不小。
3.如果系统中的垃圾对象很多，需要复制的存活对象数量并不会太大，或者非常低才行

ps：特别适合垃圾对象多，存活对象少的场景，比如s0和s1

3.3 标记-压缩算法（Mark-Compact）

3.3.1 实现原理

1.第一个阶段和标记清除算法一样，从根节点开始标记所有被引用的对象
2.第二阶段将所有的存货对象压缩在内存的一端，按照顺序排放
3.之后清理边界外所有的空间

备注：
1.最终效果等同于标记清除算法执行完成后，再进行一次内存碎片整理。
2.与标记清除算法本质区别，标记清除算法是非移动式的算法，标记压缩是移动式的
3.是否移动回收后的存活对象时一项优缺点并存的风险决策

3.3.2 优点

1.消除了标记清除算法内存区域分散的缺点，
2.消除了复制算法中，内存减半代价

3.3.3 缺点

1.从效率上来讲，标记整理算法要低于复制算法
2.移动对象的同时，如果对象被其他对象引用，则还需要调整引用的地址
3.移动的过程中，需要全程暂停用户应用程序，即STW

3.3.4 指针碰撞

如果内存分配规整，已用和未用内存都各自一边，彼此之间维护记录线依次分配起始点的标记指针，当为新对象分配内存时，只需要通过修改指针的偏移量，将新对象分配在第一个空闲内存位置上，这种分配方式就是指针碰撞（Bump the Pointer）

3.4 小结

3.5 分代收集算法

3.5.1 实现思想

1.不同生命周期的对象可以采取不同额收集方式，以便提高回收效率
2.几乎所有的GC都采用分代收集算法执行垃圾回收的

3.5.2 HotSpot举例

1.年轻代：生命周期短，存活率低，回收频繁
2.老年代：区域较大，生命周期长，存活率高，回收不及年轻代频繁

3.6 增量收集算法

3.6.1 实现思想

1.每次垃圾收集线程只收集一小片区域的内存空间，接着切换到应用程序线程，依次反复，直到垃圾收集完成
2.通过对线程间冲突的妥善管理，允许垃圾收集线程以分阶段的方式完成标记、清理或复制工作

3.6.2 缺点

线程和上下文切换导致系统吞吐量的下降

3.7 分区算法

3.7.1 实现思想

1.为了控制GC产生的停顿时间，将一块大的内存区域分割成多个小块，根据目标的停顿时间，每次合理的回收若干个小区间，而不是整个堆空间，从而减少一次GC所产生的时间
2.分代算法是将对象按照生命周期长短划分为两个部分，分区算法是将整个堆划分为连续的不同的小区间
3.每一个小区间都独立使用，独立回收，这种算法的好处是可以控制一次回收多少个小区间

3.8 写在最后

这些知识基本的算法思路，实际GC实现过程要复杂的多，目前发展中的前沿GC都是复合算法，并行和并发兼备