109 年 國立臺灣大學電機工程研究所丙組《計算機結構與作業系統(A)》

核心觀念

本題考查作業系統中用於死鎖避免（Deadlock Avoidance）的銀行家演算法（Banker's Algorithm）與安全性演算法（Safety Algorithm）。

銀行家演算法的核心資料結構與定義如下：

1. 已分配矩陣 $\text{Allocation}$：每個進程目前已持有之各式資源數量。
2. 最大需求矩陣 $\text{Max}$：每個進程完成執行所需之最大各式資源總數。
3. 尚需需求矩陣 $\text{Need}$：每個進程未來仍需申請的資源數量，計算公式為：
   $\text{Need}[i, j] = \text{Max}[i, j] - \text{Allocation}[i, j]$
4. 可用資源向量 $\text{Available}$：系統目前剩餘可自由分配的各式資源數量。

資源請求處理邏輯（當進程 $P_i$ 提出請求 $\text{Request}_i$ 時）：

1. 合法性檢查：若 $\text{Request}_i \le \text{Need}_i$ 成立，進入步驟 2；否則拋出錯誤（請求超過宣告的最大需求）。
2. 可用性檢查：若 $\text{Request}_i \le \text{Available}$ 成立，進入步驟 3；否則進程 $P_i$ 必須等待（資源暫時不足）。
3. 試探性分配與安全性測試：假設核准請求並更新系統狀態：

執行安全性演算法。若能找到至少一條安全序列（Safe Sequence），代表系統處於安全狀態（Safe State），正式核准請求；反之則恢復原狀態，讓 $P_i$ 等待。

解題方法

首先根據公式 $\text{Need} = \text{Max} - \text{Allocation}$ 計算初始狀態下各進程的 $\text{Need}$ 矩陣：

• $\text{Need}_1 = (4, 0, 1) - (0, 0, 1) = (4, 0, 0)$
• $\text{Need}_2 = (1, 7, 5) - (1, 0, 0) = (0, 7, 5)$
• $\text{Need}_3 = (2, 4, 5) - (1, 3, 5) = (1, 1, 0)$
• $\text{Need}_4 = (1, 6, 5) - (0, 6, 3) = (1, 0, 2)$

整理系統初始狀態資料表：

選項分析

選項 (a) 分析

• 請求檢查：
  $P_1$ 提出請求 $\text{Request}_1 = (2, 0, 0)$。

  1. $\text{Request}_1 (2,0,0) \le \text{Need}_1 (4,0,0)$ （符合）
  2. $\text{Request}_1 (2,0,0) \le \text{Available} (3,5,2)$ （符合）

• 試探性更新狀態：

  • $\text{Available} = (3, 5, 2) - (2, 0, 0) = (1, 5, 2)$
  • $\text{Allocation}_1 = (0, 0, 1) + (2, 0, 0) = (2, 0, 1)$
  • $\text{Need}_1 = (4, 0, 0) - (2, 0, 0) = (2, 0, 0)$

• 安全性演算法推導：
  設工作向量 $\text{Work} = \text{Available} = (1, 5, 2)$，完成狀態向量 $\text{Finish} = [\text{False}, \text{False}, \text{False}, \text{False}]$。

  1. 檢查 $P_3$：$\text{Need}_3 = (1, 1, 0) \le \text{Work} (1, 5, 2)$，可順利執行。
     • $P_3$ 執行完成後釋放資源：$\text{Work} \leftarrow (1, 5, 2) + (1, 3, 5) = (2, 8, 7)$
     • 設 $\text{Finish}[3] = \text{True}$。
  2. 檢查 $P_1$：$\text{Need}_1 = (2, 0, 0) \le \text{Work} (2, 8, 7)$，可順利執行。

核心觀念

本題考查作業系統中 死結避免（Deadlock Avoidance） 的核心演算法——銀行家演算法（Banker's Algorithm）。具體包含 資源請求演算法（Resource-Request Algorithm） 的合法性檢查與 安全性演算法（Safety Algorithm） 的系統安全狀態判定。

1. 資源請求演算法（Resource-Request Algorithm）

當程序 $P_i$ 發出資源請求向量 $\text{Request}_i$ 時，系統依據以下四大步驟處理：

