垃圾收集理论-垃圾收集算法

这里主要讲解垃圾收集理论上的算法，下一篇会介绍一些实现了这些算法的垃圾收集器。

一般我们谈垃圾收集从三个问题来帮你理解jvm的垃圾收集策略：

1.怎么判断哪些内存是垃圾？
2.用什么方法回收？
3.什么时候回收？

#垃圾回收的区域？

前面介绍了java内存运行时区域的各个部分，其中程序计数器、虚拟机栈、本地方法栈3个区域随线程而生，随线程而灭，栈中的栈帧随着方法的进入和退出而有条不紊的执行着出栈和入栈操作。每一个栈帧中分配多少内存基本上都在类结构确定下来时就已知的，因此这几个区域的内存分配和回收都具备确定性，在这几个区域内都不需要过多考虑回收的问题，因为方法结束或者线程结束时，内存自然就跟随着回收了。而java堆和方法区则不一样，一个接口中的多个实现类需要的内存可能不一样，一个方法中的多个分支需要的内存也可能不一样，我们只能在程序处于运行期间时才能知道会创建哪些对象，这部分内存的分配和回收是动态的，垃圾收集器所关注的是这部分内存。

#一.怎么判断哪些内存是垃圾？

##1.引用计数法

给对象中添加一个引用计数器，每当有一个地方引用它时，计数器值就加1，当引用失效时，计数器就减1，任何时刻计数器为0的对象就是不可能再被使用的。

但是java虚拟机并没有选用引用计数算法来管理内存，其中最重要的原因是它很难解决对象之间相互引用的问题。

public class MyObject {
    public Object ref = null;
    public static void main(String[] args) {
        MyObject myObject1 = new MyObject();
        MyObject myObject2 = new MyObject();
        myObject1.ref = myObject2;
        myObject2.ref = myObject1;
        myObject1 = null;
        myObject2 = null;
    }
}

##2.可达性分析算法

在java中采用的是可达性分析算法来判定对象是否存活的。这个算法的基本思路就是：通过一系列的称为”GC Roots"的对象作为起始点，从这些节点开始向下搜索，搜索所走过的路径称为引用链（Reference Chain），当一个对象到GC Roots没有任何引用链相连（用图论的话来说，就是从GC Roots到这个对象不可达）时，则证明此对象是不可用的。

在java语言中，可作为GC Roots的对象包括下面几种：

• 虚拟机栈（栈帧的本地变量表）中引用的对象；
• 方法区中类静态属性引用的对象；
• 方法区中常量引用的对象；
• 本地方法栈中JNI（即一般说的native方法）引用的对象；

说明：

即使在可达性分析算法中不可达的对象，也并非是“非死不可”的，这时候他们暂时处于”缓刑“阶段，要真正宣告一个对象的死亡，至少要经历两次标记过程：如果对象在进行可达性分析后发现没有与GC Roots相连接的引用链，那它将会被第一次标记并且进行一次筛选，筛选的条件是此对象是否有必要执行finalize方法。当对象没有覆盖finalize方法，或者finalize方法已经被虚拟机调用过，虚拟机将这两种情况都视为”没有必要执行了“。

如果这个对象被判定为有必要执行finalize方法，那么这个对象将会放置在一个叫做F-Queue的队列之中，并在稍后由一个由虚拟机自动建立的、低优先级的Finalizer线程去执行它（即触发这个方法）。

稍后GC将对F-Queue中的对象进行第二次小规模的标记，如果对象要在finalize中成功救赎自己——只要重新与引用链上的任何一个对象建立关联即可，那么第二次标记它将会被移除出”即将回收的“的集合，如果这个时候对象还没有逃脱，那基本上他就真的被回收了。

finalize方法建议大家完全忘记掉，不要在平时的编码中去调用。

##3.回收方法区

方法区的垃圾回收主要回收两部分内容：废弃常量和无用的类。回收废弃常量与回收java堆中的对象类似，也采用可达性。

回收无用的类条件就苛刻多了，类需要同时满足下面的3个条件才能算是”无用的类“：

• 该类所有的实例都已经被回收，也就是java堆中不存在该类的任何实例。
• 加载该类的ClassLoader已经被回收。
• 该类对应的java.lang.Class对象没有在任何地方呗引用，无法在任何地方通过访问该类的方法。

#二.什么时候回收？

  一个应用程序中那个线程运行有线程自身的优先级来决定的。垃圾回收线程几乎是所有线程中优先级最低的。

#三.用什么方法回收？

##1.标记-清理算法

标记阶段：标记出所有需要回收的对象，在标记完成后统一回收所有被标记的对象，前面已经提过。

清理阶段：

该算法的不足：

1.效率问题。效率比较低。
2.空间问题，标记清理算法会产生大量的不连续的碎片。

##2.复制算法

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

