111 年 國立成功大學電機工程學系碩士班已組《計算機組織與作業系統》

核心觀念

本題考查三種 CPU 排程法：

• FCFS（First-Come, First-Served）：依到達時間先後執行，通常為非搶先式。
• SJF（Shortest Job First）：每次 CPU 空閒時，從已到達的程序中選擇 Burst Time 最短者執行，通常指非搶先式。
• RR（Round Robin）：每個程序最多執行一個 Quantum，未完成者排到就緒佇列尾端。

相關定義如下：

$$\text{Waiting Time}=\text{First CPU Start Time}-\text{Arrival Time}$$ $$\text{Turnaround Time}=\text{Completion Time}-\text{Arrival Time}$$

亦可使用：

$$\text{Turnaround Time}=\text{Waiting Time}+\text{Burst Time}$$

平均值為：

$$\text{Average Waiting Time} =\frac{\sum \text{Waiting Time}}{5}$$ $$\text{Average Turnaround Time} =\frac{\sum \text{Turnaround Time}}{5}$$

本題的 SJF 採用非搶先式 SJF。

---

（a）FCFS

依到達時間排序：

$$P1 \rightarrow P2 \rightarrow P3 \rightarrow P4 \rightarrow P5$$

甘特圖

0        10              39   42       49             61
|   P1   |       P2       | P3 |  P4   |      P5      |

各程序計算

Process	執行區間	Completion Time	Waiting Time	Turnaround Time
P1	0–10	10	$0-0=0$	$10-0=10$
P2	10–39	39	$10-1=9$	$39-1=38$
P3	39–42	42	$39-2=37$	$42-2=40$
P4	42–49	49	$42-3=39$	$49-3=46$
P5	49–61	61	$49-4=45$	$61-4=57$

因此：

$$\text{Average Waiting Time} =\frac{0+9+37+39+45}{5} =\frac{130}{5} =26\text{ ms}$$ $$\text{Average Turnaround Time} =\frac{10+38+40+46+57}{5} =\frac{191}{5} =38.2\text{ ms}$$

---

（b）SJF

時間 $t=0$ 時只有 $P1$ 已到達，因此先執行 $P1$。

時間 $t=10$ 時，$P2、P3、P4、P5$ 都已到達，其 Burst Time 分別為 $29、3、7、12$，所以依短作業優先選擇：

$$P3 \rightarrow P4 \rightarrow P5 \rightarrow P2$$

甘特圖

0        10   13       20          32                       61
|   P1   | P3 |   P4   |     P5     |          P2            |

各程序計算

Process	執行區間	Completion Time	Waiting Time	Turnaround Time
P1	0–10	10	$0-0=0$	$10-0=10$

核心觀念

本題考查作業系統中**分段記憶體管理（Segmentation Memory Management）**的邏輯位址至實體位址轉換（Address Translation）。

在分段記憶體機制中，邏輯位址（Logical Address）由一個二元組 $(s, d)$ 表示：

• $s$：段號（Segment Number）
• $d$：段內位移量（Offset）

記憶體管理單元（MMU）進行位址轉換時的兩大核心要點：

1. 合法性檢查（Limit / Length Check）：
   位移量 $d$ 必須嚴格小於該段的長度限制 $\text{Length}[s]$。
   $d < \text{Length}[s]$
   若 $d \ge \text{Length}[s]$，代表存取範圍超出該段大小，硬體會觸發 Trap 產生定址錯誤（Addressing Error / Segment Fault）。
2. 實體位址計算（Physical Address Calculation）：
   若檢查合法，實體位址（Physical Address, PA）為基址加上位移量：
   $\text{PA} = \text{Base}[s] + d$

---

解題方法

對每一個邏輯位址 $(s, d)$，依循下列三步驟推導：

1. 查表找出段號 $s$ 對應的基址 $\text{Base}[s]$ 與長度限制 $\text{Length}[s]$。
2. 進行邊界判斷：比對 $d < \text{Length}[s]$ 是否成立。
3. 若成立，計算 $\text{PA} = \text{Base}[s] + d$；若不成立，直接判定為定址錯誤（Addressing Error / Trap）。

---

選項與小題詳細解析

