通用垃圾回收算法

Mark-Sweep（标记-清除算法）

标记-清除算法将垃圾回收分为两个阶段：标记阶段和清除阶段。一种可行的实现是，在标记阶段首先通过根节点，标记所有从根节点开始的较大对象。因此，未被标记的对象就是未被引用的垃圾对象。然后，在清除阶段，清除所有未被标记的对象。该算法最大的问题是存在大量的空间碎片，因为回收后的空间是不连续的。在对象的堆空间分配过程中，尤其是大对象的内存分配，不连续的内存空间的工作效率要低于连续的空间。

从概念上来讲，标记-清除算法使用的方法是最简单的，只需要忽略这些对象便可以了。也就是说当标记阶段完成之后，未被访问到的对象所在的空间都会被认为是空闲的，可以用来创建新的对象。这种方法需要使用一个空闲列表来记录所有的空闲区域以及大小。对空闲列表的管理会增加分配对象时的工作量。这种方法还有一个缺陷就是——虽然空闲区域的大小是足够的，但却可能没有一个单一区域能够满足这次分配所需的大小，因此本次分配还是会失败(在Java中就是一次OutOfMemoryError)。

Copying（复制算法）

将现有的内存空间分为两快，每次只使用其中一块，在垃圾回收时将正在使用的内存中的存活对象复制到未被使用的内存块中，之后，清除正在使用的内存块中的所有对象，交换两个内存的角色，完成垃圾回收。如果系统中的垃圾对象很多，复制算法需要复制的存活对象数量并不会太大。因此在真正需要垃圾回收的时刻，复制算法的效率是很高的。又由于对象在垃圾回收过程中统一被复制到新的内存空间中，因此，可确保回收后的内存空间是没有碎片的。该算法的缺点是将系统内存折半。

Java的新生代串行垃圾回收器中使用了复制算法的思想。新生代分为eden空间、from空间、to空间3个部分。其中from空间和to空间可以视为用于复制的两块大小相同、地位相等，且可进行角色互换的空间块。from和to空间也称为survivor空间，即幸存者空间，用于存放未被回收的对象。在垃圾回收时，eden空间中的存活对象会被复制到未使用的survivor空间中(假设是to)，正在使用的survivor空间(假设是from)中的年轻对象也会被复制到to空间中(大对象，或者老年对象会直接进入老年带，如果to空间已满，则对象也会直接进入老年代)。此时，eden空间和from空间中的剩余对象就是垃圾对象，可以直接清空，to空间则存放此次回收后的存活对象。这种改进的复制算法既保证了空间的连续性，又避免了大量的内存空间浪费。

标记-复制算法与标记-整理算法非常类似，它们都会将所有存活对象重新进行分配。区别在于重新分配的目标地址不同，复制算法是为存活对象分配了另外的内存 区域作为它们的新家。标记复制算法的优点在于标记阶段和复制阶段可以同时进行。它的缺点是需要一块能容纳下所有存活对象的额外的内存空间。

Mark-Compact（标记-压缩算法）

复制算法的高效性是建立在存活对象少、垃圾对象多的前提下的。这种情况在年轻代经常发生，但是在老年代更常见的情况是大部分对象都是存活对象。如果依然使用复制算法，由于存活的对象较多，复制的成本也将很高。

标记-压缩算法是一种老年代的回收算法，它在标记-清除算法的基础上做了一些优化。也首先需要从根节点开始对所有可达对象做一次标记，但之后，它并不简单地清理未标记的对象，而是将所有的存活对象压缩到内存的一端。之后，清理边界外所有的空间。这种方法既避免了碎片的产生，又不需要两块相同的内存空间，因此，其性价比比较高。

标记-压缩算法修复了标记-清除算法的短板——它将所有标记的也就是存活的对象都移动到内存区域的开始位置。这种方法的缺点就是GC暂停的时间会增 长，因为你需要将所有的对象都拷贝到一个新的地方，还得更新它们的引用地址。相对于标记-清除算法，它的优点也是显而易见的——经过整理之后，新对象的分 配只需要通过指针碰撞便能完成(pointer bumping)，相当简单。使用这种方法空闲区域的位置是始终可知的，也不会再有碎片的问题了。

Incremental Collecting（增量回收算法）

在垃圾回收过程中，应用软件将处于一种CPU消耗很高的状态。在这种CPU消耗很高的状态下，应用程序所有的线程都会挂起，暂停一切正常的工作，等待垃圾回收的完成。如果垃圾回收时间过长，应用程序会被挂起很久，将严重影响用户体验或者系统的稳定性。

