核心思想

標(biāo)記-清除算法如其名，整個(gè)過程分為兩個(gè)明確的階段：

1. 標(biāo)記階段：?遍歷所有可達(dá)對象（從 GC Roots 開始），標(biāo)記它們?yōu)椤按婊睢薄?/p>

2. 清除階段：?遍歷整個(gè)堆內(nèi)存，回收所有未被標(biāo)記為“存活”的對象所占用的空間。

算法步驟詳解

1. 暫停應(yīng)用程序線程：

   • 垃圾回收過程通常需要暫停所有應(yīng)用程序線程，這被稱為?“Stop-The-World”?停頓。這是為了確保在標(biāo)記過程中對象引用關(guān)系不會發(fā)生變化，保證垃圾回收的正確性。標(biāo)記-清除算法的 STW 時(shí)間主要發(fā)生在標(biāo)記階段（也可能在清除階段）。

2. 標(biāo)記階段：

   • 起點(diǎn)：?從一組稱為?“GC Roots”?的根對象開始。GC Roots 通常包括：

     • 虛擬機(jī)棧（棧幀中的局部變量表）中引用的對象。

     • 方法區(qū)中類靜態(tài)屬性引用的對象。

     • 方法區(qū)中常量引用的對象（如字符串常量池里的引用）。

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

     • 所有被同步鎖持有的對象。

     • JVM 內(nèi)部引用（如系統(tǒng)類加載器、基本類型對應(yīng)的 Class 對象）。

   • 遍歷：?以 GC Roots 為起點(diǎn)，通過引用鏈進(jìn)行遍歷?？梢允褂?strong>深度優(yōu)先搜索或廣度優(yōu)先搜索。

     • 訪問一個(gè)對象。

     • 將其標(biāo)記為“存活”（通常是在對象頭中設(shè)置一個(gè)標(biāo)記位）。

     • 遞歸地訪問并標(biāo)記這個(gè)對象引用的所有其他對象。

   • 結(jié)果：?所有從 GC Roots 可達(dá)的對象都會被標(biāo)記為“存活”。而無法從任何 GC Roots 訪問到的對象，則被認(rèn)為是“垃圾”。

3. 清除階段：

   • 遍歷堆：?線性（或按某種順序）遍歷整個(gè)堆內(nèi)存的地址空間。

   • 回收垃圾：?對于堆中的每一個(gè)位置（或?qū)ο?#xff09;：

     • 如果該位置的對象未被標(biāo)記為存活，則認(rèn)為它是垃圾。

     • 回收該對象占用的內(nèi)存空間?；厥胀ǔ２皇橇⒓础安脸睌?shù)據(jù)，而是將這個(gè)空間記錄到一個(gè)空閑列表中，供后續(xù)新對象分配使用。

   • 重置標(biāo)記：?在清除階段結(jié)束前（或下一次 GC 開始時(shí)），需要將所有存活對象的標(biāo)記位清除（復(fù)位），為下一次垃圾回收做準(zhǔn)備。

關(guān)鍵特點(diǎn)與優(yōu)缺點(diǎn)

• 優(yōu)點(diǎn)：

  • 概念簡單，易于理解：?算法流程非常直觀。

  • 實(shí)現(xiàn)相對容易：?早期的垃圾收集器常采用此算法。

  • 無對象移動開銷：?在清除階段，存活對象的位置沒有發(fā)生移動。這對于大對象或存活時(shí)間長的對象（如老年代對象）來說是個(gè)優(yōu)勢，避免了復(fù)制帶來的開銷。

  • 空間利用率（理論上）：?回收的內(nèi)存可以立即放入空閑列表供分配。