(a) 邏輯位址 $(0, 430)$

• 對應數據：$s = 0, d = 430$。查表得 $\text{Base}[0] = 210$，$\text{Length}[0] = 600$。
• 合法性檢查：$d = 430 < 600$（成立，合法）。
• 實體位址計算：
  $\text{PA} = \text{Base}[0] + d = 210 + 430 = 640$

(b) 邏輯位址 $(1, 10)$

• 對應數據：$s = 1, d = 10$。查表得 $\text{Base}[1] = 2300$，$\text{Length}[1] = 14$。
• 合法性檢查：$d = 10 < 14$（成立，合法）。
• 實體位址計算：

核心觀念

1. 有效存取時間（Effective Access Time, EAT）的物理意義：
   EAT 是指 CPU 在存取記憶體資料時，考量了記憶體階層架構（Memory Hierarchy）、轉譯後備緩衝區（TLB）命中與否、頁表（Page Table）查詢以及分頁錯誤（Page Fault）引發之磁碟 I/O 開銷後，平均每次讀取或寫入資料所需花費的時間期望值。

2. 核心公式與分路架構：
   在單階分頁（1-Level Paging）結合 TLB 的系統中，存取邏輯位址依序經歷 TLB 查詢、頁表查詢與磁碟讀寫。其算式結構如下：
   $\text{EAT} = T_{\text{TLB}} + \text{命中路徑開銷} + \text{未命中路徑開銷}$
   具體可分為三個互斥事件：

   • TLB Hit（機率 $h$）：時間成本 $= T_{\text{TLB}} + M$
   • TLB Miss 且 Page Hit（機率 $(1 - h)(1 - p)$）：時間成本 $= T_{\text{TLB}} + 2M$
   • TLB Miss 且 Page Fault（機率 $(1 - h)p$）：時間成本 $= T_{\text{TLB}} + 2M + \text{Page Fault Overhead}$

3. 單位統一（Unit Conversion）：
   本題給定時間單位包含 $\text{ns}$、$\mu\text{s}$ 與 $\text{ms}$，計算前必須統一單位：

   • $1\,\text{ms} = 10^3\,\mu\text{s} = 10^6\,\text{ns}$
   • $1\,\mu\text{s} = 10^3\,\text{ns}$

---

解題方法

Step 1：已知條件整理與單位統一（統一轉換為 $\mu\text{s}$）

• TLB 命中率 ($h$)：$90\% = 0.9$
• TLB 未命中率 ($1 - h$)：$10\% = 0.1$
• TLB 存取時間 ($T_{\text{TLB}}$)：$200\,\text{ns} = 0.2\,\mu\text{s}$
• 主記憶體存取時間 ($M$)：$100\,\mu\text{s}$
• 分頁錯誤率 ($p$)：$0.001\% = 0.00001 = 10^{-5}$
• 單頁磁碟存取時間 ($T_{\text{disk}}$)：$15\,\text{ms} = 15,000\,\mu\text{s}$

Step 2：分頁錯誤（Page Fault）開銷分析

題目明確規定：「每一個 page fault 皆包含 page replacement（同時考量 swap-in 與 swap-out 時間）」。

• 當 Page Fault 發生時，必須先將記憶體中髒頁（Dirty Page）寫回磁碟（Swap-out），耗時 $15\,\text{ms}$。
• 接著從磁碟讀入目標頁面（Swap-in），耗時 $15\,\text{ms}$。
• 因此，每次 Page Fault 產生的總磁碟處理時間為：
  $\text{Page Fault Overhead} = 2 \times T_{\text{disk}} = 2 \times 15\,\text{ms} = 30\,\text{ms} = 30,000\,\mu\text{s}$

Step 3：建立三路徑 EAT 總算式

1. 路徑 1（TLB Hit）：
   • 機率：$0.9$
   • 時間：$T_{\text{TLB}} + M = 0.2 + 100 = 100.2\,\mu\text{s}$
2. 路徑 2（TLB Miss 且 Page Hit）：
   • 機率：$(1 - 0.9) \times (1 - 10^{-5}) = 0.1 \times 0.99999$
   • 時間：$T_{\text{TLB}} + M(\text{查頁表}) + M(\text{讀資料}) = 0.2 + 100 + 100 = 200.2\,\mu\text{s}$
