学习垃圾回收算法

学习垃圾回收算法 什么是垃圾

什么是垃圾呢，简单定义就是：无任何引用指向该对象，那么该对象就是垃圾。（这个定义有些狭隘了，但是我也组织不了更好的语言，因为这个排除不了相互引用的问题）再简单来说就是没有任务使用途径的对象就是垃圾。

上图，new了一个Student，该Student对象在堆上进行分配，栈空间的栈桢里的一个引用student指向了堆上的Student对象，那堆上的Student就是存活的，不是垃圾。

继续看图：

这时不知道什么原因，栈桢上的student并没有指向堆里的Student了（比如：Student student = null），并且也没有其他的引用指向堆上的Student，那么时可以认为堆上的Student就是垃圾，因为没有任何的引用指向它，没有了任何的使用途径。

知道了什么是垃圾，那么怎么去找、去识别这些垃圾呢？

检测垃圾的算法

寻找检测垃圾的有两种算法：引用计数法和根可达算法。

引用计数算法

在对象中添加一个引用计数器，每当有个一地方引用它时，计数器值就加一，当引用失效时，计数器就减一；任何时刻，计数器为零的对象就是不可在被使用的。也就是垃圾。

如上图：obj1、2、3同时有引用指向了Obj4，这时Obj4引用计数的值为3；也就是obj1、2、3都用到了Obj4，这时的Obj4是一个有用有价值的对象。

这时，Obj1、2、3都取消了对Obj4的执行，并且也没有别的引用再指向了Obj4。Obj4的引用计数的值为0，这时的Obj4就是一个垃圾。

引用计数算法看起来是很简单，也很明了，记录引用的数量，有用的对象一定被引用的。但是也有特殊情况，那就是循环引用的问题是引用计数法难以解决的。如下图：

Obj1、2、3进行了相互引用，它们的引用计数都不是零。但是也没有别的引用指向它们中的任何一个，实际上这个三个对象都是垃圾，简称一堆垃圾。

根可达算法

通过一系列称为“GC Roots”的根对象为起始节点，从这些节点开始，根据引用关系向下搜索，搜索的过程所有的路径称为“引用链”，如果某个对象到GC Roots间没有任何引用链，或者说就是从GC Roots到这个对象不可达时，则证明此对象是不可能再被使用的，也就是垃圾。

如上图：

由一个GC Root出发，找到了Obj1、2、3、4这几个对象，形成一条引用链。Obj8、9两个对象，没有任何GC Roots的引用链中的引用指向它们，所有这个两个对象都是垃圾。Obj8、6、7这三个对象虽然相互引用，但是也是没有任何的GC Roots的引用链中的引用指向它们中的任何一个，所以这三个对象都是垃圾。

固定可作为GC Roots的对象包括以下几种:

在虚拟机栈中引用的对象，比如各个线程被调用的方法堆栈中使用到是参数、局部变量、临时变量等。

在方法区中类静态属性引用的对象，譬如Java类的引用类型静态变量。

在方法区中常量引用的对象，譬如字符串常量池（String Table）里的引用。

在本地方法栈中JNI（即通常所说的Native方法）引用的对象。

Java虚拟机内部的引用，如基本数据类型对应的Class对象，一些常驻的异常对象（比如NullPointExcepiton、OutOfMemoryError）等，还有系统类加载器。

所有被同步锁（synchronized关键字）持有的对象。

垃圾回收算法

在进行垃圾回收算法的学习之前，先了解一下“分代收集理论”，因为“标记清除”、“标记拷贝”、“标记压缩”算法，都是建立在分代收集理论的假说上发展而来的。

分代收集理论

分代收集理论：

弱分代假说：绝大多数对象都是朝生夕灭的。

强分代假说：熬过多次垃圾收集过程的对象就越难以消亡。

这两个假说共同奠定了多款常用垃圾收集器的一致设计原则：

收集器应该将Java堆划分出不同的区域，然后将回收对象依据其年龄（年龄即对象熬过垃圾收集过程的次数）分配到不同的区域之中存储。