增量算法现代垃圾回收的一个前身，其基本思想是，如果一次性将所有的垃圾进行处理，需要造成系统长时间的停顿，那么就可以让垃圾收集线程和应用程序线程交替执行。每次，垃圾收集线程只收集一小片区域的内存空间，接着切换到应用程序线程。依次反复，直到垃圾收集完成。使用这种方式，由于在垃圾回收过程中，间断性地还执行了应用程序代码，所以能减少系统的停顿时间。但是，因为线程切换和上下文转换的消耗，会使得垃圾回收的总体成本上升，造成系统吞吐量的下降。

Generational Collecting（分代回收算法）

分代回收器是增量收集的另一个化身，根据垃圾回收对象的特性，不同阶段最优的方式是使用合适的算法用于本阶段的垃圾回收，分代算法即是基于这种思想，它将内存区间根据对象的特点分成几块，根据 每块内存区间的特点，使用不同的回收算法，以提高垃圾回收的效率。以Hot Spot虚拟机为例，它将所有的新建对象都放入称为年轻代的内存区域，年轻代的特点是对象会很快回收，因此，在年轻代就选择效率较高的复制算法。当一个对象经过几次回收后依然存活，对象就会被放入称为老生代的内存空间。在老生代中，几乎所有的对象都是经过几次垃圾回收后依然得以幸存的。因此，可以认为这些对象在一段时期内，甚至在应用程序的整个生命周期中，将是常驻内存的。如果依然使用复制算法回收老生代，将需要复制大量对象。再加上老生代的回收性价比也要低于新 生代，因此这种做法也是不可取的。根据分代的思想，可以对老年代的回收使用与新生代不同的标记-压缩算法，以提高垃圾回收效率。

当代主流虚拟机（Hotspot VM）的垃圾回收都采用“分代回收”的算法。“分代回收”是基于这样一个事实：对象的生命周期不同，所以针对不同生命周期的对象可以采取不同的回收方式，以便提高回收效率。Hotspot VM将内存划分为不同的物理区，就是“分代”思想的体现。如图所示，JVM内存主要由新生代、老年代、永久代构成。

• 新生代（Young Generation）：大多数对象在新生代中被创建，其中很多对象的生命周期很短。每次新生代的垃圾回收（又称Minor GC）后只有少量对象存活，所以选用复制算法，只需要少量的复制成本就可以完成回收。新生代内又分三个区：一个Eden区，两个Survivor区（一般而言），大部分对象在Eden区中生成。当Eden区满时，还存活的对象将被复制到两个Survivor区（中的一个）。当这个Survivor区满时，此区的存活且不满足“晋升”条件的对象将被复制到另外一个Survivor区。对象每经历一次Minor GC，年龄加1，达到“晋升年龄阈值”后，被放到老年代，这个过程也称为“晋升”。显然，“晋升年龄阈值”的大小直接影响着对象在新生代中的停留时间，在Serial和ParNew GC两种回收器中，“晋升年龄阈值”通过参数MaxTenuringThreshold设定，默认值为15。

• 老年代（Old Generation）：在新生代中经历了N次垃圾回收后仍然存活的对象，就会被放到年老代，该区域中对象存活率高。老年代的垃圾回收（又称Major GC）通常使用“标记-清理”或“标记-整理”算法。整堆包括新生代和老年代的垃圾回收称为Full GC（HotSpot VM里，除了CMS之外，其它能收集老年代的GC都会同时收集整个GC堆，包括新生代）。

• 永久代（Perm Generation）：主要存放元数据，例如Class、Method的元信息，与垃圾回收要回收的Java对象关系不大。相对于新生代和年老代来说，该区域的划分对垃圾回收影响比较小。在Java 8之前，PermGen是存放在堆中，在Java 8之后，PermGen被Metaspace替代，并且Metaspace直接存放在原生内存，而不再是堆中。

动态年龄计算

Hotspot遍历所有对象时，按照年龄从小到大对其所占用的大小进行累积，当累积的某个年龄大小超过了survivor区的一半时，取这个年龄和MaxTenuringThreshold中更小的一个值，作为新的晋升年龄阈值。在本案例中，调优前：Survivor区= 64M，desired survivor = 32M，此时Survivor区中age<=2的对象累计大小为41M，41M大于32M，所以晋升年龄阈值被设置为2，下次Minor GC时将年龄超过2的对象被晋升到老年代。