1. 最大需求合法性檢查（Max Claim Check）：
   $\text{Request}_i \le \text{Need}_i$
   若不滿足（即有任何一類資源請求量大於剩餘需求量），則系統直接拋出錯誤條件（Error Condition），拒絕該請求。因為程序試圖請求超過其宣告的最大需求量。
2. 可用資源限制檢查（Availability Check）：
   $\text{Request}_i \le \text{Available}$
   若不滿足，表示目前空閒資源不足，$P_i$ 必須進入等待狀態（Wait）。
3. 試探性資源分配（Tentative Allocation）：
   若前兩步均通過，系統假想將資源分配給 $P_i$，並更新系統狀態矩陣：
   $\text{Available} = \text{Available} - \text{Request}_i$
   $\text{Allocation}_i = \text{Allocation}_i + \text{Request}_i$
   $\text{Need}_i = \text{Need}_i - \text{Request}_i$
4. 安全性測試（Safety Test）：
   執行安全性演算法判斷更新後的狀態是否安全：
   • 若為安全狀態（Safe State）：正式核准請求（Grant Request）。
   • 若為不安全狀態（Unsafe State）：撤銷假想分配（Rollback），$P_i$ 恢復等待。

2. 安全性演算法（Safety Algorithm）

設系統有 $n$ 個程序與 $m$ 種資源：

1. 初始化向量：
   $\text{Work} = \text{Available}$
   $\text{Finish}[i] = \text{false}, \quad \forall i = 0, 1, \dots, n-1$
2. 尋找同時滿足下列兩條件的程序 $P_i$：
   $\text{Finish}[i] == \text{false} \quad \text{且} \quad \text{Need}_i \le \text{Work}$
   若找不到，跳至步驟 4。
3. 假設 $P_i$ 獲得資源順利執行完畢並釋放資源：
   $\text{Work} = \text{Work} + \text{Allocation}_i$
   $\text{Finish}[i] = \text{true}$
   返回步驟 2 繼續尋找下一個程序。
4. 若對所有 $i$，$\text{Finish}[i] == \text{true}$，則系統處於安全狀態（存在安全序列）；否則處於不安全狀態。

解題方法

依據前題（第 1 題）給定的系統快照（5 個程序 $P_0 \sim P_4$，3 種資源 $A, B, C$）：

• 目前可用資源向量：
  $\text{Available} = (3, 3, 2)$

• 系統狀態矩陣與計算所得之需求矩陣 $\text{Need} = \text{Max} - \text{Allocation}$：

解題切入點：對於各選項提出的資源請求 $\text{Request}_i$，優先檢查是否符合第一階段的合法性約束條件 $\text{Request}_i \le \text{Need}_i$ 與 $\text{Request}_i \le \text{Available}$。若合法，再假想分配並執行安全性演算法判定。

選項分析

選項 (a) 錯誤

• 請求內容：$P_2$ 提出 $\text{Request}_2 = (0, 4, 1)$。
• 合法性檢查：
  1. 對比 $P_2$ 的需求向量 $\text{Need}_2 = (6, 0, 0)$：
     $\text{Request}_2[B] = 4 > \text{Need}_2[B] = 0$
     $\text{Request}_2[C] = 1 > \text{Need}_2[C] = 0$
     $\text{Request}_2 \nleq \text{Need}_2$，違反資源請求演算法第一條規定。$P_2$ 請求的資源 $B$ 與 $C$ 均超過其宣告的最大需求量，系統直接引發錯誤（Error Condition）並拒絕請求。
  2. 對比可用資源 $\text{Available} = (3, 3, 2)$：
     $\text{Request}_2[B] = 4 > \text{Available}[B] = 3$

核心觀念

本題考查作業系統中處理多行程同步（Synchronization）與互斥（Mutual Exclusion）的經典軟體解法——蘭波特麵包店演算法（Lamport's Bakery Algorithm）。

麵包店演算法適用於 $n$ 個行程（Processes）的臨界區段（Critical Section, CS）問題，其設計思想模擬顧客在麵包店抽號碼牌排隊取餐：

1. 抽號碼牌階段：行程欲進入臨界區段時，會先標記 choosing[i] = true，並取得一個比當前所有行程已拿到的號碼牌更大的號碼 number[i]，隨後設 choosing[i] = false。
2. 比較與等待階段：行程 $i$ 依序檢查其他行程 $j$（$j = 0, 1, \dots, n-1$）：
   • 若行程 $j$ 正在抽號碼牌（choosing[j] == true），行程 $i$ 必須忙碌等待（Busy Waiting）。
   • 若行程 $j$ 已拿到號碼牌（number[j] != 0）且優先權高於行程 $i$，行程 $i$ 亦需等待行程 $j$ 離開臨界區段。
