1. Tổng quan

Trong các ngôn ngữ lập trình bậc thấp, việc quản lý bộ nhớ phần lớn phụ thuộc vào lập trình viên, từ cấp phát, sử dụng cho đến giải phóng bộ nhớ khi không còn cần thiết. Quá trình này không chỉ tiêu tốn thời gian, công sức mà còn tiềm ẩn nhiều rủi ro như rò rỉ bộ nhớ (Memory Leak), truy cập vào vùng nhớ không hợp lệ hoặc giải phóng bộ nhớ sai cách

Để giải quyết những vấn đề này, nhiều ngôn ngữ lập trình bậc cao như Java, Python hay Go đã áp dụng cơ chế quản lý bộ nhớ tự động (Automatic Memory Management), trong đó Garbage Collection (GC) đóng vai trò phát hiện và thu hồi những vùng nhớ không còn được chương trình sử dụng. Nhờ đó, lập trình viên có thể tập trung hơn vào việc xây dựng logic nghiệp vụ thay vì phải trực tiếp kiểm soát vòng đời của từng đối tượng trong bộ nhớ

2. Các thuật toán Garbage Collection cơ bản

Để quản lý và thu hồi bộ nhớ tự động, nhiều thuật toán Garbage Collection đã được phát triển với những nguyên lý hoạt động khác nhau. Mỗi thuật toán có cách riêng để xác định các đối tượng không còn được sử dụng và giải phóng vùng nhớ mà chúng chiếm giữ. Tuy nhiên, không có thuật toán nào tối ưu trong mọi trường hợp, bởi mỗi cách tiếp cận đều có những đánh đổi về hiệu năng, mức tiêu thụ tài nguyên và thời gian tạm dừng ứng dụng

Trong phần này, chúng ta sẽ tìm hiểu hai cách tiếp cận: Reference Counting và Mark-Sweep & Mark-Compact làm nền tảng để hiểu cách hoạt động của các Garbage Collector hiện đại

2.1. Reference Counting

Reference Counting là một kỹ thuật quản lý bộ nhớ tự động dựa trên việc theo dõi số lượng tham chiếu đang trỏ đến một đối tượng. Mỗi đối tượng được gắn với một bộ đếm gọi là Reference-Count, đại diện cho số lượng tham chiếu đang sử dụng

Nguyên lý hoạt động tương đối đơn giản:

• Khi một tham chiếu mới đến đối tượng được tạo ra, Reference-Count tăng thêm 1
• Khi một tham chiếu đến đối tượng bị loại bỏ hoặc thay đổi, Reference-Count giảm đi 1
• Khi Reference-Count bằng 0, đối tượng không còn được tham chiếu và có thể được giải phóng ngay lập tức

Nhờ việc cập nhật biến đếm (Reference-Count) liên tục, Reference Counting không cần định kỳ duyệt toàn bộ đối tượng để xác định những đối tượng cần thu hồi

Về mặt triển khai, trình quản lý bộ nhớ của ngôn ngữ cần thực hiện ba thao tác chính:

1. Khởi tạo bộ đếm: Khi đối tượng được tạo, bộ đếm được thiết lập theo số tham chiếu sở hữu ban đầu
2. Cập nhật bộ đếm: Tăng hoặc giảm bộ đếm mỗi khi các tham chiếu sở hữu được thêm vào hoặc loại bỏ
3. Thu hồi bộ nhớ: Khi bộ đếm về 0, giải phóng đối tượng và tiếp tục giảm bộ đếm của những đối tượng mà nó đang sở hữu tham chiếu

Cách tiếp cận này có ưu điểm nổi bật là khả năng thu hồi đối tượng kịp thời mà không cần đợi trình quản lý bộ nhớ thực hiện các chu kỳ quét toàn bộ Heap-memory (chu kỳ GC)

Tuy nhiên nhược điểm lớn của thuật toán này là không tự xử lý được trường hợp tham chiếu vòng (Circular References)

Giả sử có hai đối tượng A và B tham chiếu lẫn nhau. Ngay cả khi chương trình không còn giữ tham chiếu bên ngoài đến chúng, Reference-Count của cả hai vẫn lớn hơn 0. Do Reference-Count không thể giảm về 0, cả hai đối tượng không được giải phóng, dẫn đến rò rỉ bộ nhớ

