虛擬記憶體練習題 (Practice - Virtual Memory)

Key Patterns (click to expand)

關鍵字	答案
DRAM cache miss 在 VM 中的名稱	page fault;handler 換頁後重新執行 faulting instruction
PTE valid=0、位址 null vs 非 null	null → Unallocated;非 null → Uncached(指向 disk)
DRAM cache 組織	fully associative + write-back + 大頁(miss 由 disk 服務,代價 ~100,000 倍)
PTE 數量公式	$# PTE = N / P = 2^{n - p}$
VPN/VPO 切法	VPO = PPO = $\log_{2} P$ bits;VPN = $n - p$ bits;PPO 不需轉譯
TLBI / TLBT	TLBI = VPN 最低 $t$ 位( $T = 2^{t}$ sets);TLBT = VPN 其餘高位
權限違規	general protection fault → kernel 送 SIGSEGV
demand-zero page	映射匿名檔案的頁;首次 touch 覆寫 victim 為 0,無磁碟資料傳輸
寫入 private COW 頁	protection fault → 複製該頁、更新 PTE、恢復寫入權限、重跑指令
malloc 對齊	32-bit mode:8 的倍數;64-bit mode:16 的倍數
internal vs external fragmentation	block > payload vs 總量夠但無單一夠大 free block
boundary tags	footer = header 複本 → 常數時間合併前一個 block
garbage 定義	從 root nodes(暫存器、stack 變數、全域變數)不可達的已配置區塊
C 的 GC 為何 conservative	記憶體無型別標記,int/float 可偽裝成指標,只能保守標為可達

Question 1 - Page Fault 語意 [recall]

CPU 存取某虛擬位址時,MMU 讀到的 PTE valid bit 為 0 且位址欄位非 null。
請說明:(a) 這代表該虛擬頁處於什麼狀態?(b) 接下來由誰處理、做哪些事?(c) handler 返回後 CPU 執行哪條指令?

查看答案

(a) 該頁已配置但未快取 (Uncached)——位址欄位指向 disk 上該 VP 的位置。
(b) MMU 觸發 page fault exception,kernel 的 page fault handler 接手:選 victim page(dirty 則先寫回 disk)、把目標頁從 disk 換入、更新 PTE。
(c) 重新執行 (restart) 造成 fault 的那條指令——fault 類例外的語意;這次存取變成 page hit。
解析:若位址欄位為 null 則是 Unallocated,存取它不會被換入而是錯誤。

Question 2 - DRAM Cache 的組織 [recall]

與 SRAM cache (L1/L2/L3) 相比,VM 系統的 DRAM cache 在相聯度、寫入策略、頁大小上如何設計?根本原因是什麼?

查看答案

DRAM cache 採 fully associative(任何 VP 可放任何 PP)、一律 write-back、大頁(典型 4 KB–2 MB)。
根本原因:miss 由 disk 服務,disk 比 DRAM 慢約 100,000 倍,miss penalty 巨大 → 一切設計以極小化 miss 率為優先;disk 太慢也不可能 write-through。

Question 3 - PTE 權限位元與違規處理 [recall]

教科書簡化的 PTE 含 SUP、READ、WRITE 三個權限位元。
(a) SUP=Yes 的頁在 user mode 可否存取?(b) 指令違反權限位元時,系統的完整處理鏈為何?(c) 為何說權限檢查是「零額外成本」?

查看答案

(a) 不可;user mode 只能存取 SUP=No 的頁,kernel mode 才能存取任何頁。
(b) CPU 觸發 general protection fault → 控制權轉給 kernel exception handler → kernel 對行程送 SIGSEGV → shell 回報 "segmentation fault"。
(c) MMU 每次轉譯本來就要讀 PTE,權限檢查只是順路多看幾個位元,不需額外記憶體存取。

Question 4 - TLB 的角色與欄位切法 [recall]

