solution

Một máy ảo quản lý bộ nhớ bằng kỹ thuật đếm tham chiếu (reference counting). Có $10$ biến (thanh ghi tham chiếu) $V_0, V_1, \ldots, V_9$, ban đầu đều là null (không trỏ tới đối tượng nào). Các đối tượng trên vùng nhớ heap được cấp phát tuần tự, đối tượng được tạo đầu tiên có id $1$, đối tượng tiếp theo có id $2$, v.v. Mỗi đối tượng có một bộ đếm tham chiếu (refcount), khi refcount giảm về $0$ thì đối tượng đó bị giải phóng vĩnh viễn (không bao giờ có refcount dương trở lại).

Các lệnh (một lệnh một dòng):

• NEW i: cấp phát một đối tượng mới (refcount khởi tạo $=1$), gán $V_i$ trỏ tới đối tượng đó. Nếu trước đó $V_i$ đang trỏ tới một đối tượng khác, refcount của đối tượng cũ giảm đi $1$.
• COPY i j: gán $V_i \gets V_j$ (sao chép tham chiếu; nếu $V_j$ là null thì $V_i$ cũng thành null). Nếu giá trị mới không phải null, refcount của đối tượng đó tăng $1$. Nếu $V_i$ trước đó đang trỏ tới một đối tượng, refcount đối tượng cũ giảm $1$.
• CLEAR i: gán $V_i \gets$ null. Nếu $V_i$ trước đó đang trỏ tới một đối tượng, refcount đối tượng đó giảm $1$.

Sau khi thực thi hết chương trình, hãy liệt kê id các đối tượng còn sống (refcount $> 0$).

Ví dụ:

NEW 0
COPY 1 0
CLEAR 0

NEW 0 tạo đối tượng id $1$ (refcount $1$) gán vào $V_0$. COPY 1 0 gán $V_1 \gets V_0$ (đối tượng $1$), refcount đối tượng $1$ tăng lên $2$. CLEAR 0 xoá $V_0$, refcount đối tượng $1$ giảm còn $1$. Kết quả: đối tượng còn sống là 1.