垃圾收集算法

这里说说5种GC算法，在说GC算法前，先谈谈判断对象是否活着的可达性分析算法

• 可达性分析算法
• 引用计数算法
• 标记-清除算法
• 标记-整理算法
• 复制算法
• 分代收集算法

可达性分析算法

垃圾回收，首先要判断对象是否还活着.

Java通過可达性分析(Reachability Analysis)来判定对象是否存活

算法基本思路：
- 通过一系列称为”GC Roots”的对象作为起点，从这些节点开始向下搜索，搜索走过的路径，叫做引用链(Reference Chain)
- 当一个对象到GC Roots没有任何引用链相连，从图论来说，就是从GC Roots到对象不可达，此时判定对象不可用

Java中，可作为GC Roots的對象包括四种

• VM Stack(栈帧中的本地变量表)中引用的对象
• 本地方法栈中JNI(即Navtive方法)引用的对象
• 方法区中类静态属性引用的对象
• 方法区中常量引用的对象

创建–>可达<–>可恢复–>不可达–>垃圾回收

强引用StringReference

• 创建对象，并把对象赋给一个引用变量，程序通过这个引用变量来操作对象，对象和数组都采用了强引用。

• 一个对象被一个或以上引用变量引用，则处于可达状态，不会被GC

软引用SoftReference

• 要用java.lang.ref.SoftReference实现
• 描述有用但非必需的对象
• 内存空间足够时，不会被GC；否则，可能会被GC
• 常用于对内存敏感的程序中
• get()获取引用的对象

弱引用WeakReference

• java.lang.ref.WeakReference实现
• 描述非必需对象
• 不管内存是否足够，都会被GC
• get()获取引用的对象

虚引用PhantomReference

• java.lang.ref.PhantomRefernce必须和java.lang.ref.RefernceQueue引用队列联合使用
• 类似于没有引用，和没有引用的效果大致相同
• 主要用于跟踪对象被垃圾回收的状态
• !!! get()无法获取引用的对象
• GC后，虚引用会被放入引用队列

即使在可达性分析算法中不可达的对象，也并非是“非死不可”，这时还处于“缓刑”状态，真正标记一个对象的死亡，至少经历两次标记过程

• 对象在可达性分析后，发现没有GC Roots相连接的引用链，此时被第一次标记，且进行一次筛选
  
  • 筛选的条件是：是否有必要执行对象的finalize()方法
  • 对象沒有重写finalze()方法，或者finalize()已经被虚拟机调用过–>没必要执行
• 如果被判定为“有必要执行”，那么对象会被放到一个叫做F-Queue的队列中，并在稍后由一个JVM自动建立的、低优先级的Finalizer线程去执行finalize()方法.
• 稍后，GC将对F-Queue中的对象进行第二次小规模的标记. 如果对象没有在finalize()中复活，那基本真的被回收了

引用计数算法(Reference Counting)

• 老牌的垃圾回收算法

• 给对象添加一个引用计数器，有一个地方引用它时，计数器+1；引用失效时，-1；计数器为0，对象就是不可能再被使用

• 客观来说，实现简单，判定效率高

• 应用如：微软的Component Object Model技术,Python,ActionScript3

• 但主流Java虚拟机没有用，因为很难解決对象间的循环引用问题

• 引用和去引用伴随+,-，影响性能

这涉及到如何判定对象是否可达，或者说是否活着，被引用着

标记-清除算法(Mark-Sweep)

• 最基础的算法，分为“标记”，“清除”两个阶段
• 这是所有收集算法的基础，后续算法都是基于这种思路，并对其不足进行改进而得到的。
• 首先，标记出需要回收的对象

• 接着，标记完成后，统一回收所有标记的对象

• 主要问题:

  • 效率: 标记和清除两个过程的效率都不高
  • 空间碎片: 标记清除后会产生大量不连续的内存碎片，碎片过多会导致大对象无法分配到足够的连续内存，从而不得不提前触发GC，甚至Stop The World

复制算法(Copying)

• 为解决效率问题，复制算法出现了

• 将内存分为大小相等的两块，每次只用一块

• 在一块内存中，当它用完了，就把还或者的对象复制到另外一块大小相等的内存中，连续存储；同时，一次过清理已经使用过的内存空间
• 相当于每次都回收整个半区，不用考虑碎片问题，只需移动堆顶指针，按顺序分配，实现简单，运行高效
• 主要问题
  
  • 效率: 在对象存活率较高时，复制操作次数多，效率降低
  • 空间: 內存缩小了一半；需要額外空间做分配担保(老年代)
• From Survivor, To Survivor使用的就是复制算法。老年代不使用这种算法

