108 年 國立成功大學電腦與通信工程研究所甲組《計算機組織與作業系統》

核心觀念

本題考查作業系統架構設計中的**可載入核心模組（Loadable Kernel Modules, LKMs）**機制。核心架構演進從傳統的單體核心（Monolithic Kernel）與微核心（Microkernel），發展出現代廣泛採用的模組化單體核心（Modular Monolithic Kernel）。理解 LKMs 的設計思想、動態連結（Dynamic Linking）機制以及相較於傳統架構的優勢，是計算機組織與作業系統的核心考點。

解題方法

針對問答題的解題切入點如下：

1. (a) 設計思想：從物件導向與模組化概念切入，說明核心僅保留最關鍵的最小功能（Core Kernel），而將驅動程式、檔案系統與網路協定等擴充功能設計為獨立模組，在執行時期（Runtime）根據需求動態載入（Load）與卸載（Unload）。
2. (b) 主要優勢：從「記憶體利用率」、「靈活性與擴充性」、「維護與開發效率」以及「效能與架構折衷（結合單體核心高效能與微核心模組化的雙重優點）」等維度進行系統化列舉與對比說明。

題型與子題分析

本題為觀念申論與分析題，分為 (a)、(b) 兩子題，以下進行詳細分析與導出：

(a) 設計思想（Design Idea of LKMs）

1. 物件導向與介面導向設計（Object-Oriented & Interface-Driven Design）：
   • 核心主體（Core Kernel）僅提供最根本的系統服務（如 CPU 排程、記憶體管理、基礎 IPC 與系統呼叫介面）。
   • 擴充功能（如裝置驅動程式 Device Drivers、檔案系統 File Systems、網路協定堆疊 Network Protocols 等）均實作於獨立的模組（Modules）中，透過定義良好的介面（Interfaces）與核心主體溝通。
2. 執行時期動態連結（Runtime Dynamic Linking / Late Binding）：
   • 模組不需要在編譯核心時預先靜態連結（Static Linking）。
   • 當系統需要某項功能（例如插入 USB 裝置或掛載新的檔案系統）時，作業系統可在執行時期將該模組動態載入核心空間（Kernel Space）並進行符號解析與連結；不使用時可主動卸載以釋放記憶體。

(b) 使用可載入核心模組的優勢（Advantages of LKMs）

1. 動態靈活性與無須重啟（Dynamic Flexibility & No Reboot Required）：
   • 新增、更新或移除系統功能與驅動程式時，完全不需要重新編譯核心（Recompile Kernel）或重啟系統（Reboot），大幅提升高可用性系統（如伺服器）的營運穩定度。
2. 高效的記憶體使用率（Memory Efficiency）：
   • 核心記憶體（Kernel Space Memory）為常駐且不可換出（Non-pageable）的珍貴資源。LKMs 採用「按需載入（Load-on-Demand）」策略，僅在需要時才載入模組，減輕記憶體負擔。
3. 兼具單體核心的高效能與微核心的模組化優點（Best of Both Worlds）：

核心觀念

本題考查作業系統中的**死鎖偵測（Deadlock Detection）**機制。

當系統未採用死鎖預防（Deadlock Prevention）或死鎖避免（Deadlock Avoidance）時，系統允許進入不安全狀態（Unsafe State），因而可能發生死鎖。此時系統必須定期或在資源無法滿足時，執行死鎖偵測演算法檢查系統狀態，以判斷死鎖是否已經發生。

死鎖偵測演算法依據系統中「每種資源類型的實體數量（Instances of Resource Types）」分為兩種架構：

1. 單一資源實體（Single Instance per Resource Type）：使用**等待圖（Wait-For Graph, WFG）**演算法。
2. 多個資源實體（Multiple Instances per Resource Type）：使用基於矩陣運算的死鎖偵測演算法（Deadlock-Detection Algorithm）。

解題方法

說明兩種資源配置情境下的演算法運作邏輯與推導步驟：

一、 單一資源實體：等待圖（Wait-For Graph, WFG）演算法

當每種資源類型僅有一個實體時，可將資源分配圖（Resource-Allocation Graph, RAG）簡化為等待圖（Wait-For Graph）：

