垃圾收集篇

垃圾收集算法

垃圾的概念

  在运行的程序中，当一个对象没有任何指针指向它时，它就会被视为垃圾。所以，判断一个对象是否被视为垃圾的关键标准就是是否由指针指向它。
进行垃圾回收有两个好处：
  1、释放内存，防止oom的发生。
  2、规整内存，提高内存的使用率。垃圾回收后，会出现零散的空位，这时候进行规整，可以得到一块连续的存储空间。

对象存活的判断

引用计数器法

  引用计数器法比较简单，每个对象保存一个整形的引用计数器属性，用于记录对象被引用的次数，只要有任何一个对象引用了该对象，该对象的引用计数器就加一，当引用失效后，引用计数器就减一，当该对象的引用计数器为0时，就表明该对象不再被引用，可以进行回收了。使用引用计数器比较简单，但是有三个缺点：
  1、每个对象需要单独的字段存储计数器，增加了空间开销。
  2、每次操作都需要增加对象的计数器，增加了时间开销。
  3、无法处理循环问题，对象A引用了对象B，对象B也引用了对象A，则这两个对象永远无法被回收。

可达性分析算法

  可达性分析算法以GC Root为起点，从上至下，找到被根对象所连接的目标对象，但是如果目标没有在引用链上，则表示对象时不可达的，这些对象也就被视为垃圾对象。GC Root 有多个，他们组成了 GC Roots，作为GC Roots 的对象引用包括下面几种类型：
  1、虚拟机栈中对象的引用，比如方法中的局部变量。
  2、本地方法栈中对象的引用。
  3、方法区中引用数据类型的静态变量。
  4、方法区中常量的引用，比如字符串常量池中的引用。
  5、被同步锁持有对象的引用
  6、jvm内部的引用，比如基本类型对应的Class对象引用，一些常驻的异常对象引用，系统类加载器对象应用。

算法

下面总结一下jvm中常用的三种算法：

标记清除算法

  标记清除算法是非常基础的一种算法。当堆中有效的内存空间被耗尽的时候，就会停止程序，然后进行两项工作：
  1、标记：使用可达性分析算法，从根节点开始遍历，标记所有被引用的对象。
  2、清除：垃圾收集器再次进行遍历，如果发现某个对象不可达，则将其回收掉。

  标记清除算法的优点是简单、且不需要移动对象，但缺点是在进行GC时，需要停止整个应用程序，且清理出来的内存是不连续的，会产生内存碎片。且该方式并不是真正的清除不可达的对象，而是将要被清除的对象地址保存在空闲的列表中，新对象申请内存时，判断某块内存是否充足，如果充足的话，就将新对象覆盖原来标记为垃圾的对象，从而实现内存的重复利用，但是如果是大对象申请时，需要花费更多时间去寻找合适的位置，甚至失败，所以标记清除算法效率不高，且部分内存碎片无法重复利用。

复制算法

  复制算法的核心思想是将空闲的内存空间分为两块，但每次只使用其中的一块，在垃圾回收时将正在使用的内存中的存活对象复制到未被使用的内存块中，然后在清除正在使用内存块中的对象，两块内存交替使用，从而完成垃圾对象的回收。
  虽然复制算法不需要进行标记，也可以保证内存的连续性，但该算法需要双倍的内存，而且需要移动对象，这就意味着需要更改对象的引用地址。如果内存中存活的对象很多，该复制算法不会很理想，因为需要复制对象的数量变大，使垃圾回收器运行效率变低。综上所述，复制算法更适用于新生代。

标记压缩算法

  在老年代中，更多的对象是存活的，不太适合使用复制算法，但可以使用标记压缩算法，它是基于标记清除算法的演进，执行流程主要分为三步：
  1、从根节点标记被引用的对象，这点和标记清除算法一致。
  2、将所有存活对象压缩到一端，按顺序排放。
  3、清除边界外的所有空间。
  其优点是避免了内存碎片，缺点是因为需要移动对象，所以需要修改对象引用地址。

垃圾收集的相关概念

STW

  在垃圾回收过程中，整个应用程序都会被暂停，没有任何响应，所以被称为Stop The World，简称为 STW。
  可达性分析算法在枚举根节点时，会造成STW，原因是如果分析过程中出现对象引用关系的变化，无法导致分析结果的准确性，当GC完成之后，STW也会停止，且STW与垃圾收集器没有关系，任何垃圾回收器都会都会发生STW。

安全点

  上面说到，垃圾回收过程中会进行STW，但是在垃圾回收时，并不是任何位置都适合停顿下来进行GC的，只有特定的位置才能停顿下来进行GC，这些位置被称为安全点（Safe Point）。
  安全点如果过少，会导致GC等待的时间过长，但是安全点太多会导致性能问题，一些常见的安全点包括：循环的结尾、方法返回前、调用方法之后、异常抛出的位置。
  当发生GC时，保证程序的线程落在安全点有两种方式：
  1、抢先式中断：GC中断所有线程，如果发现某些线程不在安全点，就重新恢复该线程，直到它跑到安全点，在进行停止。因为这种方式是GC主导位置的，导致应用程序并不是主角，所以几乎所有的虚拟机都不选择这种方式。
  2、主动式中断：GC线程给自己设置一个标志位，各个应用线程运行到安全点来查询这个标志，如果此时的GC线程的中断标志为真，则将自己中断挂起，这种方式的好处是由应用线程主动发起中断，不会被迫出现在非安全点位置中断的情况。

