Thuật toán đánh dấu ba màu trong JVM

Giới thiệu thuật toán đánh dấu ba màu

Trình thu gom rác (GC) có mục tiêu chính là thực hiện việc thu hồi bộ nhớ, trong quá trình này gồm hai bước chính: đánh dấu bộ nhớ, thu hồi bộ nhớ.

Khái niệm đánh dấu ba màu

Phương pháp đánh dấu ba màu chủ yếu nhằm mục đích đánh dấu hiệu quả các khối bộ nhớ có thể được thu hồi.

Đánh dấu ba màu (Tri-color Marking) được sử dụng như một công cụ hỗ trợ suy luận, phân loại các đối tượng gặp phải trong quá trình duyệt đồ thị đối tượng thành ba màu sau dựa trên điều kiện "đã truy cập hay chưa":

  • Màu trắng: biểu thị đối tượng chưa từng được trình thu gom rác truy cập. Rõ ràng trong giai đoạn bắt đầu phân tích khả năng tiếp cận, tất cả các đối tượng đều là màu trắng, nếu đến cuối giai đoạn phân tích vẫn còn màu trắng thì đại diện cho không thể tiếp cận.
  • Màu đen: biểu thị đối tượng đã được trình thu gom rác truy cập, và tất cả các tham chiếu của đối tượng này đã được quét xong. Các đối tượng màu đen đại diện cho đã được quét xong, chúng an toàn để tồn tại, nếu các đối tượng khác trỏ đến đối tượng màu đen thì không cần quét lại một lần nữa. Đối tượng màu đen không thể trỏ trực tiếp (không thông qua đối tượng màu xám) đến bất kỳ đối tượng màu trắng nào.
  • Màu xám: biểu thị đối tượng đã được trình thu gom rác truy cập, nhưng ít nhất một tham chiếu trên đối tượng này chưa được quét xong.

Quá trình đánh dấu ba màu

Quá trình đánh dấu:

  1. Khi GC bắt đầu đánh dấu, tất cả các đối tượng đều là màu trắng;
  2. Tất cả các đối tượng được tham chiếu trực tiếp từ GC Roots được đánh dấu vào tập hợp màu xám;
  3. Nếu xác định đối tượng trong tập hợp màu xám không có con trỏ nào, đưa nó vào tập hợp màu đen, nếu tồn tại đối tượng con trỏ, đưa tất cả các đối tượng con trỏ vào tập hợp màu xám, đối tượng hiện tại đưa vào tập hợp màu đen.
  4. Theo bước 3, tiếp tục cho đến khi tất cả các đối tượng trong tập hợp màu xám chuyển sang màu đen, hoàn thành đánh dấu vòng này, và các đối tượng trong tập hợp màu trắng trở thành đối tượng không thể tiếp cận, tức là đối tượng rác.
  5. Sau khi kết thúc đánh dấu, các đối tượng màu trắng là không thể tiếp cận từ GC Roots, có thể tiến hành thu gom rác.

Vấn đề đánh dấu sai

Trong quá trình đánh dấu ba màu, luồng đánh dấu và luồng người dùng thực thi đồng thời, do đó có thể trong quá trình đánh dấu, luồng người dùng sửa đổi mối quan hệ tham chiếu, làm cho các đối tượng vốn nên bị thu hồi bị đánh dấu sai thành đang sống. (Nói đơn giản là GC đã đánh dấu đen các đối tượng, trong quá trình đồng thời luồng người dùng làm đứt chuỗi tham chiếu, dẫn đến thực tế là các đối tượng trắng vốn là rác nhưng vẫn giữ nguyên màu đen, gọi là rác nổi). Những rác này xử lý thế nào? Câu trả lời là không xử lý trong lần này, để lại cho lần thu gom rác tiếp theo xử lý.

