Chi tiết bài học Cấp phát động

Sự cần thiết của việc cấp phát động

Biến được khai báo trong hàm sẽ được cấp phát tới vùng nhớ Stack. Các biến được cấp phát trong stack sẽ được xóa bỏ khi hàm được trả về, và vùng nhớ đã cấp phát cho chúng cũng được tự động thu hồi.

Phương thức làm việc như trên không có vấn đề gì khi ta khai báo những biến thông thường (ví dụ: int a; /* Khai báo biến kiểu số nguyên a */), Nhưng trong một số trường hợp nó gây phung phí bộ nhớ rất nhiều, xét ví dụ sau để thấy rõ vấn đề này:

struct DanhBa
{
    char ten[100];
    char diachi[100];
    char sodt[100];
};
struct DanhBa data[1000];

Trong trường hợp biến danh bạ ở trên. Nếu kích thước tối đa của ten/diachi/sodt là 100 thì ta sẽ cần tới 300KB ((100+100+100) * 1000 = 300000B = 300KB) bộ nhớ.

Lượng bộ nhớ 300KB là khá lớn trong vùng nhớ Stack. Bởi vì trong một số trình biên dịch, vùng nhớ stack chỉ có kích thước khoảng 1MB.

Khi ta sử dụng kỹ thuật lập trình đa luồng (multi-threaded), mỗi thread sẽ có một vùng Stack mở rộng, khi đó 1MB cho một thread vẫn là một kích thước khá lớn. Giả sử như chương trình tạo ra 1000 thread thì vùng nhớ Stack được phép sử dụng là 1MB * 1000 = 1GB).

Tuy nhiên trong lập trình nhúng, vùng nhớ này là rất hạn hẹp, chỉ khoảng 1 KB nên ta không được cấp phát vượt quá kích thước của nó.

Đối với khóa học này, thiên về cấu trúc dữ liệu và những thuật toán cơ bản. Ta không áp dụng kỹ thuật lập trình đa luồng ở đây. Do vậy việc cấp phát bộ nhớ như trong ví dụ ở trên là một vấn đề rất lớn (vấn đề lãng phí bộ nhớ) cho dù là bạn có dùng một số kỹ thuật để tăng kích thước của vùng Stack.

Ta sẽ tìm hiểu cách tăng kích thước của vùng nhớ Stack khi có lỗi stack overflow xảy ra ngay sau đây.

#include<stdio.h>

void f(int n){
    if(n==0) return;
    char a[1000];
    f(n-1);
}

int main(){
    f(5000);
    return 0;
}

Trong ví dụ trên, một mảng 1000 byte được khai báo trong hàm f() và hàm này được gọi đệ quy 5000 lần. Nếu 1MB được cấp cho Stack thì lỗi stack overflow (tràn stack) sẽ xảy ra ở đây, bởi vì lượng bộ nhớ cần cấp phát cho chương trình trên = 5000 * 1000 = 5000000 bytes ~ 5MB, vượt quá kích thước của stack.

Nếu ta điều chỉnh kích thước của stack, cho tăng lên thành một con số lớn hơn 5000000 (giả sử ta tăng thành 6000000). chường trình trên sẽ chạy được và không có lỗi.

Để tăng kích thước của stack trong Visual Studio (Nếu bạn chưa cài đặt Visual Studio bạn có thể xem hướng dẫn cài đặt và sử dụng tại đây) bạn click chuột phải vào project mà bạn đang làm việc rồi chọn “Properties – Configuration Properties – Linker – System – Stack Reserve Size”. Chọn phần “Edit” của Stack Reserve Size và sửa nó thành 6000000 ~ 6MB (mặc định nó sẽ là 1 MB).

Rõ ràng đây không phải cách giải quyết vấn đề trong code, vì chúng ta không thể tăng kích thước của Stack mãi được.

Vì vậy ta cần dùng một giải pháp khác. Đó là cấp phát động.

Cấp phát động là việc cấp phát bộ nhớ tại thời điểm cần chứa dữ liệu. Như vậy ta không cần khai báo trước kích thước tối đa của mảng, mà kích thước tối đa của mảng có thể được tính toán cho phù hợp sau đó, tại thời điểm chạy chương trình.

