what
 
 可达性分析算法是用来判断对象是否存活的方法，与之相同的算法还有引用计数法。
 
Java、C#使用的是可达性分析算法，在一些脚本语言中会使用引用计数法，例如：Python,Squirrel。
 
 
 
引用计数法:
 
原理：有一个地方引用对象，则此对象计数器 +1，引用失效则-1，计数器为0则不能使用
 
优缺点：判断效率高，实现简单，但是难以解决对象互相循环引用问题。
 
 
 
可达性分析算法：
 
原理：首先从GC Roots的对象作为起点开始，然后向下搜索，搜索走过的路径称为引用链，如果一个对象没有任何引用链相连，则判断为对象不可用，作为可回收对象，通过finalize()自救。
 
优缺点：解决相互循环引用问题。
 
 
 
GC Roots的对象包括：
 
虚拟机栈中本地变量表引用的对象
 
方法区中类静态属性引用，常量引用的对象
 
本地方法栈中JNI引用的对象
 
 
 
参考资料：《深入理解Java虚拟机》——周志明

垃圾收集（Garbage Collection，下文简称GC）是Java有别于其他编程语言的一大特点，GC主要考虑的有三个问题：
 
哪些内存需要回收？
什么时候回收？
如何回收？
 

 今天咱们主要聊聊JVM是如何判断对象可以被回收的。
 
常用的算法有两种：
 
引用计数算法
可达性分析算法
 
引用计数算法
 
在对象中添加一个引用计数器，每当新加一个引用时，计数器就加1，当引用失效时，计数器就减1。任何时刻只要计数器为0就代表对象没有引用可以被回收。
 
这种算法实现简单，判断高效，但是有一些缺点：
 
 主流的商用JVM实现都没有采用这种方式。
 
 
可达性分析算法
 
目前主流的商用JVM都是通过可达性分析来判断对象是否可以被回收的。
 
 
这个算法的基本思路是：
 
 
 
通过一系列被称为「GC Roots」的根对象作为起始节点集，从这些节点开始，通过引用关系向下搜寻，搜寻走过的路径称为「引用链」，如果某个对象到GC Roots没有任何引用链相连，就说明该对象不可达，即可以被回收。
 
 
初看这段话是不是一脸懵呢？笔者当初也是的，完全不知道什么意思，后面才慢慢理解。
 
要想理解可达性算法，首先要想明白几个问题：
 
 
1、什么是对象可达？
 
对象可达指的就是：双方存在直接或间接的引用关系。
 根可达或GC Roots可达就是指：对象到GC Roots存在直接或间接的引用关系。
 如下代码：
 
public class MyObject {
	private String objectName;//对象名
	private MyObject refrence;//依赖对象

	public MyObject(String objectName) {
		this.objectName = objectName;
	}

	public MyObject(String objectName, MyObject refrence) {
		this.objectName = objectName;
		this.refrence = refrence;
	}

	public static void main(String[] args) {
		MyObject a = new MyObject("a");
		MyObject b = new MyObject("b");
		MyObject c = new MyObject("c");
		a.refrence = b;
		b.refrence = c;

		new MyObject("d", new MyObject("e"));
	}
}
 
创建了5个对象，他们之间的引用关系如图：
 
 假设a是GC Roots的话，那么b、c就是可达的，d、e是不可达的。
 
2、GC Roots是什么？
 
垃圾回收时，JVM首先要找到所有的GC Roots，这个过程称作 「枚举根节点」 ，这个过程是需要暂停用户线程的，即触发STW。
 然后再从GC Roots这些根节点向下搜寻，可达的对象就保留，不可达的对象就回收。
 那么，到底什么是GC Roots呢？
 
GC Roots就是对象，而且是JVM确定当前绝对不能被回收的对象(如方法区中类静态属性引用的对象 )。
 只有找到这种对象，后面的搜寻过程才有意义，不能被回收的对象所依赖的其他对象肯定也不能回收嘛。
 
当JVM触发GC时，首先会让所有的用户线程到达安全点SafePoint时阻塞，也就是STW，然后枚举根节点，即找到所有的GC Roots，然后就可以从这些GC Roots向下搜寻，可达的对象就保留，不可达的对象就回收。
 
 
 
