1. 什么是三色標記算法？

三色標記算法 是一種用于標記存活對象 (Marking Live Objects) 的圖遍歷算法。它將堆中的所有對象劃分為三種顏色，以表示其在可達性分析過程中的不同狀態。通過這種顏色標記，垃圾回收器能夠區分出哪些對象是存活的（即不應被回收），哪些是死亡的（即可以被回收的）。

該算法是并發垃圾回收器（如CMS、G1、ZGC、Shenandoah等）能夠與應用程序線程并行工作的基礎。

三種顏色及其含義：

1. 白色 (White)：

   • 表示對象未被訪問過。
   • 在GC開始時，所有對象都是白色的。
   • 在標記階段結束時，仍是白色的對象被視為垃圾對象，將被回收。
   • 可以理解為“待處理”或“已死亡”的對象。

2. 灰色 (Gray)：

   • 表示對象已被訪問過。
   • 但它的一個或多個子對象（它引用的對象）還沒有被完全掃描。
   • 可以理解為“正在處理中”的對象。

3. 黑色 (Black)：

   • 表示對象已被訪問過。
   • 并且它的所有子對象（它引用的對象）也全部被掃描過并標記（要么是灰色，要么是黑色）。
   • 可以理解為“已處理完成”且“確認存活”的對象。

---

2. 基礎三色標記算法流程 (非并發)

為了理解并發場景下的復雜性，我們首先看一個理想化的、非并發（即應用程序停頓）的三色標記過程：

1. 初始化： GC開始時，將所有對象都標記為白色。
2. 根集掃描： 從GC Roots（如虛擬機棧、本地方法棧、方法區中的靜態變量、常量等）開始，遍歷所有直接被GC Roots引用的對象。將這些對象標記為灰色，并放入一個“待處理列表”（通常是一個隊列）。
3. 遍歷：
   • 從“待處理列表”中取出一個灰色對象A。
   • 遍歷A的所有子對象（字段引用）。
   • 如果子對象B是白色的，則將B標記為灰色，并將其加入“待處理列表”。
   • 當A的所有子對象都被掃描完畢（并相應地被標記為灰色或黑色）后，將對象A標記為黑色。
4. 重復： 重復步驟3，直到“待處理列表”為空。
5. 結束： 此時，所有黑色對象都是存活的，所有灰色對象最終都會變成黑色（或在某些特殊情況下，如果其子對象有環，它們自身也會被處理成黑色）。最終，所有仍然是白色的對象即為不可達的垃圾，可以被回收。

---

3. 并發場景下的挑戰：一致性問題

當三色標記算法在GC與應用程序線程并發運行時，事情變得復雜。應用程序線程（也稱為Mutator）可能會修改對象圖，這可能導致兩種基本的一致性問題：

3.1. 漏標 (Missing Live Object) - 最嚴重的問題

定義： 一個明明是存活的對象，在GC標記結束后卻被錯誤地標記為白色，從而被回收。這是最危險的，因為會導致程序錯誤甚至崩潰。

發生條件： 當以下兩個條件同時滿足時，就會發生漏標：

1. 應用程序刪除了從“灰色”對象到“白色”對象的引用。 (即A (灰色) 不再引用 C (白色))
2. 應用程序新增了從“黑色”對象到“白色”對象的引用。 (即B (黑色) 開始引用 C (白色))

舉例說明：

假設有對象A（灰色），B（黑色），C（白色）。

• 初始狀態：GC Roots -> A (灰色已入隊)，GC Roots -> B (黑色已處理完畢)。A -> C (C是白色)。
• GC線程正在遍歷，B已經是黑色（意味著B及其所有子對象都處理完了）。A是灰色（待處理）。
• 并發過程：
  1. 應用程序線程執行操作：A.field = null; （刪除了 A -> C 的引用）。
  2. 應用程序線程執行操作：B.new_field = C; （新增了 B -> C 的引用）。
• 結果：
  • A在處理完其子對象后，發現C不再是其子對象，因此C不會通過A的路徑被標記。
  • B已經是黑色，按照三色標記原則，黑色對象不會再被掃描，所以C也不會通過B的路徑被標記。
  • 最終，C仍然是白色，被誤判為垃圾而回收。

3.2. 錯標 (Floating Garbage) - 不那么嚴重的問題

定義： 一個明明是死亡的對象，在GC標記結束后卻被錯誤地標記為黑色，從而沒有被回收。

發生條件： 當以下條件滿足時，會發生錯標：

• 應用程序刪除了所有從“灰色”或“黑色”對象到“白色”對象的引用。 (即一個對象的所有引用鏈被切斷)
• GC線程在刪除操作之前已經訪問過該對象，并將其標記為灰色或黑色。

舉例說明：

假設對象A（灰色）引用了對象C（白色）。

• 初始狀態：A (灰色已入隊)，A -> C (C是白色)。
• 并發過程：
  1. GC線程正在處理A，A將C標記為灰色并加入待處理列表。
  2. 應用程序線程執行操作：A.field = null; （刪除了 A -> C 的引用，C變得不可達）。
• 結果： C已經被GC標記為灰色，最終會被標記為黑色。雖然它已經不可達，但GC不知道，將它作為存活對象保留了下來。這種對象被稱為“浮動垃圾”，會在下一次GC周期中被回收。

錯標雖然會增加內存占用，但不會導致程序錯誤，因此通常比漏標更容易接受和處理。

---