1. 圖形構建：從資源分配圖中移除所有資源節點，並收折邊線。若行程 $P_i$ 正等待行程 $P_j$ 所持有的資源，則建立一條由 $P_i$ 指向 $P_j$ 的有向邊（$P_i \to P_j$）。
2. 死鎖判定：系統定期執行尋找環路（Cycle-Detection）演算法。當且僅當等待圖中存在**環路（Cycle）**時，系統處於死鎖狀態。
3. 時間複雜度：$O(n^2)$，其中 $n$ 為系統中的行程數量。

二、 多個資源實體：死鎖偵測演算法（Deadlock-Detection Algorithm）

當資源類型包含多個實體時，需利用動態資料結構模擬資源回收過程。

1. 資料結構定義

假設系統有 $n$ 個行程（$P_1, P_2, \dots, P_n$）與 $m$ 種資源（$R_1, R_2, \dots, R_m$）：

• $Available[m]$：長度為 $m$ 的向量，表示各類資源目前剩餘的可利用實體數。
• $Allocation[n \times m]$：$n \times m$ 矩陣，表示各行程目前已獲分配的資源數量。
• $Request[n \times m]$：$n \times m$ 矩陣，表示各行程目前實際提出並等待中的資源請求數量。
• $Work[m]$：長度為 $m$ 的工作向量（暫存可用資源）。
• $Finish[n]$：長度為 $n$ 的布林向量，標記行程是否能順利執行完成。

2. 演算法執行步驟

• 步驟 1：初始化
  $Work = Available$
  對所有 $i = 1, 2, \dots, n$：
  若 $Allocation_i \neq 0$，則 $Finish[i] = \text{false}$；
  否則 $Finish[i] = \text{true}$。（註：完全未佔用資源的行程不可能參與死鎖）

• 步驟 2：尋找可滿足的行程
  尋找一個同時滿足下列兩個條件的指標 $i$：
  $\text{(a) } Finish[i] == \text{false}$
  $\text{(b) } Request_i \le Work$
  若找不到符合條件的 $i$，直接跳至步驟 4。

核心觀念

本題考驗作業系統（Operating System）中記憶體管理（Memory Management）的核心機制——**分頁（Paging）與轉換旁路快取（Translation Look-aside Buffer, TLB）**的硬體架構與定址轉換流程。

1. 分頁機制（Paging Scheme）：

   • 目的：實現非連續記憶體配置（Non-contiguous Memory Allocation），徹底解決實體記憶體的外部斷頭（External Fragmentation）問題。
   • 空間分割：
     • 邏輯位址空間（Logical Address Space）：切割為固定大小的區塊，稱為頁面（Page）。
     • 實體位址空間（Physical Address Space）：切割為相同大小的區塊，稱為頁框（Frame）。
   • 頁表（Page Table）：由作業系統維護的資料結構，記錄「頁號（Page Number）」與「頁框號（Frame Number）」的對應關係。
   • 位址分割：CPU 產生的邏輯位址分為兩部分：
     • 頁號 $p$（Page Number）：作為頁表的索引（Index）。
     • 頁內位移 $d$（Page Offset）：表示資料在頁面內部的相對偏移量。若頁面大小為 $2^n$ 位元組（Bytes），則 $d$ 佔用低位元 $n$ bits。

2. 轉換旁路快取（TLB, Translation Look-aside Buffer）：

   • 痛點：純分頁機制下，存取一次資料需要存取記憶體兩次（第一次讀取頁表取得實體位址，第二次存取實際資料），導致記憶體效能減半。
   • 解決方案：採用硬體實作的專用高速相聯記憶體（Associative Memory）——TLB 來快取近期使用的頁表項目（Page Table Entries, PTEs）。
   • 有效存取時間（Effective Access Time, EAT）：
     $\text{EAT} = \alpha \times (t_{\text{TLB}} + t_m) + (1 - \alpha) \times (t_{\text{TLB}} + 2 \times t_m)$
     其中 $\alpha$ 代表 TLB 命中率（Hit Ratio），$t_{\text{TLB}}$ 為 TLB 尋找時間，$t_m$ 為主記憶體存取時間。

解題方法

分項詳細說明 (a) 基本分頁實作方法與 (b) 搭配 TLB 的硬體架構：

(a) 基本分頁實作方法（Basic Method to Implement Paging）

分頁機制的硬體轉換與實作邏輯如下：

1. 位址劃分（Address Structure）：
   CPU 所發出的邏輯位址（Logical Address）包含：

   • 高位元：頁號 $p$ (Page Number)
   • 低位元：頁內位移 $d$ (Page Offset)

