Bài 8: Bộ Nhớ Ảo & Khối TLB

Mở đầu: mỗi tiến trình sống trong ảo tưởng của riêng nó

Bài 7 tăng tốc truy cập bộ nhớ VẬT LÝ bằng cache. Nhưng địa chỉ mà một chương trình THẤY (vd con trỏ trong C, biến trong JS engine) hiếm khi là địa chỉ VẬT LÝ thật trên thanh RAM — hệ điều hành chèn một tầng gián tiếp: mỗi tiến trình có một không gian địa chỉ ẢO (virtual) riêng, hoàn toàn cách ly với tiến trình khác, được dịch sang địa chỉ VẬT LÝ (physical) thật ở mỗi lần truy cập. Cái giá của tầng gián tiếp này — và cách phần cứng che giấu nó — là chủ đề bài này.

1. Bộ nhớ ảo (Virtual Memory) & Phân trang (Paging)

Bộ nhớ ảo cho phép: (1) chạy chương trình LỚN HƠN RAM vật lý (phần không dùng tới nằm trên đĩa, nạp vào RAM khi cần), và (2) CÔ LẬP an toàn — tiến trình A không thể vô tình (hay cố ý) đọc/ghi bộ nhớ của tiến trình B, vì địa chỉ ảo của A và B được dịch sang các VÙNG vật lý khác nhau hoàn toàn. Bộ nhớ được chia thành các trang (page) kích thước cố định — mặc định thường 4KB — và Page Table (bảng trang) ghi nhớ mỗi trang ẢO đang trỏ tới trang VẬT LÝ (khung trang — page frame) nào.

A virtual address (32-bit example):
+----------------------------+---------------+
|  VPN (Virtual Page Number) |   Offset      |
|          20 bits           |    12 bits    |
+----------------------------+---------------+
   looks up the Page Table     byte WITHIN the page (unchanged by translation)

# The VPN indexes the Page Table -> PFN (Physical Frame Number)
# Physical address = (PFN << 12) | Offset
#   the offset is carried over UNCHANGED; only the VPN is translated

2. MMU và một mục bảng trang thật sự chứa gì

Mục 1 nói Page Table "ghi nhớ mỗi trang ảo đang trỏ tới trang vật lý nào", nhưng chưa nói AI làm việc tra bảng đó, và một mục trong bảng thật sự chứa gì. Hai câu hỏi này quyết định phần còn lại của bài.

Người tra bảng là MMU (Memory Management Unit — khối quản lý bộ nhớ): một khối phần cứng nằm trong CPU, không phải một phần của hệ điều hành. Mỗi lần chương trình đọc hay ghi một địa chỉ, MMU chặn địa chỉ ảo đó lại, tra bảng trang, và chỉ nhả ra địa chỉ vật lý tương ứng. Hệ điều hành chỉ dựng bảng trang; MMU là thứ thi hành nó ở mọi lần truy cập, nên chương trình không có cách nào đi đường tắt qua nó.

Còn một mục bảng trang — PTE (Page Table Entry) — không phải chỉ là số PFN. Đó là lý do Mục 3 sắp tính "mỗi mục 4 byte" chứ không phải 20 bit vừa đủ cho PFN. Bên cạnh PFN, PTE còn mang mấy bit cờ mà MMU đọc ở MỖI lần truy cập:

One Page Table Entry (PTE), simplified:
+--------------------------+-----+-----+-----+-----+
|  PFN (physical frame)    |  NX | R/W |  D  |  P  |
+--------------------------+-----+-----+-----+-----+
                              |     |     |     |
   no-execute -----------------+    |     |     |
   writable? (0 = read-only) -------+     |     |
   dirty: page was written to ------------+     |
   present: mapping is valid at all ------------+

# The MMU reads these flags on EVERY access, in hardware.
# P = 0  -> the mapping does not exist -> raise a page fault
# R/W= 0 -> a write to this page raises a fault (read-only page)
# NX = 1 -> executing code from this page raises a fault
# D  = 1 -> the page differs from its copy on disk (see Lesson 7: write-back)

Với bốn bit đó, ba điều mà Mục 1 chỉ nói suông giờ có cơ chế cụ thể:

• Page fault được PHÁT HIỆN thế nào. Không phải bằng cách "tìm không thấy" — mà bằng bit P (present). MMU đọc PTE, thấy $P=0$, và lập tức phát một exception giao cho hệ điều hành xử lý (nạp trang từ đĩa vào RAM, cập nhật PTE, rồi cho lệnh gây lỗi chạy lại). Chương trình không hề biết chuyện đó vừa xảy ra — nó chỉ thấy lệnh của mình chậm hơn bình thường vài triệu chu kỳ.
• Cô lập được THI HÀNH thế nào. Mục 1 nói bộ nhớ ảo cho "cô lập an toàn", nhưng bảng trang riêng chỉ là một nửa: nó ngăn tiến trình A chạm tới bộ nhớ của B. Nửa còn lại là bit R/W và NX, ngăn một tiến trình tự làm hại CHÍNH NÓ — ghi vào vùng chỉ đọc, hay thi hành dữ liệu như thể đó là code. Đây đúng là cơ chế mà Bài 2 đã hứa khi nói hệ điều hành đánh dấu vùng code là "read-only + non-writable (bit NX/XD) ngay ở tầng phần cứng MMU" — chính bit NX trong PTE này là thứ khiến self-modifying code của Bài 2 không thể xảy ra trên một hệ thống hiện đại.
• Vì sao tráo trang ra đĩa đôi khi MIỄN PHÍ. Bit D (dirty) nói trang đã bị GHI kể từ lúc nạp vào hay chưa — đúng ý nghĩa dirty bit của cache ở Bài 7, chỉ ở cấp trang thay vì cấp dòng cache. Nếu $D=0$, bản trên đĩa vẫn còn giống y nguyên, nên hệ điều hành chỉ cần THẢ trang khỏi RAM, không phải ghi gì cả. Nếu $D=1$, nó buộc phải ghi trang xuống đĩa trước — chậm hơn hàng nghìn lần. Cùng một thao tác "giải phóng một trang", chi phí chênh nhau hoàn toàn tuỳ đúng một bit.

3. Tính toán cấu trúc & dung lượng Page Table

Với địa chỉ ảo $A$ bit và trang $O$ bit ($2^O$ byte/trang), số trang ảo TỐI ĐA có thể có là $2^{A-O}$. Page Table ĐƠN CẤP ngây thơ nhất cấp phát ĐỦ chỗ cho MỌI trang ảo có thể có — kể cả những trang KHÔNG BAO GIỜ được chương trình dùng tới:

$$\text{Single-level Page Table Size} = 2^{A-O} \times \text{Entry Size}$$

Verified thật: với địa chỉ ảo 32-bit, trang 4KB ($O=12$), mục bảng (PTE) 4-byte — Page Table đơn cấp tốn đúng 4.194.304 byte = 4MB cho MỖI tiến trình. Nghe có vẻ chấp nhận được — nhưng với địa chỉ 64-bit (thực tế CPU hiện đại dùng 48-bit khả dụng), CÙNG công thức đó cho ra 256GB — hoàn toàn BẤT KHẢ THI cho một cấu trúc dữ liệu phải tồn tại RIÊNG cho MỖI tiến trình đang chạy.

function pageTableEntryCount(addressBits, pageOffsetBits) {
  return Math.pow(2, addressBits - pageOffsetBits);
}
function singleLevelPageTableSizeBytes(addressBits, pageOffsetBits, entryBytes) {
  return pageTableEntryCount(addressBits, pageOffsetBits) * entryBytes;
}
// Verified: singleLevelPageTableSizeBytes(32, 12, 4) = 4.194.304 byte (4MB)
// Verified: singleLevelPageTableSizeBytes(48, 12, 4) / 1024^3 = 256 (GB - impossible!)

Giải pháp thật: Page Table ĐA CẤP (kiểu x86 32-bit chia 10-10-12 bit) — bảng cấp 1 LUÔN được cấp phát (nhỏ, cố định), nhưng bảng cấp 2 CHỈ được cấp phát cho những VÙNG THẬT SỰ có trang đang dùng. Verified thật: với 512 trang đang dùng (2MB không gian địa chỉ thật sự dùng tới, trên tổng 4GB khả dụng của không gian 32-bit) — Page Table 2 cấp chỉ tốn 8.192 byte (8KB), RẺ HƠN đơn cấp (4MB) đúng 512 lần.

function twoLevelPageTableSizeBytes(numUsedPages, entriesPerTable, entryBytes) {
  const firstLevelBytes = entriesPerTable * entryBytes;              // ALWAYS allocated
  // only the regions actually in use
  const numSecondLevelTables = Math.ceil(numUsedPages / entriesPerTable);
  const tableBytes = entriesPerTable * entryBytes;
  return firstLevelBytes + numSecondLevelTables * tableBytes;
}
// Verified: twoLevelPageTableSizeBytes(512, 1024, 4) = 8192 bytes (8KB)
// Against 4MB single-level for the SAME 32-bit space -> 512x cheaper

4. Khối tăng tốc dịch địa chỉ TLB

Vấn đề: Page Table BẢN THÂN nó cũng nằm trong RAM — nghĩa là MỖI lần CPU cần dịch địa chỉ ảo sang vật lý, nó phải tốn THÊM một lần truy cập RAM để đọc Page Table, TRƯỚC KHI truy cập RAM lần THỨ HAI để lấy dữ liệu thật sự cần. TLB (Translation Lookaside Buffer) giải quyết bằng cách đóng vai trò một cache CHO Page Table: lưu các cặp (VPN → PFN) đã dịch GẦN ĐÂY, y hệt cấu trúc Set-Associative + LRU của Bài 7.

