前言

三色標記（Tri-color Marking）是JVM垃圾回收器中用于追蹤存活對象的核心算法，尤其廣泛應用于CMS、G1等現代垃圾收集器。

屬于是jvm的垃圾回收算法里面的標記-清除（Mark-Sweep）算法家族的重要演進成果，但它與傳統(tǒng)標記-清除有顯著區(qū)別，演進而非隸屬。

• 如下圖所示：

由上圖可知，兩者的區(qū)別和聯系。

1、介紹

1.1、發(fā)展

屬于增量式狀態(tài)轉換標記，而非一次性全量標記，清除階段仍基于傳統(tǒng)標記-清除的思想。

引用計數（1959）
↓
標記-清除（1960）
↓
標記-整理（1960s）
↓
分代收集（1984）
↓
三色標記（1976）→ 并發(fā)標記（1990s）
↓
顏色指針（2010s）

三色標記算法通過引入中間狀態(tài)（灰色）和狀態(tài)轉換機制，使標記過程可以暫停和恢復，從而實現了并發(fā)標記這一重大突破，這是傳統(tǒng)標記-清除算法無法做到的。

兩者在思想上一脈相承，但在實現方式和應用場景上已有本質區(qū)別。

1.2、基本原理

三色標記算法將對象分為三種顏色：黑色 (Black)、灰色 (Gray) 和白色 (White)。每種顏色代表了對象的不同狀態(tài)。

• 如下圖所示:

1.白色 (White)：

• 含義：
• 表示未被訪問過的對象，即尚未被標記的對象。
• 變化：
• 在初始標記階段，所有對象都是白色的。

2.灰色 (Gray)：

• 含義：
• 表示正在被訪問的對象，即已經被標記，但其引用還沒有被完全追蹤的對象。
• 變化：
• 在并發(fā)標記過程中，當一個對象被首次標記時，它會變成灰色。然后，從灰色對象開始，追蹤其引用的對象。

3.黑色 (Black)：

• 含義：
• 表示完全訪問過的對象，即已經被標記并且其所有引用都已被追蹤的對象。
• 變化：
• 當一個灰色對象的所有引用都被追蹤完畢后，它會變成黑色。

2、執(zhí)行過程

2.1、初始標記 (Initial Marking)

• 描述：將所有對象標記為白色，并將所有GC Roots（如類靜態(tài)變量、活動線程棧中的局部變量等）直接引用的對象標記為灰色。
• 特點：這個階段需要暫停所有的應用程序線程。

2.2、并發(fā)標記 (Concurrent Marking)

• 描述：從標記過的對象開始，遞歸地追蹤其引用的對象，并將其標記。
• 特點：這個階段不需要暫停應用程序線程，可以與應用程序并發(fā)執(zhí)行。

標記過程：

• 從灰色對象開始，遍歷其引用的對象，將它們也標記為灰色（如果它們還未被標記）。同時，將已經遍歷過的灰色對象及其引用的所有對象都標記為黑色。
• 這個過程會遞歸進行，直到沒有新的灰色對象被標記。

2.3、重新標記 (Remark)

• 描述：由于并發(fā)標記過程中可能存在新的對象被創(chuàng)建或引用關系發(fā)生變化，因此需要再次檢查并標記這些變化。這個過程可能需要STW，但時間通常較短。
• 特點：這個階段需要暫停應用程序線程，以確保標記準確無誤。
• 目的：確保垃圾回收完成后沒有遺漏的垃圾對象。

2.4、垃圾清理階段

清理所有白色對象，即那些未被引用的對象，釋放它們占用的內存空間。

3、并發(fā)標記

在并發(fā)標記過程中，由于用戶線程和垃圾回收線程同時運行，可能會產生以下問題：

3.1、浮動垃圾

在并發(fā)標記過程中，用戶線程可能會創(chuàng)建新的對象或斷開現有對象的引用，導致部分對象被錯誤地標記為存活（實際上是垃圾），這些對象被稱為浮動垃圾。

浮動垃圾不會影響應用程序的正確性，但會占用內存，直到下一輪GC被清理。

如下圖，A在之前掃描已經完成標記，并且標記為黑色，但是垃圾處理過程共，又取消了對A的對象引用。

• 類似于A這種稱為浮動垃圾：

3.2、漏標

當灰色對象斷開了對白色對象的引用，并且黑色對象重新引用了該白色對象時，可能會發(fā)生漏標。

漏標會導致本應存活的對象被錯誤地回收，影響應用程序的正確性。

為了解決漏標問題，JVM采用了讀屏障和寫屏障技術來記錄引用關系的變化，并在并發(fā)標記結束后重新掃描這些變化，確保沒有漏標對象。

在E標為灰色的時候，G還未掃描，但是E取消了對G的引用，此時D又引用了G，但是D已經標記為黑色，不會重新掃描。

這就會引發(fā)很嚴重的問題，G此時是有引用的，但是現在會當成垃圾被處理掉。

總結

三色標記算法是Java垃圾回收中的一種重要技術，通過將對象分為白色、灰色和黑色三種顏色來有效管理內存中的對象。

它支持并發(fā)垃圾回收，減少了垃圾回收過程中的停頓時間，提高了應用程序的性能和響應能力。然而，在并發(fā)標記過程中仍然存在浮動垃圾和漏標等挑戰(zhàn)，需要通過讀屏障、寫屏障等技術來解決。

以上為個人經驗，希望能給大家一個參考，也希望大家多多支持腳本之家。