Bài 9: Memory Allocator Visualizer — malloc/free Hoạt Động Thế Nào

Ở Bài 8 chúng ta thấy cách hệ quản trị CSDL quản lý dữ liệu trên đĩa. Bài này đi sâu hơn vào một câu hỏi nền tảng hơn nữa: khi bạn gọi malloc() trong C, điều gì thực sự xảy ra bên dưới? Không có phép màu nào cả — chỉ là một cấu trúc dữ liệu và vài giải thuật khá đơn giản.

1. Vì sao cần một bộ cấp phát bộ nhớ động?

Chương trình xin cấp phát vùng nhớ (heap) với kích thước khác nhau tại thời điểm chạy, rồi giải phóng chúng theo thứ tự bất kỳ — không nhất thiết theo đúng thứ tự đã xin. Bộ cấp phát (allocator) phải quản lý vùng nhớ trống còn lại sao cho các lần xin cấp phát sau vẫn tìm được chỗ trống phù hợp, mà không tốn quá nhiều thời gian dò tìm.

2. Free List: Danh sách các khối nhớ trống

Kỹ thuật kinh điển nhất: bộ cấp phát duy trì một danh sách liên kết các khối nhớ trống (free list). Điều thú vị là con trỏ next của danh sách này được lưu ngay bên trong chính vùng nhớ trống đó — không tốn thêm bộ nhớ phụ nào, vì vùng nhớ đang trống thì không ai dùng tới nội dung của nó cả:

// Mô phỏng khối nhớ trống — trong C thật, size/next được ghi
// TRỰC TIẾP vào những byte đầu của vùng nhớ trống đó
class FreeBlock {
  constructor(start, size) {
    this.start = start; // địa chỉ bắt đầu
    this.size = size;   // kích thước khối (byte)
  }
}
// Free list là mảng/danh sách các FreeBlock, luôn được sắp xếp
// theo địa chỉ start tăng dần để việc gộp khối (coalescing) ở
// phần 5 chỉ cần so sánh 2 khối liền kề trong danh sách.

3. Chiến lược cấp phát: First-Fit, Best-Fit, Worst-Fit

Khi cần cấp phát $n$ byte, bộ cấp phát phải chọn 1 khối trống đủ lớn trong free list. Có 3 chiến lược kinh điển:

// First-Fit: lấy khối trống ĐẦU TIÊN đủ lớn — nhanh nhất, dừng ngay khi tìm thấy
function firstFit(freeList, size) {
  for (const block of freeList) {
    if (block.size >= size) return block;
  }
  return null; // không còn khối nào đủ lớn
}

// Best-Fit: quét HẾT danh sách, chọn khối NHỎ NHẤT vẫn đủ chứa
// (giảm thiểu phần thừa lãng phí mỗi lần cấp phát)
function bestFit(freeList, size) {
  let best = null;
  for (const block of freeList) {
    if (block.size >= size && (!best || block.size < best.size)) best = block;
  }
  return best;
}

// Worst-Fit: quét HẾT danh sách, chọn khối LỚN NHẤT
// (để phần còn thừa lại vẫn đủ lớn, hữu dụng cho lần sau)
function worstFit(freeList, size) {
  let worst = null;
  for (const block of freeList) {
    if (block.size >= size && (!worst || block.size > worst.size)) worst = block;
  }
  return worst;
}

4. Phân mảnh trong (Internal) và Phân mảnh ngoài (External)

Phân mảnh trong (internal fragmentation) xảy ra khi khối cấp phát lớn hơn yêu cầu thực tế (do làm tròn theo alignment, hoặc do chọn worst-fit để lại khối to hơn cần thiết) — phần dư đó bị "khóa" bên trong khối đã cấp phát, không ai dùng được dù nó vẫn tính là "đã cấp phát". Phân mảnh ngoài (external fragmentation) xảy ra khi tổng bộ nhớ trống đủ lớn, nhưng bị chia nhỏ rải rác thành nhiều mảnh không liền kề — không mảnh nào đủ lớn cho yêu cầu cấp phát mới dù cộng dồn lại thì thừa sức.

5. Gộp khối liền kề (Coalescing)

Khi giải phóng 1 khối, nếu khối liền trước hoặc liền sau nó trong bộ nhớ cũng đang trống, phải gộp ngay thành 1 khối trống lớn hơn — đây là kỹ thuật chống phân mảnh ngoài quan trọng nhất:

// freeList luôn được giữ SẮP XẾP theo start — gộp chỉ cần
// so sánh khối vừa thêm với khối ngay trước/sau nó trong mảng
function coalesce(freeList) {
  freeList.sort((a, b) => a.start - b.start);
  for (let i = 0; i < freeList.length - 1; i++) {
    const cur = freeList[i];
    const next = freeList[i + 1];
    if (cur.start + cur.size === next.start) { // liền kề tuyệt đối
      cur.size += next.size;      // gộp next vào cur
      freeList.splice(i + 1, 1);  // xoá next khỏi danh sách
      i--; // xét lại cur với khối kế tiếp mới (có thể gộp tiếp)
    }
  }
}

6. So sánh First-Fit, Best-Fit, Worst-Fit

Sân chơi tương tác: Memory Allocator Visualizer

Cấp phát nhiều khối kích thước khác nhau theo chiến lược bạn chọn, rồi giải phóng vài khối bằng cách click trực tiếp vào khối trên thanh bộ nhớ — quan sát phân mảnh ngoài hình thành và cách gộp khối liền kề hoạt động.