3. 優先權定義（字典序比較）：透過序對 $(number, ID)$ 進行字典序（Lexicographical Order）比較：
   $(a, b) < (c, d) \iff (a < c) \lor (a = c \land b < d)$
   號碼牌較小者優先權較高；若號碼相同，則行程識別碼（ID）較小者優先進入臨界區段。
4. 離開階段：行程離開臨界區段後，執行 number[i] = 0，表示歸還號碼牌並釋放資源。

解題方法

比對 Lamport's Bakery Algorithm 的標準程式碼結構：

do {
    choosing[i] = true;
    number[i] = 1 + max(number[0], ..., number[n-1]); // 必須包含 1 + 以確保號碼嚴格遞增
    choosing[i] = false;
    for (j = 0; j < n; j++) {
        while (choosing[j]); // 等待行程 j 完成取號
        while (number[j] != 0 && (number[j], j) < (number[i], i)); // 必須使用嚴格小於 <
    }
    // critical section
    number[i] = 0; // 離開 CS，將號碼歸零
    // remainder section
} while (1);

時間與空間複雜度分析：

• 時間複雜度：進入臨界區段前需輪詢 $n$ 個行程，單次進出 CS 之時間複雜度為 $O(n)$。
• 空間複雜度：需要長度為 $n$ 的布林陣列 choosing 與整數陣列 number，空間複雜度為 $O(n)$。

核心觀念

本題考驗作業系統中處理臨界區段（Critical Section）問題的經典純軟體演算法——**藍伯特麵包店演算法（Lamport's Bakery Algorithm）**的特性與適用條件。關鍵觀念包括：

1. 純軟體互斥機制（Software-based Mutual Exclusion）：Bakery 演算法是專為 $n$ 個行程設計的純軟體同步演算法，完全不需要作業系統（OS）支援或硬體提供的特殊原子指令（Atomic Instructions，如 Test-and-Set、Compare-and-Swap 或原子 max 運算），僅需一般的記憶體讀取（Read）與寫入（Write）即可確保互斥性（Mutual Exclusion）、前進性（Progress）與有限等待（Bounded Waiting）。
2. 分散式環境之限制（Distributed System Limitations）：Bakery 演算法原先設計於共享記憶體架構（Shared Memory Architecture）。若直接部署於跨網際網路的分散式環境，會面臨缺乏共享記憶體、網路延遲不確定（Unbounded Delay）、封包遺失及行程崩潰（Process Crash / Fail-stop）無法容錯等致命問題。
3. 進入區段之複雜度分析（Entry Section Complexity）：精確計算行程在進入臨界區段前對其他同儕行程（Peer Processes）狀態變數的查詢次數，並檢視其大 $O$ 符號（Big-$O$ Notation）表示法是否符合演算法數學規範。

解題方法

針對題目中三個關於 Bakery 演算法的敘述進行推導與驗證：

1. 評估硬體/OS依賴性：分析第 (3) 行取最大值 max 運算的實作方式，確認是否需要硬體或 OS 的原子性支援。
2. 評估分散式系統適用性：分析網際網路分散式環境之特性（訊息傳遞、無共享記憶體、網路中斷與節點崩潰）對 Bakery 演算法正確性的影響。
3. 計算查詢複雜度與 Big-$O$ 寫法：計算進入區段（Entry Section）中對其餘同儕行程變數進行查詢（Read Queries）的實際次數，並檢視其大 $O$ 符號表示法。

選項分析

• (a) 錯誤
  Bakery 演算法最重要的理論貢獻，即為完全不需要硬體或 OS 的特殊支援。第 (3) 行的取最大值運算 number[i] = 1 + max(number[0], ..., number[n-1]); 是由行程 $i$ 在使用者空間透過軟體迴圈讀取共享陣列 number 並自行計算出最大值。即使多個行程因平行執行或競態條件（Race Condition）而計算出相同的號碼（Ticket Number），Bakery 演算法後續會利用打破平手的規則：當 number[i] == number[j] 時，比較行程 ID，即以序對 $(number[i], i) < (number[j], j)$ 來決定優先權。因此，該運算完全不依賴硬體或 OS 提供原子的 max 運算支援。