JVM引入动态年龄计算，主要基于如下两点考虑：

• 如果固定按照MaxTenuringThreshold设定的阈值作为晋升条件：a）MaxTenuringThreshold设置的过大，原本应该晋升的对象一直停留在Survivor区，直到Survivor区溢出，一旦溢出发生，Eden+Svuvivor中对象将不再依据年龄全部提升到老年代，这样对象老化的机制就失效了。b）MaxTenuringThreshold设置的过小，“过早晋升”即对象不能在新生代充分被回收，大量短期对象被晋升到老年代，老年代空间迅速增长，引起频繁的Major GC。分代回收失去了意义，严重影响GC性能。

• 相同应用在不同时间的表现不同：特殊任务的执行或者流量成分的变化，都会导致对象的生命周期分布发生波动，那么固定的阈值设定，因为无法动态适应变化，会造成和上面相同的问题。

总结来说，为了更好的适应不同程序的内存情况，虚拟机并不总是要求对象年龄必须达到Maxtenuringthreshhold再晋级老年代。

Minor GC, Major GC与Full GC

针对HotSpot VM的实现，它里面的GC其实准确分类只有两大种：

• Partial GC：并不收集整个GC堆的模式

  • Young GC：只收集young gen的GC
  • Old GC：只收集old gen的GC。只有CMS的concurrent collection是这个模式
  • Mixed GC：收集整个young gen以及部分old gen的GC。只有G1有这个模式

• Full GC：收集整个堆，包括young gen、old gen、perm gen（如果存在的话）等所有部分的模式。

最简单的分代式GC策略，按HotSpot VM的serial GC的实现来看，触发条件是：

• Young GC：当young gen中的eden区分配满的时候触发。注意Young GC中有部分存活对象会晋升到old gen，所以Young GC后old gen的占用量通常会有所升高。
• Full GC：
  • 当准备要触发一次Young GC时，如果发现统计数据说之前Young GC的平均晋升大小比目前old gen剩余的空间大，则不会触发Young GC而是转为触发Full GC（因为HotSpot VM的GC里，除了CMS的concurrent collection之外，其它能收集old gen的GC都会同时收集整个GC堆，包括young gen，所以不需要事先触发一次单独的young GC）；
  • 如果有perm gen的话，要在perm gen分配空间但已经没有足够空间时，也要触发一次Full GC；
  • 或者System.gc()、heap dump带GC，默认也是触发Full GC。

Concurrent Collecting（并发回收算法）

所谓的并发回收算法即是指垃圾回收器与应用程序能够交替工作，并发回收 器其实也会暂停，但是时间非常短，它并不会在从开始回收寻找、标记、清楚、压缩或拷贝等方式过程完全暂停服务，它发现有几个时间比较长，一个就是标记，因 为这个回收一般面对的是老年代，这个区域一般很大，而一般来说绝大部分对象应该是活着的，所以标记时间很长，还有一个时间是压缩，但是压缩并不一定非要每 一次做完GC都去压缩的，而拷贝呢一般不会用在老年代，所以暂时不考虑。

所以他们想出来的办法就是：第一次短暂停机是将所有对象的根指针找到，这个非常容 易找到，而且非常快速，找到后，此时GC开始从这些根节点标记活着的节点(这里可以采用并行)，然后待标记完成后，此时可能有新的 内存申请以及被抛弃(java本身没有内存释放这一概念)，此时JVM会记录下这个过程中的增量信息，而对于老年代来说，必须要经过多次在survivor倒腾后才会进入老年代，所以它在这段时间增量一般来说会非常少，而且它被释放的概率前面也说并不大(JVM如果不是完全做Cache，自己做pageCache而且发生概率不大不小的pageout和pagein是不适合的)；JVM根据这些增量信息快速标记出内部的节点，也是非常快速 的，就可以开始回收了，由于需要杀掉的节点并不多，所以这个过程也非常快，压缩在一定时间后会专门做一次操作，有关暂停时间在Hotspot版本，也就是SUN的jdk中都是可以配置的，当在指定时间范围内无法回收时，JVM将会对相应尺寸进行调整，如果你不想让它调整，在设置各个区域的大小时，就使用定 量，而不要使用比例来控制；当采用并发回收算法的时候，一般对于老年代区域，不会等待内存小于10%左右的时候才会发起回收，因为并发回收是允许在回收的 时候被分配，那样就有可能来不及了，所以并发回收的时候，JVM可能会在68%左右的时候就开始启动对老年代GC了。