Paging & page table — bản đồ dịch địa chỉ

TL;DR: Bộ nhớ ảo không ánh xạ từng byte riêng lẻ — nó chia không gian địa chỉ ảo thành các trang (page) kích thước cố định (điển hình 4 KB) và RAM vật lý thành các khung (frame) cùng kích thước. Một page table lưu ánh xạ "trang ảo số N nằm tại khung vật lý số M". Mỗi lần chương trình đọc một địa chỉ ảo, phần cứng tách nó thành page number và offset, tra page table lấy frame number, ghép lại ra địa chỉ vật lý. Offset đi thẳng qua không đổi — đây là chi tiết thường bị bỏ qua nhưng là chìa khoá để trace từng bước. Mỗi tiến trình có page table riêng, đó là cơ chế cách ly bộ nhớ đã gặp ở bài 01.

Bạn malloc(1 MB) và OS trả về địa chỉ ảo 0x7f3a0000. Bên dưới, OS đặt lên page table của tiến trình bạn một loạt ánh xạ "trang ảo 0x7f3a0 → khung vật lý 0x1c2", "trang 0x7f3a1 → khung 0x5a7"… Những khung đó rải rác khắp RAM, nhưng tiến trình thấy một vùng liền mạch hoàn hảo tại 0x7f3a0000.

Làm thế nào OS và phần cứng biến những khung rời rạc đó thành một dải địa chỉ liền mạch mà chương trình thấy? Đó là việc của paging và page table — bài này giải thích cơ chế từng bước.

1. Analogy — bảng ghế trong rạp chiếu phim

Hình dung rạp chiếu phim có 10.000 ghế đánh số thật từ 1 đến 10.000. Khi bạn mua vé, nhân viên không đưa bạn đi tới đúng ghế số thật — họ đưa cho bạn một phiếu ghế ảo ("hàng 3, ghế 5 của phòng bạn") và giữ một bảng ánh xạ phòng nào hàng nào ghế nào tương ứng ghế thật số mấy.

Nhờ đó, hai phòng khác nhau đều có "hàng 3, ghế 5" mà không đụng nhau. Khi bạn ngồi đúng ghế ảo, nhân viên tra bảng và dẫn bạn tới ghế thật. Offset là vị trí trong phòng (hàng + cột); page number là số hiệu phòng.

2. Chia trang — vì sao kích thước cố định?

Không gian địa chỉ ảo và RAM vật lý đều được chia thành các khối cùng kích thước:

• Trang (page): đơn vị của không gian địa chỉ ảo. Điển hình 4 KB = 4096 byte.
• Khung (frame): đơn vị của RAM vật lý. Cùng kích thước với trang.

Kích thước cố định giải quyết external fragmentation — vấn đề nan giải của segmentation và cấp phát liền khối:

Internal fragmentation vẫn tồn tại: trang cuối cùng của một tiến trình thường dùng không hết 4 KB (trung bình lãng phí 2 KB). Đây là cái giá của kích thước cố định — nhưng nhỏ hơn nhiều so với external fragmentation.

3. Địa chỉ ảo = VPN + offset

Với page 4 KB = 2^12 byte, cần 12 bit để đánh địa chỉ mọi byte trong một trang. Đó là 12 bit thấp nhất của địa chỉ ảo — gọi là offset. Các bit còn lại là virtual page number (VPN).

Dia chi ao 32-bit, page 4 KB (2^12):

  |<---- 20 bit VPN ---->|<-- 12 bit offset -->|
  [ bit 31 ... bit 12   ][ bit 11 ... bit 0   ]

Vi du: dia chi ao 0x00403A2C
  VPN    = 0x00403A2C >> 12 = 0x00403    (= trang ao so 1027)
  offset = 0x00403A2C & 0xFFF = 0xA2C   (= byte 2604 trong trang)

Tương tự cho địa chỉ vật lý: 12 bit thấp là offset (giống hệt), phần còn lại là physical frame number (PFN).

flowchart LR
  VA["Dia chi ao<br/>[VPN | offset]"] -->|tra page table| PT["Page table<br/>VPN -> PFN"]
  PT -->|ghep lai| PA["Dia chi vat ly<br/>[PFN | offset]"]

4. Page table và page table entry (PTE)

Page table là một mảng (per-tiến-trình) lưu trong bộ nhớ kernel. Mỗi phần tử là một page table entry (PTE) tương ứng với một trang ảo. PTE chứa:

Khi CPU truy cập một địa chỉ ảo:

1. Tách VPN và offset từ địa chỉ ảo.
2. Dùng VPN làm chỉ số vào page table, đọc PTE.
3. Kiểm tra present bit: nếu 0 → page fault, OS xử lý (bài 04).
4. Nếu 1: lấy PFN từ PTE, ghép PFN + offset = địa chỉ vật lý.
5. Truy cập RAM tại địa chỉ vật lý đó.

5. Worked example — dịch địa chỉ từng bước