3. 路徑 3（TLB Miss 且 Page Fault）：
   • 機率：$(1 - 0.9) \times 10^{-5} = 0.1 \times 0.00001$
   • 時間：$T_{\text{TLB}} + M(\text{查頁表}) + 2 \times T_{\text{disk}}(\text{Swap-in + Swap-out}) + M(\text{重新存取資料})$
   • 耗時：$0.2 + 100 + 30,000 + 100 = 30,200.2\,\mu\text{s}$

Step 4：列出最終計算算式

將上述路徑組合，可得到依題目要求的完整計算列式：
$\text{EAT} = 0.9 \times (0.2 + 100) + 0.1 \times (1 - 10^{-5}) \times (0.2 + 200) + 0.1 \times 10^{-5} \times (0.2 + 200 + 30,000) \quad (\mu\text{s})$

核心觀念

本題考查作業系統（Operating Systems）與計算機組織（Computer Architecture）中**同步原語（Synchronization Primitives）**在不同系統架構下的實作原理與硬體限制。

1. 臨界區（Critical Section）與互斥（Mutual Exclusion）：
   當多個執行緒（Threads）或行程（Processes）競爭存取共享資源時，同步原語必須確保互斥性，即同一時間僅允許一個執行緒進入臨界區存取共享變數，以避免競態條件（Race Condition）。
2. 單處理器系統（Uniprocessor Systems）的關閉中斷機制：
   在單核 CPU 中，執行緒在臨界區被打斷並引發競爭條件的唯一途徑是外部中斷（如時脈中斷 Timer Interrupt）所導致的強制搶佔（Preemption）與上下文切換（Context Switch）。因此，進入臨界區前「關閉中斷（Disable Interrupts）」、離開後「開啟中斷（Enable Interrupts）」即可有效保證原子性（Atomicity）與互斥性。
3. 多處理器系統（Multiprocessor / Multi-core Systems）的平行執行特性：
   多處理器系統擁有多個獨立運作的 CPU Core，可同時平行（Parallel）執行不同的程式碼。

---

解題方法

說明為何「關閉中斷」不適用於多處理器系統，需從互斥失效、系統開銷與硬體架構三個層面進行深入切入與分析：

1. 互斥性失效（Failure of Mutual Exclusion）

關閉中斷指令（例如 x86 的 cli 指令）具有本機性（Local Effect Only），僅能防止發出指令的該顆 CPU Core 產生上下文切換。

• 當 CPU Core A 執行關閉中斷指令並進入臨界區時，CPU Core B 與 CPU Core C 仍處於中斷開啟狀態，且完全不知情。
• CPU Core B 與 C 依然可以同時執行並存取位於共享記憶體（Shared Memory）中的相同臨界區資源。
• 這導致關閉中斷完全無法防止多核心之間的平行競爭，互斥保證宣告失敗。

2. 跨核心廣播中斷開銷過高（Prohibitive Overhead of Inter-Processor Interrupts, IPI）

若嘗試修改機制，令 CPU Core A 在進入臨界區時透過跨處理器中斷（Inter-Processor Interrupt, IPI）廣播給系統中的所有其他 CPU Core，強制它們一併關閉中斷並停止執行：

• 廣播訊息與等待所有核心回應（Acknowledge）會引發極大的匯流排開銷（Bus Overhead）與記憶體延遲。
• 隨著系統核心數量 $N$ 的增加，同步開銷呈 $O(N)$ 甚至更高的指數級成長，嚴重破壞系統的可擴充性（Scalability）與效能。

3. 多處理器系統的正確同步機制

多處理器系統的同步原語必須仰賴硬體層級提供的原子操作指令（Hardware Atomic Instructions）：

• 例如：Test-and-Set (tas)、Compare-and-Swap (cas) 或 Load-Linked / Store-Conditional (LL/SC)。

核心觀念

本題考查作業系統（Operating System）基於硬體支援的雙模式運作（Dual-Mode Operation）與特權保護機制（Privileged Protection Mechanism）。