Còn vấn đề đánh dấu sai, ý chỉ việc đánh dấu chết các đối tượng vốn nên tồn tại. Điều này sẽ gây ra lỗi rất nghiêm trọng. Vậy loại rác này sinh ra như thế nào?

Trong hình đối tượng A được đánh dấu màu đen, lúc này hai đối tượng được nó tham chiếu B,C đều đang ở giai đoạn đánh dấu màu xám. Lúc này luồng người dùng xóa liên kết giữa B->D và thiết lập liên kết giữa A->D. Lúc này đối tượng B vẫn chưa quét xong, còn đối tượng A đã được quét xong, sẽ không tiếp tục quét xuống nữa. Do đó đối tượng D sẽ bị coi là rác và thu gom đi.

Thế nào là đánh dấu sai? Khi cả hai điều kiện dưới đây đồng thời thỏa mãn, sẽ xảy ra đánh dấu sai:

  1. Bộ gán thêm một hoặc nhiều tham chiếu từ đối tượng đen đến đối tượng trắng
  2. Bộ gán xóa tất cả các tham chiếu trực tiếp hoặc gián tiếp từ đối tượng xám đến đối tượng trắng

Giải pháp cho vấn đề đánh dấu sai

Để giải quyết vấn đề đánh dấu sai, chỉ cần phá vỡ một trong hai điều kiện trên, có hai giải pháp tương ứng: Cập nhật tăng dần (Incremental Update) và Ảnh chụp ban đầu (Snapshot At The Beginning, STAB)

Cập nhật tăng dần

Cập nhật tăng dần phá vỡ điều kiện thứ nhất, khi đối tượng đen chèn thêm tham chiếu mới đến đối tượng trắng, lưu lại tham chiếu mới chèn này, sau khi quét đồng thời kết thúc, lấy các đối tượng đen trong các mối quan hệ tham chiếu đã ghi nhận làm gốc, quét lại một lần nữa. Có thể hiểu đơn giản là, đối tượng đen một khi chèn thêm tham chiếu đến đối tượng trắng, nó sẽ trở lại thành đối tượng xám.

Ảnh chụp ban đầu (STAB)

Ảnh chụp ban đầu phá vỡ điều kiện thứ hai, khi đối tượng xám muốn xóa mối quan hệ tham chiếu đến đối tượng trắng, lưu lại tham chiếu muốn xóa này, sau khi quét đồng thời kết thúc, lấy các đối tượng xám trong các mối quan hệ tham chiếu đã ghi nhận làm gốc, quét lại một lần nữa. Cũng có thể hiểu đơn giản là, bất kể mối quan hệ tham chiếu có bị xóa hay không, đều sẽ tìm kiếm theo ảnh chụp đồ thị đối tượng tại thời điểm bắt đầu quét.

Thiếu đánh dấu và thừa đánh dấu

Thực tế vấn đề đánh dấu sai có thể chia nhỏ thành hai trường hợp: thiếu đánh dấu và thừa đánh dấu

Thừa đánh dấu - Rác nổi

Nếu đánh dấu thực hiện đến E lúc này thực hiện object.E = null

Lúc này, về lý thuyết E/F/G có thể được thu hồi. Nhưng vì E đã trở thành màu xám, nên nó sẽ tiếp tục thực thi. Kết quả cuối cùng là sẽ không đánh dấu chúng là đối tượng rác, tồn tại trong vòng đánh dấu này.

Rác nên được thu hồi trong vòng này nhưng không bị thu hồi, phần này được gọi là "rác nổi". Rác nổi không ảnh hưởng đến tính đúng đắn của chương trình, những "rác" này chỉ được dọn dẹp khi lần thu gom rác tiếp theo được kích hoạt.

Thêm nữa, các đối tượng mới sinh ra trong quá trình đánh dấu, mặc định được đánh dấu màu đen, nhưng có thể trở thành "rác" trong quá trình đánh dấu. Đây cũng là một phần của rác nổi.

Thiếu đánh dấu - Rào cản đọc ghi

