10.5K 783 122

Đã đăng vào thg 11 15, 2023 5:44 SA 18 phút đọc

1.1K

Bài 14: Cấp phát bộ nhớ động và Danh sách liên kết (phần 1) - Kĩ thuật Cấp phát bộ nhớ động

I. Phân loại các vùng nhớ trên bộ nhớ ảo

Qua một số bài học về con trỏ, chúng ta đã biết rằng việc lưu trữ dữ liệu trong khi lập trình C++ được quản lý dựa trên kĩ thuật Bộ nhớ ảo (Virtual Memory). Việc nắm rõ các phân vùng của bộ nhớ ảo và chức năng của chúng rất quan trọng trong khi lập trình, nó sẽ giúp lập trình viên hiểu rõ cơ chế lưu trữ dữ liệu, từ đó quản lý bộ nhớ một cách hợp lý. Vậy trong bài học này, trước hết chúng ta sẽ cùng nhau tổng hợp về chức năng của một số phân vùng trên bộ nhớ ảo.

Hình dưới đây mô tả thứ tự của các phân vùng trên bộ nhớ ảo:

Chức năng của các phân vùng này lần lượt được mô tả như sau:

Code Segment: Là nơi mà lưu trữ các mã lệnh đã được biên dịch của các chương trình máy tính. Những mã lệnh trong phân vùng này sẽ được chuyển đến CPU xử lý khi cần thiết. Code Segment chỉ chịu sự chi phối của hệ điều hành, các tác nhân khác không thể can thiệp trực tiếp đến phân vùng này. Việc đưa các mã lệnh đã được biên dịch của chương trình lên phân vùng Code Segment là công việc đầu tiên mà hệ điều hành cần làm khi chúng ta chạy chương trình.
Data Segment: Là phân vùng mà hệ điều hành sử dụng để khởi tạo giá trị cho các biến kiểu static, biến toàn cục của các chương trình.
.bss Segment: Cũng được dùng để lưu trữ các biến kiểu static, biến toàn cục nhưng chưa được khởi tạo giá trị cụ thể.
Heap Segment: Là vùng nhớ được sử dụng để cấp phát bộ nhớ cho chương trình thông qua kĩ thuật Cấp phát bộ nhớ động mà chúng ta sẽ đề cập ở phần bên dưới. Phân vùng này có dung lượng lưu trữ lớn nhất trong các phân vùng.
Call Stack Segment: Call Stack (thường được gọi là Stack) được dùng để cấp phát bộ nhớ cho tham số của các hàm vàà biến cục bộ của chương trình. Vùng nhớ này được xây dựng dựa trên cấu trúc dữ liệu Stack (các bạn không cần quá quan tâm đến cấu trúc này vội). Khi bắt gặp một dòng lệnh khai báo biến, nếu biến đó là biến cục bộ hoặc tham số hàm, nó sẽ được cấp phát tại địa chỉ lớn nhất hiện tại trên Stack. Khi một biến cục bộ hoặc tham số của hàm ra khỏi phạm vi khối lệnh, nó sẽ được đưa ra khỏi Stack.
Để kiểm chứng điều này, các bạn có thể chạy thử một đoạn chương trình như sau:
```
int main()
{
    int n1, n2, n3, n4, n5;

    cout << "Address of " << &n1 << endl;
    cout << "Address of " << &n2 << endl;
    cout << "Address of " << &n3 << endl;
    cout << "Address of " << &n4 << endl;
    cout << "Address of " << &n5 << endl;

    return 0;
}
```
Đoạn chương trình trên khai báo $5$ biến cục bộ liên tiếp nhau. Nếu trong trường hợp tại thời điểm khai báo, chỉ có chương trình này được CPU xử lý, chúng ta sẽ thấy địa chỉ của $5$ biến cục bộ này có địa chỉ liên tiếp nhau.

Địa chỉ sau cách địa chỉ trước đó đúng bằng kích thước của kiểu dữ liệu int. Như vậy, lần lượt biến n1 n2 n3 n4 và n5 được cấp phát tại những địa chỉ tiếp theo (từ thấp đến cao) trên phân vùng Stack, và khi ra khỏi hàm main(), lần lượt biến $n5, n4, n3, n2$ và $n1$ sẽ bị đưa ra khỏi Stack.

II. Kĩ thuật cấp phát bộ nhớ động

1. Các kiểu cấp phát bộ nhớ đối với biến toàn cục và biến cục bộ

Như chúng ta đã biết trước đây, trong C++ có hai kiểu khai báo biến là Biến toàn cục và Biến cục bộ. Thời gian tồn tại của biến sẽ phụ thuộc vào vị trí khai báo biến:

Biến toàn cục (global variable) được khai báo bên ngoài khối lệnh, có thể được truy xuất tại bất cứ dòng lệnh nào đặt bên dưới biến đó. Biến toàn cục tồn tại đến khi chương trình bị kết thúc.
Biến cục bộ (local variable) được khai báo bên trong khối lệnh, có thể được truy xuất tại bất cứ dòng lệnh nào đặt bên dưới biến đó và trong cùng khối lệnh. Biến cục bộ bị hủy khi chương trình chạy ra ngoài khối lệnh chứa biến đó.

Tương ứng với hai kiểu khai báo này, sẽ có hai cách thức cấp phát bộ nhớ cho chương trình trên bộ nhớ ảo:

Cấp phát bộ nhớ tĩnh (Static memory allocation)

Static memory allocation còn được gọi là Compile-time allocation, được áp dụng cho biến static và biến toàn cục. Đặc điểm của nó như sau:

Vùng nhớ của các biến này được cấp phát ngay khi chạy chương trình, và cấp phát trên vùng nhớ Data hoặc .bss.
Kích thước của vùng nhớ được cấp phát phải được cung cấp tại thời điểm biên dịch chương trình.
Đối với việc khai báo mảng một chiều, đây là lý do tại sao số lượng phần tử là hằng số.

Cấp phát bộ nhớ tự động (Automatic memory allocation)

Automatic memory allocation được sử dụng để cấp phát vùng nhớ cho các biến cục bộ, tham số của hàm. Đặc điểm của nó như sau:

Bộ nhớ được cấp phát tại thời điểm chương trình đang chạy, khi chương trình đi vào một khối lệnh.
Các vùng nhớ được cấp phát sẽ được thu hồi khi chương trình đi ra khỏi một khối lệnh.
Kích thước vùng cần cấp phát cũng phải được cung cấp rõ ràng.

Vấn đề tràn bộ nhớ stack (Stack over flow)

Như đã nói ở phần I, bộ nhớ ảo được chia thành nhiều phân vùng khác nhau dành cho những loại tài nguyên khác nhau. Trong đó, riêng phương thức cấp phát bộ nhớ tự động (Automatic memory allocation) sẽ sử dụng phân vùng Stack để lưu trữ. Hình dung lại bộ nhớ ảo như hình dưới đây:

Phân vùng Stack được đặt tại vùng có địa chỉ cao nhất trong dãy bộ nhớ ảo. Dung lượng của phân vùng này khá hạn chế. Tùy vào mỗi hệ điều hành mà dung lượng bộ nhớ của phân vùng Stack khác nhau. Đối với Visual studio 2015 chạy trên hệ điều hành Windows, dung lượng bộ nhớ của phân vùng Stack là khoảng 1MB (tương đương khoảng $1024$ Kilobytes hay $1024 \times 1024$ bytes).

Với sự hạn chế về dung lượng bộ nhớ của phân vùng Stack, chương trình của chúng ta sẽ phát sinh lỗi stack overflow nếu các bạn yêu cầu cấp phát vùng nhớ vượt quá dung lượng của Stack. Đây cũng chính là lí do mà việc khai báo mảng tĩnh là biến cục bộ rất dễ phát sinh lỗi tràn bộ nhớ Stack, các bạn có thể chạy thử hai đoạn chương trình sau để kiểm chứng:

Chương trình 1:
```
int main()
{
    char ch_array[1024 * 1000];

    return 0;
}
```
Trong đoạn chương trình này, một mảng kiểu char với kích thước $1024 \times 1000$ đã được khai báo. Như chúng ta đã biết, một phần tử kiểu char sẽ có kích thước 1 byte, vậy thì $1024 \times 1000$ phần tử kiểu char sẽ được cấp phát $1000$ kilobytes trên vùng nhớ Stack (vì mảng khai báo là biến cục bộ). Chương trình này vẫn sẽ chạy bình thường vì vẫn chưa vượt quá giới hạn 1 Megabyte của Stack.
Chương trình 2:
```
int main()
{
    char ch_array[1024 * 1024];

    return 0;
}
```
Kích thước vùng nhớ được yêu cầu cấp phát bây giờ là đúng bằng 1 Mb. Thử chạy chương trình ở chế độ Debug, Visual Studio 2015 trên máy tính đưa ra thông báo:

Nếu như nộp đoạn code trên ở những trang chấm bài online judge, các bạn sẽ bị báo lỗi NZEC, đó là lỗi tràn bộ nhớ. Lỗi này là do việc yêu cầu cấp phát một vùng nhớ kích thước 1MB đã gây tràn bộ nhớ Stack.