在現代電腦系統中，為了防止使用者程式（User Program）故意或無意地破壞作業系統核心、修改關鍵記憶體區域，或非法存取硬體資源（如 I/O 裝置），硬體（CPU）必須提供兩種或多種執行模式：

• 使用者模式（User Mode）：受限的執行環境，只能執行非特權指令，無法直接存取硬體與保護記憶體。
• 核心模式（Kernel Mode / Monitor Mode / Supervisor Mode / System Mode）：具備完全權限的執行環境，可執行所有指令（含特權指令）與存取所有記憶體位址。
• 模式位元（Mode Bit）：硬體暫存器（如狀態暫存器 PSW, Program Status Word）中的一個 bit，用以區分目前 CPU 處於何種模式。習慣上，用 $0$ 代表 Kernel Mode，用 $1$ 代表 User Mode。
• 特權指令（Privileged Instruction）：可能損害系統安全或干擾其他程序的指令（如設定 Base/Limit 暫存器、關閉中斷、直接執行 I/O 操作、切換 Mode Bit 等）。此類指令僅能在 Kernel Mode 下執行；若在 User Mode 下試圖執行特權指令，硬體會產生 Trap/Exception 並將控制權交給 OS。

---

解題方法

1. 雙模式運作機制說明

雙模式運作的核心目的在於達成系統保護（System Protection）。其運作原則如下：

1. 硬體支援模式位元：CPU 內部維護一個 Mode Bit。當電腦開機（Booting）時，硬體自 Kernel Mode ($Mode\ bit = 0$) 啟動並載入 OS；當 OS 準備將控制權移交給 User Process 時，會執行特權指令將 $Mode\ bit$ 設定為 $1$（切換至 User Mode）。
2. 特權指令防禦機制：當 CPU 在 User Mode 下執行指令時，硬體會檢視該指令是否為特權指令。若為特權指令且 $Mode\ bit = 1$，硬體會立即攔截並觸發 Illegal Instruction Trap，將 CPU 控制權強制轉移給 OS 的 Trap Handler 處置（通常為終止該違規程序）。
3. 安全切換管道：當 User Process 需要使用硬體資源或 OS 服務時，無法直接執行特權指令，必須透過發起系統呼叫（System Call）、觸發陷阱（Trap/Exception）或受到硬體中斷（Hardware Interrupt），促使硬體自動將 $Mode\ bit$ 置為 $0$，控制權切換回 Kernel Mode 中的中斷服務程式（ISR）。

2. 從 User Mode 切換至 Kernel Mode 之轉換流程與圖示

模式轉移的完整生命週期可分為以下步驟：

1. User Mode 執行：User Process 於 User Mode ($Mode\ bit = 1$) 順利執行一般運算。
2. 觸發轉移（System Call / Trap / Interrupt）：
   • 使用者發起 System Call（例如讀取檔案 read()）。
   • 或發生 Trap/Exception（例如除以零 Divide-by-zero、缺頁 Page Fault）。
   • 或外部硬體發出 Interrupt（例如 Timer 到期、Disk I/O 完成）。
3. 硬體自動切換模式：
   • 硬體自動將 $Mode\ bit$ 由 $1$ 設定為 $0$（進入 Kernel Mode）。
   • 將當前程序的執行狀態（PC、PSW、通用暫存器等）推入 Kernel Stack。
   • 硬體根據 Interrupt Vector Table 尋找對應的 ISR / System Call Handler 位址，並將 PC 設定為該 Handler 的起始位址。
4. Kernel Mode 處理服務：作業系統執行對應的特權指令完成要求之 I/O 或資源管理。
5. 返還控制權：
   • OS 完成服務後，執行返回指令（如 return-from-interrupt / iret / sysret）。
   • 硬體自動重置 $Mode\ bit = 1$（恢復至 User Mode）。
   • 恢復先前儲存的 User Process 暫存器狀態，繼續執行 User Process。