Để cấp phát động ta có thể dùng tới các hàm malloc() hoặc toán tử “new”.

int* ip = (int*)malloc(sizeof(int) * 1);                  /* C variable   */
char* name = (char*)malloc(sizeof(char) * 55);            /* C array      */
int* ip = new int;                                        /* C++ variable */
char* name = new char[55];                                /* C++ array    */

Một lợi thế của cấp phát động so với việc khai báo mảng tĩnh là ta có thể thu hồi bộ nhớ ngay sau khi nó được sử dụng xong (ta phải chủ động làm việc này một cách thủ công).

Để thu hồi vùng nhớ đã được sử dụng ta dùng hàm free() hoặc toán tử delete.

free(ip);        /* C variable   */
free(name);      /* C array      */
delete ip;       /* C++ variable */
delete[] name;   /* C++ array    */

Nếu cấp phát động được áp dụng cho ví dụ về DanhBa ở trên, thì mã nguồn có thể được viết lại như sau.

struct DanhBa
{
    char* ten;
    char* diachi;
    char* sodt;
};

struct DanhBa data[1000];

Với cách thực hiện này, ta đã dùng con trỏ thay cho mảng tĩnh với kích thước tối đa của mỗi phần tử mảng tĩnh là 100. Do vậy cần bao nhiêu bộ nhớ ta sẽ cấp phát từng ấy sau, chứ ta không cấp phát một khối lớn ngay từ đầu mà đôi khi không dùng hết.

Sau đây ta xét một ví dụ cấp phát bộ nhớ động cho trường tên.

void AddName(PhoneBook* pb, char* name)
{
    int len = strlen(name); /* Trả về kích thước của 'name',đây là bước tính toán kích thước bộ nhớ cần thiết để chứa 'name' */
    pb->name = new char[len + 1]; /* Để chứa 'name' trong bộ nhớ, ta cần phải chứa thêm cả ký tự kết thúc chuỗi, do vậy kích thước cần cấp phát là 'len + 1' */
    strcpy(pb->name, name); /* Sao chép nội dung (tên cần chèn) vào phần bộ nhớ đã cấp phát */
}

void main(void)
{
    AddName(&data[0], "VNDzone"); /* Gọi hàm để thực hiện việc thêm tên vào một danh bạ */
}

Trong ví dụ trên ta đã thấy việc tính toán kích thước cần thiết để cấp phát bộ nhớ được đảm nhiệm bởi hàm strlen(). Và có thể các bạn cũng đã nhận ra chương trình ví dụ trên đã không động hoàn toàn, bởi vì mảng data[1000] vẫn có kích thước tối đa cố định là 1000 (struct DanhBa data[1000]).

Phần ten, diachi, sodt và những thành phần tương tự trong danh bạ (DanhBa) được cấp phát động để có thể mở rộng hoặc thu hẹp lại trong trường hợp cần thiết. Tuy vậy ta vẫn cần dự đoán trước kích thước tối đa của mảng các cấu trúc DanhBa ngay từ ban đầu, cho dù là bạn có dùng cú pháp của kỹ thuật cấp phát động ở đây thì việc có mặt của con số thể hiện kích thước tối đa của mảng cấu trúc DanhBa là việc cần thiết.

struct DanhBa* data = new DanhBa[1000];

Dù ta có thể điều chỉnh kích thước của mảng trên trong thời gian chạy runtime, nhưng việc này sẽ phải trả một cái giá quá lớn, đó chính là hiệu năng và thời gian thực hiện chương trình sẽ tăng lên rất nhiều.

Có cách nào để khiến chương trình trên động hoàn toàn?

Để có thể dùng phương pháp cấp phát động linh hoạt cho toàn bộ chương trình trên mà không cần khai báo trước kích thước tối đa của mảng cấu trúc DanhBa, ta có thể sử dụng danh sách liên kết (linked list).

Để hiểu được lý do tại sao danh sách liên kết lại làm được điều này và cách thức hoạt động của nó mời các bạn đọc bài tiếp theo Danh sách liên kết đơn.

Uncategorized

Cấp phát động

Để lại một bình luận Hủy