常见的垃圾回收算法

GC Roots

在Java语言中，GC Roots包括以下几类元素：

1. 虚拟机栈中引用的对象，比如:各个线程被调用的方法中使用到的参数，局部变量等

2. 本地方法栈内JNI(通常说的本地方法)引用的对象

3. 方法区中类静态属性引用的对象，比如:Java类的引用类型静态变量

4. 方法区中常量引用的对象，比如:字符串常量池(String Table)里的引用

5. 所有被同步锁synchronized持有的对象

6. Java虚拟机内部的引用，基本数据类型对应的Class对象，一些常驻的异常对象(如:NullPointerException,OutOfMemoryError),系统类加载器。

7. 反映java虚拟机内部情况的JMXBean,JVMTI中注册的回调，本地代码缓存等

分代收集理论

当代商业虚拟机的垃圾收集器，大多数都遵循“分代收集”的理论进行设计，它建立在两个假说上之上：

• 弱分代假说：绝大多数对象都是朝生夕死。

• 强分代假说：熬过多次垃圾收集过程的对象就越难以消亡。

• （较少）跨代引用假说：跨代引用相对于同代引用来说仅占极少数。

这两个分代假说共同奠定了常用垃圾收集器的一致的设计原则：收集器应该将Java堆划分为不同的区域，然后将回收的对象依据年龄（对象熬过垃圾收集过程的次数）分配到不同的区域之中存储。

• 如果一个区域中大多数对象都是朝生夕死，难以熬过垃圾收集器收集的过程，把它们放到一起，每次回收只关注如何保留少量存活而不是去标记那些大量将被回收的对象，就能以最小的代价回收到大量的空间；

• 如果剩下的是难以消亡的对象，把它们放到一起，就使用较低的频率来回收这个区域；这样就兼顾了垃圾收集的时间开销和内存的空间有效利用。

在Java堆划分不同区域之后，垃圾收集器就可以每次回收其中某些部分的区域——因此，就有了“Minor GC”、“Major GC”、“Full GC”这样的回收类型的划分——才能针对这些不同区域与里面存储对象存亡的特征相匹配的垃圾收集算法——因此，发展出“标记——复制算法”“标记——清除算法”、“标记——整理算法”等针对性的垃圾收集算法。

始于分代收集理论。

分代收集并非只是简单的划分一下内存区域那么容易，它至少存在一个明显的困境：对象不是孤立的，对象之间会存在跨代引用，存在相互引用关系的两个对象，是应该倾向于同时生存或者同时消亡的。

依据这条假说，我们不应该再为少量的跨代引用去扫描整个老年代，也不必浪费空间专门记录每个对象是否存在跨代引用，只需在新生代建立一个全集的数据结构（该结构为“记忆集”，Remembered Set）。

• 标识出老年代哪块内存会存在跨代引用，当发生Minor GC时，只有包含跨代引用的小块内存里的对象才会被加入到GC Roots进行扫描。

分代收集名称定义：

• 部分收集（Partial GC）：指目标是部分收集整个Java堆的垃圾收集，其中又分为：
  • 新生代收集（Minor GC/Young GC）：只是新生代的垃圾收集。
  • 老年代收集（Major GC/Old GC）：只是老年代的垃圾收集。目前只有CMS收集器会有单独收集老年代的行为（可以设置CMSscavenge选项进行开启MinorGC机制）。
  • 混合收集（Mixed GC）：收集整个新生代以及部分老年代的垃圾收集。目前只有G1收集器会有这种行为。
• 整堆收集（Full GC）：收集整个Java堆和方法区的垃圾收集。

垃圾回收算法

JVM中比较常见的三种垃圾收集算法是标记-清除算法(Sweep),复制算法(Copying),标记-压缩算法(Mark-Compact)

标记——清除算法

算法背景