2. 位址轉換步驟（Address Translation Steps）：

   • Step 1：CPU 發出邏輯位址 $(p, d)$。
   • Step 2：硬體以頁號 $p$ 作為索引，查尋位於主記憶體中的頁表（Page Table），取得對應的頁框號 $f$ (Frame Number)。
   • Step 3：由於頁面與頁框大小完全一致，頁內位移 $d$ 保持不變。將頁框號 $f$ 與位移 $d$ 組合形成實體位址 $(f, d)$。
   • Step 4：CPU 利用實體位址 $(f, d)$ 存取實體記憶體（Physical Memory）中的目標資料。

3. 保護與共享機制（Protection & Sharing）：

   • 頁表中每個項目皆可附加保護位元（Protection Bits），如唯讀（Read-Only）、可讀寫（Read-Write）或可執行（Execute），以及有效/無效位元（Valid/Invalid Bit）來判定頁面是否已載入記憶體。

(b) 搭配 TLB 的分頁硬體機制（Paging Hardware with TLB）

為了改善二次記憶體存取的效能瓶頸，加入 TLB 後的硬體架構與執行流程如下：

1. TLB 硬體特性：
   • TLB 為包含少數項目（通常 64 至 1024 項）的高速相聯暫存器（Associative Registers）。
   • 每個 TLB 項目儲存一個鍵值對（Key-Value Pair）：[ Tag (頁號 p) | Value (頁框號 f) ]。

核心觀念

本題考查傳統網路堆疊的封包接收流程，以及 NIC、DMA、核心封包緩衝區與使用者程式之間的資料傳遞。圖中標示為「Non-batching」，表示接收流程以單一封包為單位處理，未將多個封包合併批次處理。

解題方法

依照圖中的元件與箭頭，從封包進入實體網路開始，追蹤資料如何逐步送到使用者程式：

1. **封包抵達 NIC：**封包由實體連結進入網路介面卡（NIC）。
2. **DMA 傳輸：**NIC 將封包透過 DMA 傳送至 DMA 記憶體區域。DMA 完成後，NIC 發出中斷（IRQ）通知處理器。
3. **核心接收處理：**核心收到中斷後，將 DMA 記憶體區域中的封包資料複製到核心封包緩衝區。
4. **排入接收佇列：**核心呼叫 netif_rx()，將封包放入核心的接收緩衝區或佇列（圖中標為 mbuff），等待後續處理。

核心觀念

本題旨在考查電腦架構中控制流轉移指令（Control Transfer Instructions）的定址模式（Addressing Modes），特別是**間接跳躍（Indirect Jump）**的定義、執行機制及其在組合語言與作業系統／高階語言中的實際應用。

1. 間接跳躍（Indirect Jump）之定義：
   間接跳躍是指跳躍指令本身不直接包含目標位址（Target Address）的立即數（Immediate value），而是指定一個暫存器（Register）或記憶體位置（Memory Location），在執行期（Runtime）從該暫存器或記憶體中讀取目標位址，並將其載入至程式計數器（Program Counter, $\text{PC}$）中，以完成控制流程的轉移。
2. 與直接跳躍（Direct Jump）之對比：
   • 直接跳躍（Direct Jump）：目標位址在編譯／組譯期即已確定，並硬編碼（Hard-coded）於指令內部的欄位中（例如 MIPS 的 j target）。
   • 間接跳躍（Indirect Jump）：目標位址為動態決定，可在程式執行過程中改變（例如讀取暫存器或記憶體點陣圖）。
3. 程式計數器更新公式：
   在暫存器間接跳躍模式下，$\text{PC}$ 的更新邏輯為：
   $\text{PC} \leftarrow \text{Reg}[R_s]$
   在記憶體間接跳躍模式下，$\text{PC}$ 的更新邏輯為：
   $\text{PC} \leftarrow \text{Mem}[\text{Reg}[R_s] + \text{offset}]$

解題方法

1. 間接跳躍的觀念說明

間接跳躍允許程式在執行期根據動態計算或儲存的數據決定下一個執行的指令位置。由於目標位址儲存於可變動的暫存器或記憶體中，這給予了高階語言與系統軟體高度的彈性。

2. 指令範例（Instruction Examples）

在主流的指令集架構（ISA）中，間接跳躍指令的範例如下：

• MIPS 架構：
  • 指令：jr $ra (Jump Register)
  • 說明：將通用暫存器 $ra ($31$ 號暫存器，儲存 Return Address) 中的 $32$ 位元數值寫入 $\text{PC}$。執行後，硬體將跳轉至 $ra 所指向的記憶體位址繼續執行。
