Tài trợ bài viết này và giới thiệu dịch vụ, sản phẩm, thương hiệu, nhu cầu tuyển dụng của doanh nghiệp đến với cộng đồng.
La Kiến Vinh Vấn đề phân mảnh trong quá trình cấp phát và thu hồi bộ nhớ liên tục dẫn đến thiếu bộ nhớ với các thiết bị có bộ nhớ thấp đã từng làm tôi tốn thời gian. Giải quyết vấn đề phân mảnh là nhiệm vụ của tôi và cách tôi làm là viết lại hệ thống cấp phát.
Nội dung bài viết

Giới thiệu

Khi làm việc với các thiết bị có bộ nhớ lớn như PC, MAC, iPhone, hay các dòng smartphone nói chung tôi không gặp vấn đề về bộ nhớ vì RAM có thể từ 512MB RAM cho đến 16GB. Với khả năng tối ưu hóa bộ nhớ của mình, tôi vẫn có thể giải quyết được các vấn đề đó bằng nhiều phương pháp đôi lúc hơi quái dị để giải quyết vấn đề.

Với bài viết này, ta tự tạo ra hệ thống cấp phát và thu hồi bộ nhớ để sử dụng cho mục đích chống phân mảnh.

Danh sách bài

  1. Tư Duy Tối Ưu Hóa Trong Lập Trình Games - Phần 1: Codes Trong C/C++
  2. Tư Duy Tối Ưu Hóa Trong Lập Trình Games - Phần 2: Quản Lý Bộ Nhớ Phân Mảnh

Đặt vấn đề

Nhắc lại vấn đề cấp phát động

Trong ngôn ngữ lập trình C, để cấp phát 1 vùng nhớ động trên Heap ta sử dụng hàm malloc, và thu hồi ta sử dụng hàm free. Khi sử dụng malloc, hệ điều hành tìm kiếm vùng nhớ trống tại Heap đủ để chứa dãy dữ liệu mà chúng ta muốn lưu trữ.

Cú pháp cơ bản malloc(size)

Ví dụ STDIOMember *p = (STDIOMember*) malloc(sizeof(STDIOMember));

Vấn đề nảy sinh

Giả sử màu cam là vùng đã cấp phát, 1 ô vuông là 1 byte

Cấp phát thu hồi dẫn đến bộ nhớ không được liên tục

Như hình trên, vùng màu trắng là vùng chưa cấp phát, vùng màu vàng là vùng đã cấp phát. Giả sử ta có nhu cầu cấp phát 5 bytes, theo nguyên tắc của cấp phát thì 5 bytes này phải liên tục nhau nên mặc dù ta lấy tổng của bộ nhớ lúc này (theo hình) là 9 bytes nhưng ta không tận dụng được bộ nhớ này.

Những khoảng trống đó có thể đến từ việc trước đó ta đã cấp phát dữ liệu và sau đó thu hồi tại các ô này. Bây giờ, bộ nhớ ta coi như bị phân mảnh.

Trong 1 dự án tôi giải quyết, tôi phải tìm phương pháp giải quyết vấn đề này vì với phần cứng đó tôi không có nhiều bộ nhớ, nhưng ứng dụng lại cứ thu hồi và cấp phát liên tục, tình trạng phân mảnh dẫn tới thiếu bộ nhớ là điểm mấu chốt mà tôi phát hiện ra.

Thiết kế lại phương pháp cấp phát

Vấn đề

Tôi không có quyền quyết định với hệ điều hành, do đó tôi không thể thay thế được cơ chế cấp phát của nó, nhưng không cho mình giới hạn, tôi quyết định thiết kế lại cách thức quản lý bộ nhớ trong ứng dụng của mình.

Phân tích và thiết kế

Sau khi phân tích ứng dụng của mình, tôi có các dữ liệu như sau: ứng dụng của tôi chỉ dùng tại 1 thời điểm tối đa 30MB bộ nhớ (lý tưởng là vậy), khoảng 200.000 hình ảnh và âm thanh tôi phải xử lý nạp và xóa liên tục và nhiều tác vụ nhỏ khác, bộ nhớ lý thuyết là 64MB.

Vấn đề chính dẫn đến thiếu bộ nhớ là do phân mảnh, tôi tìm 1 giải pháp chống phân mảnh, tôi phải tận dụng được các phần bộ nhớ còn trống là đủ bộ nhớ.