标记-清除算法(Mark-Sweep)是一种最基础和常见的垃圾收集算法，该算法被J.McCarthy等人在1960年提出并应用于Lisp语言，后续的收集算法大多以标记——清除算法为基础，对其缺点进行改进而得到的。

基本思路

算法的基本思路：标记出所有需要回收的对象，标记完成后，统一回收掉所有被标记的对象。

算法结构

该算法分为“ 标记” 和“ 清除” 两个阶段

• 标记阶段：就是会从根节点扫描所有的对象，如果发现某个对象有被引用，就在对象的Header(对象标识为11)中记录为可达对象；

• 清除阶段：对堆内存从头到尾线性遍历，如果发现对象的Header中没有被标记为可达对象，则将其回收。不过需要注意的时，【当执行这两个阶段的工作的时候，需要先把整个程序停止也被称为stop the world,然后再进行这两项工作】。

总体概述

当堆中的有效内存空间(available memory)被耗尽的时候，就会停止整个程序(也被称为stop the world)，然后进行两项工作，第一项则是标记（标记的是非垃圾对象也叫做可达对象），第二项则是清除，当成功区分内存中存活对象和死亡对象后，GC接下来的任务就是执行垃圾回收，释放掉无用对象所占用的内存空间，以便有足够的可用内存空间为新对象分配内存。

主要缺点

1. 执行效率不稳定，当大部分数据需要被回收时，就需要进行大量标记和清除的动作。

2. 内存空间碎片化问题，标记、清除之后会产生大量不连续的内存碎片。

3. 这种方式清理出来的空闲内存是不连续的,产生内存碎片。需要维护一个空闲列表

注意:何为清除?

标记——复制算法【新生代】

算法背景

为了解决标记-清除算法在垃圾收集效率方面的缺陷，M.L.Minsky于1963年发表了著名的论文，“使用双存储区的Lisp语言垃圾收集器CA LISP Garbage Collector Algorithm Using Serial Secondary Storage”。M.L.Minsky在该论文中描述的算法被人们称为复制(Copying)算法，它也被M.L.Minsky本人成功地引入到了Lisp语言的一个实现版本中。

核心思想

将活着的内存空间分为两块，每次只使用其中一块，在垃圾回收时将正在使用的内存中的存活对象复制到未被使用的内存块中，之后清除正在使用的内存块中的所有对象，交换两个内存的角色，最后完成垃圾回收，

把新生代分为一块较大的Eden空间和两块较小的Survivor空间，每次分配内存只使用Eden和其中一块Survivor。当发生垃圾搜索时，将Eden和Survivor中仍存活的对象一次性复制到另一个Survivor上，然后直接清除掉Eden和已用过的那块Survivor空间。

HotSpot虚拟机默认Eden和Survivor的大小比例是8：1，即10%的新生代是会被浪费掉的。当Survivor空间不足以容纳一次Minor GC之后存活的对象时，就需要以来其他内存区域进行分配担保。

原理总结

因为标记-清除算法的效率比较低，所以为了解决这个问题，就出现了复制算法。就是使用双倍的内存空间，然后其中一个内存空间是空的，里面没有存放对象，每次垃圾回收的时候就扫描非空内存空间内的全部对象，如果扫描到的对象有被引用，就复制到那个空的内存空间内，最后把最初的那个非空的内存空间整体回收掉，这样时间效率虽然高，但是空间效率比较低，因为使用了双倍的空间，这是典型的用空间换时间的思想。

这里所谓的清除并不是真的置空,而是把需要清除的对象地址保存在空闲的地址列表里。下次有新对象需要加载时,判断垃圾的位置空间是否够,如果够,就存放。

优点：

1. 实现简单，运行高效。

2. 复制过去以后保证空间的连续性，不会出现”碎片”问题。

缺点：

1. 此算法的缺点也是明显的，就是需要两倍的内存空间，浪费相关的内存

2. 对于G1这种分拆成为大量region的GC，复制而不是移动，意味着GC需要维护region之间对象引用关系，不管是内存占用或者时间开销也不小。

