垃圾回收算法和内存分配策略

Java垃圾回收

垃圾收集，也就是GC并不是Java的伴生物，而对于GC的所需要完成任务主要就是:

1.哪些内存是需要回收的？

2.何时去回收这些内存？

3.以何种方式去回收这些内存？

前面已经提到过：

程序计数器，虚拟机栈，本地方法栈3个内存区域跟随线程的生命周期，这三个区域的内存分配和回收都是确定的，JVM不需要过多的担心这些区域的内存回收和分配。

但是在堆和方法区中却不一样，只有在程序运行的时候才能知道哪些对象会被创建，而对于方法区的内存回收，Java虚拟机并不做强制性要求，这个区域的回收目标主要是针对常量池的回收和对类型的卸载。

哪些内存是需要回收的？

一句话来描述就是对象“已死”就需要回收它“生前“所占用的内存。

Java中对对象所占用内存的回收根据对象是否还存活来判断，已经死亡的对象就是说不能够再被任何途径使用到的对象，或者说不能够再被任何途径引用到的对象。而Java中的引用共分了四个等级，从强至弱依次是强引用，软引用，弱引用，虚引用

Java中的引用关系

Java中一共有四种引用关系，其引用力度强弱依次是：

强引用>软引用>弱引用>虚引用

强引用

强引用是指创建一个对象并把这个对象赋值给一个引用变量，比如new关键字创建对象然后赋值给对应的变量。

对于强引用的，Java的原则是宁愿抛出内存溢出异常，也不会回收这部分的内存，使用强引用得到的对象成为强可及对象，强引用可以显式的借助null赋值解除。

比如说fun1,如果因为内存不够导致objArr无法创建成功。宁可抛出内存溢出异常，也不会去回收objectA的内存，但是当fun1执行完成之后，objectA和objArray都已经不存在了，所以它们指向的对象都会被JVM回收。

软引用

软引用，是描述一些有用但并非必须的对象，在将要发成内存溢出的时候，会回收这部分内存，之后如果不够才抛出内存溢出异常。

软引用可以通过构造SoftReference类的实例对象来使用，通过这个类提供的get方法返回的是软引用所指向的对象的强引用。

---

Object ob = new Object();
SoftReference softrefer = new SoftReference(ob);

即对于示例代码中的Object对象来说，一共有两个引用路径，一个是来自ob的强引用，另一个是来自softrefer的弱引用。

---

在清除了强引用关系之后，虚拟机不会因为软引用关系的存在就永远不去回收Object对象所占用的内存，虚拟机对于软引用对象的回收会优先处理那些长时间没用的软可及对象（最高引用关系为软引用关系的对象），在软可及对象被回收之后，通过SoftReference的get方法得到的就是null了。

SoftReference对象除了保存软引用，也具有一般对象的特性，所以当软可及对象被回收之后，SoftReference对象也应当被回收，对于SoftReference对象的回收，可以通过ReferenceQueue对象来完成，它是一个队列，保存了一系列引用对象，且是在失去了被引用对象之后的引用对象，通过其出列方法可以判断以及回收已经在队列中的失效Reference对象。

将Reference和ReferenceQueue关联可以使用带queue参数的构造函数

//将对象与引用队列对象关联起来，软，弱，虚引用均提供了这种方法
SoftReference softrefer1 = new SoftReference(ob,queue);

弱引用

比软引用更弱一些，同样描述非必须的对象，其引用对象只能存活在下一次垃圾收集发生之前。当GC工作时，都会回收只被弱引用关联的对象。

弱引用当垃圾收集器工作时，无论当前内存是否足够，都会回收掉只被弱引用关联的对象，使用WeakReference类来实现弱引用关系。同样使用get方法来获取对象的强引用，当强引用存在的时候，即便有弱引用关系存在GC也无法回收该对象。WeakReference对象也可以借助ReferenceQueue对象进行引用失效后的回收。

虚引用

最弱的一种引用关系，等同于没有引用，其存在不会对对象的生命周期有任何影响，其引用对象可能在任何时期被GC回收，无法通过虚引用得到实例对象的强引用。

虚引用的使用必须绑定引用队列（ReferenceQueue），在对象的finalize方法（该方法会在垃圾收集器准备释放内存的时候先调用）执行之后，垃圾收集器会将PhantomReference对象加入到ReferenceQueue队列中，就是说，此时实例对象仍然是在堆内存当中的，在回收其所占用内存的时候允许收到一个系统通知，收到通知之后可以实现一些目的操作。其意义在于允许你去准确的决定一个实例对象是否要从内存中移除（在JVM即将要释放内存区域的时候）。