它将可用内存按容量划分为大小相等的两块，每次只使用其中的一块。当这一块的内存用完了，就将存活的对象复制到另外一块上面，然后再把已使用过的内存空间一次清理掉。

  我们首先一起来看一下复制算法的做法，复制算法将内存划分为两个区间，在任意时间点，所有动态分配的对象都只能分配在其中一个区间（称为活动区间），而另外一个区间（称为空闲区间）则是空闲的。

  当有效内存空间耗尽时，JVM将暂停程序运行，开启复制算法GC线程。接下来GC线程会将活动区间内的存活对象，全部复制到空闲区间，且严格按照内存地址依次排列，与此同时，GC线程将更新存活对象的内存引用地址指向新的内存地址。

  此时，空闲区间已经与活动区间交换，而垃圾对象现在已经全部留在了原来的活动区间，也就是现在的空闲区间。事实上，在活动区间转换为空间区间的同时，垃圾对象已经被一次性全部回收。

  听起来复杂吗？

  其实一点也不复杂，有了上一章的基础，相信各位理解这个算法不会费太多力气。LZ给各位绘制一幅图来说明问题，如下所示。

  其实这个图依然是上一章的例子，只不过此时内存被复制算法分成了两部分，下面我们看下当复制算法的GC线程处理之后，两个区域会变成什么样子，如下所示。

  可以看到，1和4号对象被清除了，而2、3、5、6号对象则是规则的排列在刚才的空闲区间，也就是现在的活动区间之内。此时左半部分已经变成了空闲区间，不难想象，在下一次GC之后，左边将会再次变成活动区间。

  很明显，复制算法弥补了标记/清除算法中，内存布局混乱的缺点。不过与此同时，它的缺点也是相当明显的。

  1、它浪费了一半的内存，这太要命了。
  2、如果对象的存活率很高，我们可以极端一点，假设是100%存活，那么我们需要将所有对象都复制一遍，并将所有引用地址重置一遍。复制这一工作所花费的时间，在对象存活率达到一定程度时，将会变的不可忽视。

  所以从以上描述不难看出，复制算法要想使用，最起码对象的存活率要非常低才行，而且最重要的是，我们必须要克服50%内存的浪费。

##3.标记-整理算法

  标记/整理算法与标记/清除算法非常相似，它也是分为两个阶段：标记和整理。

  标记：它的第一个阶段与标记/清除算法是一模一样的，均是遍历GC Roots，然后将存活的对象标记。

  整理：移动所有存活的对象，且按照内存地址次序依次排列，然后将末端内存地址以后的内存全部回收。因此，第二阶段才称为整理阶段。

  它GC前后的图示与复制算法的图非常相似，只不过没有了活动区间和空闲区间的区别，而过程又与标记/清除算法非常相似，我们来看GC前内存中对象的状态与布局，如下图所示。

  这张图其实与标记/清楚算法一模一样，只是LZ为了方便表示内存规则的连续排列，加了一个矩形表示内存区域。倘若此时GC线程开始工作，那么紧接着开始的就是标记阶段了。此阶段与标记/清除算法的标记阶段是一样一样的，我们看标记阶段过后对象的状态，如下图。

  没什么可解释的，接下来，便应该是整理阶段了。我们来看当整理阶段处理完以后，内存的布局是如何的，如下图。

  可以看到，标记的存活对象将会被整理，按照内存地址依次排列，而未被标记的内存会被清理掉。如此一来，当我们需要给新对象分配内存时，JVM只需要持有一个内存的起始地址即可，这比维护一个空闲列表显然少了许多开销。
  不难看出，标记/整理算法不仅可以弥补标记/清除算法当中，内存区域分散的缺点，也消除了复制算法当中，内存减半的高额代价，可谓是一举两得，一箭双雕，一石两鸟。
  不过任何算法都会有其缺点，标记/整理算法唯一的缺点就是效率也不高，不仅要标记所有存活对象，还要整理所有存活对象的引用地址。从效率上来说，标记/整理算法要低于复制算法。

##4.分代收集算法

  当前的商业虚拟机的垃圾收集都采用“分代收集”算法。这种算法并没有什么新的意思，只是根据对象的存活周期的不同将内存划分为几块。一般是把java堆分为新生代和老生代，这样就可以根据各个年代的特点采用最适合的收集算法。在新生代中，每次垃圾回收时都发现有大批对象死去，只有少量存活，那就选用复制算法，只需要付出少量存活对象的复制成本就可以完成收集。而老生代中因为对象存活率高、没有额外空间对它进行分配担保，就必须使用“标记-清理”或“标记-整理”算法来进行回收。

##5.算法对比

它们的共同点主要有以下两点。

• 1、三个算法都基于根搜索算法去判断一个对象是否应该被回收，而支撑根搜索算法可以正常工作的理论依据，就是语法中变量作用域的相关内容。因此，要想防止内存泄露，最根本的办法就是掌握好变量作用域，而不应该使用前面内存管理杂谈一章中所提到的C/C++式内存管理方式。
• 2、在GC线程开启时，它们都要暂停应用程序（stop the world）。
    它们的区别LZ按照下面几点来给各位展示。（>表示前者要优于后者，=表示两者效果一样）

效率：复制算法>标记/整理算法>标记/清除算法。
内存整齐度：复制算法=标记/整理算法>标记/清除算法。
内存利用率：标记/整理算法=标记/清除算法>复制算法。

可以看到标记/清除算法是比较落后的算法了，但是后两种算法却是在此基础上建立的，俗话说“吃水不忘挖井人”，因此各位也莫要忘记了标记/清除这一算法前辈。

难道就没有一种最优算法吗？

当然是没有的，这个世界是公平的，任何东西都有两面性，试想一下，你怎么可能找到一个又漂亮又勤快又有钱又通情达理，性格又合适，家境也合适，身高长相等等等等都合适的女人？就算你找到了，至少有一点这个女人也肯定不满足，那就是多半不会恰巧又爱上了与LZ相似的各位苦逼猿友们。你是不是想说你比LZ强太多了，那LZ只想对你说，高富帅是不会爬在电脑前看技术文章的，0.0。

没有最好的算法，只有最合适的算法。

既然这三种算法都各有缺陷，高人们自然不会容许这种情况发生。因此，高人们提出可以根据对象的不同特性，使用不同的算法处理，类似于萝卜白菜各有所爱的原理。于是奇迹发生了，高人们终于找到了GC算法中的神级算法-----分代搜集算法。