即使是号称几乎不停顿的CMS、G1等收集器，在枚举根节点时，也是要暂停用户线程的。
 
 
GC Roots是一种特殊的对象，是Java程序在运行过程中所必须的对象，而且是根对象。
 那么，哪些对象可以成为GC Roots呢？
 
3、哪些对象可以作为GC Roots？
 
可以作为GC Roots的对象可以分为两大类：全局对象和执行上下文。
 
 下面就一起来理解一下为什么这几类对象可以被作为GC Roots。
 1、方法区静态属性引用的对象
 全局对象的一种，Class对象本身很难被回收，回收的条件非常苛刻，只要Class对象不被回收，静态成员就不能被回收。
 
2、方法区常量池引用的对象
 也属于全局对象，例如字符串常量池，常量本身初始化后不会再改变，因此作为GC Roots也是合理的。
 
3、方法栈中栈帧本地变量表引用的对象
 属于执行上下文中的对象，线程在执行方法时，会将方法打包成一个栈帧入栈执行，方法里用到的局部变量会存放到栈帧的本地变量表中。只要方法还在运行，还没出栈，就意味这本地变量表的对象还会被访问，GC就不应该回收，所以这一类对象也可作为GC Roots。
 
4、JNI本地方法栈中引用的对象
 和上一条本质相同，无非是一个是Java方法栈中的变量引用，一个是native方法(C、C++)方法栈中的变量引用。
 
5、被同步锁持有的对象
 被synchronized锁住的对象也是绝对不能回收的，当前有线程持有对象锁呢，GC如果回收了对象，锁不就失效了嘛。
 
尾巴
 
总结，可达性分析就是JVM首先枚举根节点，找到一些为了保证程序能正常运行所必须要存活的对象，然后以这些对象为根，根据引用关系开始向下搜寻，存在直接或间接引用链的对象就存活，不存在引用链的对象就回收。

在堆里存放着几乎多有的java对象实例，垃圾搜集器在对堆进行回收之前，第一件事情就是确定这些对象之中哪些还“存活”着（即通过任何途径都无法使用的对象）。
 
一、可达性分析算法
 
在Java中，是通过可达性分析（Reachability Analysis）来判定对象是否存活的。该算法的基本思路就是通过一些被称为引用链（GC Roots）的对象作为起点，从这些节点开始向下搜索，搜索走过的路径被称为（Reference Chain)，当一个对象到GC Roots没有任何引用链相连时（即从GC Roots节点到该节点不可达），则证明该对象是不可用的。
 
 
可达性分析算法判断对象是否可以回收
 

 如上图所示，object1~object4对GC Root都是可达的，说明不可被回收，object5和object6对GC Root节点不可达，说明其可以被回收。
在Java中，可作为GC Root的对象包括以下几种：
 
虚拟机栈（栈帧中的本地变量表）中引用的对象
方法区中类静态属性引用的对象
方法区中常量引用的对象
本地方法栈中JNI（即一般说的Native方法）引用的对象
二、finalize()方法最终判定对象是否存活
 
即使在可达性分析算法中不可达的对象，也并非是“非死不可”的，这时候它们暂时处于“缓刑”阶段，要真正宣告一个对象死亡，至少要经历再次标记过程。
标记的前提是对象在进行可达性分析后发现没有与GC Roots相连接的引用链。
1. 第一次标记并进行一次筛选。
 筛选的条件是此对象是否有必要执行finalize()方法。
 当对象没有覆盖finalize方法，或者finzlize方法已经被虚拟机调用过，虚拟机将这两种情况都视为“没有必要执行”，对象被回收。
2. 第二次标记
 如果这个对象被判定为有必要执行finalize（）方法，那么这个对象将会被放置在一个名为：F-Queue的队列之中，并在稍后由一条虚拟机自动建立的、低优先级的Finalizer线程去执行。这里所谓的“执行”是指虚拟机会触发这个方法，但并不承诺会等待它运行结束。这样做的原因是，如果一个对象finalize（）方法中执行缓慢，或者发生死循环（更极端的情况），将很可能会导致F-Queue队列中的其他对象永久处于等待状态，甚至导致整个内存回收系统崩溃。
 Finalize（）方法是对象脱逃死亡命运的最后一次机会，稍后GC将对F-Queue中的对象进行第二次小规模标记，如果对象要在finalize（）中成功拯救自己----只要重新与引用链上的任何的一个对象建立关联即可，譬如把自己赋值给某个类变量或对象的成员变量，那在第二次标记时它将移除出“即将回收”的集合。如果对象这时候还没逃脱，那基本上它就真的被回收了。
 
