JVM垃圾回收算法
垃圾回收算法
我们常说的垃圾回收算法可以分为两部分：对象的查找算法与真正的回收方法。不同回收器的实现细节各有不同，但总的来说基本所有的回收器都会关注如下两个方面：找出所有的存活对象以及清理掉所有的其它对象——也就是那些被认为是废弃或无用的对象。Java 虚拟机规范中对垃圾收集器应该如何实现并没有任何规定，因此不同的厂商、不同版本的虚拟机所提供的垃圾收集器都可能会有很大差别，并且一般都会提供参数供用户根据自己的应用特点和要求组合出各个年代所使用的收集器。其中最主流的四个垃圾回收器分别是：通常用于单 CPU 环境的 Serial GC、Throughput/Parallel GC、CMS GC、G1 GC。
垃圾收集器分类
当我们在讨论垃圾回收器时，往往也会涉及到很多的概念；譬如并行（Parallel）与并发（Concurrent）、Minor GC 与 Major / Full GC。并行指多条垃圾收集线程并行工作，但此时用户线程仍然处于等待状态；并发指用户线程与垃圾收集线程同时执行（但不一定是并行的，可能会交替执行），用户程序在继续运行，而垃圾收集程序运行于另一个CPU上。Minor GC 指发生在新生代的垃圾收集动作，因为Java对象大多都具备朝生夕灭的特性，所以Minor GC非常频繁，一般回收速度也比较快；Major GC 指发生在老年代的GC，出现了Major GC，经常会伴随至少一次的Minor GC（但非绝对的，在Parallel Scavenge收集器的收集策略里就有直接进行Major GC的策略选择过程），Major GC的速度一般会比Minor GC慢10倍以上。从不同角度分析垃圾回收器，可以将其分为不同的类型：
| 分类标准 | 描述 |
|---|---|
| 线程数 | 分为串行垃圾回收器和并行垃圾回收器。串行垃圾回收器一次只使用一个线程进行垃圾回收；并行垃圾回收器一次将开启多个线程同时进行垃圾回收。在并行能力较强的 CPU 上，使用并行垃圾回收器可以缩短 GC 的停顿时间。 |
| 工作模式 | 分为并发式垃圾回收器和独占式垃圾回收器。并发式垃圾回收器与应用程序线程交替工作，以尽可能减少应用程序的停顿时间；独占式垃圾回收器 (Stop the world) 一旦运行，就停止应用程序中的其他所有线程，直到垃圾回收过程完全结束。 |
| 碎片处理方式 | 分为压缩式垃圾回收器和非压缩式垃圾回收器。压缩式垃圾回收器会在回收完成后，对存活对象进行压缩整理，消除回收后的碎片；非压缩式的垃圾回收器不进行这步操作。 |
| 工作的内存区间 | 新生代垃圾回收器和老年代垃圾回收器 |
垃圾回收器指标
我们最常用的评价垃圾回收器的指标就是吞吐量与停顿时间，停顿时间越短就越适合需要与用户交互的程序，良好的响应速度能提升用户的体验；而高吞吐量则可以最高效率地利用 CPU 时间，尽快地完成程序的运算任务，主要适合在后台运算而不需要太多交互的任务；具体的指标列举如下：
吞吐量：指在应用程序的生命周期内，应用程序所花费的时间和系统总运行时间的比值。系统总运行时间=应用程序耗时+GC 耗时。如果系统运行了 100min，GC 耗时 1min，那么系统的吞吐量就是 (100-1)/100=99%。
垃圾回收器负载：和吞吐量相反，垃圾回收器负载指来记回收器耗时与系统运行总时间的比值。
停顿时间：指垃圾回收器正在运行时，应用程序的暂停时间。对于独占回收器而言，停顿时间可能会比较长。使用并发的回收器时，由于垃圾回收器和应用程序交替运行，程序的停顿时间会变短，但是，由于其效率很可能不如独占垃圾回收器，故系统的吞吐量可能会较低。
垃圾回收频率：指垃圾回收器多长时间会运行一次。一般来说，对于固定的应用而言，垃圾回收器的频率应该是越低越好。通常增大堆空间可以有效降低垃圾回收发生的频率，但是可能会增加回收产生的停顿时间。
反应时间：指当一个对象被称为垃圾后多长时间内，它所占据的内存空间会被释放。
堆分配：不同的垃圾回收器对堆内存的分配方式可能是不同的。一个良好的垃圾回收器应该有一个合理的堆内存区间划分。
在对象查找算法的帮助下我们可以找到内存可以被使用的，或者说那些内存是可以回收，更多的时候我们肯定愿意做更少的事情达到同样的目的。
如何回收
JVM虚拟机如何对标记的对象进行垃圾回收，这里主要有四种垃圾回收算法：标记-清除算法、复制-整理算法、标记-整理算法、分代收集算法
标记-清除算法
常用的垃圾收集算法
| 算法名 | 优势 | 缺陷 |
|---|---|---|
| Mark-Sweep / 标记-清除 | 简单 | 效率低下且会产生很多不连续内存，分配大对象时，容易提前引起另一次垃圾回收。 |
| Copying / 复制 | 效率较高，不用考虑内存碎片化 | 存在空间浪费 |
| Mark-Compact / 标记-整理 | 避免了内存碎片化 | GC 暂停时间增长 |
标记-清除算法
标记-清除算法将垃圾回收分为两个阶段：标记阶段和清除阶段。一种可行的实现是，在标记阶段首先通过根节点，标记所有从根节点开始的较大对象。因此，未被标记的对象就是未被引用的垃圾对象。然后，在清除阶段，清除所有未被标记的对象。该算法最大的问题是存在大量的空间碎片，因为回收后的空间是不连续的。在对象的堆空间分配过程中，尤其是大对象的内存分配，不连续的内存空间的工作效率要低于连续的空间。
从概念上来讲，标记-清除算法使用的方法是最简单的，只需要忽略这些对象便可以了。也就是说当标记阶段完成之后，未被访问到的对象所在的空间都会被认为是空闲的，可以用来创建新的对象。这种方法需要使用一个空闲列表来记录所有的空闲区域以及大小。对空闲列表的管理会增加分配对象时的工作量。这种方法还有一个缺陷就是——虽然空闲区域的大小是足够的，但却可能没有一个单一区域能够满足这次分配所需的大小，因此本次分配还是会失败（在Java中就是一次 OutOfMemoryError）。
标记-清除算法采用从根集合（GC Roots）进行扫描，对存活的对象进行标记，标记完毕后，再扫描整个空间中未被标记的对象，进行回收，如下图所示。标记-清除算法不需要进行对象的移动，只需对不存活的对象进行处理，在存活对象比较多的情况下极为高效，但由于标记-清除算法直接回收不存活的对象，因此会造成内存碎片。
存在的问题
- 效率问题，标记和清除两个过程的效率都不高。
- 空间问题，标记清除之后会产生大量不连续的内存碎片，导致以后分配较大对象时内存不足以至于不得不提前触发另一次垃圾收集动作。
复制-整理算法
为了解决标记-清除算法的效率问题，JVM虚拟机提供复制-整理算法
基本思想：将现有的内存空间分为两块，每次只使用其中一块，在垃圾回收时将正在使用的内存中的存活对象复制到未被使用的内存块中，之后，清除正在使用的内存块中的所有对象，交换两个内存的角色，完成垃圾回收。
将现有的内存空间分为两快，每次只使用其中一块，在垃圾回收时将正在使用的内存中的存活对象复制到未被使用的内存块中，之后，清除正在使用的内存块中的所有对象，交换两个内存的角色，完成垃圾回收。如果系统中的垃圾对象很多，复制算法需要复制的存活对象数量并不会太大。因此在真正需要垃圾回收的时刻，复制算法的效率是很高的。又由于对象在垃圾回收过程中统一被复制到新的内存空间中，因此，可确保回收后的内存空间是没有碎片的。该算法的缺点是将系统内存折半。
Java 的新生代串行垃圾回收器中使用了复制算法的思想。新生代分为 eden 空间、from 空间、to 空间 3 个部分。其中 from 空间和 to 空间可以视为用于复制的两块大小相同、地位相等，且可进行角色互换的空间块。from 和 to 空间也称为 survivor 空间，即幸存者空间，用于存放未被回收的对象。在垃圾回收时，eden 空间中的存活对象会被复制到未使用的 survivor 空间中 (假设是 to)，正在使用的 survivor 空间 (假设是 from) 中的年轻对象也会被复制到 to 空间中 (大对象，或者老年对象会直接进入老年带，如果 to 空间已满，则对象也会直接进入老年代)。此时，eden 空间和 from 空间中的剩余对象就是垃圾对象，可以直接清空，to 空间则存放此次回收后的存活对象。这种改进的复制算法既保证了空间的连续性，又避免了大量的内存空间浪费。
标记-复制算法与标记-整理算法非常类似，它们都会将所有存活对象重新进行分配。区别在于重新分配的目标地址不同，复制算法是为存活对象分配了另外的内存 区域作为它们的新家。标记复制算法的优点在于标记阶段和复制阶段可以同时进行。它的缺点是需要一块能容纳下所有存活对象的额外的内存空间。
复制算法的提出是为了克服句柄的开销和解决内存碎片的问题。它开始时把堆分成 一个对象 面和多个空闲面， 程序从对象面为对象分配空间，当对象满了，基于copying算法的垃圾 收集就从根集合（GC Roots）中扫描活动对象，并将每个 活动对象复制到空闲面(使得活动对象所占的内存之间没有空闲洞)，这样空闲面变成了对象面，原来的对象面变成了空闲面，程序会在新的对象面中分配内存。
存在的问题
- 内存缩小为原来的一半，内存的利用率太低。
- 在内存存活率较高时就要进行较多的复制操作，复制的效率会变低
标记-整理算法
复制收集算法在对象存活率较高时就要进行较多的复制操作，效率将会变低。更关键的是，如果不想浪费50%的空间，就需要有额外的空间进行分配担保，以应对被使用的内存中所有对象都100%存活的极端情况，所以在老年代一般不能直接选用这种算法。
基本思想：标记过程仍然与“标记-清除”算法一样，但后续步骤不是直接对可回收对象进行清理，而是让所有存活的对象都向一端移动，然后直接清理掉端边界以外的内存，“标记-整理”算法的示意图如下图所示。
复制算法的高效性是建立在存活对象少、垃圾对象多的前提下的。这种情况在年轻代经常发生，但是在老年代更常见的情况是大部分对象都是存活对象。如果依然使用复制算法，由于存活的对象较多，复制的成本也将很高。
标记-整理算法是一种老年代的回收算法，它在标记-清除算法的基础上做了一些优化。也首先需要从根节点开始对所有可达对象做一次标记，但之后，它并不简单地 清理未标记的对象，而是将所有的存活对象压缩到内存的一端。之后，清理边界外所有的空间。这种方法既避免了碎片的产生，又不需要两块相同的内存空间，因此，其性价比比较高。
标记-整理算法修复了标记-清除算法的短板——它将所有标记的也就是存活的对象都移动到内存区域的开始位置。这种方法的缺点就是GC暂停的时间会增 长，因为你需要将所有的对象都拷贝到一个新的地方，还得更新它们的引用地址。相对于标记-清除算法，它的优点也是显而易见的——经过整理之后，新对象的分 配只需要通过指针碰撞便能完成（pointer bumping），相当简单。使用这种方法空闲区域的位置是始终可知的，也不会再有碎片的问题了。
标记-整理算法采用标记-清除算法一样的方式进行对象的标记，但在清除时不同，在回收不存活的对象占用的空间后，会将所有的存活对象往左端空闲空间移动，并更新对应的指针。标记-整理算法是在标记-清除算法的基础上，又进行了对象的移动，因此成本更高，但是却解决了内存碎片的问题。具体流程见下图：
增量回收算法
在垃圾回收过程中，应用软件将处于一种 CPU 消耗很高的状态。在这种 CPU 消耗很高的状态下，应用程序所有的线程都会挂起，暂停一切正常的工作，等待垃圾回收的完成。如果垃圾回收时间过长，应用程序会被挂起很久，将严重影响用户体验或者系统的稳定性。
增量算法现代垃圾回收的一个前身，其基本思想是，如果一次性将所有的垃圾进行处理，需要造成系统长时间的停顿，那么就可以让垃圾收集线程和应用程序线程交替执行。每次，垃圾收集线程只收集一小片区域的内存空间，接着切换到应用程序线程。依次反复，直到垃圾收集完成。使用这种方式，由于在垃圾回收过程中，间断性地还执行了应用程序代码，所以能减少系统的停顿时间。但是，因为线程切换和上下文转换的消耗，会使得垃圾回收的总体成本上升，造成系统吞吐量的下降。
并发回收算法
所谓的并发回收算法即是指垃圾回收器与应用程序能够交替工作，并发回收 器其实也会暂停，但是时间非常短，它并不会在从开始回收寻找、标记、清楚、压缩或拷贝等方式过程完全暂停服务，它发现有几个时间比较长，一个就是标记，因 为这个回收一般面对的是老年代，这个区域一般很大，而一般来说绝大部分对象应该是活着的，所以标记时间很长，还有一个时间是压缩，但是压缩并不一定非要每 一次做完GC都去压缩的，而拷贝呢一般不会用在老年代，所以暂时不考虑；所以他们想出来的办法就是：第一次短暂停机是将所有对象的根指针找到，这个非常容 易找到，而且非常快速，找到后，此时GC开始从这些根节点标记活着的节点（这里可以采用并行），然后待标记完成后，此时可能有新的 内存申请以及被抛弃（java本身没有内存释放这一概念），此时JVM会记录下这个过程中的增量信息，而对于老年代来说，必须要经过多次在 survivor倒腾后才会进入老年代，所以它在这段时间增量一般来说会非常少，而且它被释放的概率前面也说并不大（JVM如果不是完全做Cache，自 己做pageCache而且发生概率不大不小的pageout和pagein是不适合的）；JVM根据这些增量信息快速标记出内部的节点，也是非常快速 的，就可以开始回收了，由于需要杀掉的节点并不多，所以这个过程也非常快，压缩在一定时间后会专门做一次操作，有关暂停时间在Hotspot版本，也就是 SUN的jdk中都是可以配置的，当在指定时间范围内无法回收时，JVM将会对相应尺寸进行调整，如果你不想让它调整，在设置各个区域的大小时，就使用定 量，而不要使用比例来控制；当采用并发回收算法的时候，一般对于老年代区域，不会等待内存小于10%左右的时候才会发起回收，因为并发回收是允许在回收的 时候被分配，那样就有可能来不及了，所以并发回收的时候，JVM可能会在68%左右的时候就开始启动对老年代GC了。
分代收集算法
分代回收器是增量收集的另一个化身，根据垃圾回收对象的特性，不同阶段最优的方式是使用合适的算法用于本阶段的垃圾回收，分代算法即是基于这种思想，它将内存区间根据对象的特点分成几块，根据 每块内存区间的特点，使用不同的回收算法，以提高垃圾回收的效率。以 Hot Spot 虚拟机为例，它将所有的新建对象都放入称为年轻代的内存区域，年轻代的特点是对象会很快回收，因此，在年轻代就选择效率较高的复制算法。当一个对象经过几 次回收后依然存活，对象就会被放入称为老生代的内存空间。在老生代中，几乎所有的对象都是经过几次垃圾回收后依然得以幸存的。因此，可以认为这些对象在一 段时期内，甚至在应用程序的整个生命周期中，将是常驻内存的。如果依然使用复制算法回收老生代，将需要复制大量对象。再加上老生代的回收性价比也要低于新 生代，因此这种做法也是不可取的。根据分代的思想，可以对老年代的回收使用与新生代不同的标记-压缩算法，以提高垃圾回收效率。
分代收集算法是目前大部分JVM的垃圾收集器采用的算法。它的核心思想是根据对象存活的生命周期将内存划分为若干个不同的区域。一般情况下将堆区划分为老年代（Tenured Generation）和新生代（Young Generation），在堆区之外还有一个代就是永久代（Permanet Generation）。老年代的特点是每次垃圾收集时只有少量对象需要被回收，而新生代的特点是每次垃圾回收时都有大量的对象需要被回收，那么就可以根据不同代的特点采取最适合的收集算法。
年轻代（Young Generation）的回收算法
所有新生成的对象首先都是放在年轻代的。年轻代的目标就是尽可能快速的收集掉那些生命周期短的对象。
新生代内存按照8:1:1的比例分为一个eden区和两个survivor(survivor0,survivor1)区。一个Eden区，两个 Survivor区(一般而言)。大部分对象在Eden区中生成。回收时先将eden区存活对象复制到一个survivor0区，然后清空eden区，当这个survivor0区也存放满了时，则将eden区和survivor0区存活对象复制到另一个survivor1区，然后清空eden和这个survivor0区，此时survivor0区是空的，然后将survivor0区和survivor1区交换，即保持survivor1区为空， 如此往复。
当survivor1区不足以存放 eden和survivor0的存活对象时，就将存活对象直接存放到老年代。若是老年代也满了就会触发一次Full GC，也就是新生代、老年代都进行回收。
新生代发生的GC也叫做Minor GC，MinorGC发生频率比较高(不一定等Eden区满了才触发)。
老年代（Old Generation）的回收算法
在年轻代中经历了N次垃圾回收后仍然存活的对象，就会被放到年老代中。因此，可以认为年老代中存放的都是一些生命周期较长的对象。
内存比新生代也大很多(大概比例是1:2)，当老年代内存满时触发Major GC即Full GC，Full GC发生频率比较低，老年代对象存活时间比较长，存活率标记高
持久代（Permanent Generation）的回收算法
用于存放静态文件，如Java类、方法等。持久代对垃圾回收没有显著影响，但是有些应用可能动态生成或者调用一些class，例如Hibernate 等，在这种时候需要设置一个比较大的持久代空间来存放这些运行过程中新增的类。持久代也称方法区。