• x86 架構：
  • 暫存器間接：jmp eax（將 $\text{EAX}$ 暫存器的值載入至 $\text{EIP}$）。
  • 記憶體間接：jmp dword ptr [ebx]（從 $\text{EBX}$ 暫存器所指向的記憶體位址讀取 $32$ 位元目標位址，載入至 $\text{EIP}$）。
• RISC-V 架構：
  • 指令：jalr x0, 0(x1)（或虛擬指令 jr x1）
  • 說明：計算 $x1 + 0$ 的結果，並將其最低位元清零後載入 $\text{PC}$，同時將返回位址存入 $x0$（即忽略返回位址）。

3. 典型應用場景與 C 語言對照

間接跳躍在系統程式設計中有四大核心應用場景：

1. 子程序／函式返回（Function Return）：
   當被呼叫的子程序執行完畢時，需要返回呼叫者（Caller）。由於同一個子程序可能被多個不同的位置呼叫，返回位址必須動態儲存（例如 MIPS 的 $ra 暫存器或 Stack），並透過間接跳躍返回。
2. 函式指標（Function Pointers）：

核心觀念

本題旨在考驗微處理器系統之記憶體擴充設計與匯流排接線架構（Memory System Organization & Bus Interconnect Design）。核心觀念涵蓋以下四大主題：

1. 記憶體容量與模組擴充（Memory Capacity & Module Expansion）：
   • 當單一記憶體模組之資料寬度（Data Width）小於系統資料匯流排寬度時，需採用**並聯（Parallel Expansion）**擴充資料字元寬度。
   • 當總記憶體容量需求大於單一列（Row/Bank）容量時，需採用**串聯（Series/Bank Expansion）**擴充位址空間深度。
   • 晶片總數推導公式：
     $\text{晶片總數 } N = \frac{\text{系統總記憶體容量}}{\text{單一晶片容量}}$
2. 位址空間分頁與位址對齊（Address Mapping & Alignment）：
   • 32 位元位址匯流排（$A_{31} \sim A_0$）可尋址 $2^{32} = 4\text{ GB}$ 空間。
   • $1\text{ MB}$ 容量對應 $2^{20}\text{ Bytes}$，佔用 20 位元的位址空間（$A_{19} \sim A_0$）。
   • 在位元組定址（Byte-addressable）且資料匯流排為 32 位元（4 Bytes）的系統中，最末兩位元（$A_1, A_0$）用作 Word 內部的 Byte 偏移量選擇（Byte Offset），晶片內部位址線連接系統位址線的 Word Address 部分。
3. 高位址區段解碼（Highest Segment Decoding）：
   • 題目指定配置於記憶體空間的最頂層 $1\text{ MB}$ 區段（Highest 1MB Segment），其十六進位位址範圍為 0xFFF00000 $\sim$ 0xFFFFFFFF。
   • 高位元位址（$A_{31} \sim A_20$共 12 位元）固定為全 $1$（1111 1111 1111），作為**區段解碼器（Segment Decoder）**之致能條件。
4. 階層式解碼架構（Hierarchical Decoding Architecture）：
   • 解碼架構分為三階：區段解碼（Segment Decoding） $\rightarrow$ Bank/列解碼（Bank Decoding） $\rightarrow$ 晶片內部定址（Internal Chip Address）。

解題方法

Step 1：計算晶片陣列結構（Memory Matrix Configuration）

1. 單一 SRAM 模組規格：

   • 容量：$32\text{K} \times 8\text{ bits} = 32\text{ KB}$。
   • 位址線：15 根（$2^{15} = 32\text{K}$），標示為 $A_{14} \sim A_0$。
   • 資料線：8 根（1 Byte），標示為 $D_7 \sim D_0$。
   • 控制腳位：晶片選擇 $\overline{\text{CS}}$（Chip Select）、輸出致能 $\overline{\text{OE}}$（Output Enable / Read）、寫入致能 $\overline{\text{WE}}$（Write Enable）。

