Page fault, swap & thrashing — khi trang không có trong RAM

TL;DR: Khi CPU truy cập một địa chỉ ảo và trang tương ứng không có trong RAM, phần cứng phát một page fault — trap vào OS để xử lý. OS phân biệt minor fault (trang đã trong RAM, chỉ cần cập nhật ánh xạ) và major fault (phải nạp từ đĩa — chậm hàng chục nghìn lần so với RAM). Demand paging tận dụng điều này: OS cấp địa chỉ ảo ngay nhưng chỉ gán RAM vật lý khi trang bị chạm thật. Khi RAM đầy, OS chọn trang ít dùng để swap ra đĩa. Nếu working set (tập trang đang dùng tích cực) vượt RAM, hệ thống rơi vào thrashing — gần như đứng vì liên tục swap thay vì tính toán.

Bạn gọi malloc(1 << 30) — cấp phát 1 GB — và hàm trả về ngay tức thì trên máy chỉ có 512 MB RAM còn trống. Sau đó bạn lần lượt ghi vào từng trang, và cứ mỗi lần ghi đầu tiên vào một trang mới, chương trình dừng một chút rồi chạy tiếp. Điều gì đang xảy ra?

Câu trả lời là demand paging — OS không thật sự cấp RAM khi bạn malloc; nó chỉ hứa dải địa chỉ ảo. RAM vật lý chỉ được gán khi bạn chạm vào trang lần đầu, thông qua một page fault. Bài này giải thích cơ chế đó từ đầu đến cuối — và cả cái bẫy thrashing khi mọi thứ đi sai hướng.

1. Analogy — thư viện với sách theo yêu cầu

Hình dung một thư viện khổng lồ có hàng triệu đầu sách, nhưng kệ trong phòng đọc chỉ chứa được 1.000 cuốn cùng lúc. Thủ thư không nhét sẵn tất cả lên kệ — chỉ mang lên khi bạn yêu cầu. Nếu kệ đầy, thủ thư cất cuốn ít đọc nhất xuống kho để nhường chỗ.

2. Page fault — cơ chế bên dưới

Mỗi lần CPU phát một địa chỉ ảo, MMU tra PTE (Page Table Entry) của trang đó. PTE có một bit quan trọng: present bit (còn gọi là valid bit).

• Present bit = 1: trang đang trong RAM. MMU tính ra địa chỉ vật lý và truy cập ngay — không có fault.
• Present bit = 0: trang không trong RAM. MMU phát một page fault exception — CPU trap vào kernel, nhường quyền điều khiển cho OS page fault handler. Handler kiểm tra địa chỉ ảo: nếu thuộc vùng ánh xạ hợp lệ (chỉ chưa resident) thì nạp/zero-fill trang; nếu địa chỉ không ánh xạ hợp lệ thì gửi SIGSEGV (segfault).

flowchart TD
  CPU["CPU truy cap dia chi ao VA"] --> MMU["MMU tra page table"]
  MMU --> Present{"PTE present bit?"}
  Present -->|"= 1, doc/ghi hop le"| PA["Tra ve dia chi vat ly PA<br/>→ truy cap RAM"]
  Present -->|"= 1, ghi vao trang read-only"| WP["Write-protection fault<br/>→ trap vao OS"]
  Present -->|"= 0 (khong co)"| Trap["Page fault exception<br/>→ trap vao OS kernel"]
  WP --> COW["Copy-on-write: copy trang<br/>→ map read-write (xem bai 05)"]
  Trap --> Handler["OS: page fault handler"]
  Handler --> Source{"Nguon trang?"}
  Source -->|"Demand-zero"| Zero["Cap khung vat ly moi<br/>zero-fill → map PTE"]
  Source -->|"File / swap"| Load["Doc tu disk/swap<br/>vao khung vat ly → map PTE"]
  Zero --> Retry["CPU retry lenh"]
  Load --> Retry
  COW --> Retry
  Retry --> MMU

Minor fault vs major fault

Không phải mọi page fault đều tốn kém như nhau:

Minor fault (soft fault): fault không cần đọc đĩa — hoặc trang đã nằm sẵn trong RAM/page cache (chỉ cần map vào page table của tiến trình), hoặc OS chỉ cần cấp một khung rảnh rồi zero-fill (không có dữ liệu phải nạp từ backing store). Chỉ cập nhật PTE rồi trả về. Ví dụ:

• Demand-zero page: lần đầu tiên chạm trang mới cấp phát — OS chỉ cần lấy một khung vật lý rảnh, zero-fill, cập nhật PTE.
• Shared page (COW): nhiều tiến trình dùng chung trang read-only, minor fault để map vào không gian của tiến trình mới.
• File đã trong page cache: file được mmap nhưng trang đang nằm trong page cache kernel.

