位址空間與 VM 快取機制 (Address Spaces & VM as Caching)

Overview Table

9.1 實體定址與虛擬定址 (Physical and Virtual Addressing) (p.839-840)

主記憶體被組織成 $M$ 個連續 byte 大小的單元 (cell) 的陣列,每個 byte 有唯一的 physical address (PA),從 0 開始編號。最自然的方式是 CPU 直接用 PA 存取記憶體,稱為 physical addressing;早期 PC 曾採用此法,而 DSP、嵌入式微控制器、Cray 超級電腦等「簡單」系統至今仍然如此。現代處理器則使用 virtual addressing:CPU 產生 virtual address (VA),在送往主記憶體前先被轉換為適當的 PA。

• 將 VA 轉為 PA 的工作稱為 address translation(位址翻譯)。
• 如同例外處理,位址翻譯需要 CPU 硬體與作業系統緊密合作。
• CPU 晶片上的專用硬體 MMU (memory management unit) 即時 (on the fly) 翻譯虛擬位址,其使用的查找表 (lookup table) 存放在主記憶體中、內容由 OS 管理(即 page table,見 9.3.2)。

實體定址 (Figure 9.1):
                PA
  +-----+       4        +--------------+
  | CPU |--------------->| Main memory  |
  +-----+                | 0,1,2,...,M-1|
     ^                   +--------------+
     |____ data word _________|

虛擬定址 (Figure 9.2):
  CPU chip
  +---------------------------+
  |  +-----+   VA    +-----+  |    PA     +--------------+
  |  | CPU |-------->| MMU |--|---------->| Main memory  |
  |  +-----+  4100   +-----+  |    4      +--------------+
  +---------------------------+                 |
        ^________________ data word ____________|

9.2 位址空間 (Address Spaces) (p.840-841)

address space 是非負整數位址的有序集合 $\{0,1,2,\dots \}$;若整數連續,稱為 linear address space(本章一律假設線性)。位址空間的大小由「表示最大位址所需的位元數」刻劃:有 $N=2^n$ 個位址的虛擬位址空間稱為 n-bit address space,現代系統通常支援 32-bit 或 64-bit。

• virtual address space:$\{0,1,\dots ,N-1\}$,其中 $N=2^n$。
• physical address space:$\{0,1,\dots ,M-1\}$,對應系統的 $M$ 個 byte 實體記憶體。
• 最大虛擬位址 = $N-1=2^n-1$。

為何位址空間概念重要:它把「資料物件(bytes)」與「其屬性(addresses)」做出乾淨切割。一旦分離,就能讓每個資料物件擁有多個獨立位址,分別取自不同位址空間——這正是虛擬記憶體的基本想法:主記憶體的每個 byte 同時有一個 VA(取自虛擬位址空間)與一個 PA(取自實體位址空間)。

9.3 VM 作為快取工具 (VM as a Tool for Caching) (p.841-842)

概念上,虛擬記憶體是存放在 disk 上、由 $N$ 個連續 byte 組成的陣列,每個 byte 的虛擬位址就是陣列索引;其內容被快取在主記憶體 (DRAM) 中。如同記憶體階層中的其他快取,disk(下層)資料被切成區塊作為與 DRAM(上層)之間的傳輸單位:

• 虛擬記憶體切成固定大小的 virtual pages (VPs),每頁 $P=2^p$ bytes。
• 實體記憶體切成同樣 $P$ bytes 的 physical pages (PPs),又稱 page frames。

任一時刻,虛擬頁面集合被劃分為三個互斥子集:

     Virtual memory (disk)             Physical memory (DRAM)
   +------------------------+
VP0| Unallocated            |          +--------------+
VP1| Cached      ---------------------->  PP 0        |
VP2| Uncached               |          |  PP 1        |
VP3| Unallocated            |          |   ...        |
VP4| Cached      ---------------------->              |
VP5| Uncached               |          |  PP 2^(m-p)-1|
VP6| Cached      ---------------------->              |
VP7| Uncached               |          +--------------+
   +------------------------+
    共 2^(n-p) 個 VP                     共 2^(m-p) 個 PP

9.3.1 DRAM Cache 的組織 (p.842)

術語約定:SRAM cache 指 CPU 與主記憶體之間的 L1/L2/L3;DRAM cache 指 VM 系統用主記憶體快取虛擬頁面的那一層。DRAM cache 在階層中的位置決定其組織方式:DRAM 比 SRAM 慢至少 10 倍,disk 比 DRAM 慢約 100,000 倍,且讀取 disk sector 第一個 byte 的成本比讀後續 byte 慢約 100,000 倍。結論:DRAM cache 的組織完全由巨大的 miss 成本驅動。

9.3.2 Page Tables(頁表)(p.842-843)

VM 系統必須能判斷某個 VP 是否已快取於 DRAM、在哪個 PP;若 miss,還要知道該 VP 存於 disk 何處、挑選 victim page、把 VP 從 disk 複製進 DRAM。這些能力由三者合作提供:OS 軟體 + MMU 位址翻譯硬體 + 存於實體記憶體的 page table 資料結構。