如果一个区域中大多数对象都是朝生夕灭，难以熬过垃圾收集过程的话，那么把它们集中放在一起，每次回收时只关注如何保留少量存活而不是去标记那些大量将要被回收的对象，就能以较低代价回收到大量的空间；如果剩下的都是难以消亡的对象，那把它们集中放在一块，虚拟机便可以使用较低的频率来回收这个区域，这就同时兼顾了垃圾收集的时间开销和内存的空间有效利用。

更具分代收集理论，一般是将jvm的堆内存划分为新生代（Young Generation）和老年代（Old Generation）,新生代中存放朝生夕灭的对象，老年代中存放“越难以消亡”的对象（这里先简单粗暴的这样划分，后面会做详细介绍）。这样不同的区域特点，针对性的采用不同的垃圾回收算法。

内存区域划分也没有那么容易，因为对象实际调用往往是错综复杂的，每个对象并不是孤立的存在，也就是说可能会存在跨代引用的问题，即年轻代的对象很有可能去调用老年代的某个对象。

存在这种跨代引用，假如：此时对年轻代进行垃圾回收，发现某个对象进行跨代引用，那这时是不是得对整个老年代进行重新扫描检测，也就是说还是需要对整个的堆内存（堆=年轻代+老年代）进行垃圾检测，那么之前的两条分代假说就有些失去了意义。

所以又添加的第三条分代假说理论：

跨代引用假说：跨代引用相对于同代引用来说仅占极少数。

根据第三条分代假说理论，跨代引用只是占用了很少数，所以不必为了少量的跨代引用而去扫描整个老年代，也不必浪费空间专门记录每一个对象是否存在及存在哪些跨代引用，只需在新生代上建立一个全局的数据结构（该结构被称为“记忆集”，Remembered Set），这个结构把老年代划分成若干小块，标识出老年代的哪一块内存会存在跨代引用。此后当发生Minor GC时，只有包含了跨代引用的小块内存里的对象才会被加入到GCRoots进行扫描。虽然这种方法需要在对象改变引用关系（如将自己或者某个属性赋值）时维护记录数据的正确性，会增加一些运行时的开销，但比起收集时扫描整个老年代来说仍然是划算的。

标记清除

标记清除是最早出现也是最基础的垃圾收集算法。算法分为“标记”和“清除”两个阶段，首先标记出垃圾的位置，标记完成后，统一回收掉所有标记的对象。

如上图，标记出垃圾的位置，然后清除。

主要有两个缺点：

执行效率不稳定：如果java堆里有大量的对象需要被标记回收，那么就需要进行大量的标记和清除动作，导致标记和清除两个过程的执行效率会随着对象数量的增长而降低。

内存空间的碎片化：标记清除后可能会产生许多不连续的空间，可能会导致在分配大对象时，由于找不到足够连续的空间进行分配，从而不得不触发一次垃圾回收的动作。

标记复制

为了解决标记清除算法在面对大量可回收对象时执行效率低的问题，是一种“半区复制”的垃圾收集算法。

将可用内存按照容量划分为大小相同的两块，每次只使用一块，当使用的那一块内存区域块用完的时候，就将还存活的对象复制到另一块未使用的区域里去，然后再把已使用过的内存空间一次性清理掉。

特点：

如果大量对象都是存活的，那么就会产生大量的内存间复制的开销

如果少量对象存活，就只需要复制少数的存活对象，并且每次都是针对整个半区进行内存回收，所以没有碎片化空间这样的复杂问题。

缺点也很明显：空间浪费太多，可用空间只能为原来的一半。

标记整理

前面两种算法在面对大量对象存活时（比如老年代），执行效率都比较低，而且“标记复制算法”还会浪费一般的空间。

所以针对老年代对象的存活特征（对象存活时间长），提出了针对性的“标记整理算法”。

其中的标记过程仍然与“标记-清除”算法一样，但后续步骤不是直接对可回收对象进行清理，而是让所有存活的对象都向内存空间一端移动，然后直接清理掉边界以外的内存

标记-清除算法与标记-整理算法的本质差异在于前者是一种非移动式的回收算法，而后者是移动式的。

特点：

不会出现碎片化空间

执行效率低，因为移动存活对象并更新所有引用这些对象的地方将会是一种极为负重的 *** 作，而且这种对象移动 *** 作必须全程暂停用户应用程序才能进行。也就是会出现“Stop The Word”。