• 缺點(diǎn)：

  • 內(nèi)存碎片：?這是標(biāo)記-清除算法最嚴(yán)重的問題。

    • 清除階段回收的內(nèi)存空間散布在堆的各個(gè)角落。

    • 這些空閑內(nèi)存塊大小不一，且彼此不連續(xù)。

    • 當(dāng)需要為新對象分配一塊連續(xù)的較大內(nèi)存空間時(shí)，即使總的空閑內(nèi)存足夠，也可能因?yàn)檎也坏阶銐虼蟮倪B續(xù)空間而觸發(fā)另一次垃圾回收，甚至導(dǎo)致?OutOfMemoryError。

  • 效率問題：

    • 標(biāo)記階段需要遍歷所有存活對象，清除階段需要遍歷整個(gè)堆（包括存活對象和垃圾對象）。對于大堆，這兩個(gè)遍歷過程都可能比較耗時(shí)，導(dǎo)致較長的 STW 停頓時(shí)間。

    • 效率通常與存活對象的數(shù)量（標(biāo)記階段）和堆的總大小（清除階段）成正比。存活對象越多，堆越大，GC 時(shí)間越長。

  • 分配效率：?由于存在內(nèi)存碎片，分配新對象時(shí)需要遍歷空閑列表（Free List）來尋找合適大小的空閑塊。這比從連續(xù)空間（如復(fù)制算法中的 To 區(qū)）分配要慢。

  • 空間浪費(fèi)：?碎片本身導(dǎo)致一部分空間無法被有效利用。

應(yīng)用場景與演變

• 早期應(yīng)用：?在 JVM 發(fā)展初期，標(biāo)記-清除算法是基礎(chǔ)實(shí)現(xiàn)。

• 現(xiàn)代收集器中的角色：

  • 純粹的標(biāo)記-清除算法在現(xiàn)代 JVM 中很少單獨(dú)使用，主要因?yàn)槠渌槠瑔栴}。

  • CMS 收集器：?其老年代回收的核心部分（稱為“并發(fā)標(biāo)記清除”）就是基于標(biāo)記-清除算法的改進(jìn)。

    • 初始標(biāo)記：?短暫 STW，標(biāo)記從 GC Roots 直接關(guān)聯(lián)的對象。

    • 并發(fā)標(biāo)記：?與應(yīng)用線程并發(fā)執(zhí)行，遍歷對象圖進(jìn)行標(biāo)記。

    • 重新標(biāo)記：?短暫 STW，修正并發(fā)標(biāo)記期間因應(yīng)用線程運(yùn)行導(dǎo)致引用變化的對象標(biāo)記。

    • 并發(fā)清除：?與應(yīng)用線程并發(fā)執(zhí)行，回收垃圾對象（基于標(biāo)記結(jié)果）。

    • CMS 的缺點(diǎn)：?仍然會產(chǎn)生內(nèi)存碎片。為了解決這個(gè)問題，CMS 會在一定次數(shù)的 Full GC 后（或者碎片達(dá)到閾值時(shí)），退回到使用 Serial Old 收集器（一種“標(biāo)記-整理”算法）進(jìn)行一次帶壓縮的 Full GC 來整理老年代空間。

  • G1 / ZGC / Shenandoah：?這些現(xiàn)代收集器采用了更復(fù)雜的分區(qū)（Region）和并發(fā)標(biāo)記技術(shù)。它們本質(zhì)上仍然需要標(biāo)記階段來確定存活對象。但在清除/回收階段，它們采用了不同的策略（如復(fù)制、整理到不同的 Region）來避免或顯著減少傳統(tǒng)標(biāo)記-清除帶來的碎片問題，并實(shí)現(xiàn)更低的停頓時(shí)間目標(biāo)。

總結(jié)

標(biāo)記-清除算法是垃圾回收的基礎(chǔ)，其核心的“標(biāo)記可達(dá)對象 -> 清除不可達(dá)對象”的思想是幾乎所有現(xiàn)代垃圾收集器的基石。它的簡單性和無移動開銷是其優(yōu)點(diǎn)，但內(nèi)存碎片和效率問題是其致命弱點(diǎn)。因此，現(xiàn)代 JVM 垃圾收集器要么避免直接使用純粹的標(biāo)記-清除（如新生代普遍用復(fù)制算法），要么在其基礎(chǔ)上進(jìn)行重大改進(jìn)（如 CMS 的并發(fā)執(zhí)行、G1/ZGC/Shenandoah 的分區(qū)復(fù)制/整理）來解決碎片問題并降低停頓時(shí)間。