• (b) 正確
  Bakery 演算法是建立在**共享記憶體（Shared Memory）**的模型上，行程間透過直接讀寫共享陣列 choosing

核心觀念

本題考查獨立磁碟備援陣列（Redundant Array of Independent Disks, RAID）各層級的核心架構與運作機制，重點在於 條帶化粒度（Striping Granularity）、資料備援機制（Redundancy Mechanism） 以及 RAID 1 與 RAID 2 的標準定義。

各主要 RAID 層級特性對照如下：

• RAID 1（Mirroring）：鏡像模式。將相同資料同步寫入至兩張或以上的硬碟，提供完全備份。
• RAID 2（Memory-style ECC）：位元級條帶化（Bit-level Striping），採用**漢明碼（Hamming Code）**做錯誤偵測與更正（ECC）。
• RAID 3（Bit/Byte-level Parity）：位元/位元組級條帶化，採用單一專用奇偶校驗碟（Parity Disk）。
• RAID 4（Block-level Parity）：區塊級條帶化（Block-level Striping），採用單一專用奇偶校驗碟。
• RAID 5（Block-level Distributed Parity）：區塊級條帶化，採用分散式奇偶校驗碼（Distributed Parity）。

解題方法

解題切入點為將題目敘述逐一對照作業系統與計算機結構標準教材（如 Silberschatz 之 Operating System Concepts 或 Patterson & Hennessy 之 Computer Organization and Design）中 RAID Level 1 與 RAID Level 2 的規範定義：

1. 檢驗 RAID 1 的資料儲存方式是否為完全複製（Mirroring / Exact Copies）。

核心觀念

本題考驗獨立磁碟冗餘陣列（RAID, Redundant Array of Independent Disks） 各層級（RAID Levels）的結構定義，核心差異在於：

1. 資料分割粒度（Striping Granularity / Unit）：位元級（Bit-level）、位元組級（Byte-level）或區塊級（Block-level）。
2. 奇偶檢查碼（Parity）配置方式：集中存放在專用磁碟（Dedicated parity disk）或交錯分散於所有磁碟（Distributed parity）。

常見 RAID 層級架構歸納如下：

• RAID 0：區塊級條帶化，無冗餘（Block-level striping without parity）。
• RAID 1：鏡像（Mirroring）。
• RAID 2：位元級條帶化，採用海明碼（Bit-level striping with ECC / Hamming code）。
• RAID 3：位元組級／位元級條帶化，採用專用奇偶檢查碟（Byte-level striping with dedicated parity disk）。
• RAID 4：區塊級條帶化，採用專用奇偶檢查碟（Block-level striping with dedicated parity disk）。
• RAID 5：區塊級條帶化，採用分散式奇偶檢查（Block-level striping with distributed parity）。
• RAID 6：區塊級條帶化，採用雙重分散式奇偶檢查（Block-level striping with dual distributed parity, $P+Q$）。

解題方法

比對各選項給予的 RAID 層級，分別審視其「條帶化單位（Bit/Byte/Block-level）」與「Parity 存放機制（Dedicated/Distributed）」是否符合標準定義：

1. 確認資料切割的最小單位是 Bit、Byte 還是 Block。
2. 確認 Parity 寫入的是單一固定磁碟（Dedicated）還是分散交錯寫入所有磁碟（Distributed）。

選項分析

• (a) RAID 3 uses byte-level striping with a dedicated parity disk.（正確）

LRU – 4 frames
逐步追蹤最近最少使用頁面，結果缺頁次數為 12。
→ (a) 錯誤（非 10）。

Optimal – 6 frames
使用未來參考資訊，在第 9 參考 8 時置換頁 5，於第 13 參考 7 時置換頁 1（或 8），其餘皆命中。

參考文字串（題目 7）
$\langle 7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1\rangle$

(a) 4 frames – Reference‑bit (Clock) 演算法

1. 初始四格皆空，第一次將 $7,0,1,2$ 放入，產生 4 次缺頁。
2. 從 $2$（最後載入頁）之後的格子開始掃描。
3. 依序檢查參考位元，若為 0 則置換；若為 1 則清除再繼續掃描。
4. 按照上述規則完成整個參考序列後，缺頁次數累計 15。

結論：正確。

核心觀念