Để khắc phục, trình quản lý bộ nhớ có thể kết hợp thêm một cơ chế phát hiện chu trình tham chiếu, như Cyclic-Garbage-Collector trong Python

Ngoài ra, chi phí cập nhật Reference-Count liên tục trong mỗi lần thêm/loại bỏ một tham chiếu sở hữu và chi phí giải phóng dây chuyền (khi một đối tượng được giải phóng, Reference-Count của các đối tượng mà nó tham chiếu cũng có thể giảm về 0, gây ra quá trình giải phóng liên tiếp) cũng sẽ gây tốn kém về chi phí thực thi và tăng độ trễ tại một số thời điểm nhất định

2.2. Mark-Sweep & Mark-Compact

Để giải quyết bài toán phát hiện các đối tượng không còn khả năng truy cập, kể cả khi chúng tham chiếu lẫn nhau, các thuật toán Tracing-Garbage-Collection, điển hình là Mark-Sweep, sử dụng một hướng tiếp cận khác: xác định đối tượng còn sống dựa trên khả năng truy cập từ tập hợp các GC Roots, thay vì dựa trên số lượng tham chiếu.

Khác với Reference Counting, Mark-Sweep không quan tâm một đối tượng có bao nhiêu tham chiếu trỏ đến nó. Thay vào đó, thuật toán xác định liệu đối tượng đó có thể được truy cập từ một tập hợp các tham chiếu gốc (gọi là GC Roots) hay không. Từ đó, phân loại ra 2 loại đối tượng

• Reachable Objects: Những đối tượng có thể truy cập trực tiếp hoặc gián tiếp từ GC Roots, được xem là còn sống
• Unreachable Objects: Những đối tượng không thể truy cập từ bất kỳ GC Root nào, được xem là chết và có thể thu hồi

Mark-Sweep gồm hai giai đoạn chính: Mark (đánh dấu) và Sweep (quét).

Giai đoạn 1 – Mark

Garbage Collector bắt đầu từ tập hợp GC Roots, duyệt qua các tham chiếu để tìm tất cả đối tượng có thể truy cập và đánh dấu chúng là còn sống.

Ví dụ trong JVM, GC Roots có thể bao gồm các tham chiếu từ biến cục bộ và tham số trên stack của những phương thức đang thực thi, các tham chiếu từ trường static, hoặc những tham chiếu được JVM/JNI duy trì.

Giai đoạn 2 – Sweep

Sau khi đánh dấu hoàn tất, Garbage Collector quét các vùng bộ nhớ được quản lý trong Heap-memory

• Đối tượng đã được đánh dấu: Giữ lại
• Đối tượng không được đánh dấu: Thu hồi bộ nhớ
• Thông tin đánh dấu được thiết lập lại hoặc chuẩn bị cho chu kỳ GC tiếp theo

Cách tiếp cận của Mark-Sweep đem lại 2 ưu điểm chính gồm

• Xử lý được tham chiếu vòng: Các đối tượng tham chiếu lẫn nhau nhưng không thể truy cập từ GC Roots vẫn được xác định là đối tượng cần loại bỏ
• Tránh chi phí khi duy trì bộ đếm tham chiếu Reference-Count

Điểm hạn chế của thuật toán Mark-Sweep là gây hiện tượng phân mảnh bộ nhớ. Sau khi các đối tượng không còn sử dụng được thu hồi, những vùng nhớ trống có thể nằm rải rác xen kẽ giữa các đối tượng còn sống

Ví dụ, tổng dung lượng bộ nhớ trống có thể là 100 MB, nhưng nếu vùng trống liên tục lớn nhất chỉ có 20 MB thì một đối tượng yêu cầu 30 MB có thể không được cấp phát trong vùng nhớ đó, dù tổng dung lượng trống vẫn đủ

Để giải quyết vấn đề trên, thuật toán Mark-Compact ra đời nhằm khắc phục vấn đề phân mảnh bộ nhớ của Mark-Sweep

Cơ chế xác định những đối tượng còn sống của Mark-Compact giống với Mark-Sweep đó là dựa vào GC Roots. Tuy nhiên, thay vì chỉ thu hồi bộ nhớ của các đối tượng không còn sử dụng, Mark-Compact còn di chuyển các đối tượng còn sống về những vùng nhớ liên tục, qua đó gom các khoảng trống rải rác thành một vùng trống lớn.

