虛擬記憶體 Virtual Memory

學習目標

理解虛擬記憶體的運作原理
掌握分頁 (Paging) 與分段 (Segmentation) 的區別
理解頁表 (Page Table) 的作用和運作方式
掌握頁面錯誤 (Page Fault) 的處理流程
了解頁面置換演算法

1. 為什麼需要虛擬記憶體？

1.1 問題背景

在沒有虛擬記憶體的系統中，存在以下問題：

記憶體容量限制: 程式大小受限於實體記憶體容量
多程式執行困難: 多個程式難以同時載入記憶體
記憶體碎片: 頻繁的分配和釋放會產生碎片
程式保護困難: 程式可能存取到其他程式的記憶體空間

1.2 虛擬記憶體的解決方案

虛擬記憶體提供了一個邏輯位址空間，這個空間可以遠大於實際的實體記憶體，讓每個程式都認為自己擁有完整的記憶體空間。

2. 虛擬記憶體的運作原理

2.1 基本概念

虛擬記憶體是一種記憶體管理技術，它為每個行程提供一個： - 獨立的邏輯位址空間 - 連續的邏輯位址空間（從程式角度看起來是連續的） - 可以遠大於實際實體記憶體的位址空間

2.2 運作方式

邏輯位址空間分割: 作業系統將行程的邏輯位址空間分割成塊（頁或段）
按需載入: 只將目前需要的部分載入實體記憶體
其餘部分存放在磁碟: 不需要的部分存放在輔助儲存裝置（如硬碟）上
動態交換: 當需要時，將磁碟上的資料載入記憶體，將記憶體中的資料寫回磁碟

2.3 位址轉換

當程式存取記憶體時： 1. 程式使用的是邏輯位址 (Logical Address) 或虛擬位址 (Virtual Address) 2. 記憶體管理單元 (MMU) 將邏輯位址轉換為實體位址 (Physical Address) 3. 使用實體位址存取實際的記憶體

程式視角: 邏輯位址 0x1000
         ↓ (MMU 轉換)
實際記憶體: 實體位址 0x5000

3. 分頁 (Paging) vs 分段 (Segmentation)

3.1 分頁 (Paging)

定義

將邏輯位址空間切成固定大小的「頁 (Page)」，實體記憶體也切成相同大小的「頁框 (Frame)」。

特點

固定大小: 所有頁的大小相同（通常為 4KB 或 8KB）
使用者不可見: 由硬體和作業系統處理，程式設計師不需要關心
一維對應: 透過頁表進行簡單的線性對應
內部碎片: 最後一頁可能沒有完全使用，產生內部碎片

優點

簡單高效
容易實現
減少外部碎片

缺點

產生內部碎片
頁的大小可能不符合程式的邏輯結構

3.2 分段 (Segmentation)

定義

將邏輯位址空間切成不同大小、具邏輯意義的「段 (Segment)」，如程式碼段、資料段、堆疊段。

特點

可變大小: 段的大小根據實際需要決定
邏輯意義: 每個段有明確的用途（程式碼、資料、堆疊等）
使用者可見: 程式設計師可以指定段
二維對應: 透過段表進行對應，需要段號和段內位移
外部碎片: 不同大小的段會產生外部碎片

優點

符合程式的邏輯結構
容易實現共享和保護
段的大小可以動態調整

缺點

產生外部碎片
管理較複雜
需要複雜的記憶體分配演算法

3.3 比較表

特性	分頁 (Paging)	分段 (Segmentation)
分割單位	固定大小的「頁 (Page)」	不同大小、具邏輯意義的「段 (Segment)」
使用者觀點	使用者不可見，由硬體處理	使用者可見，程式設計師可指定段
記憶體碎片	產生內部碎片 (Internal Fragmentation)	產生外部碎片 (External Fragmentation)
位址對應	透過「頁表 (Page Table)」進行一維對應	透過「段表 (Segment Table)」進行二維對應
大小	固定（通常 4KB）	可變（根據需要）
邏輯結構	不考慮程式的邏輯結構	符合程式的邏輯結構

3.4 混合方式：段頁式 (Segmented Paging)

