前面说过，基于分代回收理论的指导，我们可以针对堆中的不同区域设计不同的垃圾回收算法，主要有以下三种：mark-ClearAlgorithmMark-CopyAlgorithmMark-SortingAlgorithm全文思维导图如下：由Lisp之父JohnMcCarthy于1960年提出，后文介绍的两种算法均基于此改进。不难理解，从名字就可以看出，整个算法分为标记和清除两大步骤。展开：标记，标记：是指标记所有需要回收的对象（即判断对象是否是垃圾，这个之前已经说过了，有两种方法：引用计数和可达性分析，由于引用的计数法不能解决循环引用的问题，所以目前主流的虚拟机都是采用可达性分析法）来清除，Sweep：指的是在标记完成后回收所有标记的对象，当然反之亦然，标记幸存的对象并统一回收所有未标记的对象。我们说这个mark-sweep算法是最基本的垃圾回收算法。后两种算法都是基于这种改进。然后是improvement改进，既然是改进，那么这个基础算法肯定是有一些问题才可以改进的。空间，对吧？mark-clear算法的缺点主要有两个：第一：执行效率不稳定。如果堆中包含大量对象，并且其中大部分需要回收，此时必须进行大量的标记和清除动作，导致标记和清除两个过程的执行效率会降低为对象的数量增加，即执行效率与对象数量成反比。第二：内存空间碎片化。标记和清除后，会产生大量不连续的内存碎片。太多的空间碎片可能会导致另一个垃圾收集动作被提前触发，因为它在程序运行过程中需要分配一个大对象时找不到足够的连续内存。Mark-Clear算法的执行过程如图所示：Mark-CopyAlgorithm，Mark-Copy“标记-复制”（Mark-Copy）算法通常简称为复制算法。为了解决mark-sweep算法在面对大量可回收对象时执行效率低的问题，Fenichel在1969年提出了一种名为“SemispaceCopying”的垃圾回收算法，具体思想大致如下：available内存根据容量分成大小相等的两个块，一次只使用其中一个。当本块内存用完后，将存活的对象复制到另一个块中，然后一次性清理所有已用内存空间。显然，这种方式不适合大多数对象都存活的情况，因为会产生大量的内存拷贝开销。但是对于大部分对象都是可回收的情况，算法只需要复制少量存活的对象，每次回收整个半个区域的内存，不需要考虑空间碎片的复杂情况分配内存时，只需移动堆顶指针，依次分配即可。这易于实施且运行高效。现在大部分商用的Java虚拟机都比较喜欢使用这种垃圾回收算法来回收新生代，这种复制恢复算法的代价是将可用内存减少到原来的一半，空间的浪费有点过分了。IBM曾经专门研究过，对新生代“生死存亡”的特征给出更加量化的解读：新生代中98%的对象都无法在第一轮收集中存活下来。所以不需要按照1:1的比例划分新生代的内存空间。简单来说，mark-copy算法设计这么大的预留区域，就是为了将存活的对象移动到这个区域，方便快速清理之前的区域。对于新生代对象来说，显着的特点就是“生死存亡”，能在一轮垃圾回收中存活下来的对象非常少。所以，我们其实不需要那么大的保留区。1989年，AndrewAppel在此基础上提出了更优的半区复制生成策略，现称为“Appel-stylerecycling”。HotSpot虚拟机的Serial、ParNew等新一代收集器采用这种策略来设计新一代的内存布局。?Appel式回收的具体方法是将新生代分成一个较大的Eden空间和两个较小的Survivor空间，每次分配内存只使用Eden和其中一个Survivor空间。当发生垃圾回收时，直接清空Eden和使用过的Survivor空间。当然，还需要将存活的对象复制到另一个Survivor空间，才能清空。这两个Survivor空间也分别称为FromSurvivor和ToSurvivor。显然，每次新生代GC之后，FromSurvivor和ToSurvivor的身份都会交换。简单理解，Eden和FromSurvivor其实是新生代可以使用的真实内存，而ToSurvivor的存在是为了在新生代空间清空时，提供一个存放存活对象的地方（即保留区）。HotSpot虚拟机默认的Eden和Survivor的比例是8:1，即每个新生代中的可用内存空间是整个新生代容量的90%（Eden的80%加上一个Survivor的10%），并且SurvivorSpace只有一个，也就是新生代空间的10%会被“浪费”。当然，没有人能100%保证每次回收不会有超过10%的对象存活下来。如果ToSurvivor的内存空间不足以容纳存活的对象怎么办？别着急，我们都能想到，老祖宗能想到吗？Appel式回收还有一个安全设计，在极少数情况下充当“逃生门”：当ToSurvivor空间不足以容纳在新一代GC中幸存下来的对象时，这些对象将通过分配保证机制（HandlePromotion)直接进入晚年。对于所谓的分配保证，mark-compact算法会在后续文章介绍垃圾收集器时详细讲解。Mark-CompactMark-Copy算法在对象存活率高的时候会进行更多的复制操作，效率会降低。更重要的是，如果不想浪费50%的空间，如果使用苹果式的回收，就需要有额外的空间分配保证，以应对所有对象在已用内存中都是100%的极端情况alive，所以在老年代对象在老年代的存活特性一般不能直接选择Mark-Copy算法。1974年，EdwardLueders提出了另一种有针对性的“Mark-Compact”算法。标记过程还是一样，但是后续步骤不是直接清理可回收对象，而是将所有存活的对象移动到内存空间的一端，然后直接清理边界外的内存，如如图：Mark-Sweep算法和Mark-Compact算法的本质区别原因在于前者是非移动回收算法，而后者是移动回收算法。回收后是否移动幸存的物体是一个有利也有弊的冒险决定。如果移动存活对象，尤其是老年代，每个集合都有大量对象存活区，需要移动存活对象，更新所有引用这些对象的地方。这是一个非常繁重的操作，这种对象移动操作必须挂起用户应用程序才能继续。这样的停顿被最初的虚拟机设计者形象地描述为“StopTheWorld(STW)”。（记住STW这个名词，以后我们会经常见到他的！！！移动存活对象时需要STW，可达性分析中的根节点枚举也需要STW）。总结一下：移动的时候内存回收会比较复杂。如果根本不考虑移动和组织存活对象，存活对象分散在堆中导致的空间碎片问题只能依赖更复杂的内存分配器和内存访问。然而，内存访问是用户程序最频繁的操作，甚至没有之一。如果在这个环节增加额外的负担，肯定会直接影响到应用的吞吐量。总结一下：如果不动，内存分配会更复杂。从垃圾回收的暂停时间来看，非移动对象的暂停时间会更短，甚至可能不需要暂停，但是从整个程序的吞吐量来看，移动对象呢会更划算。这里的吞吐量，简单理解就是用户程序和垃圾收集器效率的总和，所以我们其实可以推导出一个注重延迟/速度的收集器（比如HotSpot虚拟机中的CMS收集器）应该使用Mark-Sweep算法。关注吞吐量的收集器（例如HotSpot虚拟机中的ParallelOld收集器）应该使用Mark-Compact算法。另外，其实还有一个折中的方法。Mark-Sweep算法速度快，可以让虚拟机大部分时间使用Mark-Sweep算法，暂时容忍内存碎片的存在，直到内存空间碎片化程度大为止。当影响到对象分配时，再使用Mark-Compact算法进行收集，获得规律的内存空间（这是基于Mark-Sweep算法的CMS收集器在空间碎片过多时所面临的）。最后放上本题的背诵版：面试官：说说垃圾回收算法有哪些？Veal：主要分为三种：1）Mark-clear算法：这是最基本的算法。主要思想是首先标记所有垃圾收集算法。需要回收的对象，然后统一回收所有标记的对象。该算法有两个主要缺点：执行效率不稳定。如果堆中包含大量的对象，而且大部分都需要回收，此时必须进行大量的标记和清除动作，也就是说执行效率与对象的数量成反比以及内存空间的碎片化。标记和清除后，会产生大量不连续的内存碎片。太多的空间碎片可能导致当程序在运行过程中需要分配大对象时，由于找不到足够的连续内存而不得不提前触发另一个垃圾收集动作。后续mark-copy算法和mark-sort算法这两种算法都是在mark-sweep算法的基础上进行的改进。2）Mark-Copy算法：主要思想是将可用内存按容量分成两块大小相等，每次只使用其中一块。当本块内存用完后，将存活的对象复制到另一个块中，然后一次性清理所有已用内存空间。这种半区复制算法也有两个明显的问题：不适用于对象存活率高的情况（即一般不适用于老年代）和可用内存空间减少一半（对于这个问题，实施了“Appel式回收”）。改进是根据新生代“生死存亡”的特点，能在一轮垃圾回收中存活下来的对象很少，所以我们其实不需要那么大的保留区。具体做法是把新生代分成一个较大的Eden空间和两个较小的Survivor空间，每次内存分配只使用Eden和其中一个Survivor。当发生垃圾回收时，需要将存活的对象复制到另一个Survivor中再清空，然后直接EmptyEden和已使用的Survivor空间。另外，如果使用Apple式的回收，需要额外的空间进行分配保证，因为没有办法保证分配给ToSurvivor的内存空间可以容纳所有的survivor对象，通常的做法是当ToSurvivor空间不足以容纳新生代GC存活下来的对象，这些对象将通过分配保证机制直接进入老年代）。3）标记排序算法：主要思想是将所有存活的对象移动到内存空间的一端，然后直接清理边界外的内存。这种移动算法比不移动的mark-sweep算法具有更高的吞吐量，但速度相对较慢，因为移动物体需要停止世界。因此，关注延迟/速度的收集器（如HotSpot虚拟机中的CMS收集器）应该使用Mark-Sweep算法，而关注吞吐量的收集器（如HotSpot虚拟机中的ParallelOld收集器）应该使用Mark-Sweep算法。紧凑的算法。另外，其实还有一个折中的方法。Mark-Sweep算法速度快，可以让虚拟机大部分时间使用Mark-Sweep算法，暂时容忍内存碎片的存在，直到内存空间碎片化程度大为止。当影响到对象分配时，再使用Mark-Compact算法进行收集，获得规律的内存空间（这是基于Mark-Sweep算法的CMS收集器在空间碎片过多时所面临的）。