Nhờ vậy, việc cấp phát bộ nhớ cho những đối tượng mới trở nên thuận lợi hơn

Mark-Compact thường được mô tả thông qua ba công việc chính

Giai đoạn 1 – Mark (Đánh dấu)

Tương tự Mark-Sweep, Garbage Collector duyệt từ GC Roots để xác định những đối tượng còn sống

Giai đoạn 2 – Relocate/Compact (Di chuyển và nén)

Sau khi xác định các đối tượng còn sống, Garbage Collector tính toán vị trí mới và di chuyển chúng về những vùng bộ nhớ liên tục, loại bỏ các khoảng trống nằm giữa các đối tượng

Giai đoạn 3 – Update References (Cập nhật tham chiếu)

Do vị trí của một số đối tượng đã thay đổi, những tham chiếu trỏ đến chúng cũng phải được cập nhật để đảm bảo chương trình tiếp tục truy cập đúng đối tượng

Trên thực tế, thứ tự tính toán vị trí, cập nhật tham chiếu và di chuyển đối tượng phụ thuộc vào từng thuật toán cụ thể. Không nhất thiết mọi triển khai đều thực hiện ba công việc này theo đúng thứ tự trên

Bằng cách di chuyển những đối tượng còn sống về vùng nhớ liên tục, Mark-Compact loại bỏ phần lớn phân mảnh bên ngoài trong Heap-memory

Dù có nhiều ưu điểm đáng kể hơn so với Reference Counting, nhưng 2 thuật toán Mark-Sweep và Mark-Compact đều phải đối mặt với một vấn đề chung mang tên Stop-The-World (STW)

Trong quá trình Garbage Collection, một trong những thách thức lớn nhất là đảm bảo tính nhất quán của bộ nhớ khi ứng dụng vẫn đang hoạt động. Các luồng thực thi có thể liên tục tạo mới, thay đổi hoặc loại bỏ tham chiếu giữa các đối tượng, khiến trạng thái của đối tượng thay đổi trong lúc Garbage Collector đang phân tích

Để giải quyết vấn đề này, các thuật toán Garbage Collection truyền thống thường sử dụng cơ chế Stop-The-World (STW), tạm dừng các luồng thực thi của ứng dụng trong một khoảng thời gian để thực hiện việc đánh dấu, thu hồi hoặc di chuyển đối tượng

STW không phải yêu cầu bắt buộc về mặt lý thuyết của Mark-Sweep hay Mark-Compact. Nó là lựa chọn triển khai phổ biến trong các thuật toán truyền thống

Trong Mark-Sweep, STW giúp đảm bảo đối tượng không bị thay đổi trong quá trình đánh dấu và quét. Đối với Mark-Compact, STW còn đóng vai trò quan trọng trong việc đảm bảo các đối tượng được di chuyển và những tham chiếu liên quan được cập nhật một cách nhất quán

Tuy nhiên, Stop-The-World cũng tạo ra sự đánh đổi về hiệu năng. Trong thời gian tạm dừng, ứng dụng không thể tiếp tục xử lý công việc, làm gia tăng độ trễ và đặc biệt ảnh hưởng trong những hệ thống yêu cầu khả năng phản hồi nhanh. Đây cũng là một trong những động lực thúc đẩy sự phát triển của các Garbage Collector hiện đại, với những kỹ thuật như Concurrent Marking và Concurrent Compaction, cho phép thực hiện phần lớn công việc thu gom rác đồng thời với ứng dụng nhằm giảm thiểu thời gian tạm dừng

3. Một số Garbage Collector hiện đại

3.1. Java GC - ZGC

ZGC (Z Garbage Collector) là một Garbage Collector được phát triển cho HotSpot JVM, với mục tiêu giảm thiểu thời gian Stop-The-World, đặc biệt đối với những ứng dụng sử dụng Heap-memory lớn và yêu cầu độ trễ thấp.

ZGC sử dụng cơ chế Concurrent-Garbage-Collection, cho phép phần lớn quá trình đánh dấu và di chuyển đối tượng được thực hiện đồng thời với các luồng ứng dụng.