比如说在操作一些体积很大的图片的时候，如果你确认该图片不需要再使用，借助虚引用的特性，你可以使得虚拟机对原大图片所占用的内存的清理工作在下一张图像开始加载到内存之前进行，从而避免不必要的OOM。

如何判断对象已经死亡？

对于如何判断Java对象已经死亡，主要有两种算法，引用计数算法和可达性分析算法。

引用计数算法

引用计数算法的思想很简单，虚拟机给每一个对象设置一个引用计数器，一个对象每多一个引用就给他的引用计数加一，少一个引用就减一，当引用计数为0的时候就表示这个对象已经不能被任何途径引用到，其内存区域可以被回收释放。

引用计数算法又分为侵入式和非侵入式：

侵入式是在对象内存内部设置引用计数器

非侵入式就是用一块单独的内存区域专门实现引用计数器。

用C++的语法思想来解释就是，构造函数或者对象拷贝函数可以对计数器加一，析构函数会对计数器减一。

引用计数算法可以使内存回收穿插在程序中进行，在程序运行中，当发现某一对象的引用计数器为0时，可以立即对该对象所占用的内存空间进行回收，这种方式可以避免FULL GC时带来的程序暂停。

引用计数算法的不足

引用计数算法是一种非常简单易行的对象存活判断算法；但缺点在于它无法很好的解决对象之间的相互循环引用。

如下代码：

public class ReferenceCounterGC {
	public Object instace = null;
	private byte[] memorySize = new byte[2*1024*1024];
	public void test() {
		ReferenceCounterGC objA = new ReferenceCounterGC();//假设这里是计数器A
		//A=1
		ReferenceCounterGC objB = new ReferenceCounterGC();//假设这里是计数器B
		//B=1
		objA.instace = objB;
		//B=1+1
		objB.instace = objA;
		//A=1+1
		objA = null;
		//A=1+1-1
		objB = null;
		//B=1+1-1
		System.gc();
		//请求GC操作
	}
}

最终计数器A和B的值均为1，就是说他们标记的实例对象不应该被GC回收。但是实际结果是：

不注释objA = null;objB = null;计数器最后均为0，要被回收。



注释掉objA = null;objB = null;



从GC日志来看，无论注释掉两行引用关系与否，最后GC之后的内存均进行了大幅回收，所以JVM（HotSpot VM）并没有采用引用计数算法来判断对象存活与否。

可达性分析算法

可达性分析算法的思想是以对象引用链到GC Roots是可达路径则为判断依据，有连通则对象存活，否则对象死亡。



图中一条条绿色的路劲就是引用链，GC Roots也是对象，可达性分析算法的基本思路就是引用链到GC Roots有可达路径则对象存活，否则对象死亡，从GC Roots对象出发一路向下搜索，o1,2,3是可达的，o4和o5虽然各自持有对对方的引用，但是到GC Roots没有可达路径，所以会被判定为它们是可回收的对象。

在Java中可作为GC Roots对象的总共有4类

1.虚拟机栈栈帧的局部变量表中引用的对象

2.方法区中静态类属性应用的对象

3.方法区中常量引用的对象

4.本地方法栈中引用的对象

以何种方式去回收这些内存？

如何去回收相应的内存，就关系垃圾回收算法和垃圾回收器。对于算法的讨论，暂时定在对算法思想的讨论，因为具体的垃圾回收算法一个是跟虚拟机平台相关（因为不同的虚拟机可能采用了不同的内存操作方式），另一个是涉及到大量的程序细节。算法只是提供了如何如何去实现的思路，而具体的实现就是交由垃圾收集器来完成。

目前的垃圾收集算法主要分为四种：

标记清除算法

复制算法

标记整理算法

分代收集算法

标记清除算法是最早的收集算法，它将过程分为两部分：标记和清除，而后续的算法实际上都是基于这种算法进行改良和优化的来的。复制算法的思路也很简单，就是将内存划分为等大小的两块，每次只使用其中的一块，当使用过的一块内存用完了，就将还存活的对象复制到另一块没有使用过的内存区域上，然后清除旧有的那一块内存，二者交替使用。标记整理算法的前半部分同标记清除算法一样，不同在于后半部分不再是清理可回收对象，而是将存活的对象移向一端。

标记清除算法

标记清除算法是最早的收集算法，也是最简单的收集算法。当堆中的有效内存空间被耗尽的时候，就会停止整个程序（也被成为stop the world），然后进行两项工作，第一项则是标记，第二项则是清除。

标记的过程就是遍历所有的GC Roots对象，然后将所有的GC-Roots可达对象标记为存活对象。

