Paging
& Page Replacement

9.1 Page Fault — hành trình 1 byte

Khi process truy cập 1 virtual address, MMU tra page table:

• Nếu PTE có present bit = 1: page có trong RAM → dịch sang physical address, đọc → xong
• Nếu present bit = 0: Page Fault → CPU trap vào kernel

Kernel xử lý page fault

1. Kernel kiểm tra: VA này có hợp lệ không?
   • Không hợp lệ (vd dereference NULL) → gửi SIGSEGV → process thường chết
   • Hợp lệ → tiếp
2. Tìm physical frame trống trong RAM. Nếu hết → page replacement (xem 9.4)
3. Đọc nội dung page từ disk (hoặc zero-fill nếu là anon page mới)
4. Update PTE: present = 1, frame number = frame mới chọn
5. Resume instruction bị fail — bây giờ chạy bình thường

Toàn bộ quá trình diễn ra trong vài microsecond đến vài millisecond (nếu phải đọc từ disk).

9.2 Major vs Minor Page Fault

# Đếm major/minor fault của process
ps -o min_flt,maj_flt,comm
# min_flt   maj_flt COMMAND
#   12345         3 bash     ← minor nhiều, major ít = lành mạnh
#  123456     78901 some_app  ← major cao = thrashing

9.3 TLB — Translation Lookaside Buffer

Mỗi instruction memory access đều cần dịch VA → PA qua page table. Multi-level page table = 4 memory access mỗi lần dịch → quá chậm.

TLB = cache nhỏ nằm trong MMU, lưu kết quả dịch gần đây. Hit TLB → 1 cycle. Miss TLB → vài chục cycle.

     CPU virtual address ──▶ TLB ──┬─▶ HIT  → physical address (1 cycle)
                                    │
                                    └─▶ MISS → page table walk (4 levels)
                                              → update TLB
                                              → physical address

TLB size

• L1 TLB: ~64 entries — gần CPU, 1 cycle
• L2 TLB: ~1500 entries — chậm hơn nhưng lớn
• Mỗi entry cover 1 page (4KB), nên L1 TLB cover ~256KB working set

TLB shootdown

Khi context switch giữa process A và B, TLB chứa entry của A vô nghĩa (PA của B khác). Cần "flush" hoặc tag entry với ASID (Address Space ID).

Huge Pages giúp giảm TLB miss

1 entry TLB cover 1 page. Nếu page = 2MB thay vì 4KB, cover 500x nhiều hơn → ít TLB miss. Database, JVM dùng huge pages.

# Linux: enable transparent huge pages
cat /sys/kernel/mm/transparent_hugepage/enabled
# always madvise [never]

9.4 Bài toán Page Replacement

Khi page fault xảy ra mà RAM đã hết frame trống, kernel phải "đẩy" 1 page hiện có ra disk (swap out) để lấy chỗ cho page mới. Câu hỏi: đẩy page nào?

Đó là bài toán page replacement. Mục tiêu: chọn page ít có khả năng được dùng lại sớm nhất.

Để đo hiệu quả, dùng metric: page fault rate với một dãy reference (chuỗi page truy cập).

9.5 FIFO — và Belady's Anomaly

Đẩy ra page vào RAM lâu nhất (dù vẫn đang được dùng).

Reference: 1 2 3 4 1 2 5 1 2 3 4 5
Frames=3:

Step  1   2   3   4   1   2   5   1   2   3   4   5
F1    1   1   1   4   4   4   5   5   5   5   5   5
F2        2   2   2   1   1   1   1   1   3   3   3
F3            3   3   3   2   2   2   2   2   4   4
Fault X   X   X   X   X   X   X           X   X
                                  (1,2 đã có)
9 page faults

Belady's Anomaly

Trực giác: tăng số frame thì page fault giảm. Nhưng FIFO không có tính chất này! Có dãy mà thêm frame lại làm tăng page fault. Belady (1969) chứng minh.

Reference: 1 2 3 4 1 2 5 1 2 3 4 5
Frames=3: 9 faults
Frames=4: 10 faults  ← TĂNG khi tăng frame!

Belady's anomaly là dấu hiệu thuật toán không tốt. LRU không có anomaly này.

9.6 LRU — Least Recently Used

Đẩy page lâu nhất chưa được dùng (dùng gần đây nhất → giữ lại). Dựa trên locality of reference.

Reference: 1 2 3 4 1 2 5 1 2 3 4 5
Frames=3:

Step  1   2   3   4   1   2   5   1   2   3   4   5
F1    1   1   1   4   4   4   5   5   5   3   3   3
F2        2   2   2   1   1   1   1   1   1   4   4
F3            3   3   3   2   2   2   2   2   2   5
Fault X   X   X   X   X   X   X           X   X   X
10 page faults