現代作業系統通常結合兩種方式： - 先分段（符合邏輯結構） - 再分頁（簡化管理）

4. 頁表 (Page Table)

4.1 定義

頁表 (Page Table) 是一個資料結構，用於儲存邏輯頁 (Page) 與實體記憶體頁框 (Frame) 之間的對應關係。

4.2 頁表結構

每個行程都有自己的頁表，頁表的每一項（頁表項，Page Table Entry）包含：

頁框號 (Frame Number): 對應的實體頁框號碼
有效位 (Valid Bit): 表示該頁是否在實體記憶體中
Valid = 1: 頁在記憶體中
Valid = 0: 頁不在記憶體中（在磁碟上）
修改位 (Dirty Bit): 表示該頁是否被修改過（用於決定寫回磁碟時是否需要更新）
存取權限: 讀、寫、執行權限

4.3 位址轉換過程

當 CPU 產生一個邏輯位址時，記憶體管理單元 (MMU) 會進行以下步驟：

步驟 1: 拆分邏輯位址

邏輯位址分為兩部分： - 頁碼 (Page Number): 高位部分，用於索引頁表 - 頁內位移 (Offset): 低位部分，用於定位頁內的位置

邏輯位址: [頁碼 | 頁內位移]
例如: 32 位元位址，頁大小 4KB (12 位元)
     頁碼: 20 位元
     頁內位移: 12 位元

步驟 2: 查詢頁表

MMU 以頁碼為索引查詢該行程的頁表，找到對應的頁表項。

頁碼 = 5
→ 查詢頁表第 5 項
→ 得到頁框號 = 10

步驟 3: 檢查有效位

如果有效位 = 1（頁在記憶體中）：
繼續步驟 4
如果有效位 = 0（頁不在記憶體中）：
觸發頁面錯誤 (Page Fault)
作業系統處理頁面錯誤（見第 5 節）

步驟 4: 組合實體位址

將實體頁框號碼與頁內位移組合，形成最終的實體記憶體位址。

實體位址 = (頁框號 × 頁大小) + 頁內位移
例如: 頁框號 = 10, 頁內位移 = 0x123
     實體位址 = (10 × 4096) + 0x123 = 0xA123

4.4 位址轉換範例

假設： - 邏輯位址: 0x1234 - 頁大小: 4KB (0x1000) - 頁表: 頁 1 對應到頁框 5

轉換過程： 1. 拆分邏輯位址: - 頁碼 = 0x1234 / 0x1000 = 1 - 頁內位移 = 0x1234 % 0x1000 = 0x234

查詢頁表: - 頁 1 → 頁框 5
組合實體位址: - 實體位址 = (5 × 0x1000) + 0x234 = 0x5234

4.5 頁表的問題與優化

問題：頁表太大

如果邏輯位址空間很大，頁表也會很大。例如： - 32 位元位址空間，頁大小 4KB - 需要 2²⁰ = 1,048,576 個頁表項 - 每個頁表項 4 位元組 - 總大小 = 4MB（每個行程！）

解決方案

多級頁表 (Multi-level Page Table) - 將頁表分層，只載入需要的部分 - 減少記憶體使用
轉換後備緩衝區 (TLB - Translation Lookaside Buffer) - 快取最近使用的頁表項 - 大幅提高轉換速度

5. 頁面錯誤 (Page Fault)

5.1 發生時機

當行程試圖存取一個在頁表中標記為「無效 (invalid)」的頁面時，表示該頁面目前不在實體記憶體中，會觸發頁面錯誤。

5.2 處理流程

步驟 1: CPU 產生 Trap

當 MMU 發現有效位 = 0 時： - CPU 產生一個 trap（中斷） - 將控制權轉交給作業系統 - 保存當前行程的狀態

步驟 2: 檢查合法性

作業系統檢查此記憶體存取是否合法： - 檢查邏輯位址是否在行程的合法範圍內 - 檢查存取權限（讀、寫、執行）

如果不合法： - 終止行程（段錯誤，Segmentation Fault）

如果合法： - 繼續步驟 3