Để khắc phục hạn chế này, phần tiếp theo sẽ giới thiệu đến các bạn một phương thức cấp phát bộ nhớ mới được ngôn ngữ C++ hỗ trợ, đó là Cấp phát bộ nhớ động.

2. Kĩ thuật cấp phát bộ nhớ động (Dynamic memory allocation)

Cấp phát bộ nhớ động (Dynamic memory allocation) là một giải pháp cấp phát bộ nhớ cho chương trình tại thời điểm chương trình đang chạy (run-time). Dynamic memory allocation sử dụng phân vùng Heap trên bộ nhớ ảo để cấp phát cho chương trình. Đây là phân vùng có dung lượng lớn nhất trong bộ nhớ ảo. Do đó, bộ nhớ dùng để cấp phát cho chương trình trên phân vùng Heap chỉ bị giới hạn bởi thiết bị phần cứng (ví dụ là RAM) chứ không phụ thuộc vào hệ điều hành. Trong các máy tính hiện đại ngày nay, dung lượng bộ nhớ của phân vùng Heap có thể lên đến đơn vị GB.

Cần lưu ý, Kỹ thuật Dynamic memory allocation dùng để cấp phát bộ nhớ tại thời điểm run-time. Tại thời điểm này, chúng ta không thể tạo ra tên biến mới, mà chỉ có thể tạo ra vùng nhớ mới. Do đó, cách duy nhất để kiểm soát được những vùng nhớ được cấp phát bằng kỹ thuật Dynamic memory allocation là sử dụng con trỏ lưu trữ địa chỉ đầu tiên của vùng nhớ được cấp phát, thông qua con trỏ để quản lý vùng nhớ trên Heap.

Như vậy, việc thực hiện cấp phát bộ nhớ cần qua hai bước:

Yêu cầu cấp phát vùng nhớ trên Heap.
Lưu trữ địa chỉ của vùng nhớ vừa được cấp phát bằng con trỏ.

Yêu cầu cấp phát vùng nhớ

Ta sử dụng toán tử new để yêu cầu cấp phát vùng nhớ trên Heap. Toán tử này trả về một con trỏ kiểu void*. Cú pháp như sau:

new {Kiểu_dữ_liệu};

Lấy ví dụ:

new int; // Xin cấp phát 4 bytes trên Heap cho 1 biến int.
new double; // Xin cấp phát 8 bytes trên Heap cho 1 biến double.

Toán tử new sau khi xin cấp phát vùng nhớ trên Heap sẽ trả về một con trỏ chứa địa chỉ của vùng nhớ được cấp phát (nếu cấp phát thành công). Do đó chúng ta cần gán nó cho những con trỏ cùng kiểu để quản lý, như ví dụ dưới đây:

int* p_int = new int;
double* p_double = new double;

Sau khi vùng nhớ được cấp phát, nó sẽ được quản lý bởi hai con trỏ \text{p_int} và \text{p_double}; tức là hai vùng nhớ này được hệ điều hành trao quyền sử dụng tạm thời. Ta có thể thay đổi giá trị của hai vùng nhớ đó thông qua hai con trỏ:

int* p_int = new int;
cin >> *p_int; // Chẳng hạn nhập vào số 5.
cout << "Value at " << p_int << " is " << *p_int; // Value at 0x2084a138 is 5.

Nếu muốn, các bạn có thể khởi tạo giá trị ban đầu cho các vùng nhớ này, thông qua cú pháp bên dưới:

int* p1 = new int(5); // Khởi tạo giá trị 5 cho *p1.
int* p2 = new int{*p1}; // Copy giá trị *p1 vào *p2.

Trả lại vùng nhớ khi không cần sử dụng nữa

Khi không muốn sử dụng tiếp vùng nhớ đã được cấp phát cho chương trình trên Heap, chúng ta nên trả lại vùng nhớ đó cho hệ điều hành. Thật ra khi chương trình kết thúc, tất cả vùng nhớ của chương trình đều bị hệ điều hành thu hồi, nhưng chúng ta nên giải phóng vùng nhớ không cần thiết càng sớm càng tốt.

Để xóa một vùng nhớ, chúng ta cần có một địa chỉ cụ thể, địa chỉ đó được giữ bởi con trỏ sau khi gán địa chỉ cấp phát cho nó. Sau đó, ta sử dụng toán tử delete để trả lại vùng nhớ cho hệ điều hành:

// Using memory area at p.
int* p = new int;

// then set it free.
delete p;