2. 陣列矩陣計算：

   • 系統資料匯流排為 32-bit（4 Bytes），每列（Row / Bank）必須由 4 顆 $32\text{K} \times 8$ SRAM 並聯構成：
     $\text{每列容量} = 32\text{ KB} \times 4 = 128\text{ KB}$
   • 總記憶體需求為 $1\text{ MB} = 1024\text{ KB}$，所需列數（Bank 數量）為：
     $\text{列數 (Rows)} = \frac{1024\text{ KB}}{128\text{ KB}} = 8\text{ 列}$
   • 所需 SRAM 晶片總數：
     $\text{晶片總數 } N = 8\text{ 列} \times 4\text{ 行} = 32\text{ 顆}$

Step 2：位址線分配與解碼邏輯（Address Decoding Scheme）

系統位址匯流排共 32 位元（$A_{31} \sim A_0$），位址拆解如下表：

1. 最高 1MB 區段解碼（$A_{31} \sim A_{20}$）：

   • 最高 $1\text{ MB}$ 位址範圍：0xFFF00000 $\sim$ 0xFFFFFFFF。
   • 二進位表示：
     • 起始位址 0xFFF00000：1111 1111 1111 0000 0000 0000 0000 0000
     • 結束位址 0xFFFFFFFF：1111 1111 1111 1111 1111 1111 1111 1111
   • 使用一組 12 輸入 AND 閘（或搭配 NAND 與反相器組成的區段解碼器），當且僅當 $A_{31} A_{30} \cdots A_{20} = 1111\,1111\,1111_2$ 時，輸出區段致能訊號 $E = 1$。

2. Bank / 列解碼器（$A_{19} \sim A_{17}$）：

   • 採用顆 3-to-8 解碼器（例如 74LS138）。
   • 解碼器致能端（Enable Input）連接至區段致能訊號 $E$。
   • 輸入端接 $A_{19}, A_{18}, A_{17}$，輸出 8 組低電位致能的列選擇訊號 $\overline{\text{CS}_0} \sim \overline{\text{CS}_7}$：
     • $A_{19}A_{18}A_{17} = 000_2 \Rightarrow \overline{\text{CS}_0} = 0$（致能 Row 0）
     • $A_{19}A_{18}A_{17} = 001_2 \Rightarrow \overline{\text{CS}_1} = 0$（致能 Row 1）
     • $\vdots$
     • $A_{19}A_{18}A_{17} = 111_2 \Rightarrow \overline{\text{CS}_7} = 0$（致能 Row 7）

3. 晶片內部位址線連接（$A_{16} \sim A_2$）：

   • 系統為 Byte-addressable，32-bit Data Bus 每筆 Word 傳輸佔 4 個 Bytes。
   • 系統位址 $A_1, A_0$ 決定 Word 內的 Byte Offset。
   • 因此，系統位址 $A_{16} \sim A_2$（共 15 根線）直接平行連接至所有 32 顆 SRAM 模組的位址腳位 $A_{14} \sim A_0$。

Step 3：資料匯流排與控制訊號連接（Data Bus & Control Connections）

1. 資料匯流排分段（Data Bus Partitioning）：
   32 顆 SRAM 排列成 8 列（Row 0 $\sim$ Row 7）$\times$ 4 行（Column 0 $\sim$ Column 3）：

   • Column 0（Byte 0, $D_7 \sim D_0$）：每一列的第 0 顆 SRAM 之 $D_7 \sim D_0$ 連接至系統資料匯流排 $D_7 \sim D_0$。
   • Column 1（Byte 1, $D_{15} \sim D_8$）：每一列的第 1 顆 SRAM 之 $D_7 \sim D_0$ 連接至系統資料匯流排 $D_{15} \sim D_8$。
   • Column 2（Byte 2, $D_{23} \sim D_{16}$）：每一列的第 2 顆 SRAM 之 $D_7 \sim D_0$ 連接至系統資料匯流排 $D_{23} \sim D_{16}$。
   • Column 3（Byte 3, $D_{31} \sim D_{24}$）：每一列的第 3 顆 SRAM 之 $D_7 \sim D_0$ 連接至系統資料匯流排 $D_{31} \sim D_{24}$。