Rào cản ghi (Store Barrier)

Khi gán giá trị cho biến thành viên của một đối tượng, mã底层 đại khái như sau:

/**
 * @param field Biến thành viên của một đối tượng
 * @param new_value Giá trị mới, ví dụ: null
 */
void assign_member_variable(object* target, void* field, void* new_value) {
    target->field = new_value // Thao tác gán
}

Thực chất rào cản ghi là chèn một số logic xử lý trước và sau thao tác gán (tương tự cách tiếp cận AOP)

void assign_member_variable(object* target, void* field, void* new_value) {
    pre_store_barrier(target, field); // Rào cản ghi - rào cản trước ghi
    target->field = new_value // Thao tác gán
    post_store_barrier(target, field); // Rào cản ghi - rào cản sau ghi
}

Rào cản ghi + SATB

Khi tham chiếu biến thành viên của đối tượng E thay đổi (objE.fieldG = null;), chúng ta có thể sử dụng rào cản ghi, ghi lại đối tượng G mà tham chiếu biến thành viên gốc của E trỏ đến:

void pre_store_barrier(void* field) {
    void* old_ref = *field; // Lấy giá trị cũ
    snapshot_record.add(old_ref); // Ghi lại đối tượng tham chiếu gốc
}

[Khi tham chiếu biến thành viên gốc thay đổi trước, ghi lại đối tượng tham chiếu gốc] Cách tiếp cận này có tư tưởng: Cố gắng giữ lại ảnh chụp đồ thị lúc bắt đầu, tức là ảnh chụp ban đầu (Snapshot At The Beginning, SATB), khi GC Roots tại một thời điểm được xác định, ảnh chụp đồ thị tại thời điểm đó đã được xác định. Ví dụ tại thời điểm đó D trỏ đến G, thì quá trình đánh dấu sau này cũng nên tuân theo ảnh chụp tại thời điểm này (D trỏ đến G). Nếu có thay đổi trong khoảng thời gian này, có thể ghi lại để đảm bảo đánh dấu vẫn theo đúng bản đồ gốc.

Đáng chú ý là thao tác quét tất cả GC Roots này (tức là đánh dấu ban đầu) thường cần STW, nếu không có thể mãi mãi không quét xong, vì trong thời gian đồng thời có thể thêm GC Roots mới.

SATB phá vỡ điều kiện một: [Đối tượng xám ngắt kết nối với đối tượng trắng], từ đó đảm bảo không thiếu đánh dấu.

Một tối ưu nhỏ: Nếu không ở giai đoạn đánh dấu đồng thời của thu gom rác, hoặc đã được đánh dấu rồi, thực tế không cần ghi lại nữa, nên có thể thêm một kiểm tra đơn giản:

void pre_store_barrier(void* field) {
  // Ở giai đoạn đánh dấu đồng thời GC và đối tượng chưa được đánh dấu (truy cập)
  if(gc_execution_phase == GC_CONCURRENT_MARK_PHASE && !has_been_visited(field)) { 
      void* old_ref = *field; // Lấy giá trị cũ
      snapshot_record.add(old_ref); // Ghi lại đối tượng tham chiếu gốc
  }
}

Rào cản ghi + Cập nhật tăng dần

Khi tham chiếu biến thành viên của đối tượng D thay đổi (objD.fieldG = G;), chúng ta có thể sử dụng rào cản ghi, ghi lại đối tượng G mà tham chiếu biến thành viên mới của D trỏ đến:

void post_store_barrier(void* field, void* new_ref) {  
  if(gc_execution_phase == GC_CONCURRENT_MARK_PHASE && !has_been_visited(field)) {
      snapshot_record.add(new_ref); // Ghi lại đối tượng tham chiếu mới
  }
}

[Khi có tham chiếu mới chèn vào, ghi lại đối tượng tham chiếu mới]