标记——整理算法【老年代】

背景

• 标记-复制算法的高效性是建立在存活对象少，垃圾对象多的前提下的。这种情况在新生代经常发生，但是在老年代，更常见的情况是大部分对象都是存活对象。如果依然使用复制算法，由于存活对象较多，复制的成本也将很高。因此，基于老年代垃圾回收的特性，需要使用其它的算法。

• 标记-清除算法的确可以应用在老年代中，但是该算法不仅执行效率低下，而且在执行完内存回收后还会产生内存碎片，所以JVM的设计者需要在此基础之上进行改进。标记-压缩(Mark-Compact)算法由此诞生。

标记——整理和标记—清除算法一样，从根节点递归标记所有可达的对象，让所有存活的对象都向一端移动，然后直接清理掉端边界以外的内存。

执行过程：

1. 第一阶段和标记-清除算法一样，从根节点开始标记所有被引用对象。

2. 第二阶段将所有的存活对象压缩到内存的一端（通过指针游标进行划分），按顺序排放。

3. 之后，清理便捷外所有的空间。

优点：

1. 清楚了标记-清除算法当中，内存区域分散的缺点，我们需要给新对象分配内存时，JVM只需要持有一个内存的起始地址即可。

   • 可以看到，标记的存活对象将会被整理，按照内存地址一次排列，而未被标记的内存会被清理掉。如此一来，当我们需要给新对象分配内存时，JVM只需要持有一个内存的其实地址即可，这比维护一个空闲列表显然少了许多开销。

2. 消除了复制算法当中，内存减半的高额代价

3. 没有内存碎片

缺点：

1. 从效率上来说，标记-整理算法要低于复制算法

2. 移动对象的同时，如果对象被其它对象引用，则还需要调整引用的地址

3. 移动过程中，需要全程暂停用户应用程序。即：STW（stop the world）执行算法的时候需要先停止整个程序运行

核心原理

当成功区分出内存中存活对象和死亡对象后,GC接下来的任务就是执行垃圾回收,释放掉吴用对象所占用的内存空间,以便有足够的可用内存空间为新对象分配内存。
目前在JVM中比较常见的三种垃圾收集算法是标记-清除算法(Mark-Sweep)、复制算法(Copying)、标记-压缩算法(Mark-Compact)。

就做标记-压缩算法，这个算法的执行过程分为三个阶段，第一阶段的标记阶段和复制算法一样，先从根节点开始标记所有被引用的对象；然后第二阶段是把所有被引用的对象移到内存空间的一端，按顺序排放；第三阶段是清理内存空间的另一端中所有的没有被引用的垃圾对象。

与标记清除的区别

二者的本质差异在于标记-清除算法是一种非移动式的回收算法，标记-压缩是移动式的。是否移动回收后的存活对象是一项优缺点并存的风险决策。

分代算法

根据对象存活周期的不同将内存划分为几块。一般是把Java堆分为新生代和老年代，根据各个年代的特点采用最适当的收集算法。

• 新生代中,每次垃圾收集时都发现有大批对象死去，只有少量存活， 那就选用复制算法， 只需要付出少量存活对象的复制成本就可以完成收集。

• 老年代中因为对象存活率高、没有额外空间对它进行分配担保， 就必须使用“ 标记—清理” 或者“ 标记—整理” 算法来进行回收

分区算法

分代算法将按照对象生命周期长短划分成两部分，而分区算法则是将堆划分成不同小区间，每个区间都独立使用，独立回收，这种算法的好处控制一次回收小区间的数量。

随着计算机算力越来越强，内存也越来越便宜，生产上堆空间可供应用程序支配也越来越多，一般来讲，堆空越大GC回收的时间越长，为了更好的控制GC的时间，将大区域划分成独立小房间，独立管理独立回收，每次垃圾回收合理地回收若干小区间，可以减少GC所产生停顿的时间。