Đáng dừng lại ở chỗ TLB miss tốn ĐÚNG bao nhiêu, vì đó là toàn bộ lý do TLB tồn tại. Khi TLB không có bản dịch, MMU phải tự đi tra bảng trang trong RAM — thao tác này có tên riêng: page table walk (duyệt bảng trang). Và số lần đi RAM bằng đúng SỐ CẤP của bảng, vì mỗi cấp nằm ở một chỗ khác nhau:

TLB HIT  -> 1 RAM access total:
             (translation comes from the TLB, on-chip)
             [1] read the data itself

TLB MISS -> 3 RAM accesses total, with the 2-level table of Section 3:
             [1] read the level-1 table   -> address of the level-2 table
             [2] read the level-2 table   -> the PFN
             [3] read the data itself

# So a TLB miss costs 3x the memory traffic of a hit, not 2x - the walk is
# EXTRA work on top of the access you actually wanted.
# On x86-64 the page table has FOUR levels, so a miss there costs 5 accesses.

Đó là con số đáng nhớ của mục này: bảng 2 cấp làm một lần dịch thất bại tốn 3 lần đi RAM thay vì 1, và bảng 4 cấp của x86-64 thật tốn 5 lần. Mục 3 đã cho thấy cấu trúc đa cấp là thứ DUY NHẤT khiến bảng trang vừa nổi trong RAM — nhưng cái giá của nó là mỗi lần tra bảng dài thêm theo số cấp. TLB chính là thứ trả lại cái giá đó: chỉ cần bản dịch còn trong TLB, toàn bộ chuỗi duyệt kia được bỏ qua hoàn toàn.

function translateAddress(virtualAddress, pageOffsetBits, tlb, pageTable) {
  const { vpn, offset } = splitVirtualAddress(virtualAddress, pageOffsetBits);
  let pfn = tlb.lookup(vpn);
  if (pfn !== null) {
    const physicalAddress = (pfn << pageOffsetBits) | offset;
    return { physicalAddress, tlbHit: true, pageFault: false };
  }
  if (pageTable.has(vpn)) {
    pfn = pageTable.get(vpn);
    tlb.insert(vpn, pfn); // remember it for next time
    const physicalAddress = (pfn << pageOffsetBits) | offset;
    return { physicalAddress, tlbHit: false, pageFault: false };
  }
  return { physicalAddress: null, tlbHit: false, pageFault: true }; // VPN is not mapped
}
// Verified: first access to a VPN  -> tlbHit=false (the Page Table is consulted)
// Verified: SECOND access, same VPN -> tlbHit=true  (now cached in the TLB)
// Verified: access to an unmapped VPN -> pageFault=true

5. Thực hành: Dịch địa chỉ ảo động & mô phỏng TLB

Nhập địa chỉ ảo (hex) để dịch qua TLB + Page Table THẬT (3 trang đã ánh xạ sẵn: VPN 5, 6, 9) — thử lại CÙNG địa chỉ để thấy TLB chuyển từ MISS sang HIT, hoặc thử VPN khác để thấy Page Fault. Máy tính bên dưới so sánh trực tiếp dung lượng Page Table đơn cấp vs 2 cấp:

Tóm lược

• ✅ Bộ nhớ ảo cho phép chương trình lớn hơn RAM vật lý và cô lập an toàn giữa các tiến trình, thông qua Page Table dịch VPN → PFN.
• ✅ MMU là khối PHẦN CỨNG trong CPU thi hành bảng trang ở mọi lần truy cập; một PTE không chỉ chứa PFN mà còn các bit P/R-W/NX/D — bit P là cách page fault được phát hiện, R/W và NX là cách cô lập được thi hành, và D quyết định tráo trang ra đĩa có phải ghi hay không.
• ✅ TLB miss buộc MMU tự duyệt bảng trang (page table walk): bảng 2 cấp tốn 3 lần đi RAM thay vì 1, bảng 4 cấp của x86-64 tốn 5 lần — đó là toàn bộ lý do TLB tồn tại.
• ✅ Verified: Page Table đơn cấp 32-bit tốn 4MB; không gian 48-bit (64-bit thực tế) cần 256GB — bất khả thi, buộc phải dùng cấu trúc đa cấp.
• ✅ Verified: Page Table 2 cấp chỉ tốn 8KB khi thực dùng 2MB không gian địa chỉ — rẻ hơn đơn cấp 512 lần, vì bảng cấp 2 chỉ cấp phát cho vùng THẬT SỰ đang dùng.
• ✅ TLB là cache CHO Page Table — verified: lần đầu truy cập 1 trang là TLB miss, lần sau CÙNG trang là TLB hit; truy cập trang chưa ánh xạ gây Page Fault.
• ✅ Pitfall: TLB phải bị xoá sạch (flush) mỗi lần context switch — chi phí ẩn của việc đổi tiến trình.

Trắc nghiệm ôn tập