Cách tiếp cận này có tư tưởng: Không yêu cầu giữ lại ảnh chụp gốc, mà nhắm vào các tham chiếu mới thêm, ghi lại chúng chờ duyệt, tức là cập nhật tăng dần (Incremental Update).

Cập nhật tăng dần phá vỡ điều kiện hai: [Đối tượng đen lại tham chiếu đến đối tượng trắng đó], từ đó đảm bảo không thiếu đánh dấu.

Rào cản đọc (Load Barrier)

void* retrieve_member_reference(void* field) {
    pre_load_barrier(field); // Rào cản đọc - thao tác trước đọc
    return *field;
}

Rào cản đọc trực tiếp nhắm vào bước đầu tiên var objF = object.fieldG;,

void pre_load_barrier(void* field, void* current_ref) {  
  if(gc_execution_phase == GC_CONCURRENT_MARK_PHASE && !has_been_visited(field)) {
      void* current_ref = *field;
      snapshot_record.add(current_ref); // Ghi lại đối tượng được đọc
  }
}

Cách tiếp cận này là thận trọng, nhưng cũng an toàn. Vì trong điều kiện hai [Đối tượng đen lại tham chiếu đến đối tượng trắng], điều kiện để tham chiếu lại là: phải lấy được đối tượng trắng đó, lúc này rào cản đọc sẽ phát huy tác dụng.

Tổng kết

Thuật toán GC dựa trên phân tích khả năng tiếp cận, quá trình đánh dấu hầu như đều mượn tư tưởng thuật toán đánh dấu ba màu, mặc dù cách thực hiện không hoàn toàn giống nhau, ví dụ phương pháp đánh dấu có ngăn xếp, hàng đợi, con trỏ đa màu sắc, v.v.

Về rào cản đọc ghi, lấy ví dụ Java HotSpot VM, phương án xử lý thiếu đánh dấu trong đánh dấu đồng thời như sau:

  • CMS: Rào cản ghi + Cập nhật tăng dần
  • G1、Shenandoah: Rào cản ghi + Ảnh chụp ban đầu
  • ZGC: Rào cản đọc

Tại sao các phương án trên lại như vậy, bạn đã từng nghĩ tại sao chưa?

  • Ảnh chụp ban đầu so với cập nhật tăng dần hiệu suất cao hơn (dĩ nhiên ảnh chụp ban đầu có thể tạo ra nhiều rác nổi hơn), bởi vì không cần quét sâu lại các đối tượng bị xóa tham chiếu trong giai đoạn đánh dấu lại.
  • Mà CMS sẽ quét sâu các đối tượng gốc có tham chiếu tăng dần, G1 vì nhiều đối tượng đều ở các vùng khác nhau, CMS chỉ có một vùng già, nếu quét sâu lại các đối tượng thì chi phí của G1 sẽ cao hơn CMS, nên G1 chọn ảnh chụp ban đầu không quét sâu đối tượng, chỉ đơn giản đánh dấu, đợi đến vòng GC tiếp theo mới quét sâu.
  • Còn ZGC có thiết kế mang tính biểu tượng là kỹ thuật con trỏ nhuộm màu, con trỏ nhuộm màu có thể giảm đáng kể số lượng rào cản bộ nhớ được sử dụng trong quá trình thu gom rác, thiết lập rào cản bộ nhớ, đặc biệt là mục đích của rào cản ghi thường là để ghi lại tình hình thay đổi tham chiếu đối tượng, nếu thông tin này được duy trì trực tiếp trong con trỏ, rõ ràng có thể tiết kiệm một số thao tác ghi chuyên dụng. Mà ZGC không sử dụng rào cản ghi, chỉ sử dụng rào cản đọc, rõ ràng rất có lợi cho hiệu suất.

Thẻ: JVM garbage-collection tri-color-marking memory-management gc-algorithms

Đăng vào ngày 31 tháng 5 lúc 16:44

Thẻ Phổ Biến

©2026 Thành phố Cuồng loạn