Nhiều người nhầm tưởng rằng toán tử delete sẽ "xóa toàn bộ" mọi thứ liên quan tới vùng nhớ đã được cấp phát trên Heap. Nhưng thực ra, toán tử new và delete chỉ mang ý nghĩa về "quyền sử dụng vùng nhớ", chứ không tác động gì đến con trỏ. Tức là, toàn bộ dãy địa chỉ trên bộ nhớ ảo được quản lý bởi một chương trình mang tên "Hệ điều hành", và hệ điều hành có quyền trao lại quyền sử dụng một vùng nhớ nào đó (trên Stack hoặc trên Heap...) cho những chương trình đáng tin cậy trên máy tính.

Toán tử new dùng để làm hợp đồng sử dụng vùng nhớ trên Heap, các bạn lấy vùng nhớ được cấp phát thông qua "hợp đồng" để chương trình chạy, vậy khi bạn sử dụng toán tử delete, đơn giản là bạn chỉ xé bản hợp đồng đó đi (hoặc đưa lại cho hệ điều hành). Lúc này, Giá trị trên vùng nhớ đó có thể vẫn còn giữ nguyên do chưa có chương trình nào can thiệp vào. Còn nếu như có một chương trình nào đó sử dụng tới vùng nhớ này, thì các bạn không thể tác động tới vùng nhớ đó nữa (nếu cố làm như vậy thì chương trình sẽ bị crash).

Con trỏ bị treo (Dangling pointer)

Tình trạng "con trỏ bị treo" thường xảy ra sau khi giải phóng vùng nhớ bằng toán tử delete. Sau khi sử dụng toán tử delete, vùng nhớ được cấp phát được trả lại cho hệ điều hành quản lý, nhưng con trỏ vẫn còn trỏ vào địa chỉ đó. Sử dụng toán tử * cho con trỏ tại thời điểm này sẽ gây ra lỗi Undefined behavior.

Cùng xem ví dụ dưới đây:

#include <iostream>

using namespace std;

int main()
{
    int* ptr = new int; // Cấp phát động một vùng nhớ int.
    *ptr = 7; // Gán giá trị 7 cho vùng nhớ vừa xin cấp phát.
 
    delete ptr; // Trả lại vùng nhớ cho HĐH. Bây giờ con trỏ ptr đang bị treo.
 
    // Truy cập giá trị của vùng nhớ bây giờ sẽ bị lỗi undefined behavior.
    cout << *ptr; 
    delete ptr; // Giải phóng vùng nhớ thêm một lần nữa cũng sẽ gặp lỗi.
 
    return 0;
}

III. Cấp phát động cho mảng một chiều

Ứng dụng hai toán tử new và delete, chúng ta có thể cấp phát bộ nhớ động cho mảng một chiều trên Heap.

Cú pháp cấp phát động

Đối với việc yêu cầu cấp phát bộ nhớ cho biến đơn trên Heap, chúng ta chỉ cần cung cấp kiểu dữ liệu cho toán tử new, hệ điều hành sẽ tự tính được kích thước cần cấp phát (tương tự việc sử dụng toán tử sizeof). Nhưng khi cần cấp phát một dãy vùng nhớ liên tục nhau (mảng một chiều), ngoài kiểu dữ liệu chúng ta cần cung cấp thêm số lượng phần tử:

{Kiểu_dữ_liệu} {Tên_con_trỏ} = new {Kiểu_dữ_liệu}[{Số_lượng_phần_tử}];

Nếu quá trình cấp phát thành công, toán tử new sẽ trả về địa chỉ của phần tử đầu tiên của vùng nhớ được cấp phát, do đó chúng ta cần dùng một con trỏ có kiểu dữ liệu phù hợp lưu trữ địa trả về để quản lý vùng nhớ. Ví dụ:

int* p_arr = new int[10];

// Nhập dữ liệu cho mảng trên vùng nhớ đã cấp phát.
for (int i = 0; i < 10; ++i)
    cin >> *p_arr[i];

Nếu muốn khởi tạo giá trị ban đầu cho mảng theo cách cấp phát động, thì ta cũng làm giống như mảng một chiều thông thường:

int arr[5] = { 1, 2, 3, 4, 5 }; // Cách thông thường.
int* p_arr = new int[5] { 1, 2, 3, 4, 5 }; // Cấp phát động. Lưu ý không có dầu =.

Tuy nhiên, các bạn lưu ý cách làm này chỉ sử dụng được trong chuẩn C++11 trở lên.

Thu hồi vùng nhớ đã cấp phát

Sử dụng toán tử delete, chúng ta sẽ trả lại vùng nhớ đã cấp phát cho hệ điều hành. Tuy nhiên, do mảng một chiều là một dãy các ô nhớ liên tiếp, ta cần thêm vào cặp toán tử [] đằng sau để báo cho hệ điều hành rằng vùng nhớ đã cấp phát không phải là dành cho biến đơn:

int* p_arr = new int[10];

delete[] p_arr;

IV. Tài liệu tham khảo