1.5 垃圾回收与算法
1.5.1 如何确定垃圾
Java采用引用计数法和可达性分析来确定对象是否应该被回收，其中，引用计数法容易产生循环引用的问题，可达性分析通过根搜索算法（GC Roots Tracing）来实现。根搜索算法以一系列GC Roots的点作为起点向下搜索，在一个对象到任何GC Roots都没有引用链相连时，说明其已经死亡。根搜索算法主要针对栈中的引用、方法区中的静态引用和JNI中的引用展开分析，如图1-6所示。
图1-6
1．引用计数法
在Java中如果要操作对象，就必须先获取该对象的引用，因此可以通过引用计数法来判断一个对象是否可以被回收。在为对象添加一个引用时，引用计数加1；在为对象删除一个引用时，引进计数减1；如果一个对象的引用计数为0，则表示此刻该对象没有被引用，可以被回收。
引用计数法容易产生循环引用问题。循环引用指两个对象相互引用，导致它们的引用一直存在，而不能被回收，如图1-7所示，Object1与Object2互为引用，如果采用引用计数法，则Object1和Object2由于互为引用，其引用计数一直为1，因而无法被回收。
图1-7
2．可达性分析
为了解决引用计数法的循环引用问题，Java还采用了可达性分析来判断对象是否可以被回收。具体做法是首先定义一些GC Roots对象，然后以这些GC Roots对象作为起点向下搜索，如果在GC roots和一个对象之间没有可达路径，则称该对象是不可达的。不可达对象要经过至少两次标记才能判定其是否可以被回收，如果在两次标记后该对象仍然是不可达的，则将被垃圾收集器回收。
1.5.2 Java中常用的垃圾回收算法
Java中常用的垃圾回收算法有标记清除（Mark-Sweep）、复制（Copying）、标记整理（Mark-Compact）和分代收集（Generational Collecting）这4种垃圾回收算法，如图1-8所示。
图1-8
1．标记清除算法
标记清除算法是基础的垃圾回收算法，其过程分为标记和清除两个阶段。在标记阶段标记所有需要回收的对象，在清除阶段清除可回收的对象并释放其所占用的内存空间，如图1-9所示。
图1-9
由于标记清除算法在清理对象所占用的内存空间后并没有重新整理可用的内存空间，因此如果内存中可被回收的小对象居多，则会引起内存碎片化的问题，继而引起大对象无法获得连续可用空间的问题。
2．复制算法
复制算法是为了解决标记清除算法内存碎片化的问题而设计的。复制算法首先将内存划分为两块大小相等的内存区域，即区域1和区域2，新生成的对象都被存放在区域1中，在区域1内的对象存储满后会对区域1进行一次标记，并将标记后仍然存活的对象全部复制到区域2中，这时区域1将不存在任何存活的对象，直接清理整个区域1的内存即可，如图1-10所示。
图1-10
复制算法的内存清理效率高且易于实现，但由于同一时刻只有一个内存区域可用，即可用的内存空间被压缩到原来的一半，因此存在大量的内存浪费。同时，在系统中有大量长时间存活的对象时，这些对象将在内存区域1和内存区域2之间来回复制而影响系统的运行效率。因此，该算法只在对象为“朝生夕死”状态时运行效率较高。
3．标记整理算法
标记整理算法结合了标记清除算法和复制算法的优点，其标记阶段和标记清除算法的标记阶段相同，在标记完成后将存活的对象移到内存的另一端，然后清除该端的对象并释放内存，如图1-11所示。
图1-11
4．分代收集算法
无论是标记清除算法、复制算法还是标记整理算法，都无法对所有类型（长生命周期、短生命周期、大对象、小对象）的对象都进行垃圾回收。因此，针对不同的对象类型，JVM采用了不同的垃圾回收算法，该算法被称为分代收集算法。
分代收集算法根据对象的不同类型将内存划分为不同的区域，JVM将堆划分为新生代和老年代。新生代主要存放新生成的对象，其特点是对象数量多但是生命周期短，在每次进行垃圾回收时都有大量的对象被回收；老年代主要存放大对象和生命周期长的对象，因此可回收的对象相对较少。因此，JVM根据不同的区域对象的特点选择了不同的算法。
目前，大部分JVM在新生代都采用了复制算法，因为在新生代中每次进行垃圾回收时都有大量的对象被回收，需要复制的对象（存活的对象）较少，不存在大量的对象在内存中被来回复制的问题，因此采用复制算法能安全、高效地回收新生代大量的短生命周期的对象并释放内存。
JVM将新生代进一步划分为一块较大的Eden区和两块较小的Servivor区，Servivor区又分为ServivorFrom区和ServivorTo区。JVM在运行过程中主要使用Eden区和ServivorFrom区，进行垃圾回收时会将在Eden区和ServivorFrom区中存活的对象复制到ServivorTo区，然后清理Eden区和ServivorFrom区的内存空间，如图1-12所示。
图1-12
老年代主要存放生命周期较长的对象和大对象，因而每次只有少量非存活的对象被回收，因而在老年代采用标记清除算法。
在JVM中还有一个区域，即方法区的永久代，永久代用来存储Class类、常量、方法描述等。在永久代主要回收废弃的常量和无用的类。
JVM内存中的对象主要被分配到新生代的Eden区和ServivorFrom区，在少数情况下会被直接分配到老年代。在新生代的Eden区和ServivorFrom区的内存空间不足时会触发一次GC，该过程被称为MinorGC。在MinorGC后，在Eden区和ServivorFrom区中存活的对象会被复制到ServivorTo区，然后Eden区和ServivorFrom区被清理。如果此时在ServivorTo区无法找到连续的内存空间存储某个对象，则将这个对象直接存储到老年代。若Servivor区的对象经过一次GC后仍然存活，则其年龄加1。在默认情况下，对象在年龄达到15时，将被移到老年代。