“Mark-and-Sweep” Thuật toán Xử lý rác

Nhiều thuật toán thu gom rác chạy ngầm, trong đó có một thuật toán được gọi là đánh dấu và quét “Mark-and-Sweep”.

Tất cả các đối tượng được tạo động (sử dụng new trong C++ và Java) đều được cấp phát bộ nhớ (allocated memory) trong heap.

Nếu chúng ta tiếp tục tạo đối tượng, chúng ta có thể gặp lỗi Hết Bộ Nhớ vì không thể cấp phát bộ nhớ heap cho đối tượng. Vì vậy, chúng ta cần giải phóng bộ nhớ heap bằng cách giải phóng bộ nhớ cho tất cả các đối tượng không còn được tham chiếu (referenced) bởi chương trình (hoặc các đối tượng không thể truy cập) để có không gian cho các đối tượng mới tiếp theo. Bộ nhớ này có thể được giải phóng bởi chính lập trình viên, nhưng dường như là gánh nặng (overhead). Đây là lúc thu gom rác (garbage collection) xuất hiện, tự động giải phóng bộ nhớ heap cho tất cả các đối tượng không được tham chiếu.

Mark and Sweep Algorithm

Đánh dấu và Quét

Mọi thuật toán thu gom rác phải thực hiện 2 thao tác cơ bản. Một, nó cần phát hiện được tất cả các đối tượng không thể truy cập và thứ hai, nó phải thu hồi bộ nhớ heap được sử dụng bởi các đối tượng rác và cấp lại không gian đó cho chương trình. Các hoạt động trên được thực hiện bởi Thuật toán Đánh dấu và Quét trong hai giai đoạn như sau:

• Mark phase
• Sweep phase

Phase 1: Mark Phase 

Khi một đối tượng được tạo ra, bit đánh dấu của nó được đặt là 0 (false). Trong giai đoạn Đánh dấu, chúng ta đặt bit đánh dấu cho tất cả các đối tượng có thể truy cập (hoặc các đối tượng mà người dùng có thể tham chiếu đến) thành 1 (true). Để thực hiện thao tác này, chúng ta chỉ cần duyệt đồ thị (graph traversal), phương pháp tìm kiếm theo chiều sâu (depth-first search approach) sẽ phù hợp cho chúng ta. Ở đây, ta có thể xem mỗi đối tượng như một nút (node) và sau đó tất cả các nút (đối tượng) có thể tiếp cận từ nút này (đối tượng) được thăm và tiếp tục cho đến khi ta đã thăm tất cả các nút có thể tiếp cận.

• The root is a variable that refers to an object and is directly accessible by a local variable. We will assume that we have one root only.
  root là một biến số tham chiếu đến một đối tượng và có thể truy cập trực tiếp bằng một biến cục bộ. Chúng ta sẽ giả định rằng chúng ta chỉ có một root duy nhất.
• We can access the mark bit for an object by ‘markedBit(obj)’.
  Chúng ta có thể truy cập bit đánh dấu của một đối tượng bằng cách ‘markedBit(obj)’.

Algorithm: Mark phase

Phase 2: Sweep Phase

Như tên gọi của nó, quá trình này “quét dọn” các đối tượng không thể truy cập được, nghĩa là nó xóa bỏ các đối tượng không thể truy cập khỏi bộ nhớ heap. Tất cả những đối tượng có giá trị đánh dấu được đặt là false sẽ bị xóa khỏi bộ nhớ heap, trong khi đối với các đối tượng khác (đối tượng có thể truy cập được), bit đánh dấu được đặt thành true. Sau đó, giá trị đánh dấu cho tất cả các đối tượng có thể truy cập được sẽ được đặt lại thành false, vì chúng ta sẽ chạy thuật toán này (nếu cần) và một lần nữa trải qua giai đoạn đánh dấu để đánh dấu tất cả các đối tượng có thể truy cập được.

Algorithm: Sweep Phase

Thuật toán mark-and-sweep algorithm (đánh dấu và quét) được gọi là tracing garbage collector (bộ sưu tập rác theo dõi) vì nó theo dõi (traces) toàn bộ tập hợp các đối tượng (objects) trực tiếp hoặc gián tiếp có thể truy cập được bởi chương trình.