本題考驗 UNIX / Linux 作業系統中的系統啟動流程（Booting Process）、行程管理（Process Management）與服務管理架構（Init Systems & Daemons）：

1. 系統啟動與第一支行程（Booting & First Process）：Linux/UNIX 系統在核心（Kernel）載入完成後，建立的第一個使用者空間（User Space）行程為 init（$\text{PID} = 1$）或現代的 systemd；而 root 是超級使用者帳號（User Account, UID 0），並非行程名稱。
2. 背景守護行程（Daemon Process）：守護行程（Daemon）是指在背景（Background）持續執行且無需使用者直接與其互動的程式，通常用於處理系統服務或監聽特定事件。
3. System V Init 與運行層級（Runlevels）：傳統 SysV-style 的 init 行程採用運行層級（Runlevel 0 ~ 6）管理系統的運作狀態，且支援在不同 Runlevel 之間動態切換。

解題方法

針對題目問及 UNIX/Linux 系統之敘述，採用「概念定義對照」與「作業系統運作機制分析」進行判斷：

1. 區分「行程（Process）」與「使用者帳號（User Account）」的概念差異。
2. 檢視 Daemon 行程的定義及其在背景執行的特性。
3. 檢視 System V init 控制系統切換 Runlevel 的設計原理與機制。

選項分析

• (a) 錯誤。
  root 是 UNIX/Linux 系統中的超級使用者帳號（Superuser Account，$\text{UID} = 0$），屬於系統的權限與身份識別概念，並非「行程（Process）」。系統開機載入核心（Kernel）後，所建立的第一個使用者空間行程為 init 行程（或現代系統中的 systemd），其行程識別碼為 $\text{PID} = 1$。雖然 init 行程是以 root 權限執行，但行程本身的名稱並非 Root。

核心觀念

本題考查 UNIX / Linux 作業系統中的**進程生命週期管理（Process Life Cycle Management）**與 **System V (SysV) 初始化系統（Initialization System）**的核心運作機制，具體包含：

1. **孤兒進程（Orphan Process）**與 init 進程（PID 1）的收養機制（Adoption Mechanism）。
2. **System V Init 執行等級（Runlevel）**的規範與各 Mode 對應功能。
3. /etc/inittab 設定檔在系統啟動與 Runlevel 切換時的角色權責。

解題方法

分析 UNIX/Linux 系統管理與進程控制的核心規範：

1. 檢驗進程終止後父子關係的改變：當父進程先於子進程結束時，作業系統核心會如何處理孤兒進程。
2. 檢驗 System V Init 標準規範中各個 Runlevel ($0 \sim 6$) 的傳統定義。
3. 檢驗 /etc/inittab 在 SysV Init 架構下控制系統預設 Runlevel 及對應服務腳本呼叫的核心作用。

選項分析

• (a) 正確
  在 UNIX/Linux 作業系統中，當父進程（Parent Process）在子進程（Child Process）結束前便先行終止，該子進程即成為「孤兒進程（Orphan Process）」。作業系統核心（Kernel）會自動將所有孤兒進程的父進程重定向改為 init 進程（PID 為 1）。init 進程會定期呼叫 wait() 或 waitpid() 系統呼叫，收集並回收這些孤兒進程終止後的離開狀態與 PCB 資源，避免孤兒進程累積成為永久僵死進程（Zombie Process）。

• (b) 正確
  在經典的 System V (SysV) init 系統規範中，執行等級（Runlevel）用來定義系統的運行狀態與載入服務：

  • Runlevel 0： Halt（停機／關機）
  • Runlevel 1 / S / s： Single-user mode（單一使用者模式，僅供系統修復與維護，不啟動網路服務與多使用者登入）

參考書等級：研究所

關鍵步驟

1. 冷卻能力＝散熱功率上限 $16\text{ kW}=16000\text{ W}$。
2. 伺服器熱量＝所有元件峰值功耗之和（假設硬碟在讀寫狀態）。

(a) 單一 D2 硬碟配置

• P2 處理器峰值功耗：$60\text{ W}$
• M2 記憶體功耗：$1.8\text{ W}$
• D2 硬碟讀寫功耗：$9.5\text{ W}$

單台伺服器總熱量
$P_{a}=60+1.8+9.5=71.3\text{ W}$

可容納伺服器數目

關鍵數據

