solution

Bộ thu gom rác thế hệ (generational garbage collector) dựa trên quan sát thực nghiệm "hầu hết đối tượng chết trẻ": đối tượng mới được tạo thuộc thế hệ 0 (non); mỗi lần một đợt thu gom quét qua mà đối tượng vẫn còn sống (còn truy cập được từ gốc), số lần sống sót của nó tăng thêm $1$; khi số lần sống sót đạt ngưỡng $T$, đối tượng được thăng cấp (promote) lên thế hệ 1 vĩnh viễn (không bao giờ bị thu gom trở lại về thế hệ 0). Khác với đếm tham chiếu, thuật toán mark-and-sweep dùng ở đây duyệt đúng theo khả năng truy cập nên thu gom chính xác cả các chu trình tham chiếu.

Có $n$ biến gốc $v_1,\dots,v_n$ (ban đầu null) và $m$ lệnh:

• NEW id size: tạo đối tượng id kích thước size byte, thuộc thế hệ $0$, số lần sống sót $=0$.
• ASSIGN v id: cho biến gốc $v$ trỏ tới id (id=0 nghĩa là gán null). Không làm thay đổi refcount/trạng thái sống chết ngay lập tức — chỉ ảnh hưởng tới lần GC tiếp theo.
• LINK id field target: đặt trường con trỏ field của id trỏ tới target (ghi đè nếu đã tồn tại).
• UNLINK id field: gỡ trường con trỏ field khỏi id (nếu có).
• GC: thực hiện một đợt thu gom: tính tập các đối tượng còn truy cập được bằng cách duyệt (BFS/DFS) từ tất cả biến gốc hiện tại, đi theo các trường con trỏ hiện có, chỉ qua các đối tượng chưa từng bị thu gom. Với mỗi đối tượng còn truy cập được: tăng số lần sống sót thêm $1$; nếu đang ở thế hệ $0$ và số lần sống sót $\ge T$ thì thăng cấp lên thế hệ $1$. Với mỗi đối tượng chưa từng bị thu gom nhưng không còn truy cập được: thu gom ngay (đánh dấu đã giải phóng, cộng dồn vào tổng số byte đã giải phóng).

Đối tượng chỉ thực sự được giải phóng khi có lệnh GC chạy qua và phát hiện nó không còn truy cập được (không tự động giải phóng ngay khi mất tham chiếu).

Ví dụ: $n=1$, $T=2$, các lệnh NEW 1 10, ASSIGN 1 1, GC (obj1 sống sót lần 1, vẫn thế hệ 0), GC (obj1 sống sót lần 2 $\ge T$, thăng cấp thế hệ 1).