(a) TLB 是什麼、cache 的內容是什麼、放在哪裡?(b) 若 TLB 有 $T = 2^{t}$ 個 set,TLBI 與 TLBT 各取虛擬位址的哪些位元?(c) TLB miss 一定會導致 page fault 嗎?

查看答案

(a) TLB (translation lookaside buffer) 是 MMU 內的小型、virtually addressed 的 PTE cache,通常高關聯度,每行存一個 PTE。
(b) TLBI = VPN 的最低 $t$ 位、TLBT = VPN 其餘高位——注意是切 VPN,不是整個 VA(VPO 不參與)。
(c) 不一定。TLB miss 只是要去 memory/cache 讀 PTE;PTE valid=1 就沒有 page fault。

Question 5 - 多層 Page Table 省記憶體的機制 [recall]

32-bit 位址空間、4 KB 頁、4-byte PTE 的單層 page table 需要 4 MB 常駐記憶體。兩層階層化後靠哪兩個機制省下記憶體?多層轉譯要查 k 次 PTE,為何實務上不明顯變慢?

查看答案

機制一:若某 4 MB chunk 內全部頁未配置,L1 PTE 為 null,對應的 level 2 表根本不必存在(典型程式大部分位址空間未配置)。
機制二:只有 level 1 表須常駐記憶體,level 2 表可按需建立、換入換出。
不變慢的原因:TLB 會 cache 各層的 PTE,常用轉譯直接命中。

Question 6 - Demand-Zero Pages 與 Swap Space [recall]

Linux memory mapping 的 area 可映射到 regular file 或 anonymous file。
(a) 什麼是 demand-zero page?首次 touch 時發生什麼、有無磁碟資料傳輸?(b) 頁面初始化之後在哪裡換入換出?該空間的大小限制了什麼?

查看答案

(a) 映射到匿名檔案(kernel 建立、內容全 0)的頁。首次 touch 時 kernel 找一個 victim page(dirty 則先換出)、覆寫為全 0、更新 page table 標為 resident——磁碟與記憶體間沒有任何實際資料傳輸。
(b) 之後在 kernel 維護的 swap file (swap space) 間換入換出;swap space 大小限制所有執行中 process 可配置的虛擬頁總量。

Question 7 - Shared vs Private Object [recall]

兩個 process 以 mmap 映射磁碟上同一個物件。請比較 shared object 與 private object:(a) 寫入對其他映射者是否可見?(b) 寫入是否回寫磁碟?(c) 兩 process 的映射虛擬位址必須相同嗎?

查看答案

(a)(b) Shared object(MAP_SHARED):寫入對其他映射者可見,且會回寫到磁碟上的原物件。Private object(MAP_PRIVATE):兩者皆否——寫入時 COW 產生私有副本。
(c) 不必相同;kernel 靠物件的唯一檔名判斷已映射,直接讓兩邊 PTE 指向同一份物理頁(物理記憶體只存一份)。

Question 8 - malloc/free 的基本契約 [recall]

(a) malloc 回傳的 block 在 32-bit 與 64-bit mode 各對齊到幾的倍數?回傳的記憶體有初始化嗎?(b) free(ptr) 的 ptr 必須滿足什麼條件?違反時會怎樣?(c) 要取得清零的記憶體、或改變已配置 block 大小,分別用什麼函式?

查看答案

(a) 32-bit mode 為 8 的倍數、64-bit mode 為 16 的倍數;malloc 不初始化記憶體。
(b) ptr 必須指向由 malloc/calloc/realloc 取得之 block 的開頭;否則為 undefined behavior,且 free 無回傳值、不回報任何錯誤,常導致很久之後才發作的詭異錯誤。
(c) 清零用 calloc;改大小用 realloc。

Question 9 - 兩種碎片化 [recall]

區分 internal fragmentation 與 external fragmentation:各自的定義、成因,以及哪一種難以量化、為什麼?

查看答案

