solution

Trình biên dịch thường cấp phát vùng nhớ cho các khung ngăn xếp (stack frame) hoặc các cấu trúc tồn tại theo phạm vi (scope) bằng một bộ cấp phát ngăn xếp (stack/arena allocator): thay vì cấp phát/giải phóng từng khối riêng lẻ như malloc/free, bộ cấp phát chỉ giữ một con trỏ đỉnh (top pointer) và hỗ trợ giải phóng theo lô, theo thứ tự vào sau ra trước (LIFO) thông qua cơ chế đánh dấu (mark) và khôi phục (release) — rất phù hợp với việc vào/ra các khối lệnh lồng nhau khi biên dịch.

Bộ nhớ arena có dung lượng cố định $S$ byte, con trỏ đỉnh top ban đầu bằng $0$. Có $m$ lệnh thuộc ba loại:

• ALLOC n: cấp phát $n$ byte liên tiếp bắt đầu từ vị trí top hiện tại (nếu top + n <= S), sau đó tăng top thêm $n$; nếu không đủ chỗ (top + n > S) thì phép cấp phát thất bại và top không đổi.
• MARK: lưu lại giá trị top hiện tại vào một ngăn xếp các điểm đánh dấu (để có thể khôi phục sau này).
• RELEASE: lấy điểm đánh dấu được lưu gần nhất ra khỏi ngăn xếp và đặt lại top bằng giá trị đó (giải phóng tức thời toàn bộ những gì đã cấp phát kể từ MARK tương ứng).

Dữ liệu đảm bảo mỗi lệnh RELEASE đều có một lệnh MARK tương ứng chưa được dùng trước đó (ngăn xếp mark không bao giờ rỗng khi gặp RELEASE).

Ví dụ: $S=20$ và các lệnh ALLOC 5, MARK, ALLOC 8, ALLOC 10, RELEASE, ALLOC 4:

• ALLOC 5: cấp tại địa chỉ $0$, top=5.
• MARK: lưu $5$.
• ALLOC 8: cấp tại địa chỉ $5$, top=13.
• ALLOC 10: cần $13+10=23>20$ nên thất bại (in $-1$), top vẫn là $13$.
• RELEASE: khôi phục top=5.
• ALLOC 4: cấp tại địa chỉ $5$, top=9. Đỉnh cao nhất (peak) từng đạt được trong suốt quá trình là $13$.