---
tags: CSAPP, 作業系統
---

# CSAPP: Chapter 9

:::info
僅記錄最粗淺的概念，詳細的例子請直接參考原書籍或者課程投影片:
* [Virtual Memory: Concepts](http://www.cs.cmu.edu/afs/cs/academic/class/15213-m19/www/lectures/17-vm-concepts.pdf)
* [Virtual Memory: Systems](http://www.cs.cmu.edu/afs/cs/academic/class/15213-m19/www/lectures/18-vm-systems.pdf)
:::

## Physical Addressing and Virtual Addressing


上圖中展示了一個使用物理尋址的案例，CPU 執行一個載入指令後，生成一個物理地址並透過 bus 傳遞給 memory，memory 透過此地址直接取出相應的資料返回給 CPU。


上圖中則展現了現代處理器中更常使用的虛擬尋址方式，CPU 生成一個虛擬地址且準備傳遞到 memory 前，先經過 [MMU](https://en.wikipedia.org/wiki/Memory_management_unit) 進行轉址(address translation)來將虛擬地址轉換為物理地址後載入。

虛擬尋址的方式看起來麻煩許多，那麼為甚麼現代處理器傾向以這種方式存取地址呢? 大致可以統整為以下幾個原因:
1. 有效的使用主記憶體: 主記憶體的 DRAM 可以作為 virtual adress space 之 cache
2. 更簡單的記憶體管理: virtual memory 可以給每個 process 相同且看似連續的定址空間，這讓程式的撰寫相對容易而且安全
3. 獨立的 address space: process 間不會互相影響(除了共享記憶體部分)，因此 user space 的程式也無法存取到 kernel space 的程式和資料

> [Virtual memory](https://en.wikipedia.org/wiki/Virtual_memory)

## VM as a Tool for Caching

概念上，virtual memory 可被視為一個在 disk 上由 N 個連續 bytes 組成的 array，而 array 中的某些內容可以被 cache 在 DRAM 上。

在此想法之下，由於對 DRAM 的存取會比 SRAM 還慢 10 倍左右，而對於 disk 的存取則會比 DRAM 要來得慢 1 萬倍，由此可見 DRAM 的不命中比起 SRAM 不命中成本要來的昂貴許多。因此，virtual page 往往很大(例如常見的 4 KB 大小)，且以 fully associative 方式來存取(see [Cache placement policies](https://en.wikipedia.org/wiki/Cache_placement_policies))。而不命中的替換策略也因此很重要，因此作業系統對其採取更複雜且精密的演算法來降低錯誤的替換所帶來的成本。最後，因為對 disk 的存取時間很長，因此替換時採取 write-back 而不是 write-through 策略(see [Cache (computing)](https://en.wikipedia.org/wiki/Cache_(computing)))。

### Page table
為了可以判定一個 virtual page 是否存在 DRAM 中，需要 **page table** 這個資料結構。


page table 常駐 DRAM 中，由多個 PTE(page table entry) 組成，如圖展示了一個基本的 pte: 由一個 valid bit 以及一個 n bits 的地址所組成。valid bit 表明 virtual page 是否存在 DRAM 中，如果 valid bit 被設置，則地址就是其在 DRAM 中的相應位置。


如果 CPU 想要讀在 VP2 中的內容，透過解析 virdual address 可以找到對應的 PTE 位置並讀取之，而因為 valid bits 被設置，所以它可以透過此 PTE 中的地址找到其映射的內容 PP1。這種狀況稱為 page hit。


與之相對的，例如 CPU 想要讀在 VP3 的內容，而對應的 PTE 的 valid bit 是沒有被設置的，此時的狀況稱為 page fault。當 page fault 發生，會調用 kernel 中的 page fault handler 來處理，handler 會選擇某個在 DRAM 中的 page 來替換之，如下圖可以看到 VP4 成為了犧牲頁被替換。如果 VP4 已經被修改，kernel 需要將其內容同步回 disk 中，而 VP4 對應的 PTE 也需要被修改已反映其不在存在於 DRAM 中的情形。


當替換完成後，原本造成 page fault 的指令再次被啟動，但現在 VP3 已經存在 DRAM 中了，所以發生 page hit。

在這邊要提到 virtual memory management 中的重要策略:[demand paging](https://en.wikipedia.org/wiki/Demand_paging)。系統可以事先為每個程序分配 virtual page 但不建立 physical page 的對應，直到該 page 真正的被存取，這使得記憶體可以被有效的使用。


如上圖展示的是當作業系統分配一個 virtual page 時的情境。VP5 的分配導致了在 disk 上的分配空間並更新 PTE。

在了解了 virtual memory 的基本概念後，其運作機制看似十分沒有效率，因為 page fault 的成本很高。不過，多虧了程式通常具有的 locality， 因為在任意時刻，程序通常都只在一個較小的 page 工作集(working set)上運作，在初始時 page fault 發生，virtual memory system 將 working set 中的 page 都載入之後，對於這些 page 的使用就會 page hit，而沒有額外的開銷了。

不過，當然還是會發生 working set 太大而超出可用記憶體的情況，此時會發生 [thrashing](https://en.wikipedia.org/wiki/Thrashing_(computer_science))，page 不斷的被換進換出導致 CPU 資源無法專注在真正的工作上。

## VM as a tool for memory management

在上一章節中，我們可以看到可以通過 virtual memory 比 physical memory 更大的定址空間的特性所帶來的好處。不過在早期的系統中，其實也存在比 physical memory 更小的 virtual memory space 的系統，即使如此，virtual memory 仍然是有用的機制。virtual memory 可以提供對記憶體的保護，使得每個 process 持有獨立的定址空間，這簡化了許多記憶體管理的策略:

* 簡化記憶體配置: 對於 user space 的程式調用如 malloc 的配置請求時，作業系統可以分配一個連續的 virtual page，這使得程式的設計更為容易，而在 physical memory 中這些 page 則實際上可以零散的分佈。並且，virtual address 在不同時刻映射到不同的 physical address 也是可行的
* 簡化共享: 不同的 virtual page 可以映射到相同的 physical page，因此不同的 process 在使用相同的函式庫時不需要各自持有獨立的副本
* 簡化鏈接: 獨立的空間使得 process 間的段可以有統一的格式，例如 64 位元的 Linux 系統，code section 總是由 0x400000 開始。這簡化了 linker 的實作
* 簡化加載: executable 的加載變得相對容易，要將 object file 的 .text 和 .data 載入，Linux 會為其分配 virtual page 並標註為 invalid，然而不直接複製內容至記憶體中，直到 page 被首次使用

## VM as a tool for memory protection

virtual memory system 可以透過 PTE 的標記來規範每個地址的存取權限。

## Address translation

virtual address 該如何轉換成 physical address 呢? 形式上而言，地址的轉換是將一個包含 N 個元素的 virtaul address space V({0,1,...N-1}) 映射到一個包含 M 個元素的 physical address space P({0,1,...M-1}) 的過程。

$$
MAP: V → P \cup {\emptyset}
$$

對於一個 virtual address $a$，如果可能轉換成一個 physical address $a'$ 或者不存在對應。


上圖展示了 MMU 透過 page table 完成前述行為的過程。一個 n bits 長度的 virtual address 包含了 VPN 和 VPO 兩個部分。MMU 透過 VPN 來索引 page table 以找到正確的 PTE:
* 如果 valid bit 被設置，表示 page hit，則將 PTE 中的 PPN 與 VPO 串聯起來，就可以得到 physical address，以此位址去存取 cache / memory
* 如果 valid bit 未被設置，觸發 page fault exception，控制轉移到 page fault handler 來選擇 physical page 中的某個 page 被替換，並更新 PTE。從 page fault handler 返回後，再次執行原本造成 page fault 的指令，此時狀況就變成了 page hit

## Multi-Level Page Tables
如果延續前面的說法，假設系統中 page 大小為 4KB，使用 48 bits 的定址空間, 且 PTE 大小需要 8-byte 的情況下，無論一個程序是否需要完整的 48 bits 空間，總是需要一個大小為 $8 * (2^{48} / 2^{12}) = 2^{39}$ bytes 的 page table 常駐在記憶體中，這個大小對於記憶體來說可說是個龐大的負擔。針對這個問題，最好的解決方法是使用一個多級的 page table 架構。


從上圖中展現的 2 級 page table 架構可以理解多級 page table 的好處，因為只有一級 page table 需要常駐在記憶體中，而如果第一級的 page table 的 pte 為空，則第二級的 page table 就可以不必存在，而對於一般的程式而言，原本就不常需要用盡整個定址空間，因此就可以有效地降低記憶體的需求。

## TLB

將 page table 轉換成多層級的結構需要更多次的存取 PTE，這似乎對效能會產生重大的影響，所幸，[Translation Lookaside Buffer (TLB)](https://en.wikipedia.org/wiki/Translation_lookaside_buffer) 的存在可以有效避免此種問題的頻繁發生。


可以理解 TLB 為一個虛擬轉址的 cache，假設 TLB 有 $2^t$ 個 set，VPN 中的最低之 t bit 就被當成 index，剩餘位元則做為 tag。則地址轉換的流程為: CPU 透過傳遞 virtual address 給 MMU，MMU 會取出 VPN 的 index 部分來查詢 TLB 的對應 set，如果存在相同的 tag，就可以直接取出 TLB 中對應的 PTE 進行轉址，如果不命中，才真正去存取多層級的 PTE 以得到相應的 physical address，且 TLB 反映近期存取的 PTE 而被更新。而受益於 locality 的影響，TLB miss 並不會頻繁發生，因此地址的轉換成本得以被有效的優化。

## Memory mapping

Linux 系統中通過將一個 virtual memory 區域對應到 disk 上的物件已建立記憶體的映射(memory mapping)。這個區域可以是:
* 普通文件(regular file):檔案中的 section 以 page 為單位區分成多個 chunk 建立 virtual page，直到這些 virtual page 被引用時，才配置實體記憶體並從 disk 中複製內容
* 匿名文件(anonymous file): 匿名文件由 kernel 建立，CPU 初次引用時，在實體記憶體中找到 page 建立對應，映射的區域在與 disk 間沒有數據的傳送

### Virtual memory in Linux

在 Linux 系統中，kernel 會為每個 process 維護一個獨立的 `task_struct` 結構，這個結構包含 process 需要的相關信息(例如 pid, user stack pointer, program counter 位置等)。而其中還包含一個 `mm_struct`，`mm_struct` 中一個關鍵的變數是 `pgd`，這指向第一級 page table 的位址，另一個則是 `mmap`，這是一個 `vm_area_struct` 結構的 linked list，每個單元都描述一個當前的 virtual memory area，具體的重要成員包含:
* `vm_start`: 指向區域的起始
* `vm_end`: 指向區域的結束
* `vm_prot`: 描述這個區域的存取權限
* `vm_flags`: 描述區域的特性(例如是否與其他 process 共享)


在理解了 `vm_area_struct` 之後，讓我們更進一步的來看 Linux 對於 page fault 的處理程序。當 MMU 在試圖存取一個 virtual address $a$ 時，觸發 page fault，:

1. 檢查 $a$ 是否存在 `vm_area_struct` 中標示的範圍中，如果不是則會觸發 segmentation fault
2. 如果存在某個 `vm_area_struct` 的範圍，則對該區段的存取權限進行檢查，例如，是否對只讀的 page 嘗試做寫入操作? 或者 user space process 嘗試寫入 kernel 的範圍?
3. 如果前述的檢查顯示了對此位址的存取合法，MMU 就去選擇一個頁面然後替換之並更新 page table。再次存取 $a$ 就能夠正確的轉換 $a$ 到正確的 physical page 了

### Private object and Shared object

一個 object 可以被映射到實體記憶體中，並作為 private object 或者 shared object 存在。


假設 process 1 將一個 shared object 映射到自己的 virtual memory area 中，另一個 process 2 可以將同一個 shared object 也映射到自己的空間中(且不一定要在和 process 1 相同的虛擬位址)。對於 shared object，共享的任一 process 對其內容的改變也會反映到其他共享的 process，同時也反映到 disk 上的內容。附帶一提，實際上 shared object 載入 physical memory 並不要求連續。


而對於 private object，一種稱作 [Copy-on-write](https://en.wikipedia.org/wiki/Copy-on-write) 的技術可以被使用以映射到記憶體中。如上圖所展示的，private object 起始的生命週期和 shared object 相同，共享的實體記憶體區塊被標記為 read-only 且 private copy-on-write，如果沒有 process 嘗試改寫此區域，它們就可以維持共享的狀態。與之相對的，如果某個 process 嘗試寫入，則觸發 protection fault，handler 會建立一個新的可讀可寫副本並重新映射，再次返回觸發 fault 的指令時，寫入操作就可以正常的執行了。