Transition Diagram（模式轉換狀態圖）：

                  +-----------------------------------+
                  |            User Mode              |
                  |          (Mode bit = 1)           |
                  +-----------------------------------+
                                    |
                                    |  1. System Call / Trap / Interrupt
                                    |     (Hardware sets Mode bit = 0)
                                    v
                  +-----------------------------------+
                  |            Kernel Mode            |
                  |          (Mode bit = 0)           |
                  +-----------------------------------+
                                    |
                                    |  2. Execute Privileged Instructions
                                    |     and System Services
                                    v
                  +-----------------------------------+
                  |     Return-from-interrupt / iret  |
                  |     (Hardware sets Mode bit = 1)  |
                  +-----------------------------------+
                                    |
                                    v
                  +-----------------------------------+
                  |            User Mode              |
                  |          (Mode bit = 1)           |
                  +-----------------------------------+

---

選項分析

本題屬於簡答與繪圖題（Essay / Short Answer Question），無選項。評分要點與答題構面分析如下：

核心觀念

本題考查多位元組資料在記憶體中的排列方式，也就是 Endian（位元組序）。

一個 4 bytes 的數值 0x13579ACE 可拆成四個位元組：

$$0x13579ACE = \underbrace{0x13}_{\text{最高有效位元組}} \ \underbrace{0x57}_{} \ \underbrace{0x9A}_{} \ \underbrace{0xCE}_{\text{最低有效位元組}}$$

• Little-endian：最低有效位元組放在最低記憶體位址。
• Big-endian：最高有效位元組放在最低記憶體位址。

題目指定資料從位址 $0$ 開始，且 word size 為 4 bytes，因此會使用位址 $0$、$1$、$2$、$3$。

解題方法

先將 32 位元數值由高位元組到低位元組排列：

位元組意義	數值
最高有效位元組（MSB）	0x13
次高位元組	0x57
次低位元組	0x9A
最低有效位元組（LSB）	0xCE

接著依照位址由小到大的順序填入記憶體。

(a) Little-endian machine

Little-endian 將最低有效位元組 0xCE 放在最低位址 $0$：

記憶體位址	儲存內容
0	0xCE
1	0x9A
2	0x57
3	0x13

因此記憶體排列為：

$$\boxed{ \begin{array}{c|cccc} \text{Address} & 0 & 1 & 2 & 3 \\ \hline \text{Data} & \texttt{CE} & \texttt{9A} & \texttt{57} & \texttt{13} \end{array} }$$

(b) Big-endian machine

Big-endian 將最高有效位元組 0x13 放在最低位址 $0$：

記憶體位址	儲存內容
0	0x13
1	0x57
2	0x9A
3	0xCE

因此記憶體排列為：

核心觀念

本題整合測試計算機組織與結構（Computer Organization and Architecture）的多個核心觀念：

1. 效能評估指標（Performance Evaluation Metrics）：MIPS（Million Instructions Per Second）的定義、限制及其為何不能跨架構比較效能。
2. 算術與邏輯位移（Shift Operations & Integer Arithmetic）：邏輯右移（Logical Right Shift）與算術右移（Arithmetic Right Shift）在補碼（Two's Complement）表示法下對無號數與有號數進行除法（Division by Power of 2）時的取整行為（Rounding Behavior）差異。
3. 管線化處理器吞吐量（Pipeline Throughput）：單一管線處理器在理想狀況下的 IPC（Instructions Per Cycle）、CPI（Cycles Per Instruction）與加速比（Speedup）之關係。
4. 區域性原理（Principle of Locality）：時間區域性（Temporal Locality）與空間區域性（Spatial Locality）如何作為記憶體階層（Memory Hierarchy）的理論基礎，用以緩解主記憶體長延遲（Memory Access Latency）問題。
5. 快取缺失三分法（3C Miss Model）：強制缺失（Compulsory Misses）、容量缺失（Capacity Misses）與衝突缺失（Conflict Misses）的成因及應對改善策略。

---

解題方法

本題為計算機組織與結構的觀念選擇題，解題切入點如下：

