前言

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

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

• 如下圖所示：

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

1、介紹

1.1、發(fā)展

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

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

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

兩者在思想上一脈相承，但在實(shí)現(xiàn)方式和應(yīng)用場景上已有本質(zhì)區(qū)別。

1.2、基本原理

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

• 如下圖所示:

1.白色 (White)：

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

2.灰色 (Gray)：

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

3.黑色 (Black)：

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

2、執(zhí)行過程

2.1、初始標(biāo)記 (Initial Marking)

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

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

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

標(biāo)記過程：

• 從灰色對象開始，遍歷其引用的對象，將它們也標(biāo)記為灰色（如果它們還未被標(biāo)記）。同時，將已經(jīng)遍歷過的灰色對象及其引用的所有對象都標(biāo)記為黑色。
• 這個過程會遞歸進(jìn)行，直到?jīng)]有新的灰色對象被標(biāo)記。

2.3、重新標(biāo)記 (Remark)

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

2.4、垃圾清理階段

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

3、并發(fā)標(biāo)記

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

3.1、浮動垃圾

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

浮動垃圾不會影響應(yīng)用程序的正確性，但會占用內(nèi)存，直到下一輪GC被清理。

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

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

3.2、漏標(biāo)

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

漏標(biāo)會導(dǎo)致本應(yīng)存活的對象被錯誤地回收，影響應(yīng)用程序的正確性。

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

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

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

總結(jié)

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

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

以上為個人經(jīng)驗(yàn)，希望能給大家一個參考，也希望大家多多支持腳本之家。

最新評論