2. 控制訊號連接（Control Signals）：

   • 讀取控制訊號 $\overline{\text{OE}}$：所有 32 顆 SRAM 的 $\overline{\text{OE}}$ 腳位全數平行連接至系統的讀取控制線（$\overline{\text{RD}}$ 或 $\overline{\text{MEMR}}$）。
   • 寫入控制訊號 $\overline{\text{WE}}$：所有 32 顆 SRAM 的 $\overline{\text{WE}}$ 腳位全數平行連接至系統的寫入控制線（$\overline{\text{WR}}$ 或 $\overline{\text{MEMW}}$）。
   • 晶片選擇訊號 $\overline{\text{CS}}$：第 $i$ 列（Row $i$, $i=0 \sim 7$）包含的 4 顆 SRAM，其 $\overline{\text{CS}}$ 腳位共同連接至 3-to-8 解碼器的第 $i$ 個輸出端 $\overline{\text{CS}_i}$（若需支援單一位元組存取 Byte Enable，可將 $\overline{\text{CS}_i}$ 另外與位元組致能訊號 $\overline{\text{BE}_3} \sim \overline{\text{BE}_0}$ 進行 OR 閘組合邏輯輸入）。

Step 4：整體記憶體系統架構示意圖

核心觀念

本題考查多處理器（Symmetric Multiprocessing, SMP）系統中**快取一致性協定（Cache Coherence Protocol）**的典型代表——MESI 協定（又稱 Illinois Protocol）。

MESI 協定是一種基於**寫回法（Write-Back）與寫無效化（Write-Invalidate）的匯流排偵聽（Bus Snooping）**協定。其核心目的在於保證多核心處理器在共享同一主記憶體空間時，各核心區域快取（L1/L2 Cache）內資料的一致性，同時減少不必要的匯流排廣播開銷。

MESI 協定名稱由其定義的 4 種快取區段（Cache Line）狀態首字母組成：

1. M (Modified)：修改狀態。快取區段僅存在於當前快取中，且已被修改過（與主記憶體資料不一致，為 Dirty 狀態）。當前處理器擁有獨占讀寫權。
2. E (Exclusive)：獨占狀態。快取區段僅存在於當前快取中，且未被修改過（與主記憶體資料一致，為 Clean 狀態）。當前處理器擁有獨占讀寫權。
3. S (Shared)：共享狀態。快取區段可能同時存在於其他處理器的快取中，且未被修改（與主記憶體資料一致，為 Clean 狀態）。當前處理器僅擁有唯讀權。
4. I (Invalid)：無效狀態。當前快取區段不包含有效資料（即快取未命中 Cache Miss，或資料已遭其他核心寫無效化）。

解題方法

回答 MESI 協定的問答題時，切入點應涵蓋以下三大層次：

1. 四大狀態定義與屬性：說明狀態在「資料獨占性（Exclusive/Shared）」與「記憶體一致性（Clean/Dirty）」上的維度分布。
2. 觸發事件分類：
   • 本機處理器動作（Local Processor Actions）：$\text{PrRd}$（處理器讀取）、$\text{PrWr}$（處理器寫入）。
   • 匯流排偵聽動作（Bus Snooped Actions）：$\text{BusRd}$（偵聽到其他核心讀取）、$\text{BusRdX}$（偵聽到其他核心讀取並意圖寫入）、$\text{BusUpgr}$（偵聽到其他核心發出升級使他人無效化請求）。
3. 狀態轉移機制（State Transition Dynamics）：
   • $\text{I} \rightarrow \text{E / S}$：發起 $\text{PrRd}$，若其他 Cache 均無此副本（以 Shared Line 判斷）則轉為 $\text{E}$；若其他 Cache 有副本則轉為 $\text{S}$。
   • $\text{E} \rightarrow \text{M}$：發起 $\text{PrWr}$，直接轉為 $\text{M}$，無需廣播匯流排無效化訊號（靜默升級，Silent Upgrade）。
   • $\text{S} \rightarrow \text{M}$：發起 $\text{PrWr}$，必須廣播 $\text{BusUpgr}$ 或 $\text{BusRdX}$ 強制其他核心將副本轉為 $\text{I}$ 後方可升級為 $\text{M}$。
   • 任何非 $\text{I}$ 狀態偵聽到外部 $\text{BusRdX}$ 時，均會將自身狀態降級為 $\text{I}$。

選項分析

本題為簡答／問答題，針對 MESI 協定的四大狀態進行詳細特徵對比與狀態行為分析：

| 狀態名稱 | 是否存在於其他 Cache？ | 是否與主記憶體一致？ | 本機處理器讀取 ($\text{PrRd}$) | 本機處理器寫入 ($\text{PrWr}$) | 偵聽到外部讀取 ($\text{BusRd}$) | 偵聽到外部寫入/無效化 ($\text{BusRdX}/\text{BusUpgr}$) |

核心觀念

