solution

Hệ thống buddy (buddy system) là một kỹ thuật cấp phát bộ nhớ cổ điển: toàn bộ vùng nhớ có kích thước $M$ (với $M$ là lũy thừa của $2$) được xem như một khối duy nhất ở "mức" $k=\log_2 M$. Một khối ở mức $\ell$ có kích thước $2^\ell$ và có thể được tách (split) thành hai khối "buddy" bằng nhau ở mức $\ell-1$; ngược lại, hai khối buddy cùng mức đang trống có thể được gộp (merge) trở lại thành một khối ở mức cao hơn. Hai khối kích thước $2^\ell$ tại địa chỉ a và a XOR 2^\ell luôn là buddy của nhau.

• ALLOC id n: gọi $sz=2^\ell$ là lũy thừa của $2$ nhỏ nhất thỏa $sz \ge n$ (yêu cầu $sz \le M$, nếu không cấp phát thất bại). Tìm khối trống nhỏ nhất có kích thước $\ge sz$ (ưu tiên mức thấp nhất có khối trống, và trong mức đó chọn khối có địa chỉ nhỏ nhất); nếu không có khối trống nào đủ lớn, thất bại. Nếu khối tìm được lớn hơn $sz$, tách liên tiếp thành hai buddy bằng nhau cho tới khi đạt đúng mức $\ell$: mỗi lần tách, nửa có địa chỉ lớn hơn được đưa vào danh sách khối trống ở mức thấp hơn, nửa còn lại (địa chỉ nhỏ hơn) tiếp tục được xét/tách. Khối cuối cùng kích thước $sz$ được gán cho id.
• FREE id: giải phóng khối của id (kích thước $2^\ell$ tại địa chỉ a); sau đó gộp lặp lại: nếu buddy của khối (địa chỉ a XOR 2^\ell) đang trống và cùng mức $\ell$, gộp thành khối kích thước $2^{\ell+1}$ tại địa chỉ $\min(a, \text{buddy})$, rồi tiếp tục thử gộp ở mức cao hơn, cho tới khi không thể gộp nữa hoặc đã đạt mức $k$.

Phần chênh lệch $sz - n$ của mỗi lần cấp phát thành công gọi là phân mảnh nội bộ (internal fragmentation) của khối đó.

Ví dụ: $M=64$ ($k=6$), các lệnh ALLOC A 10, ALLOC B 20, ALLOC C 5, FREE B, ALLOC D 8, FREE A:

• A 10$\to sz=16$: tách khối $64$ thành $32+32$ rồi tách nửa $32$ thành $16+16$; cấp $A$ tại địa chỉ $0$ (kích thước $16$); còn trống: mức $5$ có $\{32\}$, mức $4$ có $\{16\}$.
• B 20$\to sz=32$: dùng luôn khối trống $32$ tại địa chỉ $32$; cấp tại $32$ (kích thước $32$).
• C 5$\to sz=8$: tách khối $16$ tại $16$ thành $8+8$; cấp $C$ tại $16$ (kích thước $8$); còn trống mức $3$: $\{24\}$.
• FREE B: buddy của $(32,32)$ là địa chỉ $0$ ở mức $5$ — không trống (đang là hai khối con) nên không gộp; khối $32$ trở lại trống.
• D 8$\to sz=8$: dùng khối trống $8$ tại $24$; cấp tại $24$.
• FREE A: buddy của $(0,16)$ là địa chỉ $16$ ở mức $4$ — không trống (đã tách) nên không gộp; khối $16$ tại $0$ trở lại trống.

Cuối cùng còn trống: khối $16$ tại $0$ và khối $32$ tại $32$, tổng $48$ byte, $2$ khối. Các đối tượng còn đang cấp phát: $C$ (mức $3$, kích thước $8$, phân mảnh $8-5=3$) và $D$ (kích thước $8$, phân mảnh $0$); tổng phân mảnh nội bộ hiện tại là $3$.