百科

在计算机科学中，垃圾回收（英语：Garbage Collection，缩写为GC）是指一种自动的存储器管理机制。当某个程序占用的一部分内存空间不再被这个程序访问时，这个程序会借助垃圾回收算法向操作系统归还这部分内存空间。垃圾回收器可以减轻程序员的负担，也减少程序中的错误。垃圾回收最早起源于LISP语言。目前许多语言如Smalltalk、Java、C#、Go和D语言都支持垃圾回收器。

收集器实现

垃圾回收器有两个基本的原理：
1.考虑某个对象在未来的程序执行中，将不会被访问。
2.回收这些对象所占用的存储器。

引用计数算法

最早的也是最简单的垃圾回收实现方法，这种方法为占用物理空间的对象附加一个计数器，当有其他对象引用这个对象时计数器加一，反之引用解除时减一。这种算法会定期检查尚未被回收的对象的计数器，为零的话则回收其所占物理空间，因为此时的对象已经无法访问。这种方法无法回收循环引用的存储对象。

优点：实现简单，垃圾易于辨识；判定效率高，回收没有延迟性。

缺点：

1. 需要单独的字段存储器，增加了存储空间开销
2. 每次赋值都需要更新计数器，增加了时间开销
3. 无法解决循环引用问题（因此Java并未使用该算法）

循环引用概述

如下图所示，当对象A引用对象B，对象B引用对象C，而对象C则引用对象A时，此时A，B，C三个对象就形成了循环引用关系

当Root对象不在引用对象A时，此时A，B，C三个对象本应该作为垃圾进行回收，但因为循环引用的原因，他们的引用计数器并未归零，所以无法被作为垃圾回收

如何解决循环引用：

1. 手动解除
2. 使用强弱引用

可达性分析算法

对于引用计数算法而言，可达性分析算法不仅同样具备实现简单和执行效率高效等特点，更重要的时该算法可以有效的解决在引用计数算法中的循环引用问题，防止内存泄露的发生

基本思路：

1. 可达性分析算法是以根对象集合（GC Roots）为起点，按照从上至下的方式搜索被根对象集合所连接的目标对象是否可达
2. 使用可达分析算法后，内存中的存活对象都会被根对象集合直接或间接连接着，搜索所走过的路径称为引用链（Reference Chain）
3. 如果目标对象没有和任何引用链相连，则被视为是不可达的，就意味着该对象已经死亡，可以标记为垃圾对象
4. 在可达性分析算法中，只有能够被根对象集合直接或间接连接的对象才是存活对象

如上图所示，object1~object4对GC Root都是可达的，说明不可被回收，object5和object6对GC Root节点不可达，说明其可以被回收。

GC Roots

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

• 虚拟机栈（栈帧中的局部变量表）中引用的对象
• 本地方法栈内JNI（本地放法）引用的对象
• 方法区中静态属性引用的对象
• 方法去中常量引用的对象
• 所有被同步锁synchronized持有的对象
• Java虚拟机内部的引用（基本数据类型对应的Class对象，一些常驻异常对象，系统类加载器等）
• 反应Java虚拟机内部情况的JMXBean，JVMTI中注册的回调，本地代码缓存等

回收算法

当成功区分内存中的存活对象和死亡对象后，GC 接下来的任务就是执行垃圾回收，释放掉无用的对象所占用的内存空间，以便有足够的可用的内存空间为新对象分配内存

目前在JVM中比较常见的三种垃圾收集算法是标记-清除算法（Mark-Sweep），复制算法（Copying），标记-压缩算法（Mark-Compact）

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

标记-清除算法（Mark-Sweep）是一种非常常见的垃圾收集算法，该算法被J.McMcarthy等人在1960年提出并应用于Lisp语言

执行过程

当堆中的有效内存空间（available memory）被耗尽时，就会停止整个程序（也被称为为stop the world），然后进行两项工作，第一项是标记，第二项则是清除。

• 标记：Collector从引用根节点（GC Roots）开始遍历，标记所有被引用的对象。一般是在对象的Header中记录为可达对象。
• 清除：Collector对堆内存从头到尾进行线性遍历，如果发现某个对象在其Header中没有标记为可达对象，则将其回收

缺点：

• 两次遍历扫描，效率不高
• 在进行GC时，需要停止整个应用程序，导致用户体验差
• 清理后产生的空间内存是不连续的，产生内存碎片，需要维护一个空闲列表

注意事项：

• 清除并不是真的将内存置空，而是将需要清除的对象地址保存在空闲的地址列表里，写入新对象时，直接覆盖操作

复制算法（Copying）

为了解决碎片空间的问题，出现了“复制算法”。复制算法的原理是，将内存分成两块，每次申请内存时都使用其中的一块，当内存不够时，将这一块内存中所有存活的复制到另一块上。然后将然后再把已使用的内存整个清理掉。