三、Java引用
 
从可达性算法中可以看出，判断对象是否可达时，与“引用”有关。那么什么情况下可以说一个对象被引用，引用到底代表什么？
 在JDK1.2之后，Java对引用的概念进行了扩充，可以将引用分为以下四类：
 
强引用（Strong Reference)
软引用（Soft Reference)
弱引用（Weak Reference)
虚引用（Phantom Reference)
这四种引用从上到下，依次减弱
 
3.1 强引用
 
强引用就是指在程序代码中普遍存在的，类似Object obj = new Object()这类似的引用，只要强引用在，垃圾搜集器永远不会搜集被引用的对象。也就是说，宁愿出现内存溢出，也不会回收这些对象。
 
3.2 软引用
 
软引用是用来描述一些有用但并不是必需的对象，在Java中用java.lang.ref.SoftReference类来表示。对于软引用关联着的对象，只有在内存不足的时候JVM才会回收该对象。因此，这一点可以很好地用来解决OOM的问题，并且这个特性很适合用来实现缓存：比如网页缓存、图片缓存等。
 
import java.lang.ref.SoftReference;
 
public class Main {
    public static void main(String[] args) {
         
        SoftReference<String> sr = new SoftReference<String>(new String("hello"));
        System.out.println(sr.get());
    }
}
 
3.3 弱引用
 
弱引用也是用来描述非必需对象的，当JVM进行垃圾回收时，无论内存是否充足，都会回收被弱引用关联的对象。在java中，用java.lang.ref.WeakReference类来表示。下面是使用示例：
 
import java.lang.ref.WeakReference;
 
public class Main {
    public static void main(String[] args) {
     
        WeakReference<String> sr = new WeakReference<String>(new String("hello"));
         
        System.out.println(sr.get());
        System.gc();                //通知JVM的gc进行垃圾回收
        System.out.println(sr.get());
    }
}
 
3.4 虚引用
 
虚引用和前面的软引用、弱引用不同，它并不影响对象的生命周期。在java中用java.lang.ref.PhantomReference类表示。如果一个对象与虚引用关联，则跟没有引用与之关联一样，在任何时候都可能被垃圾回收器回收。
 要注意的是，虚引用必须和引用队列关联使用，当垃圾回收器准备回收一个对象时，如果发现它还有虚引用，就会把这个虚引用加入到与之 关联的引用队列中。程序可以通过判断引用队列中是否已经加入了虚引用，来了解被引用的对象是否将要被垃圾回收。如果程序发现某个虚引用已经被加入到引用队列，那么就可以在所引用的对象的内存被回收之前采取必要的行动。
 
import java.lang.ref.PhantomReference;
import java.lang.ref.ReferenceQueue;
 
public class Main {
    public static void main(String[] args) {
        ReferenceQueue<String> queue = new ReferenceQueue<String>();
        PhantomReference<String> pr = new PhantomReference<String>(new String("hello"), queue);
        System.out.println(pr.get());
    }
}
 
3.5 软引用和弱引用进一步说明
 
在SoftReference类中，有三个方法，两个构造方法和一个get方法（WekReference类似）：
 
public class SoftReference<T> extends Reference<T> {

    /**
     * Timestamp clock, updated by the garbage collector
     */
    static private long clock;

    /**
     * Timestamp updated by each invocation of the get method.  The VM may use
     * this field when selecting soft references to be cleared, but it is not
     * required to do so.
     */
    private long timestamp;

    /**
     * Creates a new soft reference that refers to the given object.  The new
     * reference is not registered with any queue.
     *
     * @param referent object the new soft reference will refer to
     */
    public SoftReference(T referent) {
        super(referent);
        this.timestamp = clock;
    }