清除就是遍历堆中的所有对象，将没有标记的对象全部清除。

Stop the world

将整个程序其它所有线程停止下来只有垃圾收集线程运行，原因也并不难理解，对于垃圾回收而言，前提是一个对象与GC Roots之间不存在可达路径，假设GC先是判定了对象A是不可达的，而后在程序运行中，A又与GC Roots形成了可达路径，那么A对象所占用内存的回收就是本不应该发生而发生了，为了保证回收的正确性，GC线程的运行前提需要停止所有非GC线程，而各种收集器的进化过程，一直在优化的就有Stop the World所占用时间，就是在减少这个Stop the world的时间，从而保证程序的良好交互性。

标记算法的缺点也很明显， 要遍历所有的对象，标记要遍历，清除也要遍历，导致两个步骤需要停留大量的时间。还有一点就是从图中可以看出清理后的未使用的内存区域并不是连续的这样导致当需要给大对象分配内存的时候会导致内存不够用而不得不又去触发另一次垃圾收集操作。

复制算法

标记清除算法缺点在于效率，为了解决效率问题，复制算法出现了，它将可用的内存划分为相等大小的两个部分 ，每次只使用一种的一块，当其中的一块内存用完了，就直接将标记的存活对象全部复制到另一块没有使用过的内存上面然后将旧有的那一块内存一次性清理掉。

这样解决了标记清除算法因连续内存不够而又去触发另一次垃圾回收的不足，不再需要对整个堆进行遍历，也一定程度提高了效率，但是复制算法的问题也很明显，每次只使用了一半的内存，这是一种变相的浪费内存资源。

解决这种资源浪费的关键点在于，Java中相当大一部分对象的生命时长是朝生夕死的，这个比例IBM公司曾经做过统计，新生代中的对象98%符合这个特性。所以并不需要把内存区域划分为等大小两块，之前在谈论Java堆内存细分的时候提到了堆又可以细分为Eden，Survivor等多个区域，下面看下这张图所示的复制算法：



堆内存分为了三个部分，Eden区，Survivor区，和Old区，Eden区和Survivor区属于新生代，Old区属于老年代，图中所示红色部分是存活的对象，绿色部分是未使用内存，黄色部分是可回收内存，在内存回收的时候，将Eden区和FromSurvivor区上还存活的对象复制到ToSurvivor区上，然后一次性清除这两个区域，HotSpot虚拟机默认Eden区和To Survivor区的比例是8:1，两个合起来占总新生代区域内存的90%；这些比例是可修改的。

这样就非常好的解决了复制算法的空间浪费的问题，但也并不是完美无瑕的，这里使用了一个确定的比例，如果说某次存活对象占用内存的比例大于10%怎么办？即这里的超出了ToSurvivor区域的内存该怎么处理，为此，当Survivor空间不够用的时候，解决问题的点就落在了蓝色Old区域上，即由老年代进行（内存）分配担保。

标记整理算法

通过将内存细分为不同比例的不同区域，解决了复制算法的浪费内存空间的不足，但复制毕竟是一个费时的操作，如果存在大量的对象存活，就会出现两个不足，一个是大量复制导致的时间和处理上的浪费。而老年代中存储的对象的明显特点就是活得时间有点长大量复制操作对于老年代的对象而言显然是不划算的，所以针对老年代这种结构特点，出现了标记整理算法，标记过程还是同标记清除算法中的一样标记过程一致，但后续不再是直接遍历整个堆回收可回收的对象，而是将标记好的对象移动到区域的一端，记录下端界位置，将端界的另一端一次性清除。

分代收集算法

分代收集算法就是根据对象的存活周期把对象划分为几个不同的区域，然后对不同的区域采取不同的收集算法，对于新生代采用复制算法，对于老年代采用标记整理算法。

内存分配策略

Java的动态内存管理技术总的来说分成了两个部分，动态内存回收和动态内存分配，关于动态内存分配，主要了解动态内存分配采取的一些策略。动态内存分配策略，主要是：

1.对象优先在Eden区分配

2.大对象直接进入老年代

3.长期存活的对象将进入老年代

4.动态对象年龄判定

5.内存分配担保

1.对象优先在Eden区分配

对象优先在Eden区分配，当Eden区内存不够的时候触发MinorGC进行一次内存回收。

MinorGC：发生在新生代的GC行为，回收速度快

MajorGC(FullGC)：发生在老年代的GC行为，一般伴随一次MinorGC，回收速度慢

