solution

Hệ thống Buddy System quản lý một vùng nhớ kích thước $2^K$ đơn vị. Khi cần cấp phát size đơn vị, kích thước thực tế được cấp là lũy thừa của 2 nhỏ nhất $\ge$ size (gọi là bậc/order $o$, kích thước $2^o$). Ban đầu toàn vùng nhớ là MỘT khối trống bậc $K$.

• Cấp phát bậc $o$: nếu có sẵn khối trống bậc $o$, lấy khối có ĐỊA CHỈ NHỎ NHẤT. Nếu không, tìm khối trống bậc $o' > o$ nhỏ nhất hiện có, rồi TÁCH LIÊN TIẾP làm đôi (mỗi lần tách bậc giảm 1, tạo ra 2 khối "buddy" bằng nhau) cho tới khi được khối bậc $o$; nửa còn lại ở mỗi lần tách trở thành khối trống. Nếu không có khối trống nào đủ dùng (kể cả sau khi thử tách), cấp phát THẤT BẠI.
• Giải phóng: khối được trả về trạng thái trống; sau đó liên tục kiểm tra "buddy" (khối anh em cùng bậc, được ghép với khối này khi tách ra từ khối bậc lớn hơn 1 bậc) — nếu buddy đó ĐANG TRỐNG, hợp nhất hai khối thành một khối trống bậc cao hơn 1, và tiếp tục thử hợp nhất lên các bậc cao hơn cho tới khi buddy không trống hoặc đã đạt bậc $K$.

Ví dụ: $K=4$ (vùng nhớ 16 đơn vị). A 1 5 (cần 5 đơn vị $\Rightarrow$ bậc $3$, kích thước 8) cấp tại địa chỉ $0$; A 2 3 (bậc $2$, kích thước 4) cấp tại địa chỉ $8$; A 3 4 (bậc $2$) cấp tại địa chỉ $12$; F 1; A 4 8 (bậc $3$) cấp lại tại địa chỉ $0$ (khối vừa giải phóng); F 2; F 3 (hai khối bậc $2$ liền buddy được hợp nhất thành khối bậc $3$ tại địa chỉ $8$).