    /**
     * Creates a new soft reference that refers to the given object and is
     * registered with the given queue.
     *
     * @param referent object the new soft reference will refer to
     * @param q the queue with which the reference is to be registered,
     *          or <tt>null</tt> if registration is not required
     *
     */
    public SoftReference(T referent, ReferenceQueue<? super T> q) {
        super(referent, q);
        this.timestamp = clock;
    }

    /**
     * Returns this reference object's referent.  If this reference object has
     * been cleared, either by the program or by the garbage collector, then
     * this method returns <code>null</code>.
     *
     * @return   The object to which this reference refers, or
     *           <code>null</code> if this reference object has been cleared
     */
    public T get() {
        T o = super.get();
        if (o != null && this.timestamp != clock)
            this.timestamp = clock;
        return o;
    }

}
 
get方法用来获取与软引用关联的对象的引用，如果该对象被回收了，则返回null。
 
在使用软引用和弱引用的时候，我们可以显示地通过System.gc()来通知JVM进行垃圾回收，但是要注意的是，虽然发出了通知，JVM不一定会立刻执行，也就是说这句是无法确保此时JVM一定会进行垃圾回收的。
 
3.6 虚引用进一步说明：
 
虚引用中有一个构造函数，可以看出，其必须和一个引用队列一起存在。get()方法永远返回null，因为虚引用永远不可达。
 
public class PhantomReference<T> extends Reference<T> {

    /**
     * Returns this reference object's referent.  Because the referent of a
     * phantom reference is always inaccessible, this method always returns
     * <code>null</code>.
     *
     * @return  <code>null</code>
     */
    public T get() {
        return null;
    }

    /**
     * Creates a new phantom reference that refers to the given object and
     * is registered with the given queue.
     *
     * <p> It is possible to create a phantom reference with a <tt>null</tt>
     * queue, but such a reference is completely useless: Its <tt>get</tt>
     * method will always return null and, since it does not have a queue, it
     * will never be enqueued.
     *
     * @param referent the object the new phantom reference will refer to
     * @param q the queue with which the reference is to be registered,
     *          or <tt>null</tt> if registration is not required
     */
    public PhantomReference(T referent, ReferenceQueue<? super T> q) {
        super(referent, q);
    }
}
 
 
 
参考
 
 
《深入理解Java虚拟机》

可达性分析（或根搜索算法、追踪性垃圾收集）
 
可达性分析概述
 
相对于引用计数算法而言，可达性分析算法不仅同样具备实现简单和执行高效率的特点，更重要的是**该算法可以有效地解决在引用计数算法中循环引用的问题，防止内存泄漏的发生。**相较于引用计数算法，这里的可达性分析就是Java、C#选择的，这种类型的垃圾收集通常也叫做追踪性垃圾回收。
 
基本思路
 
1.可达性分析算法是以跟对象集合（GC Roots）为起始点，按照从上到下的方式搜索根对象集合所连接的目标对象是否可达。
 2.使用可达性分析算法后，内存中的存活对象都会被根对象集合直接或间接连接着，搜搜所走过的路径称为引用链。
 3.如果目标对象没有任何引用链相连，则是不可达的，就意味着该对象已经死亡，可以标记为垃圾对象。
 4.在可达性分析算法中，只有能够被对象集合直接或间接连接的对象才是存活对象
 
 
GC Roots
 
在Java语言中，GC Roots包括以下几类元素：
 1.虚拟机栈中引用的对象。比如各个线程调用的方法中使用到的参数、局部变量等。
 2.本地方法栈内JNI引用的对象。
 3.方法区中类静态属性引用的对象。比如Java类的引用类型静态变量。
 4.方法区中常量引用的对象。比如字符串常量池里的引用。
 5.所有被同步锁synchronized持有的对象
 等等
 
 小技巧：由于GC Roots采用栈方式存放变量和指针，所以如果一个指针，它保存了堆内存里面的对象，但是自己又不能存放在堆内存里面，那么它就是一个GC Roots。
 
注意：如果要使用可达性分析算法来判断内存中是否可回收，那么分析工作必须在一个能够保障一致性的快照中进行，这点不能满足的话分析结果的准确性就无法保证。这点也是导致GC进行时必须"Stop The World"的一个重要原因，即使是号称（几乎）不会发生停顿的CMS收集器中，枚举根节点时也是必须要停顿的。