Major fault (hard fault): trang không có trong RAM, phải đọc từ đĩa hoặc swap. Đây là trường hợp chậm — I/O đĩa tốn hàng trăm microsecond đến vài millisecond, gấp ~1.000 lần (SSD) đến ~100.000 lần (HDD) so với truy cập RAM (~100 ns). Ví dụ:

• Truy cập lần đầu vào trang đã bị swap-out.
• Nạp trang từ file được mmap lần đầu (executable, shared library, dữ liệu).

3. Demand paging — cấp phát lười biếng

Demand paging (hay còn gọi là lazy allocation) là chiến lược: OS cấp địa chỉ ảo ngay, nhưng không gán khung vật lý tới khi trang đó thực sự bị truy cập.

// malloc cap phat 1 GB dia chi AO ngay lap tuc
char *buf = malloc(1024 * 1024 * 1024);
// buf != NULL, nhung RAM chua duoc dung

// Lan dau ghi vao offset 0 -> minor page fault -> OS cap khung
buf[0] = 'A';

// Ghi vao offset 4096 (trang ke tiep) -> minor page fault tiep theo
buf[4096] = 'B';

Vì sao thiết kế này tồn tại? Vì phần lớn bộ nhớ cấp phát không bao giờ thực sự dùng. Một server Java khởi động với heap -Xmx4g nhưng chỉ thực sự dùng 800 MB — nếu OS cấp RAM ngay, 3.2 GB sẽ bị giữ chết. Demand paging cho phép nhiều tiến trình chia sẻ RAM vật lý hiệu quả hơn, với giả định chúng không dùng hết quota cùng lúc.

Nối với bài 01 — Pitfall 3: lý do malloc lớn không tiêu RAM ngay chính là demand paging.

4. Swap và page replacement

Swap là gì

Khi RAM đầy và OS cần thêm khung vật lý cho trang mới, nó phải lấy lại một khung đang dùng bằng cách đẩy nội dung của khung đó ra swap — vùng lưu trữ trên đĩa (partition hoặc file) dành riêng. Khi chương trình truy cập trang đã swap-out, OS đọc lại từ swap vào RAM (swap-in).

• Swap-out: chọn một trang, copy nội dung ra đĩa, đánh dấu PTE present = 0 (lưu vị trí trên swap vào PTE), giải phóng khung.
• Swap-in: trang được chạm → major page fault → OS đọc từ swap, gán khung mới, cập nhật PTE present = 1.

Page replacement — chọn trang nào để đẩy ra

OS cần thuật toán chọn "nạn nhân" khi phải swap-out. Thuật toán lý tưởng là OPT (Optimal) — đẩy trang sẽ bị dùng muộn nhất trong tương lai — nhưng không thể thực thi vì không biết tương lai.

LRU (Least Recently Used) gần tối ưu: đẩy trang ít dùng nhất gần đây. Nhưng LRU thuần cần theo dõi thứ tự truy cập chính xác — tốn kém phần cứng.

Clock algorithm (Second-chance) — LRU approximation thực tế trên Linux:

1. PTE có thêm accessed bit (còn gọi là reference bit): hardware tự set = 1 mỗi khi trang được truy cập.
2. OS chạy một "kim đồng hồ" quét qua danh sách khung tuần hoàn.
3. Khi cần swap-out: kim dừng tại khung đang xét.
   • Nếu accessed = 1: clear bit (cho thêm cơ hội thứ hai), tiến kim.
   • Nếu accessed = 0: chọn trang này để swap-out.
4. Khung bẩn (dirty bit = 1, nghĩa là đã bị ghi, khác bản trên swap) cần được ghi lại trước khi swap-out tốn thêm I/O. Khung sạch (dirty = 0) swap-out miễn phí.

flowchart LR
  NeedFrame["Can them khung<br/>(RAM day)"]
  NeedFrame --> Clock["Clock: xet khung hien tai"]
  Clock --> Acc{"Accessed bit?"}
  Acc -->|"= 1"| Clear["Clear bit = 0<br/>Tien kim sang khung ke"]
  Clear --> Clock
  Acc -->|"= 0"| Dirty{"Dirty bit?"}
  Dirty -->|"= 1 (co ghi)"| WriteBack["Ghi trang ra swap<br/>Roi chon khung nay"]
  Dirty -->|"= 0 (sach)"| Evict["Chon khung nay<br/>(swap-out mien phi)"]
  WriteBack --> Done["Giai phong khung<br/>Cap cho trang moi"]
  Evict --> Done

5. Thrashing — cái bẫy khi RAM quá đầy

Thrashing xảy ra khi tổng working set (tập trang đang thực sự dùng tích cực) của các tiến trình vượt RAM vật lý. Hệ quả:

