核心思想

標記-整理算法同樣分為兩個主要階段，但第二個階段有所不同：

1. 標記階段：?與標記-清除算法完全一致。遍歷所有可達對象（從 GC Roots 開始），標記它們為“存活”。

2. 整理階段：?不再簡單地清除垃圾對象，而是將所有存活的對象向內存空間的一端（通常是起始地址或結束地址）移動，緊湊排列。移動完成后，邊界之外的內存空間全部被視為空閑空間，可以一次性分配。

算法步驟詳解

1. 暫停應用程序線程：

   • 同樣需要?“Stop-The-World”?停頓，以確保對象引用關系在標記和移動過程中保持穩定。標記-整理算法的 STW 時間通常比標記-清除更長，因為它包含了對象的移動開銷。

2. 標記階段：

   • 起點：?從?GC Roots?開始。

   • 遍歷：?采用深度優先搜索或廣度優先搜索遍歷對象圖。

   • 標記：?將所有從 GC Roots 可達的對象標記為“存活”。結果與標記-清除算法相同。

3. 整理階段：?這是算法的核心改進點。

   • 計算新地址：

     • 遍歷堆內存（通常是線性掃描）。

     • 計算每個存活對象在整理后應該被移動到的新地址。新地址通常是連續的，從堆空間的某一端（如低地址端）開始排列。

     • 一種常見的策略是：維護一個“指針”（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 長的缺點，將標記-整理的思想推向了新的高度，使其能夠應用于對延遲極其敏感的系統中。