• 最大散熱功率：$300\ \text{W/ft}^2$
• 機架佔地：$11\ \text{ft}^2$
• 每機架允許的最高散熱功率
  $P_{\max}=300\ \frac{\text{W}}{\text{ft}^2}\times 11\ \text{ft}^2 = 3300\ \text{W}=3.3\ \text{kW}$

判斷每敘述

核心觀念

本題考驗快取記憶體（Cache）架構優化策略及其硬體權衡關係（Trade-offs）。
在計算機結構中，衡量快取效能的核心指標為平均記憶體存取時間（Average Memory Access Time, AMAT）：
$\text{AMAT} = \text{Hit Time} + \text{Miss Rate} \times \text{Miss Penalty}$

快取的失誤（Miss）可依據 3C 模型進行分類：

1. 強制失誤（Compulsory Misses）：資料第一次被 CPU 存取時必然產生的失誤（又稱冷啟動失誤 Cold-Start Misses）。
2. 容量失誤（Capacity Misses）：快取總容量不足以容納程式執行期間所需的所有資料區塊而發生的失误。
3. 衝突失誤（Conflict Misses）：在直接對映（Direct-Mapped）或組相聯（Set-Associative）快取中，多個記憶體區塊競爭對映至同一個 Set 所發生的失誤。

適當調整快取的三大硬體參數（Block Size、Cache Capacity、Associativity）可以降低特定類型的 Miss Rate，但同時也會帶來相應的效能或硬體代價。

解題方法

本題採用「快取優化策略權衡分析（Trade-off Analysis）」進行判讀。逐一對比題目所述的三種優化手段（加大區塊、加大容量、提高相聯度）對失誤率（Miss Rate）、失誤懲罰（Miss Penalty）、命中時間（Hit Time）與硬體成本/功耗（Cost & Power）的影響是否符合經典計算機架構理論。

選項分析

• (a) 正確
  • 降低 Compulsory Misses：較大的 Block Size 能夠更好地利用「空間局部性（Spatial Locality）」。當發生快取失誤時，一次將較大的連續記憶體資料塊載入快取，後續存取鄰近位址資料時便能直接命中，從而降低 compulsory misses。
  • 增加 Miss Penalty：由於每個區塊包含更多 Byte，當失誤發生並需要從下一層記憶體（如主記憶體）抓取資料時，資料傳輸時間（Data Transfer Time）會變長，使得 miss penalty 增加。
  • 可能增加 Capacity 或 Conflict Misses：在快取總容量（Total Cache Capacity）固定的狀況下，加大 Block Size 意味著快取內能容納的區塊總數量（Total Number of Blocks）會減少。

核心觀念

本題旨在考驗快取記憶體優化技術（Cache Optimization Techniques）的核心原理，包含以下三大重點：

1. 多層級快取（Multilevel Caches）：如何權衡命中時間（Hit Time）與失誤懲罰（Miss Penalty）。
2. 讀取與寫入失誤之優先權調度（Read Misses over Writes）：如何利用寫入緩衝區（Write Buffer）降低處理器停頓（Stall）。
3. 虛擬索引物理標籤快取（Virtually Indexed, Physically Tagged, VIPT）：利用頁面偏移量（Page Offset）平行存取快取與 TLB，以縮短關鍵路徑（Critical Path）。

解題方法

針對各個選項所涉及的計算機結構核心優化理論分析如下：

1. 多層級快取的設計哲學：
   平均記憶體存取時間（AMAT）公式為：
   $\text{AMAT} = \text{Hit Time}_{L1} + \text{Miss Rate}_{L1} \times \text{Miss Penalty}_{L1}$
   其中第一層快取失誤懲罰等於第二層快取的存取時間：
   $\text{Miss Penalty}_{L1} = \text{Hit Time}_{L2} + \text{Miss Rate}_{L2} \times \text{Miss Penalty}_{L2}$
   為配合高頻率 CPU 的時脈週期（Clock Cycle），L1 快取必須極小且極快；而 L2/L3 快取則設計得足夠大，以攔截未命中 L1 而原本需存取主記憶體（Main Memory）的大量請求。

2. Read/Write Miss 優先權原則：
   當管線發生 Read Miss 時，CPU 必須等待資料傳回才能繼續執行（屬阻塞式存取 Blocked Access）；而 Write Miss 則可將資料寫入寫入緩衝區（Write Buffer）後繼續執行。若處理器讓 Read Miss 優先處理，可減少 CPU 停頓時間，從而有效降低失誤懲罰。

