Bộ Quản Lý Bộ Nhớ Nhóm Bạn (Buddy Memory Allocation)

Trong bữa cơm tối hôm nay, một ý tưởng chợt lóe lên trong đầu tôi: cần thiết kế một bộ cấp phát bộ nhớ tùy chỉnh để giải quyết bài toán quản lý pool chuỗi trong bộ nhớ chia sẻ. Đặc điểm yêu cầu của bộ quản lý này là phi xâm nhập - không ghi cookie vào các khối bộ nhớ được cấp phát. May mắn thay, trong trường hợp của tôi, các khối bộ nhớ cần quản lý đều có độ dài là lũy thừa cơ số 2, phù hợp hoàn hảo với thuật toán Buddy Memory Allocation.

Cốt lõi của thuật toán

Ý tưởng trung tâm của thuật toán cực kỳ tinh gọn:

• Khi cấp phát, chia đôi khối bộ nhớ liên tục cho đến khi có được kích thước phù hợp
• Khi giải phóng, hợp nhất 2 khối “bạn đồng hành” (cùng cha mẹ, kích thước bằng nhau) nếu cả hai đều rảnh

Hiệu suất của thuật toán thuộc độ phức tạp O(log N) cho cả cấp phát và giải phóng, với N là bậc lũy thừa của khối bộ nhớ lớn nhất. Đặc tính ưu việt của nó nằm ở việc giảm thiểu phân mảnh cực tốt, đồng thời dễ dàng triển khai theo dạng phi xâm nhập nhờ việc tách biệt cây nhị phân trạng thái ra khỏi vùng nhớ dữ liệu vật lý.

Triển khai thực tế

Sau bữa ăn, tôi nhanh chóng kiểm tra tài nguyên trực tuyến nhưng không tìm thấy giải pháp phù hợp. Tính toán sơ bộ, đoạn mã C cần khoảng dưới 200 dòng và có thể hoàn thành trong 1 giờ. Không chần chừ, tôi bắt tay vào xây dựng ngay và chia sẻ mã nguồn mở trên GitHub để cộng đồng tiện sử dụng.

Tối ưu hóa và bài học

Thuật toán phiên bản đầu tiên sử dụng đệ quy, điều mà tôi từng thành thạo từ thời học sinh dự thi Olympic Tin học. Tuy nhiên, khi làm việc với C, việc sử dụng hồi quy có những điểm bất tiện do:

• Chi phí quản lý stack frame cao
• Giới hạn độ sâu đệ quy
• Không tương thích tốt với closure

Vì thế, tôi đã viết lại bằng cơ chế duyệt cây không đệ quy, kết hợp với việc lưu trữ dưới dạng cây nhị phân hoàn chỉnh, giúp giảm 30% bộ nhớ sử dụng và tăng tốc đáng kể. Một cải tiến đáng chú ý khác được đề xuất bởi cộng đồng là lưu kích thước vùng trống lớn nhất trong mỗi node, giúp tối ưu quá trình phân bổ.

Cách sử dụng đơn giản

Bộ thư viện hoạt động như một “bản đồ ảo” cho vùng nhớ vật lý của bạn:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

// Tạo vùng quản lý 1024KB (2^10 * 1KB)
buddy_t* manager = buddy_new(10); 

// Cấp phát 4 trang 1KB (trả về chỉ số)
int index = buddy_alloc(manager, 4); 

// Giải phóng khi dùng xong
buddy_free(manager, index); 

// Gỡ lỗi trực quan
buddy_dump(manager); 

Triết lý thiết kế

Câu chuyện này khiến tôi chiêm nghiệm: Viết tài liệu mô tả đôi khi còn tốn thời gian hơn cả việc viết mã. Điều này lý giải tại sao nhiều dự án càng nhiều người lại càng chậm tiến độ. Quan trọng là phải xác định rõ nhu cầu thực tế - như trường hợp của tôi, hiệu năng thời gian không phải là yếu tố then chốt nên không cần tối ưu quá mức.

Cập nhật mới nhất

• 21/12: Hoàn thiện triển khai không đệ quy, giảm 40% memory footprint
• 25/12: Kết hợp đề xuất từ cộng đồng về tracking vùng trống tối ưu

Bạn có thể tìm thấy phiên bản nâng cấp tại:

“Thiết kế thông minh không phải là thêm thật nhiều tính năng, mà là loại bỏ mọi thứ không cần thiết” - Đây chính là kim chỉ nam tôi áp dụng trong dự án này.