Bài trước coi bộ nhớ là một dãy địa chỉ dài, và đo xem đọc ở mỗi tầng tốn bao lâu. Bài này cho thấy dãy địa chỉ đó là một ảo ảnh có chủ đích. Thí nghiệm mở đầu:
volatile char *q = malloc((size_t)256 << 30); // 256 GiB
printf("%s\n", q ? "succeeded" : "failed"); // succeeded
Trên một máy có ít RAM hơn 256 GiB rất nhiều, malloc vẫn thành công, và gần như không tốn thêm một byte RAM nào. Để hiểu vì sao, cần đi qua cách một chương trình nhìn thấy bộ nhớ.
Lộ trình: không gian địa chỉ của một tiến trình, stack, heap (và một list Python thật ra tốn bao nhiêu), bộ nhớ ảo và trang nhớ, cái giá của lần chạm đầu tiên, dịch địa chỉ và TLB, segfault, rồi vài hệ quả thực tế.
Mọi con số trong bài đều đo trên máy thật, bằng C (clang) và Python 3.12, một luồng. Hệ điều hành ở đây là macOS; Linux và Windows làm cùng những việc này với vài khác biệt về con số, được nói rõ khi cần.
Mỗi chương trình một thế giới riêng
In địa chỉ của bốn thứ trong một chương trình C: một hàm, một biến toàn cục, một vùng malloc, và một biến cục bộ:
int global = 1;
int main(void) {
int local = 2;
int *heap = malloc(sizeof(int));
printf("code (main) %p\n", (void *)main);
printf("global variable %p\n", (void *)&global);
printf("heap (malloc) %p\n", (void *)heap);
printf("stack (local) %p\n", (void *)&local);
}
Chạy hai lần:
lần 1 lần 2
code 0x104b684f8 0x1005584f8
global 0x104b70000 0x100560000
heap 0x105335c40 0x100aa1c40
stack 0x16b29678c 0x16f8a678c
Hai điều đáng chú ý. Thứ nhất, các vùng nằm theo một bố cục quen thuộc: code và biến toàn cục ở thấp, heap phía trên chúng, stack ở xa phía trên. Thứ hai, mỗi lần chạy, địa chỉ lại khác. Hệ điều hành cố ý xáo vị trí các vùng ở mỗi lần chạy (ASLR, address space layout randomization), để kẻ tấn công không đoán trước được hàm hay dữ liệu nằm ở đâu.
Và điều quan trọng nhất không thấy được trong bảng: đây đều là địa chỉ ảo. Hai chương trình chạy cùng lúc hoàn toàn có thể cùng dùng địa chỉ 0x100560000, mà mỗi chương trình thấy dữ liệu của riêng mình ở đó. Mỗi tiến trình có một không gian địa chỉ riêng; con chip và hệ điều hành cùng nhau dịch địa chỉ ảo sang địa chỉ thật trong RAM.
Stack: nhanh, tự dọn, và có giới hạn
Mỗi lần gọi hàm, chương trình cần chỗ cho biến cục bộ và cho địa chỉ để quay về sau khi hàm xong. Chỗ đó là một khung (frame) trên stack: một vùng nhớ mà CPU giữ một thanh ghi trỏ tới đỉnh. Gọi hàm thì đỉnh dịch xuống một đoạn (stack mọc từ địa chỉ cao xuống thấp), trả về thì dịch lại. Cấp phát và giải phóng trên stack chỉ là một phép cộng trừ vào một thanh ghi, nên rất nhanh, và tự động: biến cục bộ biến mất khi hàm trả về.
Cái giá là stack có kích thước cố định, chọn từ lúc tạo luồng:
| Kích thước stack | |
|---|---|
Luồng chính (giới hạn mặc định, ulimit -s) |
8.176 KiB (~8 MiB) |
| Một luồng mới tạo (mặc định của hệ điều hành này) | 512 KiB |
Trên Linux, luồng mới thường cũng được 8 MiB (bài Python chạy đồng thời thế nào đã nhắc con số đó). Đệ quy quá sâu thì vượt khỏi vùng đó, gọi là tràn stack (stack overflow), và chương trình bị dừng. Giới hạn đệ quy mặc định của Python, 1.000 tầng (sys.getrecursionlimit()), một phần là để chặn trước khi điều đó xảy ra với stack của chính trình thông dịch.
Heap: sống lâu hơn hàm đã tạo ra nó
Thứ gì cần sống lâu hơn hàm tạo ra nó, hoặc có kích thước chỉ biết lúc chạy, thì nằm trên heap: malloc xin một vùng, free trả lại. Bộ cấp phát phải tìm chỗ trống vừa kích thước, ghi nhớ vùng nào đang dùng, và gom lại chỗ trống khi được trả; chậm hơn stack nhiều, nhưng linh hoạt.
Trong Python, mọi object đều nằm trên heap. Đo một list một triệu số nguyên bằng tracemalloc, so với array của thư viện chuẩn chứa cùng các con số dưới dạng số 64-bit thô:
import array, tracemalloc
tracemalloc.start()
a = [i + 1000 for i in range(1_000_000)]
print(tracemalloc.get_traced_memory()[0]) # bytes in use
| Tổng | Mỗi số | |
|---|---|---|
list các int |
40,4 MB | 40,4 byte |
array("q", ...) |
8,2 MB | 8,2 byte |
Mỗi phần tử của list tốn 8 byte cho con trỏ, cộng 32 byte cho object số nguyên (28 byte thật, làm tròn lên theo bộ cấp phát). Gấp gần 5 lần một số 64-bit trần. Bài trước đã cho thấy cái giá thứ hai của cách lưu này: các object rải rác, và đi qua chúng theo thứ tự lộn xộn chậm hơn 7,6 lần.
Bộ nhớ ảo: malloc chỉ là một lời hứa
Hệ điều hành chia bộ nhớ thành các trang (page) có kích thước cố định. Trên máy này một trang là 16 KiB; trên phần lớn máy x86 và Linux là 4 KiB. Với mỗi tiến trình, hệ điều hành giữ một bảng trang (page table) ghi: trang ảo này ứng với trang thật nào trong RAM, hoặc chưa ứng với trang nào cả.
Khi chương trình malloc một vùng lớn, hệ điều hành chỉ ghi lại rằng dải địa chỉ đó được phép dùng. Nó chưa cấp trang RAM nào. Chỉ khi chương trình chạm (đọc hay ghi) vào một trang lần đầu tiên, CPU mới phát hiện trang đó chưa có trong bảng, dừng chương trình lại và báo cho hệ điều hành: một page fault. Hệ điều hành tìm một trang RAM trống, xóa nó về 0, ghi vào bảng trang, rồi cho chương trình chạy tiếp như chưa có chuyện gì.
Thí nghiệm: xin 512 MiB, rồi chạm lần lượt vào từng trang, theo dõi bộ nhớ thật mà tiến trình dùng (resident) và số page fault:
volatile char *p = malloc(512u << 20);
for (size_t i = 0; i < size; i += page) p[i] = 1; // first touch: the OS has to find a real page
| Thời điểm | RAM thật đã dùng (đỉnh) | Số page fault |
|---|---|---|
| Lúc bắt đầu | 1,3 MiB | 289 |
Sau malloc(512 MiB) |
1,3 MiB | 291 |
| Sau khi chạm vào mọi trang | 513,3 MiB | 33.059 |
| Sau 5 lượt chạm nữa | 513,3 MiB | 33.067 (không tăng) |
Sau malloc(256 GiB) |
513,6 MiB | 33.077 |
| Sau khi chạm 2 byte trong 256 GiB đó | 513,6 MiB | 33.079 |
malloc(512 MiB)không tốn thêm chút RAM nào.- Chạm vào từng trang thì RAM tăng đúng 512 MiB, và số page fault tăng khoảng 32.768, đúng bằng số trang 16 KiB trong 512 MiB.
- Những lượt chạm sau không gây thêm page fault: các trang đã có thật.
malloc(256 GiB)thành công, và chạm vào hai đầu của nó chỉ tốn hai page fault, hai trang, 32 KiB RAM.
Thời gian cho mỗi trang:
| Mỗi trang | |
|---|---|
| Lần chạm đầu (có page fault) | khoảng 1,3–1,6 µs |
| Các lần sau | 7,5 ns |
Lần chạm đầu đắt gần 200 lần: mỗi page fault là một chuyến đi vào hệ điều hành, tìm trang trống, xóa 16 KiB về 0, cập nhật bảng trang. Đó là lý do một chương trình cấp phát một vùng nhớ lớn thường chậm ở lần dùng đầu tiên, và vì sao các chương trình cần độ trễ ổn định (database, game) hay "chạm trước" bộ nhớ của mình lúc khởi động.
Nếu chương trình thực sự chạm vào nhiều trang hơn RAM có? Hệ điều hành phải lấy lại trang từ đâu đó: nén các trang ít dùng (macOS làm việc này trước tiên), ghi chúng ra đĩa (swap), hoặc, trên Linux khi hết cách, chọn một tiến trình để dừng hẳn (OOM killer). Lời hứa của malloc rẻ; thực hiện lời hứa thì không.
Dịch địa chỉ và TLB
Mỗi lần đọc bộ nhớ, địa chỉ ảo phải được dịch sang địa chỉ thật. Bảng trang lớn, và được tổ chức thành nhiều tầng (một bảng của các bảng), nên tra một địa chỉ có thể cần đọc vài lần vào chính bộ nhớ. Nếu mỗi lần đọc dữ liệu lại kéo theo vài lần đọc bảng trang, mọi thứ sẽ chậm đi nhiều lần.
Lời giải lại là một cache: TLB (translation lookaside buffer), một bộ nhớ rất nhỏ trong CPU giữ những bản dịch vừa dùng. Trúng TLB, việc dịch gần như miễn phí. Trượt TLB, CPU phải tự đi dò bảng trang (page walk), mất thêm nhiều chu kỳ. TLB chỉ chứa được một số bản dịch nhất định, nên dữ liệu trải trên càng nhiều trang thì càng hay trượt. Đó là một phần lý do độ trễ ở bài trước tăng dần ngay trong vùng cache L2 thay vì phẳng: đọc ngẫu nhiên trên 16 MiB nghĩa là rải đều trên 1.024 trang khác nhau.
Đây cũng là lý do kích thước trang quan trọng. Trang 16 KiB có nghĩa là mỗi bản dịch trong TLB phủ được gấp 4 lần vùng nhớ so với trang 4 KiB. Các hệ thống cần nhiều bộ nhớ (database, máy ảo, huấn luyện mô hình) thường dùng thêm trang lớn (huge page, vài MiB mỗi trang) để TLB phủ được nhiều hơn nữa.
Segfault: khi chạm vào chỗ không được phép
Bảng trang không chỉ ghi trang ảo ứng với trang thật nào, mà còn ghi quyền: trang này được đọc, được ghi, được chạy như code hay không. Code thường chỉ được đọc và chạy, không được ghi; dữ liệu được đọc và ghi, không được chạy. Địa chỉ 0 và vùng quanh nó không ứng với trang nào cả.
Khi chương trình chạm vào một trang không có trong bảng (chưa từng được cấp, hoặc đã free và trả lại), hay làm việc mà quyền của trang không cho phép, CPU cũng báo page fault. Nhưng lần này hệ điều hành không có gì để "sửa", nên nó dừng chương trình: segmentation fault. Đọc qua con trỏ NULL là trường hợp phổ biến nhất. Cũng chính cơ chế này giữ cho các tiến trình không đọc được bộ nhớ của nhau: một tiến trình chỉ có thể chạm vào những trang có trong bảng của chính nó.
Python gần như không bao giờ segfault trong code bình thường, vì nó không cho bạn cầm con trỏ trần: mọi truy cập đi qua object và được kiểm tra. Khi một chương trình Python có segfault, thủ phạm gần như luôn là một phần mở rộng viết bằng C.
Vài hệ quả thực tế
forkrẻ nhờ copy-on-write. Tạo một tiến trình con không chép toàn bộ bộ nhớ: hai tiến trình dùng chung các trang thật, đánh dấu chỉ đọc, và chỉ khi một bên ghi vào một trang thì trang đó mới được chép ra. Đó là nền tảng của các server chạy nhiều tiến trình con.mmapmột file: ánh xạ file vào không gian địa chỉ, và các trang của file chỉ được đọc từ đĩa khi bị chạm tới. Đó là cách các file trọng số mô hình lớn (như định dạng safetensors ở bài 2 của seri LLM) có thể "mở" gần như tức thì: phần lớn công việc đọc được hoãn tới lúc thật sự cần.- Bộ nhớ "dùng" là một con số mơ hồ. Bộ nhớ ảo (đã hứa), bộ nhớ thường trú (đang có trang thật), bộ nhớ dùng chung với tiến trình khác: các công cụ theo dõi hiển thị những con số khác nhau, và một tiến trình với "256 GiB" bộ nhớ ảo có thể chỉ đang dùng vài MiB.
- Cấu trúc dữ liệu gọn tiết kiệm hai lần.
arrayhay NumPy thay cho list số nguyên tiết kiệm 5 lần bộ nhớ, và cũng ít trang hơn, ít trượt TLB hơn, ít trượt cache hơn.
Tóm lại
| Khái niệm | Thực chất |
|---|---|
| Không gian địa chỉ | Mỗi tiến trình có dãy địa chỉ ảo riêng; ASLR xáo vị trí mỗi lần chạy |
| Stack | Khung cho mỗi lời gọi hàm; cấp phát bằng một phép trừ; ~8 MiB cho luồng chính, 512 KiB cho luồng mới ở đây |
| Heap | malloc/free; mọi object Python ở đây; một int trong list tốn ~40 byte |
| Trang | Đơn vị của bộ nhớ ảo: 16 KiB ở đây, 4 KiB trên phần lớn x86 |
malloc |
Chỉ là lời hứa: 512 MiB hay 256 GiB đều không tốn RAM cho tới khi chạm |
| Page fault | Lần chạm đầu: ~1,3–1,6 µs mỗi trang, so với 7,5 ns cho các lần sau |
| TLB | Cache của các bản dịch địa chỉ; trượt thì phải dò bảng trang |
| Segfault | Chạm vào trang không có hoặc không đủ quyền; hệ điều hành dừng chương trình |
Ai giữ bảng trang, ai xử lý page fault, ai quyết định tiến trình nào được chạy trên lõi CPU nào, và ai nói chuyện với GPU? Hệ điều hành. Bài sau: kernel, system call, lập lịch, và vì sao CPU với GPU được thiết kế cho hai kiểu công việc rất khác nhau.