各个JVM运行时数据区域的垃圾回收 线程共享区域的垃圾回收

像程序计数器、虚拟机栈、本地方法栈这三个是线程特有的区域，当一个线程结束时，内存自然就回收了。

方法区的垃圾回收

《Java虚拟机规范》中提到过可以不要求虚拟机在方法区中实现垃圾收集，事实上也确实有未实现或未能完整实现方法区类型卸载的收集器存在，方法区垃圾收集的“性价比”通常也是比较低的：在Java堆中，尤其是在新生代中，对常规应用进行一次垃圾收集通常可以回收70%至99%的内存空间，相比之下，方法区回收囿于苛刻的判定条件，其区域垃圾收集的回收成果往往远低于此。

方法区的垃圾收集主要回收两部分内容：废弃的常量和不再使用的类型。回收废弃常量与回收Java堆中的对象非常类似。举个常量池中字面量回收的例子，假如一个字符串“java”曾经进入常量池中，但是当前系统又没有任何一个字符串对象的值是“java”，换句话说，已经没有任何字符串对象引用常量池中的“java”常量，且虚拟机中也没有其他地方引用这个字面量。如果在这时发生内存回收，而且垃圾收集器判断确有必要的话，这个“java”常量就将会被系统清理出常量池。常量池中其他类（接口）、方法、字段的符号引用也与此类似。

判定一个常量是否“废弃”还是相对简单，而要判定一个类型是否属于“不再被使用的类”的条件就比较苛刻了。需要同时满足下面三个条件：

该类所有的实例都已经被回收，也就是Java堆中不存在该类及其任何派生子类的实例。

加载该类的类加载器已经被回收，这个条件除非是经过精心设计的可替换类加载器的场景，如
OSGi、JSP的重加载等，否则通常是很难达成的。

该类对应的java.lang.Class对象没有在任何地方被引用，无法在任何地方通过反射访问该类的方
法。

Java虚拟机被允许对满足上述三个条件的无用类进行回收，这里说的仅仅是“被允许”，而并不是
和对象一样，没有引用了就必然会回收。

jvm堆内存的垃圾回收机制（分代收集）

按照分代理论的设计原则，将java堆划分为不同的区域，然后将回收对象按照年龄分配到不同的区域之中存储。

下图为堆的内存划分：

默认情况下：  
  新生代：老年代 = 1：2  
  伊甸区（eden）：幸存区1：幸存区2 = 8：1：1

新生代采用垃圾收集算法为：标记复制算法；    
老年代采用垃圾收集算法为：标记整理算法；

新生代中的对象有98%熬不过第一轮垃圾收集，所以不需要将新生代的区域按照1：1比例来划分，而是按照8：1：1设计出两个幸存者区域（Survivor）。

当发生垃圾收集时：将Eden和Survivor中仍然存活的对象一次性复制到另外一块Survivor空间上，然后直接清理掉Eden和已用过的那块Survivor空间。

虚拟机给每个对象定义了一个对象年龄（Age）计数器，存储在对象头中。对象通常在Eden区里诞生，如果经过第一次垃圾收集后仍然存活，并且能被Survivor容纳的话，该对象会被移动到Survivor空间中，并且将其对象
年龄设为1岁。对象在Survivor区中每熬过一次Minor GC，年龄就增加1岁，当它的年龄增加到一定程度（默认15），就会被晋升到老年代中。

演示：

假设系统刚使用，所有的新对象都分配在了伊甸区。

在进行第一轮垃圾收集时发现只有Obj1、2存活，于是将伊甸区（Eden）存活的Obj1、2复制到Survivor1中，Obj1、2各自年龄加一，然后对伊甸区（Eden）进行垃圾清除（标记复制算法）。

应用继续运行使用，不断有新对象在伊甸区（Eden）分配创建…

进行第二轮垃圾回收时发现伊甸区（Eden）只有Obj4对象存活，而Survivor1区中也只有Obj1存活，这时将Obj4和Obj1复制到Survivor2（因为Survivor1是空的），Obj1、4各自年龄加一，然后清空伊甸区（Eden）和Survivor1两个区域。

如此不断反复…

进行第n轮的时候，发现Obj1还存活并且它的年龄已经满足移到老年代去了（默认为15岁），于是将Obj1移到了老年代。