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.

Dia chi ao (32-bit vi du):
+----------------------------+---------------+
|   VPN (Virtual Page Number)|   Offset      |
|          20 bit            |    12 bit     |
+----------------------------+---------------+
        tra Page Table            byte TRONG trang (khong doi khi dich)

# VPN tra Page Table -> PFN (Physical Frame Number)
# Dia chi vat ly = (PFN << 12) | Offset  (offset GIU NGUYEN, chi VPN duoc dich)

2. 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 - bat kha thi!)

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;             // LUON cap phat
  const numSecondLevelTables = Math.ceil(numUsedPages / entriesPerTable); // CHI vung dang dung
  const tableBytes = entriesPerTable * entryBytes;
  return firstLevelBytes + numSecondLevelTables * tableBytes;
}
// Verified: twoLevelPageTableSizeBytes(512, 1024, 4) = 8192 byte (8KB)
// So voi don cap 4MB cho CUNG khong gian 32-bit -> re hon 512 lan

3. 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.

function translateAddress(virtualAddress, pageOffsetBits, tlb, pageTable) {
  const { vpn, offset } = splitVirtualAddress(virtualAddress, pageOffsetBits);
  let pfn = tlb.lookup(vpn);
  if (pfn !== null) return { physicalAddress: (pfn << pageOffsetBits) | offset, tlbHit: true, pageFault: false };
  if (pageTable.has(vpn)) {
    pfn = pageTable.get(vpn);
    tlb.insert(vpn, pfn); // luu lai cho lan sau
    return { physicalAddress: (pfn << pageOffsetBits) | offset, tlbHit: false, pageFault: false };
  }
  return { physicalAddress: null, tlbHit: false, pageFault: true }; // VPN chua duoc anh xa
}
// Verified: lan dau truy cap 1 VPN -> tlbHit=false (phai tra Page Table)
// Verified: lan HAI truy cap CUNG VPN -> tlbHit=true (da luu trong TLB)
// Verified: truy cap VPN chua anh xa -> pageFault=true

4. 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.
• ✅ 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