标记-整理(Mark-Compact)

• 根据老年代的特点，提出了标记-整理/压缩算法

• 标记阶段与标记-清除算法一样

• 后续，让存活对象都向一端移动，对齐，直接清理掉端边界以外的内存
• 老年代使用的算法

分代收集算法(Generational Collection)

当前的商业虚拟机的垃圾回收都采用 分代收集 算法。根据对象存活周期的不同，将内存划分为几块。

一般将Java堆分为新生代和老年代。

新生代: 每次GC都有大批对象死去，只有少量存活

• 使用复制算法，只需要复制少量存活的对象

老年代：对此存活率高，没有额外空间做分配担保

• 使用 标记-清除,标记-整理两种算法

HotSpot的算法实现

首先，要解决的，是可达性分析，从GC Roots中找对象是否有可达的引用链。

枚举GC Roots根节点

可做GC Roots节点的，上文说过，主要有 全局性的引用(包括常量或类静态属性)，执行上下文(栈帧中的本地变量表和JNI引用的对象). 问题是，现在的应用，仅方法区就数百Megabyte，如果逐个检查这里边的引用，必然消耗很多时间

可达性分析必须在一个能确保一致性的内存快照中进行，分析期间，内存系统不能出现变化，否则，会出现分析不正确的情况，例如，前脚这边标记了A对象不可达，此时内存系统还在运行，万一A又被引用了，但A已经被标记为不可达。所以，得有GC停顿,号称几乎不会GC停顿的CMS收集器，在枚举根节点时，也必须停顿

目前主流VM使用准确式GC，所以不需要一个不漏地检查完所有的全局和上下文的引用的位置，虚拟机有办法直接得知哪些地方存放着对象的引用

HotSpot的实现中，使用一组叫做OopMap的数据结构来达到目的。

(1)类加载完成时，HotSpot就把对象内什么偏移量上是什么类型的数据计算出来。
(2)在JIT编译过程中，会在特定的位置记录下栈和寄存器中，哪些位置是引用

这样，GC扫描时，就可以直接得知这些信息了

安全点(SafePoint)

在OopMap(Ordinary Object Pointer Map)的协助下，HotSpot可以快速准确完成GC Roots枚举。

问题是，引用关系变化，OopMap内容变化的指令非常多，如果为每一条指令生成对应的OopMap,那会需要有大量的空间，GC的空间成本会变得很高

事实上，HotSpot没有为每条指令生成OopMap，前面说了，是在“特定位置”，这个特定位置，就是安全点SafePoint. 程序执行不是所有地方都停顿下来GC，而是到安全点，才停顿。

安全点选定

所以，安全点的选定，不能太过少，否则GC等待时间太长，产生OOM；也不能太过频繁，否则会增大运行时的负荷。

因此，安全点选择的准则：

• 是否具有让程序长时间执行的特征

具有这个特征的就是指令序列复用，例如方法调用，循环跳转，异常跳转。所以，具有这些功能的指令才会产生SafePoint

让所有线程跑到最近的安全点

另一个问题，发生GC时，如何让所有线程跑到最近的安全点，除了JNI调用的线程。

两种方案

• 抢占式中断(Preemptive Suspension)
  
  • GC来时，先中断线程，若发现线程不在安全点上，恢复线程，让它跑的安全点
  • 现在，几乎没有VM使用这种方式
• 主动式中断(Voluntary Suspension)
  
  • 不主动操作线程，GC来时，简单地设个标记，各个线程执行时主动轮询这个标记，发现为真时，自己中断挂起
  • 轮询标记的地方和安全点重合，另外加上创建对象时需要分配内存的地方

安全区域(Safe Region)

SafePoint只是解决获得CPU执行时间的线程，在不太长的时间内，可以遇到GC的SafePoint的问题。

但没有分配到CPU执行时间的线程，如Sleep,Block状的线程，它们无法响应JVM的中断请求，跑到SafePoint中断挂起，JVM显然也不会等待线程重新获得CPU时间

对这一问题，需要安全区域Safe Region

安全区域

• 一段代码片段中，引用关系不会发生变化
• 这个区域之中，任意地方开始GC，都是安全的
• 可以看作SafePoint的扩展

当线程执行到安全区域中的代码时，首先标识自己已经进入Safe Region。那么，这段时间里JVM发起GC时，就不用管标识自己在Safe Region状态的线程了，因为这些线程的引用关系不会发生变化。

线程离开Safe Region时，要检查系统是否已经完成GC Roots枚举或者整个GC过程。如果沒有，就必須等待，直到收到可以安全离开的信号为止；如果完成了，线程继续执行。