Internal:allocated block 比 payload 大(對齊 padding、最小 block size 限制);容易量化 = Σ(block size − payload),只取決於過去的 requests 與實作。
External:總 free 空間足夠,但沒有單一 free block 夠大;難以量化——它還取決於未來 requests 的模式,無法預測。
解析:allocator 不允許 compaction(搬動已配置 block),所以 external fragmentation 無法靠搬動解決,只能靠 heuristics 維持少量大 free blocks。

Question 10 - PTE 數量與位址欄位計算 [application]

某系統虛擬位址 n = 24 bits、實體位址 m = 20 bits、頁大小 P = 2 KB。
計算:(a) page table 的 PTE 數量;(b) VPN、VPO、PPN、PPO 各佔幾個 bits。

查看答案

P = 2 KB → p = 11。
(a) $# PTE = 2^{n - p} = 2^{24 - 11} = 2^{13} = 8192$ 。
(b) VPO = PPO = 11 bits;VPN = 24 − 11 = 13 bits;PPN = 20 − 11 = 9 bits。
解析:虛實頁大小相同,故 PPO = VPO 直接照抄、不需轉譯;PTE 數只跟虛擬位址空間與頁大小有關。

Question 11 - Implicit Free List 的 Block Size 與 Header [application]

配置器使用 implicit free list,double-word (8-byte) 對齊,block 格式為 1-word (4-byte) header + payload + 選擇性 padding(無 footer)。
求 malloc(9) 與 malloc(20) 產生的 block size,以及各自 header 的十六進位值(allocated)。

查看答案

Block size = round_up(payload + 4, 8)。
malloc(9):9 + 4 = 13 → 向上取整到 16 bytes;header = 0x10 | 0x1 = 0x11。
malloc(20):20 + 4 = 24,已是 8 的倍數 → 24 bytes;header = 0x18 | 0x1 = 0x19。
解析:header 的 size 是整個 block(含 header 與 padding),不是 payload;低 3 bits 恆為 0,最低位借來當 allocated bit。

Question 12 - fork 後的 Copy-on-Write [application]

執行以下程式,fork 之後父子行程都還沒寫入任何資料,接著子行程對陣列元素賦值:
int *buf = malloc(4096);        /* 恰好一頁 */
buf[0] = 1;                     /* fork 前已 touch */
if (fork() == 0) {
    buf[0] = 42;                /* 子行程寫入 */
}
說明 fork 當下 kernel 對虛擬記憶體做了什麼、子行程執行 buf[0] = 42 時硬體與 kernel 依序發生哪些事,以及此機制一次複製多少資料。

查看答案

fork 當下:kernel 只複製 metadata——mm_struct、area structs、page tables;父子雙方的每一頁 PTE 都標 read-only、每個 area struct 標 private copy-on-write,不複製任何物理頁。
子行程寫入時:PTE 為 read-only → 觸發 protection fault → handler 發現是寫入 private COW area → 在物理記憶體複製該頁、更新子行程 PTE 指向新副本、恢復寫入權限 → 返回後 CPU 重新執行該寫入指令,成功寫到新頁。
一次只複製被寫入的那一頁(4 KB),不是整個位址空間——把複製延遲到最後一刻,是 fork 低成本的關鍵。

Question 13 - Mark&Sweep 走訪與 Conservative GC [analysis]

某 heap 有已配置區塊 1–6,指標關係:3→1、4→3、4→6、6→2;唯一的 root 指向區塊 4。另外,區塊 5 的 payload 中有一個 int,其值恰好等於區塊 2 的 payload 位址。
(a) 在 exact collector 下,mark 階段後哪些區塊被標記?sweep 後哪些被回收?(b) 換成 C 的 conservative collector,且假設某 root 可達區塊中含上述那種偽裝值指向區塊 5,結果會有何不同?為什麼 C 只能這樣做?

查看答案