优点：

• 没有标记和清除过程，实现简单，运行高效
• 复制过去以后能保证空间的连续性，不会出现内存碎片

缺点：

• 需要两倍的内存空间
• 对于G1这种拆分成大量region的GC，复制而不是移动，意味着GC需要维护region之间的对象引用关系
• 复制对象时，如果对象被其他对象引用，则需要调整引用地址

注意事项：

• 当内存中存活对象过多时时，复制算法因为要复制大量的存活对象，所以效率会特别慢，即复制算法适用于存活对象很少的场景，如堆中的新生代

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

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

标记-清除算法的确可以应用于老年代，但是该算法不仅执行效率地下，而且执行完后还会产生内存碎片，所以JVM的设计者需要在此基础上进行该进。标记-压缩算法因此诞生

执行过程：

• 标记：和标记-清除算法一样，从根节点开始标记所有被引用的对象
• 压缩：将所有的存活对象压缩到内存的一端，按顺序排放之后，清理边界外的空间

标记压缩算法的最终效果等同于标记-清除算法执行完成后，再进行一次内存碎片整理

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

标记-压缩算法的存活对象将会被整理，按照内存地址依次排列。这样一来，当我们需要给新对象分配内存空间时，JVM只需要持有一个内存的起始地址即可（采用指针碰撞方式），这比维护一个空闲列表少了许多开销

优点：

• 消除了标记-清除算法中，会产生内存碎片的缺点
• 消除了复制算法需要双倍内存空间的高额代价

缺点：

• 通常情况下，效率低于复制算法
• 移动对象时，如果对象被其他对象引用，则需要调整引用地址
• 移动过程中，需要全程暂停用户应用程序，即：STW

分代收集算法

分代收集算法是根据对象的生命周期，把内存作分代，然后在分配对象的时候，不同生命周期的对象放在不同的代里面，不同的代上使用合适的回收算法进行回收，比方说，新生代里面的对象存活周期一般都比较短，每次垃圾回收的时候都会发现有大量的对象死去，所以新生代可以使用复制算法来完成垃圾收集。而老年代里的对象存活率比较高，所以就采用标记清除或者标记整理进行回收。

基本思路：

• 根据对象的存活周期，把内存分成多个区域，不同区域使用不同的回收算法回收对象。

优点：

• 可以更有效的清除不需要的对象
• 提升了垃圾回收效率

增量收集算法

上述现有的算法，在垃圾回收过程中，应用软件处于一种Stop the world 的状态，在STW状态下，用户线程会被挂起，暂停一切正常工作，等待垃圾回收完成。如果垃圾回收时间过长，将严重影响用户体验和系统稳定性。为了解决这个问题，即对实时垃圾收集算法的直接导致了增量收集（Incermental Collecting）算法的诞生

基本思路：

• 如果一次性将所有垃圾进行处理，需要造成系统长时间停顿，那么就可以让垃圾收集线程和应用程序线程交替执行。每次，垃圾收集线程只收集一小片区域的内存空间，接着切换到用户线程，依次反复，直到垃圾回收完成

优点：

• STW时间短，用户体验更佳

缺点：

• 频繁的线程切换和上下文转换，会使得垃圾回收的总体成本增加，造成系统的吞吐量下降

分区收集算法

一般来说，在相同条件下，堆空间越大，一次GC时所需要的时间就越长，有关GC产生的停顿也越长。为了更好地控制GC产生的停顿时间，将一块大的内存区域分割成多个小块，根据目标的停顿时间，每次合理地回收若干个小区间，而不是整个堆空间，从而减少一次GC所产生的停顿。分代算法将按照对象的生命周期长短划分成两个部分，分区算法将整个堆空间划分成连续的不同小区间。每一个小区间都独立使用，独立回收。这种算法的好处是可以控制一次回收多少个小区间

扩展

内存分配方式

Java堆是被所有线程共享的一块内存区域，主要用于存放对象实例，在堆上为对象分配内存就是把一块大小确定的内存从堆内存中划分出来，将对象放进去。常用的分配方法有指针碰撞和空闲列表两种实现方式。

在上述的垃圾回收算法中，复制算法和标记-压缩算法产生的内存空间是完整的，而标记清除算法产生的内存空间则是不完整的

指针碰撞

适用于堆内存完整的情况，已分配的内存和空闲内存分表在不同的一侧，通过一个指针指向分界点，当需要分配内存时，把指针往空闲的一端移动与对象大小相等的距离即可，用于Serial和ParNew等不会产生内存碎片的垃圾收集器。

空闲列表

适用于堆内存不完整的情况，已分配的内存和空闲内存相互交错，JVM通过维护一张内存列表记录可用的内存块信息，当分配内存时，从列表中找到一个足够大的内存块分配给对象实例，并更新列表上的记录，最常见的使用此方案的垃圾收集器就是CMS。