安全区域

  当某些线程被阻塞了，无法走到安全点，也就无法响应jvm的中断请求，为了解决这个问题，引入了安全区域的概念。
  安全区域指的是在一段代码片段中，对象的引用关系不会发生变化，在这个区域中的任何位置开始GC都是安全的。
  线程对于安全区域的处理如下：
  1、当线程走到安全区域的代码时，首先已经标识进入了安全区域，如果这段时间内发生GC，jvm会忽略在安全区域的线程，忽略的意思是说如果除了在安全区域内的其他线程到达了安全点，就可以进行GC了。
  2、当线程离开安全区域，会检查jvm是否已经完成了GC，如果完成了则继续执行，否则就阻塞，直到GC完成之后才继续执行。
  从JVM角度出发，安全区域是放大了的安全点，都是可以进行GC的位置。但是从应用线程来看，这两个位置本质不同，安全点是应用线程自己挂起自己的地方，安全区域是应用线程无需挂起的地方（只是在出安全区域的时候才会挂起）

垃圾收集器

  上面讲的找到垃圾的算法是垃圾回收算法的基础，垃圾回收算法又是垃圾收集器的基础。下面来总结一下垃圾收集器。

重要指标

  对于垃圾收集器来说，有两个重要的指标，一个是吞吐量，一个是停顿时间。

吞吐量

  吞吐量是CPU用于运行用户代码的时间与CPU总消耗时间的比值，即吞吐量=运行用户代码时间/（运行用户代码时间+垃圾收集时间）。比如垃圾回收了2次，每次200ms，CPU总耗时是6000ms，则吞吐量=（6000-400）/6000=93.33%。

停顿时间

  停顿时间是指一个时间段内应用线程暂停，只让垃圾收集线程执行的时间。比如下图中，每次垃圾回收停顿100ms，总共停顿5次，一共500ms，虽然和上图比总的停顿时间变长了，但是每次停顿的时间减少了，整体看，应用程序的延迟是比较低的。但此时程序的吞吐量=（6000-500）/6000=91.67%。

  综上所述，高吞吐量和低停顿时间不能同时满足。如果选择吞吐量优先，那么就需要降低内存回收的次数，这样会导致垃圾收集需要更长的时间，用户的体验感会下降。如果以低停顿时间优先，每次停顿时间降低了，但回收次数变多了，就会引起吞吐量的下降。

垃圾收集器的分类

  根据垃圾收集器工作的内存区间不同，可以分为新生代垃圾收集器，老年代垃圾收集器和整堆垃圾收集器。
  新生代垃圾收集器：Serial、ParNew、Parallel Scavenge
  老年代垃圾收集器：Serial Old、Parallel Old、CMS
  整堆垃圾收集器：G1

  按照线程工作方式划分，也可以划分为三种：
  串行收集器：Serial、Serial Old
  并行收集器：ParaNew、Parallel Scavenge、Parallel Old
  并发收集器：CMS、G1

  串行垃圾收集器是指单线程收集垃圾，即使会存在多个cpu可用，但也只能用一个cpu进行垃圾回收。
  并行收集器是指多个垃圾收集线程并行工作，当存在多个cpu可用时，并行垃圾回收器就会使用多个cpu进行回收。
  并发收集器是指用户线程和垃圾收集线程“同时”进行，也就是可能存在交替执行的状况，当有多个cpu或者存在多个cpu核的情况时，用户线程和垃圾收集线程就会并行执行。虽然叫并发收集器，但是还是可能会存在并行的情况。

Serial 收集器：串行回收

  Serial 收集器时是新生代的垃圾收集器，采用的是复制算法、串行回收。此外，Serial 还提供了老年代的垃圾收集器 Serial Old 收集器，它采用的是标记压缩算法，并且它还是CMS收集器的备用方案（下文会说到）。该收集器已经几乎不存在了，因为它是串行，所以一般会用在单核CPU的环境下。

ParNew 收集器：并行回收

  ParNew就是Serial的多线程版本，除了采用多线程进行回收之外，它和Serial 没有任何区别。
在多CPU的情况下，ParNew 的效率高于Serial，但是在单线程情况下，Serial的效率会更高一些，因为此时减少了线程切换的开销。

Parallel Scavenge 收集器：吞吐量优先

  Parallel Scavenge 收集器也采用了并行回收、复制算法的机制，但是他和ParNew的区别在于他拥有自适应调节策略，他支持动态的调整参数以提供最合适的停顿时间或最大的吞吐量。并且它是jdk8的默认收集器。
  在吞吐量优先的业务中，Parallel Scavenge（新生代） 和 Parallel Old（老年代）收集器组合使用，可以达到不错的回收性能。