1. OS liên tục swap-out trang của tiến trình A để nhường cho B.
2. B ngay sau đó lại fault và cần trang vừa bị swap-out.
3. CPU dành phần lớn thời gian ở kernel xử lý page fault và I/O đĩa, thay vì chạy code của các tiến trình.
4. Throughput hệ thống rơi gần về 0 dù CPU utilization trông có vẻ cao (vì đang bận xử lý fault).

Dùng thang độ trễ từ Module 2: RAM ~100 ns, đĩa HDD ~1–10 ms → chênh lệch ~10.000–100.000 lần. Chỉ cần một phần nhỏ truy cập bộ nhớ phải đi qua swap, throughput đã sụp đổ — vì mỗi lần chạm swap đắt gấp hàng chục nghìn lần so với một truy cập RAM bình thường.

Working set model (Denning, 1968): định nghĩa working set của tiến trình là tập trang được truy cập trong cửa sổ thời gian gần nhất. OS có thể đo và chỉ schedule tiến trình khi RAM đủ chứa working set của nó — ngăn thrashing bằng cách giảm mức độ multiprogramming khi RAM căng.

OOM killer: khi cả RAM và swap đều cạn, Linux OOM (Out-of-Memory) killer chọn một tiến trình để kill — ưu tiên tiến trình tiêu thụ nhiều bộ nhớ nhất (điểm oom_score, chủ yếu tính theo RSS + swap), có thể tinh chỉnh qua oom_score_adj (mặc định 0) nếu muốn ưu tiên bảo vệ hoặc hi sinh một tiến trình. Kernel không tự đánh giá tiến trình nào "quan trọng" — mặc định chỉ xét lượng bộ nhớ tiêu thụ. Đây là biện pháp cuối cùng.

6. Pitfall tổng hợp

❌ Nhầm 1: "Page fault luôn là lỗi" — Minor fault hoàn toàn bình thường và xảy ra hàng triệu lần mỗi giây trên hệ thống hoạt động. Chỉ fault vào địa chỉ ảo không hợp lệ mới sinh SIGSEGV.

❌ Nhầm 2: Swap nhanh như RAM — Swap lưu trên SSD NVMe cũng chậm hơn RAM ~1.000 lần; trên HDD còn chậm hơn ~100.000 lần. Hệ thống phụ thuộc vào swap cho workload thường xuyên sẽ rất chậm.

❌ Nhầm 3: "Máy có 32 GB swap thì không bao giờ bị thiếu bộ nhớ" — Swap không thay thế RAM; nó chỉ là lưới an toàn. Khi cần swap thường xuyên, throughput sụp đổ. OOM killer vẫn kích hoạt khi swap hết.

❌ Nhầm 4: malloc lớn tiêu RAM ngay — OS chỉ cấp địa chỉ ảo; RAM thật chỉ bị dùng khi trang bị chạm. Đây là lý do malloc(1GB) trả về ngay kể cả khi RAM trống chỉ còn 200 MB.

7. Đào sâu (tuỳ chọn)

8. Liên hệ các bài khác

• Bài 02 — Paging & page table: present bit trong PTE là trigger của mọi page fault — bài này giải thích cấu trúc PTE và cơ chế ánh xạ.
• Bài 03 — MMU & TLB: MMU là phần cứng phát page fault exception khi tra bảng và thấy present = 0; TLB miss cũng đi qua page walk trước khi fault.
• Bài 05 — mmap & copy-on-write: COW dùng page fault làm cơ chế kích hoạt copy: trang shared bị ghi → fault → OS copy trang. mmap file dùng major fault để nạp trang theo demand paging.
• Module 2 — Độ trễ tầng bộ nhớ: thang độ trễ RAM ~100 ns vs SSD ~100 µs giải thích vì sao thrashing chí mạng — swap chậm gấp ~1.000 lần RAM.

9. Tóm tắt

• Page fault xảy ra khi PTE present bit = 0 — MMU trap vào OS để xử lý.
• Minor fault: trang đã trong RAM, chỉ cần cập nhật PTE — nhanh (~µs). Major fault: phải đọc từ đĩa/swap — chậm (~100 µs–ms).
• Demand paging: OS cấp địa chỉ ảo ngay nhưng chỉ gán RAM vật lý khi trang bị chạm lần đầu — lý do malloc lớn trả về tức thì.
• Swap: khi RAM đầy, OS đẩy trang ít dùng ra đĩa (swap-out). Clock algorithm dùng accessed bit và dirty bit để chọn nạn nhân.
• Thrashing: working set vượt RAM → OS swap liên tục → CPU dành phần lớn thời gian chờ I/O → throughput sụp đổ.
• OOM killer là biện pháp cuối khi cả RAM và swap đều hết — kill tiến trình để giải phóng bộ nhớ.

10. Tự kiểm tra

Bài tiếp theo: mmap & copy-on-write