115 年 國立臺灣大學資訊網路與媒體研究所《計算機結構與作業系統》

核心觀念

本題考查特定應用場景下的作業系統與系統架構設計目標 (Application-Specific Operating System & System Design Goals)。現代作業系統設計需根據硬體特性與應用情境（如行動裝置、AI 伺服器、安全攸關系統）進行權衡 (Trade-offs)，核心觀念包含：

1. 行動裝置 (Smartphones)：受限於電池容量與散熱空間，系統設計的核心在於能源效率 (Energy Efficiency)、動態電源管理 (Dynamic Power Management, DPM) 與熱限制 (Thermal Throttling)。
2. 人工智慧伺服器 (AI Servers)：主要處理大規模矩陣運算與深度學習模型，系統設計強調高記憶體頻寬 (High Memory Bandwidth) 與高效能異質算力管理 (GPU/NPU Resource Management & Scheduling)，以克服記憶體牆 (Memory Wall) 並提升整體吞吐量。
3. 安全攸關與即時系統 (Safety-Critical & Real-Time Systems)：應用於航空、醫療、車控等領域，系統的首要考量為安全性 (Safety) 與可預測性 (Predictability)。系統必須保證滿足最壞情況執行時間 (Worst-Case Execution Time, WCET)，因此偏好確定性排程 (Deterministic Scheduling)，而非追求平均效能。

---

解題方法

本題為概念分析型的多選題。切入點為比對各選項所述之系統設計目標與特定應用場景的需求是否符合：

• 針對智慧型手機，分析資源受限（電池）帶來的硬性約束。
• 針對 AI 伺服器，分析計算與資料傳輸負載特徵（GPU/TPU 協同運算與高頻寬記憶體需求）。
• 針對 Safety-Critical 系統，區分即時系統中的「最壞情況 (Worst-Case)」與一般系統的「平均情況 (Average-Case)」，以及「確定性 (Deterministic)」排程對系統安全性的決定性影響。

---

選項分析

核心觀念

本題考查作業系統中**行程（Process）與執行緒（Thread）的核心架構差異、記憶體空間劃分（Shared vs. Per-thread resources）、執行緒上下文切換（Context Switching）開銷比較，以及多執行緒模型中的同步執行緒（Synchronous Threading）與非同步執行緒（Asynchronous Threading）**定義。

1. 行程與執行緒的資源劃分：
   • 共享資源（Shared Resources）：程式碼區段（Code Section）、資料區段（Data Section）、堆積區段（Heap Section）、作業系統資源（如開啟檔案表 open files、訊號處理 signals）。
   • 獨享資源（Per-Thread Resources）：執行緒識別碼（Thread ID）、暫存器集合（Register Set，包含 Program Counter）、堆疊區段（Stack Section，用於儲存區域變數、函式呼叫框架與傳回位址）。
2. 上下文切換開銷（Context Switch Overhead）：
   • 行程切換（Process Context Switch）：需切換虛擬位址空間、頁表指標（Page Table Pointer / CR3 暫存器），並引發 TLB（Translation Lookaside Buffer）失效與快取未命中（Cache Miss），開銷較大。
   • 同行程內的執行緒切換（Thread Context Switch）：共享同一虛擬位址空間與頁表，僅需保存與還原 CPU 暫存器狀態與 Stack Pointer，開銷顯著較小。
3. 多執行緒模式定義：
   • Synchronous Threading（同步執行緒）：父執行緒建立子執行緒後，必須阻塞等待（Wait / Join）子執行緒執行終止，才會恢復（Resume）自身執行。
   • Asynchronous Threading（非同步執行緒）：父執行緒建立子執行緒後，立即恢復自身執行，父子執行緒平行獨立運作。

---

解題方法

本題採用作業系統標準理論（Silberschatz Operating System Concepts）作為切入點，針對記憶體配置、CPU 排程狀態及執行緒建立模式，逐一審視各選項敘述的正確性。

---

選項分析

• (A) 錯誤：
  同一行程內的所有執行緒共享 Code Section、Data Section 與 Heap Section，但**每一個執行緒皆擁有獨立的 Stack S

核心觀念

本題旨在考驗對作業系統「虛擬記憶體（Virtual Memory）」機制的綜合理解，涵蓋以下核心觀念與定義：