CMS收集器：低延迟

  CMS是一款并发收集器（不是并行），可以让垃圾收集线程和用户线程同时工作。它更关注的是如何在垃圾回收时，用户线程的停顿时间变短，可以为用户提供良好的体验。
CMS的工作原理主要分为4个步骤：
  1、初始标记。第一步就是利用可达性分析算法，找出所有的GC Roots直接关联的对象，为了一次性找齐全，需要进行STW，等找完之后就会恢复用户线程。
  2、并发标记。上一步是找到了GC Roots直接关联的对象，这一步是沿着链继续查找所有的关联对象，该步骤不需要STW，可以和用户线程并发进行。因为它和用户线程并发进行的，也就会导致找到的对象不是很准确，可能标记了一个对象为非垃圾对象，因为此时用户线程正在使用该对象；然后该对象没有引用了，变成了垃圾对象，但是在CMS看来，该对象还是存活状态的，可以理解为此时的并发标记是一次快照。但是如果一次性找正确，为啥不进行STW呢，第三部解释了原因。
  3、重新标记。为了解决上述并发标记的问题，CMS在此阶段需要重新标记引用不正确的对象。但是为了防止此阶段再次出现引用不正确的现象，需要进行STW。可以看出CMS在此处选择STW还是很有道理的，因为此时引用不正确的对象肯定小于第二步并发标记的对象，所以选择在此步骤进行STW，不在第二步STW，提高了用户体验感。
  4、并发清除。清除标记为死亡状态的对象，可以和用户线程并发进行。但是在清除的阶段还是会产生浮动垃圾。
  因为CMS在并发标记和并发清除两个阶段不需要STW，所以停顿时间相对较短，但是它也存在一定的缺点：
  1、会产生内存碎片。因为CMS是基于标记-清除算法的，所以会产生内存碎片，遇到分配大对象的情况时，需要提前进行Full GC。
  2、产生浮动垃圾。在并发标记和并发清除阶段，因为是和用户线程并发进行的，所以用户线程还是会产生浮动垃圾，产生的这些垃圾只能等到下次GC再进行清除。
  3、对CPU比较敏感。因为它是和用户线程并发进行，会在一定程度上影响用户线程的吞吐量。
  4、如果在并发清除阶段，用户线程的内存不足，就会采用备用方案，启动Serial Old收集器进行一次Full GC。

G1 收集器：区域化分代

  G1（Garbage first）收集器是一款基于并发和并行的垃圾收集器，它把堆分割成很多个大小相等的区域（region），一般大小控制在1～32M，为2的N次幂。每个区域可能是老年代也可能是新生代。所以它和传统的收集器不同，并不是直接将堆划分为新生代和老年代两部分。

  如上图所示，每个region都可能是Eden、S、Old区，除此之外，G1中还存在Humongous区域，大小一般超过region的1.5倍，设置H区的原因是防止因region区放不下大对象而提前进行Full GC。它和CMS不同的是，每一个region区域进行分配对象的方式为指针碰撞，而CMS为引用列表的方式。这也说明了G1收集器不会产生内存碎片。
  它可以根据每个region区域被回收后释放的大小和所需时间来决定优先回收哪个，所以叫做Garbage first。
它的回收流程如下：
一、新生代GC。
  jvm启动时，不断的创建Eden区，然后将存活的对象放入到Eden区中，当Eden区耗尽时，会进行一次GC，然后回收Eden和S区。
  GC过程如下：
  1、扫描根。找到GC Roots直接关联的对象。
  2、更新Rset。Rset指的是如果一个region 引用其他region中对象，就在当前region中记录一个集合，用于存放相关引用对象所在的region。
  3、处理Rset。如果年轻代的对象被老年代引用，则这些对象属于是存活对象。
  4、复制对象。将存活的对象复制到S区，然后年龄加一，如果达到了年龄的阈值，就复制到Old区。
  5、处理引用。主要处理的是一些软引用、弱引用，最终Eden中的数据为空，此时目标内存中的数据都是连续的，没有产生内存碎片。
二、并发标记。
  上述主要进行了年轻代的GC，这次主要处理老年代。
  1、初始标记阶段：标记根节点可达的对象，此阶段会进行STW。
  2、根区域扫描。找到S区中直接引用的Old区中的对象，并进行标记。
  3、并发标记。在整个堆中进行并发标记找到存活的对象，该过程和用户线程是并发执行的。如果在此阶段发现有的region区域全是垃圾，则直接进行回收。
  4、再次标记。此阶段会进行STW，和CMS的重新标记一样。
  5、独占清理。此阶段不进行回收，只是找出可以混合回收的区域（一个region可以回收一部分的区域。）
  6、并发清理。此阶段找到完全空闲的区域，并进行清除。
三、混合回收。
  并发标记结束后，只会清除老年代中百分百为垃圾的区域，上面的第5步还会存在一些混合区域。于是此阶段会进行回收一部分老年代+一部分年轻代，回收过程和新生代GC过程一致。