Ngoài ra, ZGC còn tổ chức Heap-memory thành nhiều vùng bộ nhớ (ZPages), cho phép Garbage Collector lựa chọn những vùng phù hợp để thu gom và di chuyển các đối tượng còn sống, thay vì phải compact toàn bộ vùng nhớ trong một lần

Để đảm bảo tính nhất quán của bộ nhớ, ZGC kết hợp hai kỹ thuật quan trọng là Colored Pointers và Load Barriers.

• <u>Colored Pointers</u>: Mã hóa một số thông tin trạng thái phục vụ GC trong biểu diễn tham chiếu
• <u>Load Barriers:</u> Phát hiện và xử lý những tham chiếu cần được điều chỉnh khi ứng dụng truy cập đối tượng. Nhờ đó, ZGC có thể di chuyển đối tượng mà không cần tạm dừng ứng dụng trong toàn bộ quá trình.

Ưu điểm nổi bật của ZGC là khả năng duy trì thời gian chờ GC rất thấp và tương đối độc lập với kích thước Heap-memory.

Vệc thực hiện GC đồng thời với ứng dụng và sử dụng các Barrier cũng tạo ra chi phí CPU, đồng thời đòi hỏi bộ nhớ dự phòng để đảm bảo GC có thể hoàn thành trong khi ứng dụng tiếp tục cấp phát đối tượng

3.2. Go GC

Go sử dụng cơ chế Concurrent-Mark-Sweep, được thiết kế nhằm cân bằng giữa thời gian tạm dừng ứng dụng, hiệu năng xử lý và mức tiêu thụ bộ nhớ

Khác với ZGC, Go GC không thực hiện di chuyển các đối tượng còn sống (Non-Moving GC). Qua đó tránh được chi phí cập nhật tham chiếu

Trong quá trình thu gom, Go sử dụng Tri-Color Marking để phân loại trạng thái các đối tượng thành White (chưa được đánh dấu), Gray (đã phát hiện nhưng chưa quét xong tham chiếu) và Black (đã quét xong tham chiếu). Đây cũng là điểm khác biệt so với thuật toán Mark-Sweep truyền thống - chỉ có 2 trạng thái

Quá trình đánh dấu diễn ra đồng thời với ứng dụng, kết hợp với Write Barriers để theo dõi những thay đổi tham chiếu và đảm bảo các đối tượng còn sống không bị bỏ sót. Sau đó, những đối tượng không còn được sử dụng sẽ được thu hồi

Ưu điểm của Go GC là cơ chế tương đối đơn giản, phần lớn công việc thu gom được thực hiện đồng thời với ứng dụng và không phát sinh chi phí di chuyển đối tượng.

Tuy nhiên, việc không thực hiện compaction bằng cách di chuyển đối tượng có thể dẫn đến phân mảnh bộ nhớ. Ngoài ra, Concurrent Marking và Write Barriers cũng tiêu tốn tài nguyên CPU, tạo ra sự đánh đổi giữa hiệu năng và mức sử dụng bộ nhớ.

3.3. Cyclic GC - CPython

Khác với Java ZGC và Go GC, CPython sử dụng Reference Counting làm cơ chế quản lý bộ nhớ chính, kết hợp với Cyclic-Garbage-Collection để xử lý những trường hợp tham chiếu vòng

Trong cơ chế Reference Counting truyền thống, mỗi đối tượng duy trì một bộ đếm tham chiếu và thường được giải phóng ngay khi bộ đếm giảm về 0. Tuy nhiên, đối với những đối tượng tham chiếu lẫn nhau, bộ đếm có thể không bao giờ về 0 mặc dù chúng không còn được chương trình sử dụng. Để giải quyết vấn đề này, CPython sử dụng Cyclic GC nhằm phát hiện và thu hồi những nhóm đối tượng không còn được sử dụng nhưng vẫn tồn tại do các tham chiếu nội bộ

Ưu điểm của cơ chế này là khả năng thu hồi kịp thời phần lớn đối tượng mà không cần chờ một chu kỳ quét Heap-memory.

Tuy nhiên, việc liên tục cập nhật Reference-Count tạo ra chi phí thực thi, trong khi Cyclic GC vẫn cần thực hiện các chu kỳ kiểm tra bổ sung và có thể gây ra những khoảng tạm dừng ứng dụng