1. 分析 (a)：引用 CPU 效能方程式 $\text{CPU Time} = \text{Instruction Count} \times \text{CPI} \times \text{Clock Cycle Time}$，檢驗 MIPS 能否客觀反應不同處理器執行同一程式的總時間。
2. 分析 (b)：分別檢視無號整數（Unsigned）與補碼有號整數（Signed）在右移運算中的算術結果，比較向零取整（Truncate toward zero）與向負無窮大取整（Floor toward $-\infty$）的差異。
3. 分析 (c)：釐清「吞吐量（IPC）」與「加速比（Speedup）」的定義，推導單管線（Single Pipeline）在理想狀態下的每週期完成指令數。
4. 分析 (d)：從快取記憶體（Cache Memory）設計初衷出發，確認記憶體階層結構如何利用區域性定理（Principle of Locality）縮短平均記憶體存取時間（AMAT）。
5. 分析 (e)：運用 3C Miss 模型定義，評估增加快取總容量（Cache Size）對容量缺失（Capacity Misses）的影響。

---

選項分析

• (a) 錯誤
  MIPS（Million Instructions Per Second，每秒百萬條指令）之定義公式為：
  $\text{MIPS} = \frac{\text{Instruction Count}}{\text{Execution Time} \times 10^6} = \frac{\text{Clock Rate}}{\text{CPI} \times 10^6}$
  使用 MIPS 評估兩台不同處理器的整體效能有以下致命缺點：

  1. 忽略指令集架構（ISA）差異：不同 ISA 的處理器執行相同程式所需的指令數（Instruction Count, IC）不同。若 A 處理器需要執行較多簡單指令，其 MIPS 可能很高，但總執行時間反而比 MIPS 較低的 B 處理器更長。
  2. 忽略指令複雜度（CPI 差異）：同一處理器執行不同程式時，CPI 會有所變化，導致 MIPS 隨程式而異。
     因此，MIPS 不能單獨作為比較不同處理器整體效能（Overall Performance）的可靠指標。

• (b) 錯誤
  在無號整數（Unsigned Integer）的情況下，邏輯右移（Logical Right Shift）$k$ 位元確實等於整數除以 $2^k$。然而，在補碼（Two's Complement）有號整數（Signed Integer）的情況下：

  1. 標準整數除法（如 C 語言與多數 ISA）採向零取整（Truncate toward zero）。例如：$-3 / 2 = -1$。

核心觀念

本題考驗經典五階段 RISC 管線處理器（5-stage RISC-V/MIPS Pipeline Processor）對**記憶體讀取指令（Load Instruction）**的執行流程與資料路徑（Data Path）細節。

典型的五階段管線包含以下五個順序執行的階段，各階段之間透過管線暫存器（Pipeline Registers，如 IF/ID、ID/EX、EX/MEM、MEM/WB）傳遞資料與控制訊號：

1. IF（Instruction Fetch，取指階段）
2. ID（Instruction Decode / Register Read，譯碼與暫存器讀取階段）
3. EX（Execute / Address Calculation，執行與位址計算階段）
4. MEM（Memory Access，記憶體存取階段）
5. WB（Write Back，寫回暫存器階段）

指令 ld rd, immed(rs1) 的功能為從記憶體中讀取一個雙字組（Doubleword，64 位元 / 8 位元組），其目標記憶體有效位址（Effective Address）為基底暫存器 $\text{Reg}[\text{rs1}]$ 的數值加上符號擴充後的立即數 $\text{immed}$，最後將讀出的資料寫回目的暫存器 $\text{rd}$ 中。

---

解題方法

分析 ld rd, immed(rs1) 在五階段管線處理器中每個階段的詳細運作機制與資料流動：

1. IF 階段（Instruction Fetch，取指階段）

• 動作：使用程式計數器（Program Counter, $PC$）儲存的位址，從指令記憶體（Instruction Memory）中擷取 32 位元的 ld 指令碼。
• 計算：同時透過加法器計算下一個順序指令位址：
  $PC_{\text{new}} = PC + 4$
• 鎖存：將讀出的 ld 指令碼與 $PC + 4$ 鎖存至 IF/ID 管線暫存器 中，準備供下個階段使用。

2. ID 階段（Instruction Decode / Register Read，譯碼與暫存器讀取階段）

