Java 面试题：Java的垃圾收集算法 --xunznux

标记算法

标记算法（Marking Algorithm）是垃圾收集的核心机制之一，用于在垃圾收集中确定哪些对象是存活的，哪些对象是垃圾。标记算法主要用于 标记-清除 和 标记-整理 等垃圾收集算法中。它的基本目标是从一组根对象（GC Roots）开始，找到所有仍然可达的对象，并将这些对象标记为存活对象。

可达性分析算法

也可以称为 根搜索算法、追踪性垃圾收集。该算法可以有效地解决在引用计数算法中循环引用的问题，防止内存泄漏的发生。
所谓"GCRoots”根集合就是一组必须活跃的引用。
基本思路：

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

标记算法的基本流程：

1. 从 GC Roots 开始：GC Roots 通常包括一些特殊的引用，比如线程栈中的引用、本地方法栈中的引用、类静态属性的引用、常量池中的引用等。标记算法首先从这些 GC Roots 对象出发，开始遍历对象引用图。

2. 可达性分析：标记算法通过可达性分析（Reachability Analysis）遍历对象引用的关系链，找到所有可以通过直接或间接引用从 GC Roots 到达的对象。这些被称为“可达对象”（Reachable Objects），它们被认为是存活的。

3. 标记存活对象：每个在遍历中遇到的对象都会被标记，表示该对象仍然存活。这种标记通常在对象的头部设置一个特殊的标志位或在内存中维护一个标记位图。

4. 结束遍历：当所有可达的对象都被标记完毕后，标记阶段结束。

5. 清除或整理：标记阶段之后，垃圾收集器会进行清理或整理：

   • 标记-清除算法：垃圾收集器会遍历整个堆空间，回收所有未标记的对象（即不可达对象），释放它们占用的内存。
   • 标记-整理算法：垃圾收集器将存活对象移动到堆的一端，形成连续的内存空间，避免内存碎片。

标记算法的特点：

• 准确性：标记算法通过引用关系来判断对象是否存活，避免了将仍被引用的对象错误回收。
• 并发或并行执行：现代垃圾收集器（如 CMS、G1）通常可以在用户线程运行的同时并发执行标记阶段，从而减少垃圾收集对应用的影响。
• 基于可达性：标记算法采用可达性分析，这与过去使用引用计数来判断对象是否存活的做法不同。引用计数容易产生循环引用问题，而标记算法不会有这种问题。

标记算法的局限性：

• 需要暂停应用：传统的标记算法需要Stop The World (STW)，即暂停用户程序执行，以确保对象引用关系在标记过程中的一致性。这种暂停可能会影响应用的性能，尤其在大堆内存的情况下，暂停时间可能很长。
• 内存碎片：在标记-清除算法中，虽然可以有效回收内存，但会产生内存碎片，导致后续的内存分配不够高效。

标记算法的优化：

• 并发标记：一些现代垃圾收集器（如 CMS、G1）通过并发标记的方式，将标记过程与用户程序并发执行，减少应用的停顿时间。
• 增量标记：增量标记是通过将标记过程分割成多个小步骤，分阶段完成，降低了单次垃圾收集的停顿时间，提升了实时性。

结论：

标记算法是垃圾收集过程中判断对象存活与否的关键技术，通过可达性分析确保不回收仍然被引用的对象。现代 JVM 的垃圾收集器针对标记算法进行了大量优化，以减少停顿时间，提升回收效率。

JVM（Java 虚拟机）中的垃圾收集算法主要用于管理堆内存，自动回收不再使用的对象。常见的垃圾收集算法包括：

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

基本原理：

标记阶段：从 GC Roots 开始，进行可达性分析，标记所有存活的对象。
清除阶段：遍历整个堆空间，回收没有被标记的对象，释放其占用的内存。

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

优点：

直接清除不可达的对象，无需移动对象。

缺点：

• 会产生内存碎片，即清除后内存中留下不连续的空闲块，可能导致后续的内存分配不够高效。
• 整个清除过程比较慢，且可能引起长时间的暂停（Stop The World，STW）。

2. 复制算法（Copying）

核心思想

将内存空间分为两块，每次只使用其中一块，在垃圾回收时将正在使用的内存中的存活对象复制到未被使用的内存块中，之后清除正在使用的内存块中的所有对象，交换两个内存的角色，最后完成垃圾回收。
在遍历过程中把可达的对象，直接复制到另外一个区域中复制完成后，A区就没有用了，里面的对象可以直接清除掉，其实里面的新生代里面就用到了复制算法。Survivor 0区和1区。

基本原理：

将堆空间分为两个区域，通常是From 区域和To 区域。每次垃圾收集时，只遍历“From”区域，将存活的对象复制到“To”区域。
未被复制的对象会被认为是垃圾，并直接清除掉。

优点：

• 没有内存碎片，因为存活对象被连续地复制到新区域。（使用可达性分析算法进行遍历）
• 整个过程只涉及存活对象的复制，效率较高。

缺点：