Giả sử: page 4 KB, địa chỉ ảo 32-bit, page table sau (chỉ trích một phần):

Yêu cầu dịch địa chỉ ảo 0x00003A2C:

Buoc 1: tach VPN va offset
  Dia chi ao = 0x00003A2C
  VPN    = 0x00003A2C >> 12 = 3      (trang ao so 3)
  offset = 0x00003A2C & 0xFFF = 0xA2C

Buoc 2: tra page table voi VPN = 3
  PTE[3]: PFN = 7, present = 1 -> OK

Buoc 3: ghep dia chi vat ly
  Dia chi vat ly = (PFN << 12) | offset
                 = (7 << 12) | 0xA2C
                 = 0x00007000 | 0xA2C
                 = 0x00007A2C

Offset 0xA2C giữ nguyên — nó đi thẳng vào địa chỉ vật lý không đổi. Chỉ VPN được đổi thành PFN.

Thử với VPN = 2 (present = 0):

Buoc 1: VPN = 2, offset = bat ky
Buoc 2: PTE[2].present = 0 -> page fault!
  CPU raise exception -> OS handler chay -> nap trang tu swap vao RAM
  (xem bai 04)

6. Mỗi tiến trình — một page table riêng

Khi OS tạo một tiến trình mới, nó cấp phát một page table mới cho tiến trình đó. Khi OS switch từ tiến trình A sang B, nó nạp con trỏ page table của B vào thanh ghi CR3 (x86) — MMU tự động dùng page table mới.

Đây là lý do hai tiến trình cùng có code tại 0x400000 mà không đụng nhau (bài 01): VPN 0x400 của A trỏ tới khung vật lý khác VPN 0x400 của B, vì chúng có page table khác nhau.

flowchart TD
  subgraph A["Tien trinh A"]
    VA1["VA 0x400A2C<br/>VPN=0x400, off=0xA2C"]
  end
  subgraph B["Tien trinh B"]
    VA2["VA 0x400A2C<br/>VPN=0x400, off=0xA2C"]
  end
  VA1 -->|page table A| F1["Khung #512"]
  VA2 -->|page table B| F2["Khung #47"]
  F1 --> RAM["RAM vat ly"]
  F2 --> RAM

7. Pitfall tổng hợp

❌ Nhầm 1: Nghĩ page và cache line là một. Cache line là 64 byte — đơn vị trao đổi giữa cache và RAM, ở tầng phần cứng. Page là 4 KB — đơn vị quản lý bộ nhớ ảo, ở tầng OS. Hai tầng khác nhau, kích thước khác nhau; một page chứa 64 cache line.

❌ Nhầm 2: Nghĩ page table phẳng với 48-bit address space nhỏ thôi. Thật ra: địa chỉ ảo 48-bit, page 4 KB → VPN 36 bit → 2^36 entry = 64 tỉ entry. Nếu mỗi PTE 8 byte → page table phẳng tốn 512 GB cho mỗi tiến trình. Đó là lý do cần multi-level page table (bài 03).

❌ Nhầm 3: Nghĩ cấp phát ảo (malloc) tiêu ngay RAM vật lý. OS thường chỉ thêm entry vào page table với present = 0; RAM chỉ được gán khi trang bị chạm lần đầu (lazy allocation, bài 04).

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

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

• Bài 01 — Vì sao cần bộ nhớ ảo: page table là "bảng tra của lễ tân" bài 01 đề cập — bài này giải thích bảng đó cấu tạo thế nào và hoạt động ra sao.
• Bài 03 — MMU & TLB: ai thực hiện dịch địa chỉ bằng page table (MMU), và TLB cache bản dịch để tránh đi RAM mỗi lần.
• Bài 04 — Page fault & swap: present bit = 0 trong PTE kích page fault — OS phải làm gì tiếp theo.

10. Tóm tắt

• Paging chia không gian địa chỉ ảo và RAM thành các khối cố định kích thước bằng nhau (điển hình 4 KB), tránh external fragmentation của cấp phát liền khối.
• Địa chỉ ảo = VPN (page number) + offset (vị trí trong trang). Với page 4 KB → offset 12 bit, VPN là phần còn lại.
• Page table ánh xạ VPN → PFN (physical frame number). Dịch địa chỉ: tách VPN+offset → tra PTE → lấy PFN → ghép PFN+offset = địa chỉ vật lý. Offset không đổi.
• PTE chứa PFN + các bit trạng thái: present (0 → page fault), dirty, accessed, R/W, User/Supervisor.
• Mỗi tiến trình có page table riêng — đây là cơ sở cách ly: cùng VPN ở hai tiến trình trỏ tới PFN khác nhau.
• Page table phẳng cho không gian 48-bit cần 2^36 entry — quá lớn → cần multi-level page table (bài 03).

11. Tự kiểm tra

Bài tiếp theo: MMU & TLB — dịch địa chỉ mà không chậm