(LRU đôi khi nhiều fault hơn FIFO trên dãy ngắn,
 nhưng không có Belady's Anomaly và tốt hơn average)

Cài đặt LRU

• Linked list: mỗi truy cập → di chuyển page lên đầu. Đẩy: lấy cuối list. O(1) move, O(1) evict — nhưng cần update mỗi access → tốn quá. Dùng cho cache application-level (Redis, LRUCache library).
• Page table accessed bit: hardware set bit khi page accessed. Kernel scan định kỳ — xấp xỉ LRU.
• Linux dùng 2 list LRU: active + inactive — gần đúng LRU với cost thấp.

"True LRU" trong page replacement quá đắt — dùng xấp xỉ qua Clock algorithm.

9.7 Clock (Second Chance)

Xấp xỉ LRU rẻ hơn nhiều. Sắp các page thành vòng tròn, có 1 con trỏ "kim đồng hồ". Mỗi PTE có R bit (reference / accessed), hardware tự set khi truy cập.

Khi cần evict

1. Kim trỏ vào page hiện tại
2. Nếu R = 0 → evict page này, kim tiến 1
3. Nếu R = 1 → set R = 0, "tha thứ" lần này, kim tiến 1, lặp

Page đang dùng thường xuyên có R = 1 → tha. Page lâu không dùng có R = 0 → evict. Xấp xỉ LRU.

Linux thực tế

Linux dùng biến thể "two-handed clock" + active/inactive list. Phức tạp hơn pure clock nhưng cùng triết lý.

9.8 Optimal (Belady's Algorithm) — không thể implement

Đẩy page sẽ được dùng lại lâu nhất trong tương lai. Đây là tối ưu lý thuyết, có thể chứng minh là cho fewest page fault.

Nhược: không thể biết tương lai. Optimal chỉ dùng để so sánh — đo distance giữa thuật toán thực với optimal.

9.9 Working Set — kích thước memory thực sự cần

Working set của process tại thời điểm t = tập các page mà process đã truy cập trong khoảng thời gian Δ trước đó.

Quan sát: process có "locality" — chỉ dùng 1 phần memory mỗi giai đoạn. Nếu working set vừa đủ trong RAM, page fault thấp. Nếu working set > RAM, page fault cao.

Working Set Size — chỉ số quan trọng

OS có thể đo working set của mỗi process, dùng để:

• Quyết định cấp bao nhiêu frame cho mỗi process
• Tránh thrashing: nếu tổng working set > RAM, suspend bớt process

9.10 Thrashing — máy "lag" không lý do

Thrashing = OS dành phần lớn thời gian cho page fault thay vì chạy code thực sự. CPU usage giảm, disk I/O tăng cao.

Tại sao xảy ra?

Quá nhiều process. Mỗi process được cấp ít frame → working set không đủ → page fault liên tục → swap in/out không ngừng → mọi process tiến triển chậm → OS tưởng cần chạy thêm process → cấp thêm → tệ hơn → tử vòng.

Dấu hiệu

• vmstat: si/so (swap in/out) cao
• CPU idle cao mà mọi thứ chạy rất chậm
• Disk I/O 100% liên tục
• Tiếng ổ cứng kêu liên tục (HDD)

Khắc phục

• Thêm RAM (giải pháp tự nhiên nhất)
• Suspend bớt process (Linux OOM killer làm điều này)
• Working set algorithm: chỉ schedule process có thể fit working set
• Trong cloud: scale out instance thay vì cố nhồi nhiều workload

9.11 CPU Cache — paging thu nhỏ

CPU cache (L1/L2/L3) cùng nguyên lý với paging — chỉ khác cấp độ.

Cache line

CPU cache đơn vị = cache line (64 byte trên x86). Đọc 1 byte → load cả cache line. Ghi 1 byte → đánh dấu cache line dirty.

Locality of Reference — nguyên lý cốt lõi

• Spatial locality: đã truy cập x → có thể sắp truy cập x+1 (mảng tuần tự)
• Temporal locality: đã truy cập x → có thể truy cập lại x sớm

Đây là nền tảng cho cả CPU cache hit rate cao lẫn LRU page replacement.

False sharing — bug performance

// Bug: 2 thread cùng đọc/ghi 2 biến KHÁC NHAU nhưng cùng cache line
struct {
    int a;  // thread 1 ghi
    int b;  // thread 2 ghi
} data;     // a, b ở cùng 64-byte cache line

// Mỗi lần thread 1 ghi a, cache line bị invalidate trên CPU 2
// → Thread 2 phải reload cache → SLOW

// Fix: padding để a, b ở cache line khác nhau
struct {
    int a;
    char pad[64];
    int b;
} data;

Bài tập

Tổng kết chương 9

• ✅ Page fault = present bit 0; kernel cấp frame + (nếu cần) load từ disk
• ✅ Major fault (đọc disk, ms) ≠ Minor fault (chỉ update PTE, µs)
• ✅ TLB = cache page table; quan trọng vì mỗi instruction đều dịch VA
• ✅ Page replacement algorithms: FIFO (đơn giản, có Belady's), LRU (tốt nhưng đắt), Clock (xấp xỉ LRU rẻ), Optimal (lý thuyết)
• ✅ Linux dùng biến thể Clock với active/inactive list
• ✅ Working Set: tập page đang được dùng; nếu vượt RAM → thrashing
• ✅ Thrashing: page fault liên tục, máy lag dù CPU idle
• ✅ CPU cache (L1/L2/L3) cùng nguyên lý paging; locality of reference làm cả hai work
• ✅ False sharing: 2 thread ghi 2 biến cùng cache line gây slow