(a) 從 root 走訪:4 → {3, 6},3 → 1,6 → 2 ⇒ 標記 {1, 2, 3, 4, 6};sweep 回收唯一「已配置但未標記」的區塊 5。
(b) Conservative collector 無法分辨那個 int 是不是指標,只能保守地把區塊 5 標為可達 ⇒ 區塊 5 漏收,本輪沒有任何區塊被回收。
根因:C 的記憶體不帶型別標記,isPtr 無法判斷一個字組是 int/float 還是指標;保證是「可達必標記(correct)」,代價是誤標不可達區塊,造成不必要的 external fragmentation,但不影響程式正確性。

Question 14 - 記憶體錯誤診斷 [analysis]

以下三段 C 程式各含一個經典記憶體錯誤,請指出錯誤、解釋底層機制,並說明各自最可能的發作方式:
/* (a) */ int val; scanf("%d", val);
/* (b) */ int *p = malloc(n * sizeof(int)); int sum = 0;
          for (int i = 0; i < n; i++) sum += p[i];
/* (c) */ int *stackref(void) { int val = 42; return &val; }

查看答案

(a) 解參考壞指標:漏了 &,scanf 把 val 的內容當位址寫入。最好的情況是寫到 VM 空洞/唯讀區立即觸發 segmentation/protection exception;最壞是 val 恰為合法 R/W 位址而默默覆寫,很久之後才爆炸。
(b) 讀未初始化記憶體:heap 記憶體不保證為 0(.bss 才由 loader 清零),sum 是垃圾值。修法:改用 calloc 或顯式初始化。
(c) 參考已消失的變數:回傳 stack 區域變數位址;函式返回後 frame 被 pop,位址仍「合法」但變數已無效,之後解參考可能改到其他函式的 stack frame。
共同特徵:action at a distance——發作點與病灶在時間與空間上都相距甚遠,難以除錯。

Pattern Summary (click to expand)

答題模式	要點
PTE 判讀	valid=1 → cached;valid=0 + null → unallocated;valid=0 + 非 null → uncached(page fault 換入)
fault 類例外語意	page fault / COW protection fault 處理完都重跑原指令;權限違規則 SIGSEGV 終止
位址欄位計算	先算 $p = \log_{2} P$ ;VPO=PPO=p;VPN=n−p;PPN=m−p;#PTE= $2^{n - p}$ ;TLBI 取 VPN 低 t 位
DRAM cache 設計	一切由「miss 由 disk 服務、貴 10 萬倍」推導:fully associative、write-back、大頁
映射性質判斷	anonymous → demand-zero(無磁碟 I/O);shared → 一份物理副本、寫入可見且回寫;private → COW
COW 三步	protection fault → 只複製被寫的那一頁 + 更新 PTE + 恢復權限 → 重跑寫入指令
block size 計算	round_up(payload + overhead, 對齊);header = size \| alloc bit;size 含 header/padding
碎片化分類	block > payload → internal(可量化);總量夠但無單一夠大 → external(取決於未來 requests)
GC 走訪題	從 root 做圖走訪標記;sweep 回收「已配置且未標記」;C 為 conservative(偽裝指標→誤標可達)
記憶體 bug 題	先問「寫到哪裡去了」:壞指標/越界/已釋放/已 pop 的 frame;共同特徵 action at a distance

Related Concepts

Question 1 - Page Fault 語意 [recall]

Question 2 - DRAM Cache 的組織 [recall]

Question 3 - PTE 權限位元與違規處理 [recall]

Question 4 - TLB 的角色與欄位切法 [recall]

Question 5 - 多層 Page Table 省記憶體的機制 [recall]

Question 6 - Demand-Zero Pages 與 Swap Space [recall]

Question 7 - Shared vs Private Object [recall]

Question 8 - malloc/free 的基本契約 [recall]

Question 9 - 兩種碎片化 [recall]

Question 10 - PTE 數量與位址欄位計算 [application]

Question 11 - Implicit Free List 的 Block Size 與 Header [application]

Question 12 - fork 後的 Copy-on-Write [application]

Question 13 - Mark&Sweep 走訪與 Conservative GC [analysis]

Question 14 - 記憶體錯誤診斷 [analysis]