4. 屏障機制 (Barrier) - 解決并發問題

為了解決并發標記中的漏標問題，現代GC引入了屏障機制。屏障是JVM在編譯器或運行時，在應用程序代碼中插入的一小段代碼，用于攔截特定內存操作（讀或寫），從而記錄引用變化信息。

4.1. 寫屏障 (Write Barrier)

寫屏障在對象引用被修改時觸發。它分為：

1. 增量更新 (Incremental Update) - 基于后寫屏障 (Post-write Barrier)

   • 解決思路： 當一個黑色對象A新增了一個對白色對象C的引用時（B.new_field = C;），認為這種引用關系是新增出來，在標記階段結束時可以重新掃描。
   • 工作原理： 當一個黑色對象引用了一個白色對象時，后寫屏障會把這個黑色對象重新標記為灰色，讓GC重新掃描它的子對象，或者將白色對象C標記為灰色加入待處理隊列。
   • 效果： 這種機制確保“黑色對象引用白色對象”的鏈條不會被遺漏。它只避免了漏標，但可能會造成更多的浮動垃圾。
   • 采用者： CMS GC。

2. 原始快照 (Snapshot At The Beginning, SATB) - 基于前寫屏障 (Pre-write Barrier)

   • 解決思路： 當一個“灰色”對象A刪除一個對“白色”對象C的引用時（A.field = null;），將A在GC開始時指向的引用C記錄下來。
   • 工作原理： 當一個引用即將從另一個引用中消失時（即修改一個對象的引用字段前），前寫屏障會捕捉到被刪除的舊引用，將其指向的對象標記為灰色（即放入待處理隊列）。
   • 效果： 確保在GC標記開始時所有可達的對象都被標記。這種方式避免了漏標，但會產生更多的浮動垃圾（因為即使對象不可達了，只要GC開始時它可達，就會被標記為存活）。
   • 采用者： G1 GC。

4.2. 讀屏障 (Load Barrier)

讀屏障在應用程序讀取對象引用時觸發。它不是直接解決三色標記的漏標問題，而是為了支持更高級的并發機制（如并發對象移動），但在這種機制下，也順帶解決了標記的一致性問題。

• 解決思路： 應用程序讀取引用時，由屏障檢查并修正引用狀態。
• 工作原理： 當應用程序讀取到一個對象引用時，讀屏障會攔截該操作，檢查該引用所指向的對象的狀態（通過染色指針或轉發指針）。如果對象在GC過程中已經被移動，或者其狀態需要更新，讀屏障會自動將引用修正為新地址或更新其標記狀態，然后才將修正后的引用返回給應用程序。
• 效果： 在并發對象移動的情況下，確保應用程序總是訪問到對象最新、正確的地址，從而避免了因對象移動導致的任何不一致，也就間接解決了標記階段的正確性。
• 采用者： ZGC (染色指針)，Shenandoah GC (Brooks Pointer)。

---

5. 各GC收集器中的三色標記應用

• CMS GC (Concurrent Mark-Sweep)：
  • 標記算法： 基于三色標記。
  • 屏障： 主要使用增量更新（寫屏障）。在并發標記階段，如果黑色對象引用了白色對象，CMS會通過寫屏障將黑色對象置灰，以便重新掃描。這會導致浮動垃圾，但避免了漏標。
  • 暫停： 初始標記和最終標記階段需要STW。
• G1 GC (Garbage-First)：
  • 標記算法： 基于三色標記。
  • 屏障： 使用SATB（前寫屏障）。G1會在并發標記開始時創建堆的邏輯快照，并發標記過程中引用的刪除會被記錄下來。最終標記時，會處理這些記錄。SATB能非常高效地避免漏標，但會產生更多的浮動垃圾。
  • 暫停： 初始標記（通常與Young GC綁定）、最終標記（Remark）、混合GC（Mixed GC）階段需要STW。
• ZGC (The Z Garbage Collector)：
  • 標記算法： 內部仍基于三色標記思想（通過染色指針的Marked0/Marked1位表示）。
  • 屏障： 核心是讀屏障和染色指針。讀屏障會在應用程序讀取引用時檢查染色指針的狀態，如果對象正在被移動或標記狀態需要更新，屏障會直接修正引用。
  • 暫停： 初始標記、最終標記和轉移開始這幾個STW階段的停頓時間與堆大小無關，極短（亞毫秒級）。
• Shenandoah GC：
  • 標記算法： 內部基于三色標記。
  • 屏障： 核心是讀屏障和Brooks Pointer（轉發指針）。讀屏障在讀取引用時，通過Brooks Pointer找到對象的最新地址。
  • 暫停： 初始標記和最終標記這幾個STW階段的停頓時間與堆大小無關，極短（亞毫秒級）。

---

6. 總結

三色標記算法是理解現代垃圾回收器并發機制的基石。它通過將對象劃分為白、灰、黑三種顏色，清晰地定義了GC的標記過程。然而，在并發GC中，由于應用程序線程對對象圖的修改，可能導致漏標（最危險）或錯標（浮動垃圾）。各種屏障機制（寫屏障的增量更新/SATB、讀屏障）被發明出來，以保證并發GC過程中的引用修改不會導致漏標，從而確保GC的正確性，并盡可能地減少STW時間。

不同GC收集器選擇不同的屏障機制和并發策略，以在吞吐量、停頓時間和內存/CPU開銷之間取得平衡。理解這些機制有助于我們更好地診斷GC問題和進行性能調優。