• page table 是 page table entries (PTEs) 的陣列;虛擬位址空間中的每一頁在頁表中都有一個位於固定 offset 的 PTE。
• 本章簡化假設:每個 PTE = valid bit + n-bit 位址欄位。
• 位址翻譯硬體每次做 VA→PA 轉換都會讀取 page table;OS 負責維護頁表內容並在 disk 與 DRAM 間搬移頁面。

PTE 三種情形的判讀:

        Page table (常駐 DRAM)                DRAM                disk
      Valid  PPN or disk addr
PTE 0 [ 0 | null      ]                   +---------+        +---------+
PTE 1 [ 1 | ----------------------------> | VP1 PP0 |        |  VP 1   |
PTE 2 [ 1 | ----------------------------> | VP2     |        |  VP 2   |
PTE 3 [ 0 | .......................................  ......> |  VP 3   |
PTE 4 [ 1 | ----------------------------> | VP4 PP3 |        |  VP 4   |
PTE 5 [ 0 | null      ]                   +---------+        |  VP 6   |
PTE 6 [ 0 | .......................................  ......> |  VP 7   |
PTE 7 [ 1 | ----------------------------> | VP7     |        +---------+
      (實線 → DRAM;虛線 ....> disk)

9.3.3 Page Hits(頁命中)(p.844)

CPU 讀取一個位於已快取頁(如 VP 2)中的字 (word) 時:

1. 位址翻譯硬體以 VA 為索引定位 PTE 2 並從記憶體讀出。
2. valid bit = 1 → 硬體得知 VP 2 已快取。
3. 硬體用 PTE 中的實體位址(指向 PP 1 中該快取頁的起頭)組出該字的實體位址——全程純硬體,不驚動 OS。

9.3.4 Page Faults(頁錯誤)(p.844-845)

VM 術語中,DRAM cache miss 稱為 page fault。完整處理流程(以參考 VP 3、victim 為 VP 4/PP 3 為例):

CPU 參考 VP 3 中的字
   |
   v
翻譯硬體讀 PTE 3 --> valid = 0 且非 null(已配置未快取)
   |
   v
觸發 page fault exception ----> 進入 kernel 的 page fault handler
   |                                |
   |               (1) 選 victim page(此例 VP 4,在 PP 3)
   |               (2) 若 VP 4 已被修改(dirty)→ 寫回 disk
   |               (3) 修改 VP 4 的 PTE:標記為不再快取
   |               (4) 把 VP 3 從 disk 複製到 PP 3,更新 PTE 3
   |               (5) handler 返回
   v
重新執行 (restart) 造成 fault 的指令
   |
   v
同一 VA 重送翻譯硬體 → 這次是 page hit,正常完成,不再產生例外

• swapping / paging:在 disk 與記憶體間傳輸頁的活動;swapped in (paged in) = disk→DRAM,swapped out (paged out) = DRAM→disk。
• demand paging:等到 miss 發生的最後一刻才把頁換入的策略;所有現代系統都採用 demand paging(預測性換入雖可能,但非主流)。
• 術語差異的歷史原因:VM 發明於 1960 年代初,早於 CPU-memory gap 催生的 SRAM cache,故用語不同(block → page;miss → page fault)。

9.3.5 Allocating Pages(配置新頁)(p.846)

當 OS 配置新的虛擬記憶體頁(例如程式呼叫 malloc 的結果)時:

• 在 disk 上建立空間(該 VP 從 Unallocated → Uncached)。
• 更新對應 PTE,使其指向 disk 上新建立的頁(valid 仍為 0)。
• 注意:此時尚未載入任何內容到 DRAM;首次實際存取時才會經由 page fault 換入(demand paging 的精神)。

9.3.6 Locality 再度救援 (Locality to the Rescue Again) (p.846)

直覺上 VM 的巨大 miss penalty 似乎會摧毀效能,但實務上 VM 運作良好,關鍵在 locality(區域性):

• 程式整個執行期間參考的頁總數可能超過實體記憶體大小,但 locality 保證任一時刻程式傾向於在一組較小的活躍頁面上工作,稱為 **working set(工作集)**或 resident set。
• 初始開銷(把 working set 換入記憶體)之後,對 working set 的後續參考全是 hit,不再有 disk 流量。
• thrashing(顛簸):若 working set 大小 > 實體記憶體大小,頁面會被連續不斷地換入換出,效能崩跌。

公式總表

Exam/Test Patterns

Related Notes

• 09-Virtual-Memory/02-VM-Management-and-Protection
• 09-Virtual-Memory/03-Address-Translation-and-TLB
• 09-Virtual-Memory/04-Memory-Mapping
• 06-Memory-Hierarchy/02-Locality-and-Memory-Hierarchy
• 06-Memory-Hierarchy/03-Cache-Memories
• 08-Exceptional-Control-Flow/01-Exceptions