步驟 3: 尋找空閒頁框

在實體記憶體中尋找一個空閒的頁框 (Frame)：

情況 A: 有空閒頁框 - 直接使用該頁框

情況 B: 沒有空閒頁框 - 執行頁面置換演算法（見第 6 節） - 選擇一個「犧牲頁框 (Victim Frame)」 - 如果犧牲頁框被修改過（Dirty Bit = 1），先寫回磁碟 - 清空該頁框

步驟 4: 載入頁面

將所需的頁面從磁碟讀取到找到的頁框中： - 從磁碟的對應位置讀取頁面資料 - 寫入實體記憶體的頁框 - 這是一個 I/O 操作，需要時間

步驟 5: 更新頁表

更新頁表： - 將該頁的對應頁框號碼填入頁表 - 將有效位 (valid bit) 設為「有效 (valid)」 - 更新其他相關位元（如存取位、修改位）

步驟 6: 重新執行指令

將控制權交還給原行程
重新執行導致頁面錯誤的指令
這次應該可以成功存取（頁面已在記憶體中）

5.3 處理流程圖

頁面錯誤發生
    ↓
CPU 產生 Trap
    ↓
作業系統接管
    ↓
檢查存取合法性
    ↓ (不合法) → 終止行程
    ↓ (合法)
尋找空閒頁框
    ↓ (沒有) → 執行頁面置換
    ↓ (有)
從磁碟載入頁面
    ↓
更新頁表
    ↓
重新執行指令

6. 頁面置換演算法

當實體記憶體已滿，需要載入新頁面時，必須選擇一個頁面置換出去。常用的演算法有：

6.1 最佳置換 (Optimal)

原理： 選擇未來最長時間不會被使用的頁面。

優點： 理論上最佳

缺點： 需要知道未來的存取序列，實際無法實現

用途： 作為其他演算法的比較基準

6.2 先進先出 (FIFO)

原理： 選擇最早進入記憶體的頁面。

優點： 簡單易實現

缺點： 可能置換掉經常使用的頁面（Belady's Anomaly）

6.3 最近最少使用 (LRU - Least Recently Used)

原理： 選擇最長時間沒有被存取的頁面。

優點： 符合程式執行的局部性原理，效能好

缺點： 實現複雜，需要記錄存取時間

實現方式： - 使用計數器記錄最後存取時間 - 使用堆疊記錄存取順序

6.4 時鐘演算法 (Clock)

原理： 類似 LRU，但實現更簡單。

運作方式： - 使用一個時鐘指標循環掃描頁框 - 每個頁框有一個參考位 (Reference Bit) - 當頁面被存取時，參考位設為 1 - 置換時，選擇參考位為 0 的頁面，並將掃描過的頁面參考位設為 0

7. 練習題

練習題 1

請說明虛擬記憶體的運作原理。

參考答案： 虛擬記憶體為每個行程提供一個獨立的、連續的邏輯位址空間，這個空間可以遠大於實際的實體記憶體。作業系統將行程的邏輯位址空間分割成塊，只將目前需要的部分載入實體記憶體，其餘部分存放在磁碟上。當需要時，動態地交換記憶體和磁碟的內容。

練習題 2

請比較分頁和分段的差異。

參考答案： - 分頁: 固定大小，使用者不可見，產生內部碎片，一維對應 - 分段: 可變大小，使用者可見，產生外部碎片，二維對應，符合邏輯結構

練習題 3

請說明頁面錯誤的處理流程。

參考答案： 1. CPU 產生 trap 2. 作業系統檢查合法性 3. 尋找空閒頁框（沒有則執行頁面置換） 4. 從磁碟載入頁面 5. 更新頁表 6. 重新執行指令

8. 考試重點提醒

虛擬記憶體原理: 要能清楚說明為什麼需要虛擬記憶體以及它如何運作
分頁 vs 分段: 這是必考重點，要能清楚比較兩者的差異
頁表作用: 理解頁表如何進行位址轉換
頁面錯誤處理: 要能詳細說明處理流程的每個步驟
頁面置換: 了解常見的置換演算法（LRU 最重要）