• 指令解碼與控制：主控制單元（Main Control Unit）解碼 IF/ID 中的指令碼，識別為 Load 指令，並產生該指令所需的所有控制訊號（如 ALUSrc、MemRead、RegWrite、MemtoReg 等）。
• 暫存器讀取：根據指令中的來源暫存器欄位 rs1，從暫存器檔案（Register File）讀取基底暫存器的值 $\text{Reg}[\text{rs1}]$。
• 立即數擴充：立即數產生器（Immediate Generator）將指令中的 12 位元立即數 immed 進行符號擴充（Sign-extension），生成 64 位元的擴充值 $\text{SignExt}(\text{immed})$。
• 鎖存：將 $\text{Reg}[\text{rs1}]$、$\text{SignExt}(\text{immed})$、目的暫存器代碼 rd 及控制訊號鎖存至 ID/EX 管線暫存器 中。

3. EX 階段（Execute / Address Calculation，執行與位址計算階段）

• 位址計算：多工器根據控制訊號 ALUSrc = 1 選擇符號擴充後的立即數作為算術邏輯單元（ALU）的第二個輸入源。ALU 執行加法運算，計算記憶體有效位址：
  $\text{Effective Address} = \text{Reg}[\text{rs1}] + \text{SignExt}(\text{immed})$
• 鎖存：將計算出的有效位址 $\text{Effective Address}$、欲寫回的目的暫存器代碼 rd 及 MEM/WB 階段需要的控制訊號鎖存至 EX/MEM 管線暫存器 中。

4. MEM 階段（Memory Access，記憶體存取階段）

• 記憶體讀取：在控制訊號 MemRead = 1 作用下，將 EX/MEM 管線暫存器中的有效位址傳送至資料記憶體（Data Memory / Cache）的位址輸入端，從記憶體讀出 64 位元（8 位元組）的資料：
  $\text{Data} = \text{Mem}\left[\text{Reg}[\text{rs1}] + \text{SignExt}(\text{immed})\right]$
• 鎖存：將讀出的 64 位元資料、目的暫存器代碼 rd 以及 WB 階段控制訊號鎖存至 MEM/WB 管線暫存器 中。

核心觀念

1. TLB 的全稱與定義：

   • TLB 的全稱為 Translation Lookaside Buffer（中文常譯為轉譯後備緩衝區）。
   • 它是一個位於記憶體管理單元（MMU）內的特殊高速快取記憶體（Cache），專門用於存放最近使用過的「虛擬頁碼（VPN, Virtual Page Number）至實體頁碼（PFN, Physical Frame Number）」之位址轉譯對（Page Table Entry, PTE）。
   • 在記憶體階層（Memory Hierarchy）中，TLB 的存取速度極快（通常為 $1 \text{ to } 2$ 個 CPU 週期），能避免每次進行虛擬位址轉換時都必須存取位於主記憶體（DRAM）中的頁表（Page Table），有效降低平均記憶體存取時間（AMAT）。

2. TLB Miss（TLB 缺失）：

   • 當 CPU 發出虛擬位址欲存取記憶體時，MMU 會先在 TLB 中搜尋對應的轉譯紀錄。若未命中（即 TLB 內無該頁面的轉譯資料），稱為 TLB Miss。

---

解題方法

當 TLB Miss 發生時，系統必須取得實體位址。在計算機結構中，TLB Miss Handler 的處理機制主要分為 硬體管理（Hardware-managed TLB） 與 軟體管理（Software-managed TLB） 兩大類，解題時應將兩種架構的完整處理流程分別說明：

1. 硬體管理機制（Hardware-Managed TLB Miss）

代表架構：x86, ARM

• Step 1：硬體走訪頁表（Page Table Walk）
  當 TLB 發生 Miss 時，MMU 硬體會自動讀取頁表基底暫存器（如 x86 的 CR3 暫存器），在主記憶體中進行多層頁表走訪（Page Table Walk），尋找對應的頁表項（PTE）。
• Step 2：判斷 PTE 狀態
  • 狀況 A：PTE 存在於主記憶體中（Present bit / Valid bit = 1）
    MMU 硬體自動將查到的 PTE 載入（Update）TLB 中，並自動重試（Retry）剛才被暫停的記憶體存取指令，完成位址轉譯。
  • 狀況 B：PTE 顯示頁面不在主記憶體中（Present bit / Valid bit = 0）
    硬體無法單獨解決，會觸發一個中斷異常 Page Fault（頁面錯誤），將控制權移交給作業系統核心（OS Kernel）的 Page Fault Handler（從磁碟將資料頁面載入 RAM，更新頁表後再返回重試指令）。