本題考查計算機結構（Computer Architecture）中關於指令級平行（ILP）、**GPU 資料/執行緒平行（SIMT）以及多核心系統（MIMD）**之核心架構與名詞定義。主要包含：

1. 動態排程與亂序執行（OoO Execution）：硬體如何透過動態排程突破指令間相依性（Data Hazards），以提升管道化效能並隱藏記憶體延遲。
2. GPU 執行模型（SIMT Architecture）：Flynn 分類法延伸之 GPU 平行架構，涵蓋 Warp/Wavefront 執行、執行緒隱藏延遲與分支分歧（Warp Divergence）。
3. 多核心與 Flynn 分類法（MIMD Multi-core）：硬體獨立核心間多指令多資料流平行運算，及其快取一致性（Cache Coherence）與記憶體共享體系。

解題方法

解答名詞解釋題時，應遵循標準三段式結構：

1. 精確定義（Definition）：說明該技術的全稱、背景及其在電腦體系結構中的定位。
2. 運作機制與關鍵組件（Mechanism & Key Components）：解釋硬體如何實作該功能（如流水線階段、控制單元、暫存器或快取）。
3. 優缺點與應用場景（Pros, Cons & Applications）：點出其帶來的效益（如 ILP、TLP、High Throughput）與面臨的挑戰（如硬體複雜度、Warp Divergence、Cache Coherence）。

子題詳解與分析

(a) Out-of-Order (OoO) execution（亂序執行 / 非順序執行）

• 精確定義：
  亂序執行（Out-of-Order Execution, OoO）是一種 CPU 微架構動態排程（Dynamic Scheduling）技術。CPU 不嚴格依照程式碼的原生順序（Program Order）執行指令，而是在資料倚賴（Data Dependency）滿足且執行單元（Functional Units）空閒時，優先執行後續已準備就緒的指令。
• 運作機制與五大階段：
  1. 順序取指與解碼（In-Order Fetch & Decode）：按程式原生順序取指並完成指令解碼。
  2. 順序派發與暫存器重命名（In-Order Issue/Dispatch & Register Renaming）：將指令發射至保留站（Reservation Station, RS）或發射佇列。利用**暫存器重命名（Register Renaming）技術將架構暫存器映射至實體暫存器，用以消除反向相依（WAR）與輸出相依（WAW）**這兩種虛擬資料倚賴。
  3. 亂序執行（Out-of-Order Execution）：只要指令所需運算子（Operands）就緒且算術邏輯單元（ALU）空閒，指令即可執行，不必等待前方被阻塞（Stalled）的指令。
  4. 亂序寫回（Out-of-Order Writeback）：執行完畢後，將結果廣播至通用資料匯流排（Common Data Bus, CDB）並寫回保留站與重排序緩衝器（Reorder Buffer, ROB）。
  5. 順序提交（In-Order Commit/Retire）：利用 ROB 確保指令依照原始 Program Order 更新架構暫存器與記憶體，以維護精確中斷（Precise Interrupts）。
• 效益與挑戰：
  • 效益：極大化指令級平行度（Instruction-Level Parallelism, ILP），大幅降低因高延遲指令（如 Cache Miss 導致的 Memory Load）引發的管道停頓。
  • 挑戰：硬體控制邏輯（保留站、ROB、CDB 廣播）極度複雜，晶片面積與功耗高昂。

(b) SIMT GPU（Single Instruction, Multiple Threads GPU）

• 精確定義：
  SIMT（單指令多執行緒）是 NVIDIA 針對現代 GPU 所提出的一種微架構與執行模型。硬體將大量獨立的純量執行緒（Scalar Threads）組織成固定大小的群組（在 NVIDIA 中稱為 Warp，通常包含 32 個 Threads），並由單一指令發射單元同時發射相同的一條指令給該 Warp 內的所有執行緒執行。
• 運作機制與特徵：
  1. 純量程式設計與向量硬體：開發者撰寫單一純量執行緒程式碼，硬體自動將 32 個執行緒打包成 Warp，並分派至 SIMD 管道硬體上平行執行。每個執行緒擁有獨立的暫存器與記憶體位址空間。
  2. 執行緒分歧（Warp Divergence）：當 Warp 內的執行緒遇到條件分支（如 if-else），若不同執行緒走向不同路徑，GPU 會將執行序列化（Serialization）——先執行走向 if 的執行緒（其餘執行緒關閉屏蔽 Mask off），再執行走向 else 的執行緒，最後重新匯合（Re-converge）。