对象优先在Eden区分配，原因在于绝大多数对象都是朝生夕死的，在专门的区域分配可以针对这块区域做专门的处理，提高内存分配和回收的效率。当Eden区内存不够的时候，就会触发MinorGC进行一次内存回收，如果说回收之后的内存还是不够，那么就会借助内存分配机制将Eden区域的部分内存转移提前转移到老年代区中，用图中所示的代码测试一下，首先数组对象location1,2，3所占用的内存都是2MB，location4占用的内存是4MB。

-verbose:gc -Xms20M -Xmx20M -Xmn10M -XX:+PrintGCDetails -XX:SurvivorRatio=8

虚拟机参数，指定堆内存新生代为10M，总内存为20M，新生代中Eden和Survivor区比例为8:1

运行结果：

从日志中输出的结果看来，Eden区占用了内存4M，老年代占用了内存6M，整个流程是这样的，在分配location123的时候，Eden区中的内存使用了6M，是足够的，当为location4分配的时候，需要4M，发现内存不够，触发一次新生代的垃圾回收，回收之后，新生代占用的内存从原来的7351K减少到了992K,堆上的总内存从原来的7351K减少到了3376K，在走完垃圾回收之后，发现Eden区余下的内存还是不够location4使用，而location123又无法放入到ToSurvivor中，于是只能通过内存分配担保机制提前的将location123转移到老年代中，所以gc之后老年代占用了6M，Eden区余下内存足够放下location4，所以Eden去最终占用了约4M。

2.大对象直接进入老年代

大对象：需要大量连续内存空间的Java对象，典型大数组和长字符串

虚拟机对于大对象的处理是直接使其进入老年代，这个是可以通过给虚拟机设置参数来指定多大体积的对象称为大对象，因为这里我电脑上HotSpot VM这里采用的是Parallel Scavege收集器，无法识别这个参数，所以我直接用了逼近Eden区域总内存，大小为7MB的byte类型数组来做大对象。

byte[] location = new byte[7*_1MB];

验证的结果是：老年代中刚好占用了7M的空间且没有触发GC回收，说明大对象location是直接进入到老年代的内存区域中。

3.长期存活的对象将进入老年代

虚拟机采用分代思想来管理内存，那么在内存回收时候就能够已经知晓什么对象是年轻的，什么对象是老年的。

每一个对象都有一个对象年龄计数器，挺过一次GC就将年龄+1岁，默认15岁为今日老年状态。

通过参数-XX:MaxTenuringThreshold=10 指定晋升老年代的对象年龄为10，默认值是15。

虚拟机为每一个对象都设置了一个年龄计数器，对象在Eden区诞生，如果顺利的挺过它的第一次MinorGC，这个对象就将复制转移到Survivor区域中，更准确地是FromSurvivor区，在Survivor区中每挺过一次MinorGC，它的年龄就将+1，默认到15岁的时候，就将晋升为老年对象，转移到老年代中。

4.动态年龄判定

虚拟机并不要求必须达到年龄参数的阈值才能晋升为老年代，如果在Survivor空间中，相同年龄的所有对象占用内存总和超过了Survivor空间的一半，等于大于该年龄的对象即晋升为老年代。

5.空间分配担保

这一步骤发生在MinorGC之前，虚拟机首先检查老年代最大可用空间是否大于新生代所有对象总空间，如果大于那么MinorGC就是安全的，直接执行这次GC即可，如果不大于，则说明这次MinorGC是有风险的（会使得对象直接进入老年代）。

在Survivor区域内存不够的情况下会触发MinorGC对新生代进行一次垃圾回收，当还是GC之后还是不够用的情况下（即Survivor区无法容纳接下来要复制进Survivor区的对象（上面说到的对象在Eden区挺过一次MinorGC就将进入到Survivor区域）），就会进行空间分配担保，将对象直接复制进老年代（这里的直接复制进老年代就是风险所在），而老年代要进行担保的前提是自身还有足够的剩余空间容纳这些对象，但是在完成内存回收工作之前，是无法准确知道担保是否会成功的，所以这里用到了动态概率的手段，虚拟机会取之前每一次晋升到老年代的对象的体积的平均水平来作为本次担保的依据，根据这个平均水平来确认是否需要发起一次Full GC来清理老年代以腾出更多空间，因为是动态概率手段，结果不一定是正确的，比如某次要转移到老年代的对象猛增，就会导致担保失败。

再JDK6之后，取消了这个参数，只要老年代连续空间大于新生代对象总大小或者历次晋升老年代的平均大小，就只进行MinorGC，否则就进行Full GC。

---

参考资料：

《深入理解Java虚拟机》

《Java 虚拟机规范》