2. 軟體管理機制（Software-Managed TLB Miss）

代表架構：MIPS, SPARC, Alpha

• Step 1：引發 TLB Miss 異常（Trap/Exception）
  MMU 發現 TLB Miss 後，立刻暫停目前指令執行，硬體自動引發一個特權層級的 TLB Miss Trap，將 CPU 控制權移交給作業系統的 TLB Miss Handler。
• Step 2：軟體查表與寫入 TLB
  • OS 的 TLB Miss Handler 執行一段經過高度優化的核心程式碼，從記憶體頁表中尋找該虛擬頁碼對應的 PTE。
  • 找到 PTE 後，Handler 使用特權指令（例如 MIPS 的 tlbwi 或 tlbwr）將該 PTE 手動寫入 TLB 之中。
• Step 3：指令重試與例外接續
  Handler 執行結束後返回使用者模式，重新執行引發 TLB Miss 的指令。若 Handler 在走訪頁表時發現該頁面尚未載入主記憶體（Page Fault），則會轉由作業系統的 Page Fault Handler 處理磁碟 I/O。

---

選項分析

核心觀念

本題考查計算機架構中**動態分支預測（Dynamic Branch Prediction）**的核心機制——2-bit 滯後/飽和計數器分支預測器（2-bit Saturating Counter / Hysteresis Branch Predictor）。

1. 基本定義：

   • 動態分支預測器在硬體執行期（Runtime）記錄分支指令歷史執行的結果（Taken 或 Not Taken），並以此預測未來該分支是否會發生跳躍。
   • 1-bit 預測器僅紀錄上一次的結果，在遇到迴圈（Loop）結束或頻繁交替的分支時，容易發生連續兩次預測錯誤（Misprediction）。
   • 2-bit 預測器具備 4 個狀態，導入滯後性（Hysteresis），要求分支指令必須連續兩次預測錯誤才會徹底改變預測方向，大幅減低迴圈開頭與結尾的預測懲罰。

2. 狀態定義與輸出：
   2-bit 預測器內部由一個 2-bit 的飽和計數器組成，共有 4 個狀態：

   • 狀態 $11$（Strongly Taken）：輸出預測 Taken (T)
   • 狀態 $10$（Weakly Taken）：輸出預測 Taken (T)
   • 狀態 $01$（Weakly Not Taken）：輸出預測 Not Taken (NT)
   • 狀態 $00$（Strongly Not Taken）：輸出預測 Not Taken (NT)

---

解題方法

繪製 2-bit 分支預測器的狀態轉移圖時，必須明確標示狀態名稱/二進位編碼、該狀態對應的預測輸出（Predict T / Predict NT），以及在接收到實際執行結果（Taken / Not Taken）時的轉移條件。

1. 狀態轉移機制推導

• 實際結果為 Taken (T)：推動狀態向「Strongly Taken ($11$)」移動（計數器 $+1$，最大值飽和於 $11$）。
• 實際結果為 Not Taken (NT)：推動狀態向「Strongly Not Taken ($00$)」移動（計數器 $-1$，最小值飽和於 $00$）。

2. 2-bit 分支預測器狀態轉移圖（Finite State Machine Diagram）

                     +---------------------------------------+
                     |             Taken (T)                 |
                     v                                       |
             +---------------+   Not Taken (NT)      +---------------+
             | Strongly Taken|---------------------->|  Weakly Taken |
             |     (11)      |                       |     (10)      |
             |  [Predict T]  |<----------------------|  [Predict T]  |
             +---------------+       Taken (T)       +---------------+
                                                             |
                                                             | Not Taken (NT)
                                                             v
             +---------------+       Taken (T)       +---------------+
             |Strongly NT    |<----------------------| Weakly NT     |
             |     (00)      |                       |     (01)      |
             | [Predict NT]  |---------------------->|  [Predict NT] |
             +---------------+   Not Taken (NT)      +---------------+
                     ^                                       |
                     |             Not Taken (NT)            |
                     +---------------------------------------+

3. 狀態轉移表（State Transition Table）