3. VIPT 平行定址機制：
   在分頁虛擬記憶體中，虛擬位址（Virtual Address, VA）轉譯為物理位址（Physical Address, PA）時，僅頁碼部分進行轉譯，頁面偏移量（Page Offset）完全相同。

核心觀念

暫存器重新命名可以消除假相依，包括寫後讀（WAR）與寫後寫（WAW）；真正的讀後寫（RAW）資料相依仍須保留。排程時也要同時考慮指令的資料就緒時間與功能單元是否可用。

依題目提示，延遲標示為 $+k$ 的指令，總延遲為 $1+k$ 個週期；例如 LW +4 需 5 個週期，依賴它的指令最早可在第 5 個週期後發射。

解題方法

圖中可讀到：解碼器將指令送入保留站（RS），RS 連接兩個 ALU 及一個 LD/ST，LD/ST 再連接記憶體；題幹限制每個週期最多向各 ALU 發一個運算，並向 LD/ST 發一個記憶體運算。原題沒有說明 LD/ST 能否在前一操作完成前接收下一筆；以下依單一、非流水化 LD/ST 計算，也就是前一操作完成後才接受下一筆。

將第 [1] 至 [3] 指令的 R1 改名為新的暫存器 R5：

[1] LW   R5, 0(R3)
[2] ADDI R5, R5, #1
[3] SW   R5, 0(R3)
[4] LW   R1, 0(R0)
[5] SUB  R4, R1, R2
[6] BNZ  R4, Loop

第 [1]、[2]、[3] 之間的真實資料相依仍存在：第 [1] 的載入結果供第 [2] 使用，第 [2] 的結果供第 [3] 寫入記憶體。重新命名則消除了它們與第 [4] 寫入 R1 之間的暫存器名稱相依，讓第 [4] 可以提早發射。

選項分析

(a) 正確。 未重新命名時，第 [4] 的 LW 寫入 R1，須避免覆寫第 [3] 尚未讀取的值，因而受 WAR 相依限制。重新命名後，第 [4] 的 R1 與前面指令使用的 R5 無關，可以提早發射。

以本題採用的非流水化 LD/ST 假設比較：未重新命名時，第 [1] 在 $N$ 發射，第 [2] 在 $N+5$ 發射，第 [3] 最早在 $N+6$ 發射；LD/ST 到 $N+8$ 才能接收第 [4]。第 [4] 的結果在 $N+13$ 可用，第 [5] 在 $N+13$ 發射，第 [6] 在 $N+14$ 發射並於 $N+17$ 完成。

解題重點

1. 第一輪迭代的週期數
   • 週期 0：前端送出 2 條已重新命名的指令至 RS。
   • 每條指令在 RS 中等待 1 個 dispatcher 週期才能送到功能單元。
   • 功能單元延遲 (以題目常用設定) ：
     • Load/Store (LD/ST) 延遲 2 週期
     • ALU (ADD、SUB 等) 延遲 1 週期
   • 依序發射與執行的最長路徑為
     $1\;(\text{dispatch}) + 2\;(\text{LD}) + 1\;(\text{ALU}) + 2\;(\text{ST}) + 1\;(\text{dispatch}) + 1\;(\text{ALU}) = 9$ 週期。
   • 因此 (a) 為真。

解析

• 每次迴圈 $k$ 產生兩筆除法運算（$4/(4k+1)$、$-4/(4k+3)$），共 2 FLOP。

• 只寫入結果至陣列 $r$，無讀取。若假設每筆資料為 8 Byte（double），則每次迴圈寫入 $2 \times 8 = 16$ Byte。

  $\text{Arithmetic intensity} = \frac{\text{FLOP}}{\text{byte}} = \frac{2}{16}=0.125$

核心觀念

本題考查計算機效能評估中的**每指令週期數（Cycles Per Instruction, CPI）與總執行週期數（CPU Execution Cycles）**之計算。

相關基本定義與計算公式如下：

1. 總指令數（Instruction Count, $IC$）：
   程式所執行的總指令數量。若程式包含多種指令類別，則總指令數為各類別指令數之和：
   $IC = \sum_{i} IC_i$

