JVM(7)——详解标记-整理算法
核心思想
标记-整理算法同样分为两个主要阶段，但第二个阶段有所不同：
-
标记阶段： 与标记-清除算法完全一致。遍历所有可达对象（从 GC Roots 开始），标记它们为“存活”。
-
整理阶段： 不再简单地清除垃圾对象，而是将所有存活的对象向内存空间的一端（通常是起始地址或结束地址）移动，紧凑排列。移动完成后，边界之外的内存空间全部被视为空闲空间，可以一次性分配。
算法步骤详解
-
暂停应用程序线程：
-
同样需要 “Stop-The-World” 停顿，以确保对象引用关系在标记和移动过程中保持稳定。标记-整理算法的 STW 时间通常比标记-清除更长，因为它包含了对象的移动开销。
-
-
标记阶段：
-
起点： 从 GC Roots 开始。
-
遍历： 采用深度优先搜索或广度优先搜索遍历对象图。
-
标记： 将所有从 GC Roots 可达的对象标记为“存活”。结果与标记-清除算法相同。
-
-
整理阶段： 这是算法的核心改进点。
-
计算新地址：
-
遍历堆内存（通常是线性扫描）。
-
计算每个存活对象在整理后应该被移动到的新地址。新地址通常是连续的，从堆空间的某一端（如低地址端）开始排列。
-
一种常见的策略是：维护一个“指针”（
compaction pointer），初始指向目标区域（如堆起始地址）。每遇到一个存活对象，就计算其大小，将该对象的新地址设置为当前指针位置，然后将指针向后移动该对象大小的距离。
-
-
更新引用：
-
由于对象被移动了位置，所有指向这些移动对象的引用（包括 GC Roots 中的引用和存活对象内部字段的引用）都需要被更新为对象的新地址。
-
这一步需要再次遍历对象图（从 GC Roots 开始），访问所有存活对象及其引用，将指向被移动对象的引用值修改为计算好的新地址。
-
关键点： 更新引用必须在对象实际移动之前完成，或者在移动过程中使用特殊的技巧（如 Brooks 指针）来保证引用的正确性。否则，移动对象后，旧的引用就会指向无效地址。
-
-
移动对象：
-
遍历堆内存（通常是线性扫描）。
-
将每个存活对象复制（移动）到其在步骤 1 中计算好的新地址。
-
移动完成后，所有存活对象都被紧密地排列在堆空间的一端（如低地址端）。
-
-
回收空间：
-
移动完成后，从最后一个存活对象之后的位置开始，直到堆空间的另一端（如高地址端），所有内存空间都是连续的空闲空间。
-
这个连续的大块空闲内存可以被一个简单的指针（如
bump pointer）管理，新对象的分配变得极其高效（只需移动指针并清零内存）。
-
-
关键特点与优缺点
-
优点：
-
解决内存碎片： 这是最核心的优势！通过将存活对象紧凑排列，消除了标记-清除算法产生的内存碎片问题。分配新对象时，只需要在连续空闲空间的末尾进行指针碰撞（
bump-the-pointer），分配速度非常快且简单。 -
空间利用率高： 消除了碎片浪费，堆空间得到更有效的利用。特别是对于需要分配大对象的场景，成功率更高。
-
局部性原理提升： 紧凑排列的对象在内存中位置相邻，更有可能被加载到 CPU 缓存同一缓存行（Cache Line）中。这可以提升程序访问对象的效率（缓存命中率提高）。
-
-
缺点：
-
STW 时间更长： 移动对象和更新引用的开销通常比简单的清除操作要大得多。这导致 Stop-The-World 停顿时间通常比标记-清除算法更长，尤其是在堆很大、存活对象很多的情况下。这是标记-整理算法最主要的缺点。
-
移动开销： 复制对象本身需要时间，尤其是对于大对象。
-
更新引用开销： 需要遍历整个对象图来更新所有指向被移动对象的引用，这也是一个耗时的操作。
-
实现更复杂： 需要精确地处理对象移动和引用更新，实现难度高于标记-清除算法。
-
应用场景与演变
-
典型应用：
-
老年代回收： 标记-整理算法因其能有效解决碎片问题，非常适合老年代的垃圾回收。老年代对象的特点是：
-
存活率高（每次GC后大部分对象依然存活）。
-
对象存活时间长。
-
分配频率相对新生代较低。
-
对内存碎片非常敏感（长期运行后碎片累积会导致 Full GC 失败）。
-
-
Serial Old： HotSpot JVM 中的老年代串行收集器就使用标记-整理算法。
-
Parallel Old： HotSpot JVM 中的老年代并行收集器也使用标记-整理算法（多线程并行执行标记和整理）。
-
CMS 的备胎： 当 CMS（Concurrent Mark-Sweep）收集器发生 Concurrent Mode Failure（并发收集跟不上对象分配速度）或 晋升失败（Promotion Failed），或者堆中碎片过多时，CMS 会退回到 Serial Old 收集器（标记-整理）进行一次 Full GC 来整理老年代碎片。
-
-
现代收集器中的优化：
-
G1： 虽然 G1 的目标是可控停顿时间，并且主要使用复制算法在 Region 间转移存活对象，但其在全局层面也可以看作是一种更精细、更智能的标记-整理（通过选择性地回收和整理 Region 来减少碎片）。
-
ZGC / Shenandoah： 这些超低停顿收集器使用极其复杂的并发算法，但它们在回收阶段的核心目标之一也是移动对象进行整理（并发地或部分并发地），以消除碎片。它们通过读屏障等技术来实现并发移动对象和更新引用，极大地减少了 STW 时间（通常缩短到几毫秒级别），克服了传统标记-整理算法 STW 长的最大缺点。
-
与标记-清除算法的对比总结
| 特性 | 标记-清除算法 | 标记-整理算法 |
|---|---|---|
| 核心阶段 | 标记 -> 清除 | 标记 -> 整理（计算地址->更新引用->移动对象） |
| 内存碎片 | 严重，产生大量不连续碎片 | 无，产生连续大块空闲空间 |
| 分配速度 | 慢（需搜索空闲列表） | 极快（指针碰撞） |
| STW 时间 | 相对较短（主要耗时在标记） | 相对较长（标记 + 移动 + 更新引用） |
| 移动对象 | 否 | 是 |
| 空间开销 | 低（只需标记位） | 低（标记位+可能的额外空间记录新地址） |
| 时间开销 | 与存活对象数+堆大小成正比 | 与存活对象数成正比 |
| 局部性 | 差（对象分散） | 好（对象紧凑） |
| 典型场景 | 较少单独使用（如 CMS 的并发清除） | 老年代（Serial Old, Parallel Old） |
总结
标记-整理算法通过引入对象移动和紧凑排列的整理阶段，完美解决了标记-清除算法最致命的内存碎片问题，带来了更高的内存利用率和更快的对象分配速度（指针碰撞）。然而，这种优势是以更长的 Stop-The-World 停顿时间（主要来自移动对象和更新引用）为代价的。
因此，它非常适合对碎片敏感但能容忍较长停顿的老年代垃圾回收。传统的 Serial Old 和 Parallel Old 收集器就是其代表。现代超低停顿收集器（如 ZGC, Shenandoah）通过并发移动和读屏障等革命性技术，极大地克服了 STW 长的缺点，将标记-整理的思想推向了新的高度，使其能够应用于对延迟极其敏感的系统中。