• 需要分配两块内存区域，内存使用效率较低（通常只使用一半的空间）。
• 对于G1这种分拆成为大量region的GC，复制而不是移动，意味着GC需要维护region之间对象引用关系，不管是内存占用或者时间开销也不小。
• 如果系统中的垃圾对象很多，复制算法需要复制的存活对象数量并不会太大，或者说非常低才行（老年代大量的对象存活，那么复制的对象将会有很多，效率会很低）

3. 标记-整理算法（Mark-Compact）

复制算法的高效性是建立在存活对象少、垃圾对象多的前提下的。这种情况在新生代经常发生，但是在老年代，更常见的情况是大部分对象都是存活对象。如果依然使用复制算法，由于存活对象较多，复制的成本也将很高。因此，基于老年代垃圾回收的特性，需要使用其他的算法。
标记-清除算法的确可以应用在老年代中，但是该算法不仅执行效率低下，而且在执行完内存回收后还会产生内存碎片。

基本原理：

• 首先进行标记阶段，和标记-清除算法相同，标记所有存活对象。
• 整理阶段则会将存活对象移到堆的一端，重新整理内存，使得所有存活对象都在一起，剩下的内存成为连续的空闲空间。

优点：

• 没有内存碎片，所有存活对象都集中存储，后续内存分配更高效。
• 消除了复制算法当中，内存减半的高额代价。

缺点：

• 相比标记-清除算法，标记-整理需要进行额外的对象移动，效率稍低。
• 移动对象的同时，如果对象被其他对象引用，则还需要调整引用的地址。（因为对象被移动了）

4. 分代收集算法（Generational GC）

核心思想

分代收集算法，是基于这样一个事实：不同的对象的生命周期是不一样的。因此，不同生命周期的对象可以采取不同的收集方式，以便提高回收效率。一般是把Java堆分为新生代和老年代，这样就可以根据各个年代的特点使用不同的回收算法，以提高垃圾回收的效率。

基本原理：

将堆分为两代：年轻代（Young Generation）和老年代（Old Generation）。

• 年轻代中对象的生命周期通常较短，采用复制算法。大部分对象在年轻代被快速回收。
• 老年代对象存活时间较长，通常使用标记-清除或标记-整理算法来进行回收。

回收机制：

新生代 GC（Minor GC）：针对年轻代进行垃圾收集，通常执行频繁但速度快。
老年代 GC（Major GC / Full GC）：针对老年代进行垃圾收集，通常会触发标记-清除或标记-整理算法，执行较慢。

• 标记阶段的开销与存活对象的数量成正比。
• 清除阶段的开销与所管理区域的大小成正相关。
• 整理阶段的开销与存活对象的数据成正比。

优点：

分代收集通过根据对象的生命周期选择不同的算法，提高了垃圾收集的效率。
新生代的对象大多数会很快成为垃圾，因此采用复制算法可以快速回收。

缺点：

老年代 GC 执行较慢，特别是当需要 Full GC 时，可能会引发长时间的 STW。

5. G1（Garbage First）收集器

基本原理：

G1 将堆划分为多个大小相等的区域（Region），每个区域可以属于年轻代或老年代。然后每个region不同时间代表角色不固定，不过整体分为四种：Eden、Survioor、Old、Humongous（存储大对
象）
通过并发标记的方式，在后台追踪哪些区域中有最多的垃圾。
根据用户设置的最大暂停时间目标，G1 优先清理垃圾最多的区域，避免长时间的暂停。

四个主要阶段：

1. 初始标记阶段
   标记目标：标记所有与 GC Roots 直接关联的对象。
   操作特点：需要STW (Stop The World)，即暂停所有用户线程，短时间内完成标记。
2. 并发标记阶段
   标记过程：与用户程序并发执行，遍历整个堆空间，标记所有存活对象。
   操作特点：在该阶段，垃圾收集器与用户程序同时运行，不需要暂停用户线程。
3. 最终标记阶段
   标记目标：处理并发标记阶段结束后，用户程序执行期间新创建的对象。
   操作特点：需要短暂的 STW 以确保标记的完整性，通常为处理少量新产生的对象。
4. 筛选回收阶段
   回收策略：根据各个 Region 的垃圾比例，对其回收价值进行排序，依据用户设置的期望停顿时间选择性回收。

操作特点：

• 使用标记-复制算法回收对象，即将存活对象复制到新区域。
• 多条垃圾收集线程并发执行，不要求一次性清理所有垃圾区域。
• 该阶段同样需要 STW 来执行具体的回收操作。

G1 的设计目标是通过分阶段回收和控制停顿时间，来达到高效的内存管理与用户程序执行的平衡。

特点：

G1 采用标记-复制算法来清理垃圾，同时避免了大块的内存碎片。
它是为了大堆内存和低停顿设计的，适用于服务器端应用。

优点：

可控制停顿时间，满足应用对响应速度的要求。
并发标记阶段不需要长时间的 STW。

总结：

JVM 中的垃圾收集算法各有优缺点，常见的垃圾收集器（如 Serial、Parallel、CMS、G1）根据不同的垃圾收集算法进行优化，以平衡垃圾收集的效率与应用性能。