JVM(6)——详解标记-清除算法

核心思想

标记-清除算法如其名，整个过程分为两个明确的阶段：

1. 标记阶段： 遍历所有可达对象（从 GC Roots 开始），标记它们为“存活”。

2. 清除阶段： 遍历整个堆内存，回收所有未被标记为“存活”的对象所占用的空间。

算法步骤详解

1. 暂停应用程序线程：

   • 垃圾回收过程通常需要暂停所有应用程序线程，这被称为 “Stop-The-World” 停顿。这是为了确保在标记过程中对象引用关系不会发生变化，保证垃圾回收的正确性。标记-清除算法的 STW 时间主要发生在标记阶段（也可能在清除阶段）。

2. 标记阶段：

   • 起点： 从一组称为 “GC Roots” 的根对象开始。GC Roots 通常包括：

     • 虚拟机栈（栈帧中的局部变量表）中引用的对象。

     • 方法区中类静态属性引用的对象。

     • 方法区中常量引用的对象（如字符串常量池里的引用）。

     • 本地方法栈中 JNI（即 Native 方法）引用的对象。

     • 所有被同步锁持有的对象。

     • JVM 内部引用（如系统类加载器、基本类型对应的 Class 对象）。

   • 遍历： 以 GC Roots 为起点，通过引用链进行遍历。可以使用深度优先搜索或广度优先搜索。

     • 访问一个对象。

     • 将其标记为“存活”（通常是在对象头中设置一个标记位）。

     • 递归地访问并标记这个对象引用的所有其他对象。

   • 结果： 所有从 GC Roots 可达的对象都会被标记为“存活”。而无法从任何 GC Roots 访问到的对象，则被认为是“垃圾”。

3. 清除阶段：

   • 遍历堆： 线性（或按某种顺序）遍历整个堆内存的地址空间。

   • 回收垃圾： 对于堆中的每一个位置（或对象）：

     • 如果该位置的对象未被标记为存活，则认为它是垃圾。

     • 回收该对象占用的内存空间。回收通常不是立即“擦除”数据，而是将这个空间记录到一个空闲列表中，供后续新对象分配使用。

   • 重置标记： 在清除阶段结束前（或下一次 GC 开始时），需要将所有存活对象的标记位清除（复位），为下一次垃圾回收做准备。

关键特点与优缺点

• 优点：

  • 概念简单，易于理解： 算法流程非常直观。

  • 实现相对容易： 早期的垃圾收集器常采用此算法。

  • 无对象移动开销： 在清除阶段，存活对象的位置没有发生移动。这对于大对象或存活时间长的对象（如老年代对象）来说是个优势，避免了复制带来的开销。

  • 空间利用率（理论上）： 回收的内存可以立即放入空闲列表供分配。

• 缺点：

  • 内存碎片： 这是标记-清除算法最严重的问题。

    • 清除阶段回收的内存空间散布在堆的各个角落。

    • 这些空闲内存块大小不一，且彼此不连续。

    • 当需要为新对象分配一块连续的较大内存空间时，即使总的空闲内存足够，也可能因为找不到足够大的连续空间而触发另一次垃圾回收，甚至导致 OutOfMemoryError。

  • 效率问题：

    • 标记阶段需要遍历所有存活对象，清除阶段需要遍历整个堆（包括存活对象和垃圾对象）。对于大堆，这两个遍历过程都可能比较耗时，导致较长的 STW 停顿时间。

    • 效率通常与存活对象的数量（标记阶段）和堆的总大小（清除阶段）成正比。存活对象越多，堆越大，GC 时间越长。

  • 分配效率： 由于存在内存碎片，分配新对象时需要遍历空闲列表（Free List）来寻找合适大小的空闲块。这比从连续空间（如复制算法中的 To 区）分配要慢。

  • 空间浪费： 碎片本身导致一部分空间无法被有效利用。

应用场景与演变

• 早期应用： 在 JVM 发展初期，标记-清除算法是基础实现。

• 现代收集器中的角色：

  • 纯粹的标记-清除算法在现代 JVM 中很少单独使用，主要因为其碎片问题。

  • CMS 收集器： 其老年代回收的核心部分（称为“并发标记清除”）就是基于标记-清除算法的改进。

    • 初始标记： 短暂 STW，标记从 GC Roots 直接关联的对象。

    • 并发标记： 与应用线程并发执行，遍历对象图进行标记。

    • 重新标记： 短暂 STW，修正并发标记期间因应用线程运行导致引用变化的对象标记。

    • 并发清除： 与应用线程并发执行，回收垃圾对象（基于标记结果）。

    • CMS 的缺点： 仍然会产生内存碎片。为了解决这个问题，CMS 会在一定次数的 Full GC 后（或者碎片达到阈值时），退回到使用 Serial Old 收集器（一种“标记-整理”算法）进行一次带压缩的 Full GC 来整理老年代空间。

  • G1 / ZGC / Shenandoah： 这些现代收集器采用了更复杂的分区（Region）和并发标记技术。它们本质上仍然需要标记阶段来确定存活对象。但在清除/回收阶段，它们采用了不同的策略（如复制、整理到不同的 Region）来避免或显著减少传统标记-清除带来的碎片问题，并实现更低的停顿时间目标。

总结

标记-清除算法是垃圾回收的基础，其核心的“标记可达对象 -> 清除不可达对象”的思想是几乎所有现代垃圾收集器的基石。它的简单性和无移动开销是其优点，但内存碎片和效率问题是其致命弱点。因此，现代 JVM 垃圾收集器要么避免直接使用纯粹的标记-清除（如新生代普遍用复制算法），要么在其基础上进行重大改进（如 CMS 的并发执行、G1/ZGC/Shenandoah 的分区复制/整理）来解决碎片问题并降低停顿时间。