2. 總執行週期數（CPU Cycles）：
   執行一段程式所需消耗的總時脈週期數。當程式包含不同 CPI 的指令類別時，總時脈週期數為各類別指令數與其對應 CPI 乘積之累加：
   $\text{CPU Cycles} = \sum_{i} (IC_i \times CPI_i)$

3. 平均每指令週期數（Average CPI）：
   整段程式平均每執行一道指令所消耗的週期數，計算公式為總執行週期數除以總指令數：
   $\text{Average CPI} = \frac{\text{CPU Cycles}}{IC} = \frac{\sum_{i} (IC_i \times CPI_i)}{\sum_{i} IC_i}$

解題方法

題目給定三種指令類別及其對應的 CPI 分別為：

• A 類指令：$CPI_A = 2$
• B 類指令：$CPI_B = 3$
• C 類指令：$CPI_C = 6$

解題切入點為將各選項給定的指令數量帶入公式，計算出對應的總執行週期數與平均 CPI，藉此逐一比對選項敘述之正確性。

選項分析

• (a) 正確
  • 已知條件：A 類指令數 $IC_A = 10$，B 類指令數 $IC_B = 8$，C 類指令數 $IC_C = 5$。
  • 推導過程：
    帶入總執行週期數公式：
    $\text{CPU Cycles} = IC_A \times CPI_A + IC_B \times CPI_B + IC_C \times CPI_C$

核心觀念

本題考驗多核心／多處理器系統中的**快取一致性協定（Cache Coherence Protocols）機制比較，主要聚焦於窺探協定（Snooping Protocol）與目錄式協定（Directory-based Protocol）**在架構運送原理、擴展性（Scalability）、硬體複雜度與適用系統規模上的根本差異。

1. 快取一致性（Cache Coherence）：確保多處理器環境中，各處理器的區域快取（Local Cache）在讀寫同一記憶體區塊（Cache Block）時，能取得最新的正確資料。
2. 窺探協定（Snooping Protocol）：
   • 依賴共享廣播介質（Shared Bus / Broadcast Network）。
   • 每台處理器的快取控制器（Cache Controller）持續「窺探（Snoop）」匯流排上的廣播要求。
   • 系統不記錄哪些 Cache 持有該資料區塊；寫入或失效要求一律透過廣播通知所有快取。
3. 目錄式協定（Directory-based Protocol）：
   • 透過**目錄（Directory）**記錄每個記憶體區塊目前的共享狀態（State）以及哪些 Cache 持有副本（Sharer Bit Vector）。
   • 寫入或無效化時，目錄僅需發送**點對點訊息（Point-to-point / Unicast）**給實際持有副本的 Cache，無需廣播全網。

解題方法

本題分析切入點為兩種協定的「資料記錄機制」、「訊息傳播方式」與「規模擴展代價」：

1. 訊息與儲存機制：Snooping 採用「廣播且無共享者記錄」；Directory 採用「點對點且由目錄集中/分散記錄共享者位元向量（Sharers Vector）」。
2. 可擴展性（Scalability）：當處理器數量 $N$ 增加時，Snooping 的匯流排廣播頻寬會迅速成為效能瓶頸，總訊息量極大；Directory 僅發送點對點訊息給實際 Sharers，極具大系統擴展優勢。
3. 系統規模與複雜度權衡：小型系統中 Snooping 架構簡單低延遲；Directory 則需額外目錄儲存空間（Directory Storage）、目錄查詢延遲（Directory Lookup Latency）與複雜的異步協議狀態機，小系統上顯得過於複雜且無效率。

選項分析

步驟與公式

• 時脈頻率 $f = 6.3\ \text{GHz}$ → 時脈週期 $T = \frac{1}{f}=0.15873\ \text{ns}$。
• 遠端參考比例 $p =0.2\% =0.002$。
• 遠端參考耗時 $t_{\text{remote}} = (100+10h)\ \text{ns}$，其中 $h$ 為 往返 跳數。
• 往返跳數換算成時脈週期：$\displaystyle C_{\text{remote}}=\frac{t_{\text{remote}}}{T}$。
• 平均 CPI：$\displaystyle \text{CPI}=0.75 + p\;C_{\text{remote}}$。

(a) 4×4 處理器格網

格網的曼哈頓距離最大為 $3+3=6$ 跳；往返 $h_{\max}=2\times6=12$。
$t_{\max}=100+10\times12=220\ \text{ns}$
不等於 150 ns → 敘述錯誤。