*Trước khi tiếp tục: nếu bạn không chắc về C/C++ bạn có thể tìm hiểu trước khi đọc tiếp các bài trong Chủ Đề Về C++ Trong STDIO.

Các bước tiến hành

Tóm tắt các bước

  1. Tạo 1 cấu trúc dữ liệu STDIOMemory để quản lý khối dữ liệu 32MB, bao gồm 2 phần tử, char* m_data (mảng dữ liệu 32MB) và danh sách liên kết lưu 2 thông tin là list<info> m_info (1 info chứa id, offset, size; đoạn này tôi tạm dùng mã giả để giải thích vì trong C không có template và list).
  2. Khi chương trình vừa bắt đầu, ta sử dụng malloc của C chuẩn để xin hệ điều hành 32MB bộ nhớ (để an toàn, mặc dù tôi phân tích chỉ tầm 28MB hoặc 30MB là đủ, hệ số an toàn phụ thuộc kinh nghiệm của bạn). Việc xin này tôi sử dụng hàm malloc và cho cấu trúc dữ liệu STDIOMemory quản lý.
  3. Xây dựng lại khái niệm CẤP PHÁT (STDIO_malloc) và HỦY (STDIO_free) dữ liệu theo cách cá nhân, trong 32MB đã xin cấp phát từ hệ điều hành. Tầng ứng dụng sẽ xin cấp phát sử dụng bao nhiêu bytes trong 32MB ta xin hệ điều hành khi chương trình vừa bắt đầu và tính từ đâu (offset).
  4. Khi cấp phát ta dùng STDIO_malloc để tìm kiếm các vùng trống trong m_data dựa trên danh sách liên kết, ta tìm kiếm các vùng nhớ trống đủ số bytes để "gửi gắm" dữ liệu tại đó và cập nhật vào danh sách liên kết, nếu như không còn đủ bộ nhớ trong 32MB đó nữa, ta sẽ sắp xếp lại toàn bộ dữ liệu trong mảng m_data dồn về bên trái nhất và cập nhật lại các thông tin trong m_info cụ thể là offset mới, sau đó tạo 1 info mới bao gồm offset và size rồi trả về id vừa cấp phát ra bên ngoài (với id này, ta phải quản lý sao cho nó là tồn tại duy nhất). Ở đoạn này, tôi có tối ưu rằng, chỉ khi phát hiện ra không còn vùng nhớ để cấp phát, ta mới tiến hành sắp xếp lại dữ liệu, vì chi phí sắp xếp dữ liệu rất lớn, trong các ngữ cảnh cụ thể của bạn, bạn có thể tối ưu theo phong cách của mình, ví dụ như hệ thống chạy sau 2 phút thì được 3 giây nghỉ ngơi, trong thời gian này bạn có thể ra lệnh cho nó sắp xếp lại dữ liệu chẳng hạn.
  5. Khi muốn hủy dữ liệu, ta sẽ sử dụng STDIO_free, truyền id muốn giải phóng vào, dựa vào id ta sẽ tìm kiếm trong danh sách info và gỡ bỏ info có id này ra khỏi danh sách info.
  6. Trước khi kết thúc chương trình ta hủy vùng nhớ m_data bằng free của C chuẩn.

Một số code mẫu tôi viết ra cho bạn hình dung các bước trên

typedef struct info
{
	int id;
	int offset;
	int size;
} Info;

typedef struct stdioMemory
{
	listInfo * m_info; // Danh sach lien ket lisInfo ban phai tu xay dung
	char* m_data;
	
} STDIOMemory;

int STDIO_malloc(STDIOMemory* memory, int size)
{
	// Tim kiem trong danh sach m_info va tim cho du vung nho co the cap phat
	// Neu khong tim thay thi sap xep lai danh sach
	// Tien hanh cap phat tao ra 1 node info moi voi offset tim thay va size
	// Chen node info moi vao danh sach voi id moi nhat
	// Tra id ra ngoai, neu khong con bo nho thi tra ve -1
}

int STDIO_free(STDIOMemory* memory, int id)
{
	// Tim kiem trong danh m_info va neu co thi free node do bang cach go bo khoi danh sach
	// Neu khong tim thay thi tra ve 0
	// Neu tim thay tra ve 1 va tien hanh go bo node do
}
THẢO LUẬN
ĐÓNG