1. 純請求分頁 (Pure Demand Paging)：行程 (Process) 啟動時完全不載入任何分頁至實體記憶體 (Physical Memory)，僅在執行過程產生頁錯失 (Page Fault) 時才依需求載入。
2. 最佳分頁替換演算法 (Optimal Page Replacement Algorithm, OPT / MIN)：替換未來最長時間不會被存取的分頁，作為評估其他替換演算法效能的理論基準 (Benchmark)。
3. 堆疊屬性 (Stack Property) 與比拉迪異常 (Belady's Anomaly)：若一個分頁替換演算法在分配 $N$ 個框架 (Frame) 時所保留的分頁集合，恆為分配 $N+1$ 個框架時分頁集合的子集，即具備堆疊屬性。具備堆疊屬性的演算法數學上保證絕不發生 Belady's Anomaly（即增加實體框架數量反而導致分頁錯失次數增加的異常現象）。
4. 工作集模型 (Working-Set Model) 與傾擠 (Thrashing)：利用歷時視窗 $\Delta$ 內行程存取的分頁集合（即工作集 $WSS_i$）來預估行程實體框架的需求總量。當總需求 $D = \sum WSS_i$ 超過系統可用實體框架總數 $m$ 時，系統將陷入劇烈換頁（Thrashing）狀態。
5. 區域替換 vs. 全域替換 (Local vs. Global Page Replacement)：區域替換僅允許行程替換屬於自身的框架，能隔離行程間的干擾並提供高可預測性；全域替換則可動態調配全局框架，可提升系統整體資源利用率與吞吐量 (Throughput)。

---

解題方法

本題為複選題，須逐一檢視各選項敘述是否符合作業系統（如 Silberschatz 所著之 Operating System Concepts）標準理論定義與數學性質推導。

---

選項分析

• (A) 正確

  • 分析：在純請求分頁 (Pure Demand Paging) 策略下，作業系統採取「零預載 (No Pre-paging)」原則。當行程建立並準備執行時，其所有頁表項 (Page Table Entries) 的 Valid/Invalid Bit 皆設為 Invalid。當 CPU 擷取 (Fetch) 第一條指令時，因為該指令所在的分頁尚未存在於實體記憶體中，硬體（MMU）會立即觸發第一個頁錯失 (Page Fault)，由 Trap 處理常式將該頁從次級儲存裝置載入實體框架。

• (B) 正確

  • 分析：最佳分頁替換演算法 (OPT) 的規則是「發生 Page Fault 時，選擇未來最長一段時間內不會被存取的頁面予以換出」。然而，在一般的通用作業系統環境中，未來的分頁參考序列 (Page Reference String) 取決於動態的執行流程與使用者輸入，無法在事前完全預知。

核心觀念

本題考查作業系統安全（Operating System Security）的核心防禦機制與存取控制模型：

1. 雙模式運作（Dual-Mode Operation）與模式分離（User-Kernel Mode Separation）：利用硬體模式位元（Mode Bit）區分 User Mode 與 Kernel Mode，確保使用者程式無法直接執行特權指令（Privileged Instructions）或直接存取硬體。
2. 位址空間隔離（Address Space Isolation）：透過虛擬記憶體機制（MMU、頁表、界限暫存器），將不同行程（Process）的獨立記憶體空間相互隔絕，防止非法跨行程存取。
3. 存取控制模型（Access Control Models）：
   • 自主存取控制（Discretionary Access Control, DAC）：檔案擁有者（Owner）可自行決定與修改存取權限。
   • 強制存取控制（Mandatory Access Control, MAC）：由系統中央安全政策（System Policy / Administrator）統一管制，資源擁有者無權私自變更存取權限。
4. 沙盒機制（Sandboxing）：限制行程對系統資源（如檔案系統、網路、系統呼叫）存取權限的隔離環境，其套用時機與邊界並非限制於 main() 執行完畢後。
5. 靜態資料加密（Data at Rest Encryption）：保護儲存於實體介面（硬碟、SSD、資料庫等）之資料機密性與使用者隱私。

---

解題方法

本題為系統安全觀念的複選題。解題切入點在於區分各安全機制的「實作層級（硬體/作業系統/應用程式）」與「核心定義」：

1. 區分硬體與特權隔離：確認雙模式運作（User/Kernel mode）與 MMU 位址空間隔離的作用範圍。
2. 對比 DAC 與 MAC：注意「權限可否由使用者自由轉移與設定」是區分 DAC（自主存取控制）與 MAC（強制存取控制）的關鍵指標。
3. 檢視沙盒（Sandboxing）套用時機：沙盒約束通常在行程啟動時（由父行程設定）、載入期間或程式初期執行系統呼叫（如 seccomp）時設定，並非限定在 main() 函數「執行完畢之後」。
4. 評估資料安全保護效果：確認靜態資料加密（Data at Rest Encryption）是否能在實體裝置丟失或未授權存取時提供隱私保護。

---

選項分析

• (A) 正確。
  說明：作業系統利用硬體的模式位元（Mode Bit）實作使用者模式（User Mode）與核心模式（Kernel Mode）的分離。特權指令（如直接存取 I/O 埠、修改頁表、中斷控制等）僅能於 Kernel Mode 執行；User Mode 程式欲存取硬體資源時，必須透過系統呼叫（System Call）由 Kernel 代為執行，從而有效防止使用者程式直接破壞或存取硬體。

核心觀念

本題考查作業系統中 CPU 排程（CPU Scheduling）與即時排程（Real-Time Scheduling）演算法的**最佳性（Optimality）**定義：

1. 最小化平均等待時間（Minimizing Average Waiting Time）：

   • 行程同時到達（Same Arrival Time, $t=0$）：Shortest-Job-First (SJF) 為最佳（Optimal）排程法，此時搶佔（Preemptive）與非搶佔（Non-preemptive）產生的排程結果完全相同。
   • 行程不同時到達（Different Arrival Times）：僅有搶佔式的 Shortest-Remaining-Time-First (SRTF，即 Preemptive SJF) 能保證取得最小平均等待時間；非搶佔式 SJF 無法保證最佳。

2. 截止時間與可排程性（Schedulability with Deadlines）：

   • Earliest-Deadline-First (EDF)：在單處理器（Single Processor）環境下，若允許搶佔（Preemptive），EDF 為具備最佳可排程性（Optimal for Schedulability）的動態優先權排程演算法。即若存在某種排程法能使該組行程均不錯過 Deadline，則 EDF 亦必然能達成。
   • 若為**非搶佔（Non-preemptive）**環境，當行程到達時間不同時，EDF 並非最佳排程法。

---

解題方法

分析排程演算法的最佳性時，需針對「到達時間（Arrive Time）」與「是否允許搶佔（Preemption）」建立判斷矩陣：

1. 評估平均等待時間（Average Waiting Time）：

   • 同時到達：直接依 Burst Time 由小到大排序執行，SJF 即為最佳。
   • 不同時到達：新行程到達時若所需的 Burst Time 比當前行程短，非搶佔式 SJF 無法中斷當前行程，導致新行程必須等待，平均等待時間被拉長。因此必須採用 SRTF（允許搶佔）才能保證最佳。

2. 評估 Deadline 可排程性（Schedulability）：

   • 搶佔式 EDF：根據 Horn 定理（1974），在允許搶佔且行程隨時可中斷的單 CPU 環境中，EDF 具備最佳可排程性。
   • 非搶佔式 EDF：若當前正在執行一個 Deadline 很長但 Burst Time 很長的行程，此時到達一個 Deadline 極緊迫的行程，由於無法搶佔，後者將會錯過 Deadline。因此非搶佔式 EDF 無法保證最佳可排程性。

---

選項分析

• (A) 正確
  題目描述：If the processes arrive at the same time, the optimal nonpreemptive scheduling for minimizing average waiting time is the Shortest-Job-First (SJF) scheduling.
  說明：當所有行程皆在相同時間（$t=0$）到達時，將 CPU 優先分配給 Burst Time 最短的行程，能讓最多行程以最快速度完成並離開等待佇列，從而使總等待時間與平均等待時間達到極小值。此時非搶佔式 SJF 數學上已證明為最佳（Optimal）。

• (B) 錯誤
  題目描述：If the processes arrive at different times, the optimal nonpreemptive scheduling for minimizing average waiting time is the Shortest-Job-First (SJF) scheduling.
  說明：當行程到達時間不同時，非搶佔式 SJF 並非最佳。
  反例：行程 $P_1$ 於 $t=0$ 到達（CPU Burst = $10$）；行程 $P_2$ 於 $t=1$ 到達（CPU Burst = $1$）。
  在非搶佔式 SJF 下，$t=0$ 時只有 $P_1$，故 $P_1$ 執行至 $t=10$；$P_2$ 於 $t=10$ 才開始執行至 $t=11$。

  • $P_1$ 等待時間 $= 0$
  • $P_2$ 等待時間 $= 10 - 1 = 9$
  • 平均等待時間 $= \frac{0 + 9}{2} = 4.5$

解析

• 兩行程共用變數 turn，表示輪到哪一個程式進入臨界區。
• 原子的 load、store 保證對 turn 的讀寫不會被中斷。

Approach 1

1. $P_1$ 先執行 turn = j，隨即進入 while (turn == j) ;
   • 此時 turn 已等於 $j$，條件必為真，$P_1$ 進入無限忙等待。
2. $P_2$ 同理在執行 turn = i 後亦進入自己的忙等待。
3. 兩者皆已把 turn 設成對方的值，沒有任何程式再改變 turn，因此會死鎖。
   • 互斥：在任何時刻至多有一個程式進入臨界區（實際上永遠沒有程式進入），故 A 成立。
   • 有界等待：若另一程式持續佔用臨界區，自己會永遠等待，違反有界等待，B 不成立。

核心觀念

本題考查電腦結構（Computer Architecture）與指令集架構（ISA）設計的基本原則，重點在於**CPU 效能公式（CPU Performance Equation）**及軟硬體之間的權衡關係（Trade-off）。

1. CPU 效能公式：
   $\text{CPU Time} = \text{Instruction Count (IC)} \times \text{CPI} \times \text{Clock Cycle Time (CCT)}$

   • $\text{IC}$：執行應用程式所需的總指令數（受 ISA、編譯器影響）。
   • $\text{CPI}$（Clock cycles Per Instruction）：每指令平均時脈週期數（受微架構設計、 hazards 影響）。
   • $\text{CCT}$：時脈週期時間（與時脈頻率 $f$ 成反比 $f = 1/\text{CCT}$，受電路關鍵路徑 Critical Path 影響）。

2. ISA 設計權衡 (RISC vs. CISC)：

   • 指令集設計旨在尋求 IC、CPI 與 CCT 三者的最佳平衡。
   • 增加定址模式複雜度或提供強大功能的指令可降低 IC，但往往會增加電路解碼與執行的複雜度，導致 CCT 拉長或 CPI 增加。

3. 管線化（Pipelining）影響：

   • 切細管線階段（增加管線深度）可縮短單一階段的關鍵路徑，其主要效益為降低 CCT（提升時脈頻率）。

---

解題方法

針對題目關於 ISA、管線化及硬體實現的五個敘述，將每個選項所採取的設計變更，對應至效能三要素（$\text{IC}$、$\text{CPI}$、$\text{CCT}$）以及硬體複雜度的變化進行分析判斷：

1. Pipeline 深度與 CCT / CPI 的關係。
2. Byte 存取指令有無對編譯後 IC 及 Code Size 的影響。
3. Memory-Register ISA vs. Load/Store ISA 的指令數差異。
4. 架構暫存器（Architectural Registers）數量對 Register Spilling 與 IC 的影響。
5. **複雜定址模式（Complex Addressing Modes）**對 IC 與 CCT 的影響。

---

選項分析

• (A) 錯誤。
  增加管線深度（Increasing pipeline depth）主要目的是將組合邏輯電路切成更多階段，以縮短關鍵路徑（Critical Path），進而降低時脈週期時間（CCT）（即提高時脈頻率）。
  在理想狀況下，管線化的吞吐量提升，但實際 CPI 會因為控制冒險（Branch Misprediction Penalty）與資料冒險（Data Hazard Stalls）帶來的停頓週期（Bubbles）增加而微幅上升（變差）。因此，管線化提升效能主因是降低 CCT，而非降低 CPI。

• (B) 正確。
  若從 ISA 中移除位元組載入與儲存指令（如 lb / sb），當程式需要處理 char 型態、字串或 byte 陣列時，編譯器必須改用字組（Word）單位的載入指令（如 lw），搭配多個位元移位（Shif

核心觀念

本題考查大型語言模型（LLM）推論時的快取架構（Memory Hierarchy）、記憶體頻寬限制（Memory Bandwidth Bound）、向量與矩陣運算之空間/時間局部性（Locality），以及模型量化（Quantization）對系統效能與記憶體容量需求的影響。

1. 矩陣與向量記憶體容量計算：
   • 元素數量為 $N \times N$ 之矩陣，資料型別精度為 FP16（2 bytes）、INT8（1 byte）、INT4（0.5 bytes）。
   • 容量計算公式：
     $\text{總容量 (Bytes)} = \text{元素個數} \times \text{單一元素位元組數}$
2. 快取記憶體容量與局部性（Cache Capacity & Locality）：
   • 時間局部性（Temporal Locality）：同一個資料項目在短時間內被重複存取。
   • 當資料總容量小於 Cache 容量時，資料可全數保留於該層級 Cache 中，避免至下一層記憶體提取（Eviction）。
3. 記憶體受限模型（Memory-Bound Workload）：
   • LLM 在單一 Token 生成階段（Autoregressive Decoding）主要執行矩陣-向量乘法（Matrix-Vector Multiplication, GEMV），每個權重僅被讀取一次（Operational Intensity 極低），系統效能瓶頸為記憶體傳輸頻寬（Memory Bandwidth）。
   • 執行時間與傳輸資料量成正比：
     $\text{Token 產生速率 (Tokens/s)} \approx \frac{\text{記憶體頻寬 (GB/s)}}{\text{權重模型大小 (GB)}}$

---

解題方法

根據題目給定的硬體與模型規格：

• L1 Cache：32 KB / core
• L2 Cache：256 KB / core
• L3 Cache：32 MB shared
• Main Memory：64 GB DDR5, Bandwidth 50 GB/s
• 權重與向量資料長度：
  • FP16：2 bytes / element
  • INT8：1 byte / element
  • INT4：0.5 bytes / element
  • float（Activation $x$ 與 $y$）：4 bytes / element

將選項中的矩陣容量、活化向量容量及 7B 模型總容量逐一計算並進行規格比對與效能分析。

---

選項分析

• (A) 錯誤

  • 權重矩陣 $W$ 大小為 $4096 \times 4096 = 16,777,216$ 個元素。
  • 使用 FP16 精度時，矩陣所需的記憶體容量為：
    $16,777,216 \times 2 \text{ bytes} = 33,554,432 \text{ bytes} = 32 \text{ MB}$
  • 雖然 $32 \text{ MB}$ 數值上等於 L3 Cache 的總容量（$32 \text{ MB}$），但權重矩陣本身已佔滿 $100\%$ 的 L3 空間，完全沒有額外空間容納活化向量 $x$、$y$、程式碼與系統其他快取資料。因此「fits comfortably with room...（舒適放入並留有空間）」之敘述錯誤。

• (B) 正確

  • FP16 權重每個元素佔用 2 bytes，INT4 權重每個元素佔用 0.5 bytes。
  • 權重資料量的縮減比例為：
    $\frac{2 \text{ bytes}}{0.5 \text{ bytes}} = 4 \text{ 倍}$

核心觀念

本題考查大型語言模型（LLM）推理時的異質計算架構（CPU-NPU）資料搬移瓶頸與**記憶體頻寬受限（Bandwidth-Bound）**特性。

在 LLM 單一 Token 生成（Auto-regressive decoding）階段，模型權重需要逐層載入至加速器進行矩陣運算。系統整體延遲 $T_{\text{token}}$ 由兩部分組成：

1. 傳輸延遲（Transmission Latency）：資料經由 PCIe 匯流排搬移至 NPU SRAM 的時間。
   $t_{\text{PCIe}} = \frac{\text{Data Size}}{\text{PCIe Bandwidth}}$
2. 計算延遲（Computation Latency）：NPU 執行算術運算的時間。
   $t_{\text{compute}} = \frac{\text{FLOPs}}{\text{Throughput}}$

當加速器晶上記憶體（SRAM）容量小於模型權重總量時，權重無法常駐（Weight Resident），導致系統效能大幅受限於匯流排傳輸頻寬（PCIe-bandwidth-bound）。

---

解題方法

1. 基準延遲定量計算

• 單層 PCIe 傳輸延遲：
  $t_{\text{PCIe, layer}} = \frac{875 \text{ MB}}{50 \text{ GB/s}} = \frac{0.875 \text{ GB}}{50 \text{ GB/s}} = 0.0175 \text{ s} = 17.5 \text{ ms}$

• 單層 NPU 計算延遲：
  $t_{\text{NPU, layer}} = \frac{140 \times 10^9 \text{ ops}}{400 \times 10^{12} \text{ ops/s}} = 0.00035 \text{ s} = 0.35 \text{ ms}$

• 單一 Token 生成之總傳輸延遲（共 80 層）：
  $T_{\text{PCIe}} = 80 \times 17.5 \text{ ms} = 1400 \text{ ms} = 1.4 \text{ s}$

• 單一 Token 生成之總計算延遲（共 80 層）：
  $T_{\text{NPU}} = 80 \times 0.35 \text{ ms} = 28 \text{ ms} = 0.028 \text{ s}$

• 每 Token 生成之總延遲：
  $T_{\text{total}} = T_{\text{PCIe}} + T_{\text{NPU}} = 1.4 \text{ s} + 0.028 \text{ s} = 1.428 \text{ s}$

2. 時間與空間複雜度小結

• 傳輸資料量：$O(N_{\text{layers}} \times W_{\text{layer}}) = 70 \text{ GB}$ / Token
• 計算複雜度：$O(N_{\text{layers}} \times C_{\text{layer}}) = 11.2 \times 10^{12}$ INT8 Operations / Token

---

選項分析

• (A) 正確

  • 分析：
    總 PCIe 傳輸延遲為 $1.4\text{ s}$（$1400\text{ ms}$），總 NPU 計算延遲為 $28\text{ ms}$。
    比值計算：$\frac{1400\text{ ms}}{28\text{ ms}} = 50$ 倍。
    傳輸時間佔據整體時間的 $\frac{1.4}{1.428} \approx 98.04\%$，系統效能嚴重受限於 PCIe 頻寬（PCIe-bandwidth-bound），敘述完全符合計算結果。

• (B) 正確

  • 分析：
    將模型由 INT8（1 Byte/param）量化至 INT4（0.5 Byte/param），模型權重容量減半至 $35\text{ GB}$（單層權重為

核心觀念

本題評量 6 階段 RISC-V 管線處理器（6-stage Pipeline） 的資料相依（Data Hazard）、結構特性、2-bit 分支預測器（2-bit Branch Predictor）、分支目標緩衝區（BTB）以及迭代執行週期（Iteration Execution Cycles）的計算。

1. 6 階段管線結構：
   • 各階段依序為：IF（擷取）$\to$ ID（解碼與讀取暫存器）$\to$ EX（執行／分支解析）$\to$ MEM1（記憶體存取第 1 階段）$\to$ MEM2（記憶體存取第 2 階段）$\to$ WB（寫回暫存器）。
2. 分離式暫存器檔案（Split-Phase Register File）：
   • 前半週期（First Half Cycle）執行寫入（Write），後半週期（Second Half Cycle）執行讀取（Read）。
   • 當前一指令於 Cycle $k$ 處於 WB 階段時，後續指令可在同一 Cycle $k$ 的 ID 階段直接讀取最新資料，無需額外停頓。
3. 資料轉發（Forwarding）與停頓（Stall）：
   • With Full Hardware Forwarding：
     • lw 指令在 MEM2 階段結束後產生載入資料。若後續指令在 EX 階段需要該資料（Load-Use Hazard），需在 ID 階段停頓 2 個週期（Stall 2 cycles），再由 MEM2 轉發至 EX。
     • ALU 指令（如 add, addi）之計算結果在 EX 階段結束後即可轉發給後續指令的 EX，無需停頓。
   • Without Hardware Forwarding：
     • 所有資料相依性必須等待生產指令進入 WB 階段寫入暫存器後，消費指令才能在 ID 階段讀取（藉由 Split-Phase 特性，可在生產指令的 WB 週期之後半段完成 ID 讀取）。
4. 分支預測與懲罰（Branch Prediction & Penalty）：
   • 分支指令在 EX 階段（即分支指令進入管線後的第 3 個週期）完成條件判斷與目標解析。
   • 若預測正確（Correct Prediction）：配合 BTB，在預測 Taken 時已於 IF 階段預測目標位址，無管線懲罰（0 penalty cycles）。
   • 若預測錯誤（Misprediction）：在 EX 階段發現錯誤並刷新（Flush）管線中已擷取的 2 道錯誤指令，目標位址（或循序位址）的 IF 於次一週期開始，造成 2 個週期的分支懲罰（Branch Penalty = 2 cycles）。
5. 迭代執行週期之定義：
   • 第 $i$ 次迭代執行週期數 = 第 $(i+1)$ 次迭代的 IF 開始週期 $-$ 第 $i$ 次迭代的 IF 開始週期（最後一次迭代則以離開迴圈後第一道指令的 IF 開始週期做計算）。

---

解題方法與推導

1. 迴圈內指令與相依性整理

I1: lw      x3, 0(x11)      # 寫入 x3（於 MEM2 產生）
I2: lw      x4, 0(x12)      # 寫入 x4（於 MEM2 產生）
I3: add     x5, x3, x4      # 讀取 x3, x4；寫入 x5（於 EX 產生）
I4: sw      x5, 0(x11)      # 讀取 x5, x11
I5: addi    x11, x11, 4     # 讀取/寫入 x11（於 EX 產生）
I6: addi    x12, x12, 4     # 讀取/寫入 x12（於 EX 產生）
I7: bne     x11, x13, Loop  # 讀取 x11, x13；於 EX 階段判斷

---

2. 有硬體轉發（With Full Forwarding）分析

(1) 第 1 次迭代（Iteration 1）管線追蹤：

• 初始預測器狀態為 Predict Non-Taken, 11。
• I3 (add) 相依於 I2 (lw) 的 x4，因 lw 需至 MEM2 結束才產生資料，I3 需在 ID 停頓 2 個週期。
• I7 (bne) 於 Cycle 9 進入 IF，Cycle 11 進入 EX 並解析出實際結果為 Taken（因第 1 次迭代未結束）。
• 預測為 Non-Taken，實際為 Taken $\to$ 預測錯誤（Misprediction），管線在 Cycle 11 刷新錯誤擷取的指令。
• 第 2 次迭代的 I1 於 Cycle 12 進入 IF。
• 2-bit 預測器狀態從 11 (Strongly NT) 轉移至 10 (Weakly NT)。

(2) 第 2 次迭代（Iteration 2）管線追蹤：

• 進入第 2 次迭代時，預測器狀態為 10 (Weakly NT)，依然預測 Non-Taken。
• 管線時序如下表（從 Cycle 12 開始）：

指令	C12	C13	C14	C15	C16	C17	C18	C19	C20	C21	C22	C23
I1: lw	IF	ID	EX	M1	M2	WB
I2: lw		IF	ID	EX	M1	M2	WB
I3: add			IF	ID	ID	ID	EX	M1	M2	WB
I4: sw				IF	IF	IF	ID	EX	M1	M2	WB
I5: addi							IF	ID	EX	M1	M2	WB
I6: addi								IF	ID	EX	M1	M2
I7: bne									IF	ID	EX

• 詳細推導：
  • Cycle 12: I1 進入 IF。
  • Cycle 13: I2 進入 IF。
  • Cycle 14: I3 進入 IF。
  • Cycle 15~17: I3 進入 ID 階段。由於 I2 (lw) 在 Cycle 17 結束時才完成 MEM2，I3 必須停頓至 Cycle 17，並在 Cycle 18 進入 EX（透過 Forwarding 取得 x4）。
  • Cycle 18: I4 進入 ID，I5 進入 IF。
  • Cycle 19: I5 進入 ID，I6 進入 IF。
  • Cycle 20: I6 進入 ID，I7 (bne) 進入 IF。
  • Cycle 21: I7 進入 ID。
  • Cycle 22: I7 進入 EX 解析分支。實際結果為 Taken，但預測為 Non-Taken $\to$ 再次預測錯誤！
  • Cycle 23: 刷新管線後，第 3 次迭代的 I1 於 Cycle 23 開始 IF。
• 第 2 次迭代執行時間：
  $T_{\text{iter 2}} = 23 - 12 = 11 \text{ 週期}$

---

3. 無硬體轉發（Without Forwarding）分析

在沒有硬體轉發的情況下，所有暫存器相依性必須等待生產指令到達 WB 階段，消費者才能在 ID 階段讀取：

1. I3 (add) 需等待 I2 (lw) 進入 WB 階段（寫入 x4），故 I3 在 ID 停頓等待。

核心觀念

本題旨在考驗多核心處理器在並行（Parallel）與串行（Serial）工作負載切換下的執行時間（Execution Time/Delay）、動態功耗（Dynamic Power）、漏電功耗（Leakage Power）與總消耗能量（Energy Consumption）的綜合分析能力。

解題用到的主要定義與公式如下：

1. CPU 執行時間公式 (CPU Time / Delay)：
   $T = \frac{I \times \text{CPI}}{f}$
   其中 $I$ 為指令數、$\text{CPI}$ 為平均每指令週期數、$f$ 為工作頻率。
   在雙核心平行執行階段，指令平分給兩個核心，每個核心負擔 $\frac{I_p}{2}$ 的指令量；串行階段則僅由單核心執行 $I_s$ 的指令量。

2. 動態功耗 (Dynamic Power)：
   $P_{\text{dyn}} = C \times V^2 \times f$
   其中 $C$ 為單核心電容（Capacitance）、$V$ 為工作電壓（Voltage）、$f$ 為工作頻率。

3. 能量消耗 (Energy)：
   $\text{Energy} = \text{Power} \times \text{Time} = E_{\text{dyn}} + E_{\text{leak}}$

   • 單一指令動態能量：$E_{\text{dyn, inst}} = P_{\text{dyn}} \times \left(\frac{\text{CPI}}{f}\right) = C \times V^2 \times \text{CPI}$（與頻率 $f$ 無關）。
   • 總動態能量：$E_{\text{dyn}} = N_{\text{total}} \times C \times V^2 \times \text{CPI}$。
   • 總漏電能量：$E_{\text{leak}} = P_{\text{leak, 1core}} \times T_{\text{serial}} + P_{\text{leak, 2core}} \times T_{\text{parallel}}$。當單一核心關閉時，漏電功耗減半。

4. 能量延遲積 (Energy-Delay Product, EDP)：
   $\text{EDP} = \text{Energy} \times \text{Delay}$
   EDP 數值越小，代表能源效率（Energy Efficiency）越佳。

---

解題方法

將工作負載拆解為「串行階段」（Serial Phase，指令數 $N_s = 0.25 \times 10^9$）與「平行階段」（Parallel Phase，指令數 $N_p = 0.75 \times 10^9$，雙核平分後單核負責 $0.375 \times 10^9$），分別計算 Processor A 與 Processor B 的執行時間、功耗與總能量。

1. 執行時間 (Delay) 計算

• Processor A ($f_A = 3.0\text{ GHz}, \text{CPI}_A = 1.2$)：

  • 串行時間：$T_{s, A} = \frac{0.25 \times 10^9 \times 1.2}{3.0 \times 10^9} = 0.1\text{ s}$
  • 平行時間：$T_{p, A} = \frac{0.375 \times 10^9 \times 1.2}{3.0 \times 10^9} = 0.15\text{ s}$
  • 總執行時間：$T_A = T_{s, A} + T_{p, A} = 0.1 + 0.15 = 0.25\text{ s}$

• Processor B ($f_B = 2.0\text{ GHz}, \text{CPI}_B = 1.0$)：

  • 串行時間：$T_{s, B} = \frac{0.25 \times 10^9 \times 1.0}{2.0 \times 10^9} = 0.125\text{ s}$
  • 平行時間：$T_{p, B} = \frac{0.375 \times 10^9 \times 1.0}{2.0 \times 10^9} = 0.1875\text{ s}$
  • 總執行時間：$T_B = T_{s, B} + T_{p, B} = 0.125 + 0.1875 = 0.3125\text{ s}$

2. 功耗與能量計算

• Processor A ($C_A = 1.2\text{ nF}, V_A = 1.1\text{ V}, P_{\text{leak, 2core}} = 500\text{ mW} = 0.5\text{ W}$)：
  • 單核動態功耗：$P_{\text{dyn, A, 1core}} = 1.2 \times 10^{-9} \times (1.1)^2 \times 3.0 \times 10^9 = 4.356\text{ W}$
  • 總動態能量：$E_{\text{dyn, A}} = 10^9 \times (1.2 \times 10^{-9}) \times (1.1)^2 \times 1.2 = 1.7424\text{ J}$

核心觀念

本題考查計算機結構中 CPU 執行時間（CPU Time）、動態功耗（Dynamic Power）、**漏電功耗（Leakage Power）與能量延遲積（Energy-Delay Product, EDP）**的計算與綜合評估。

1. CPU 執行時間公式：
   $T = \frac{\text{Instruction Count} \times \text{CPI}}{\text{Frequency}}$
2. 功耗與能量關係：
   • 動態功耗（Dynamic Power）：$P_{\text{dyn}} = C \times V^2 \times F$（單核心 active 時）。
   • 動態能量（Dynamic Energy）：執行 $I$ 條指令時，每條指令消耗的動態能量為 $\text{CPI} \times C \times V^2$。因此總動態能量為 $E_{\text{dyn}} = I \times \text{CPI} \times C \times V^2$。
   • 漏電能量（Leakage Energy）：$E_{\text{leak}} = P_{\text{leak}} \times T$。當單核 active、單核 power-gated 時，開啟的核心數減半，漏電功耗亦隨之減半。
   • 總能量（Total Energy）：$E_{\text{total}} = E_{\text{dyn}} + E_{\text{leak}}$。
3. 能量效率指標（Energy Efficiency Metric）：
   • 能量延遲積（Energy-Delay Product, EDP）：$\text{EDP} = E_{\text{total}} \times T$
   • EDP 指標越小，代表處理器在綜合考量速度與省電下的能量效率越高。

---

解題方法

1. 工作負載拆解（Workload Analysis）

總指令數 $I_{\text{total}} = 10^9$ 條：

• 串行部分（Serial Part, 25%）：$I_{\text{serial}} = 0.25 \times 10^9$ 條指令。由 1 個核心執行，另 1 個核心 Power-gated（功耗為 0）。
• 平行部分（Parallel Part, 75%）：$I_{\text{parallel}} = 0.75 \times 10^9$ 條指令。均勻平分給 2 個核心執行，各執行 $0.375 \times 10^9$ 條指令，2 個核心皆處於 active 狀態。

---

2. 處理器 A（Processor A）推導與計算

• 參數：$F_A = 3.0\text{ GHz}$、$V_A = 1.1\text{ V}$、$\text{CPI}_A = 1.2$、$C_A = 1.2\text{ nF}$、$P_{\text{leak, A}} = 0.5\text{ W}$（雙核全開）。

(1) 執行時間（Execution Time）

• 串行時間：
  $T_{\text{serial, A}} = \frac{0.25 \times 10^9 \times 1.2}{3.0 \times 10^9} = 0.1\text{ 秒}$
• 平行時間：
  $T_{\text{parallel, A}} = \frac{0.375 \times 10^9 \times 1.2}{3.0 \times 10^9} = 0.15\text{ 秒}$
• 總執行時間（Delay）：
  $T_A = 0.1 + 0.15 = 0.25\text{ 秒}$

(2) 漏電能量（Leakage Energy）

• 串行模式（1 核 active, 1 核 power-gated）：$P_{\text{leak, serial}} = \frac{0.5}{2} = 0.25\text{ W}$
  $E_{\text{leak, serial, A}} = 0.25\text{ W} \times 0.1\text{ s} = 0.025\text{ J}$
• 平行模式（2 核 active）：$P_{\text{leak, parallel}} = 0.5\text{ W}$
  $E_{\text{leak, parallel, A}} = 0.5\text{ W} \times 0.15\text{ s} = 0.075\text{ J}$
• 總漏電能量：
  $E_{\text{leak, A}} = 0.025 + 0.075 = 0.100\text{ J}$

(3) 動態能量與總能量（Dynamic & Total Energy）

• 單核動態功耗：
  $P_{\text{dyn, A, 1core}} = 1.2 \times 10^{-9} \times (1.1)^2 \times 3.0 \times 10^9 = 4.356\text{ W}$
• 總動態能量：
  $E_{\text{dyn, A}} = (4.356 \times 0.1) + (2 \times 4.356 \times 0.15) = 0.4356 + 1.3068 = 1.7424\text{ J}$
• 總能量：
  $\text{Energy}(A) = E_{\text{dyn, A}} + E_{\text{leak, A}} = 1.7424 + 0.100 = 1.8424\text{ J}$

---

3. 處理器 B（Processor B）推導與計算

• 參數：$F_B = 2.0\text{ GHz}$、$V_B = 0.9\text{ V}$、$\text{CPI}_B = 1.0$、$C_B = 1.0\text{ nF}$、$P_{\text{leak, B}} = 0.4\text{ W}$（雙核全開）。

(1) 執行時間（Execution Time）

• 串行時間：
  $T_{\text{serial, B}} = \frac{0.25 \times 10^9 \times 1.0}{2.0 \times 10^9} = 0.125\text{ 秒}$
• 平行時間：

核心觀念

本題考驗作業系統（Operating System）中檔案配置（File Allocation）的三大基本策略：連續配置（Contiguous Allocation）、鏈結配置（Linked Allocation） 與 索引配置（Indexed Allocation） 之區塊空間開銷分析。

• 區塊大小（Block Size, $B$）：$4,096 \text{ bytes}$
• 指標大小（Pointer Size, $P$）：$8 \text{ bytes}$
• 檔案大小（File Size, $N$）：$N \text{ bytes}$

當檔案大小 $N$ 趨近於無限大（$N \to \infty$）時，可忽略極小項與無條件進位（$\lceil \cdot \rceil$）產生的邊界開銷，利用極限分析各配置方式中「資料區塊」與「指標/索引等元資料（Metadata）區塊」的總開銷比例。

---

解題方法

當 $N \to \infty$ 時，分別推導四種配置方式所要求的總區塊數 $W, X, Y, Z$：

1. 連續配置（Contiguous Allocation）—— 區塊數 $W$

在連續配置下，檔案資料連續存放於磁碟區塊中，資料區塊內不需額外儲存鏈結指標。

• 每個區塊完全用於存放檔案資料，容量為 $B = 4,096 \text{ bytes}$。
• 總區塊數：
  $W \approx \frac{N}{4,096}$

2. 無叢集鏈結配置（Linked Allocation without Clustering）—— 區塊數 $X$

每個區塊內包含檔案資料以及指向下一個區塊的指標（$8 \text{ bytes}$）。

• 每個區塊可用於存放檔案資料的有效空間為 $B - P = 4,096 - 8 = 4,088 \text{ bytes}$。
• 總區塊數：
  $X \approx \frac{N}{4,088}$

3. 具叢集鏈結配置（Linked Allocation with Clustering, $K$ Blocks/Cluster）—— 區塊數 $Y$

以 $K$ 個連續區塊合稱為一個「叢集（Cluster）」，鏈結指標以叢集為單位進行連結。

• 一個叢集的總容量為 $K \times B = 4,096K \text{ bytes}$。
• 扣除一個叢集指標 $P = 8 \text{ bytes}$ 後，每個叢集可用於存放檔案資料的有效空間為 $4,096K - 8 \text{ bytes}$。
• 所需叢集數為 $\frac{N}{4,096K - 8}$，故總區塊數 $Y$ 為：
  $Y \approx K \times \frac{N}{4,096K - 8} = \frac{N}{4,096 - \frac{8}{K}}$

4. 索引配置且索引採無叢集鏈結（Indexed Allocation with Linked Indexes）—— 區塊數 $Z$

索引配置將「資料區塊」與「索引區塊」分離：

• 資料區塊（Data Blocks）：專門存放檔案資料，每個區塊滿載 $4,096 \text{ bytes}$ 資料，故資料區塊數等於連續配置的區塊數 $W \approx \frac{N}{4,096}$。
• 索引區塊（Index Blocks）：每個索引區塊大小為 $4,096 \text{ bytes}$。由於索引區塊之間採用無叢集鏈結，每個索引區塊需保留 $P = 8 \text{ bytes}$ 作為指向下一個索引區塊的指標，剩餘 $4,096 - 8 = 4,088 \text{ bytes}$ 用於存放指向資料區塊的指標。
• 每個索引區塊可指向的資料區塊數：
  $\frac{4,088 \text{ bytes}}{8 \text{ bytes/pointer}} = 511 \text{ 個指標}$
• 所需索引區塊數：

核心觀念

兩個佇列各自維持固定順序，因此任何可行排程都是兩個序列的交錯排列。任務不能搶先，但可以因到達時間而等待；相鄰任務的切換時間則取決於它們是否來自同一佇列。

可用動態規劃記錄已完成前 $i$ 個 $S$ 任務、前 $j$ 個 $T$ 任務時，最後一個任務來自哪個佇列，以及最早能在何時完成。

解題方法

令 $F_S(i,j)$ 表示完成 $S_1,\ldots,S_i$ 與 $T_1,\ldots,T_j$，且最後完成的是 $S_i$ 時的最早完成時間；$F_T(i,j)$ 則表示最後完成的是 $T_j$ 時的最早完成時間。

若前一個任務完成時間為 $c$，而下一個任務到達時間為 $r$，其切換時間為 $w$、執行時間為 $e$，則下一個任務的完成時間是

$$\max(r,c+w)+e$$

其中同佇列切換取 $W_s=1$，跨佇列切換取 $W_d=3$。各狀態只需比較兩種可能的前一個佇列；例如：

$$F_S(i,j)= \min\left\{ \max(A_i,F_S(i-1,j)+W_s)+E_{Si}, \max(A_i,F_T(i-1,j)+W_d)+E_{Si} \right\}$$

$F_T(i,j)$ 以相同方式由 $(i,j-1)$ 的兩種結尾狀態轉移而來。若前綴中沒有任務，則直接從到達時間開始執行。

依此計算，本題的關鍵狀態如下。每格依序列出「最後為 $S$ 任務的最早完成時間、最後為 $T$ 任務的最早完成時間」：

已完成任務	最早完成時間 $(F_S,F_T)$
前 6 個 $S$、前 6 個 $T$	$(140,139)$
前 6 個 $S$、前 7 個 $T$	$(166,158)$
前 7 個 $S$、前 6 個 $T$	$(145,152)$
前 7 個 $S$、前 7 個 $T$	$(165,164)$

因此最短完工時間為