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

核心觀念

本題考查計算機架構中評估 CPU 效能的核心理論——效能鐵律（Iron Law of Processor Performance），以及管線化（Pipelining）設計與效能評估指標（MIPS vs. Execution Time）的基本定義。

CPU 的執行時間（Execution Time）由三大因素決定，其數學表示式如下：
$\text{CPU Execution Time} = \text{Instruction Count (IC)} \times \text{Cycles Per Instruction (CPI)} \times \text{Clock Cycle Time (CCT)}$

亦可寫為：
$\text{CPU Execution Time} = \frac{\text{IC} \times \text{CPI}}{\text{Clock Rate}}$

效能（Performance）與執行時間成反比關係：
$\text{Performance} = \frac{1}{\text{Execution Time}}$

此外，本題涵蓋以下觀念：

1. 單週期 vs. 管線化：管線化透過分割執行階段來縮短時脈週期時間（CCT），進而大幅提高單位時間完成的指令數（Throughput）；但因各階段之間加入管線暫存器（Pipeline Registers）會產生額外開銷（Overhead），單一指令從開始到結束的延遲（Latency）通常會增加。
2. CPI 的動態特性：程式的平均 CPI 取決於硬體架構設計、指令混合比例（Instruction Mix）與記憶體階層架構（如 Cache Miss Rate）等因素。
3. MIPS 的評比限制：MIPS（每秒執行百萬條指令數）未考量不同指令集架構（ISA）之間指令複雜度與指令數量的差異，因此無法作為跨 ISA 電腦效能評比的公正指標；「執行時間」才是唯一客觀的評比標準。

---

解題方法

針對題目問及的 CPU 效能鐵律與計算機組織基本概念，採用效能公式推導法與計算機組織原理定義逐一審視各選項：

1. 將題目給定之條件代入效能鐵律公式，分析變數之間的正反比關係與獨立性。
2. 運用單週期（Single-Cycle）與管線化（Pipelined）架構的 CCT、Latency 與 Throughput 定義進行比較。
3. 根據 MIPS 的數學定義 $\text{MIPS} = \frac{\text{Clock Rate}}{\text{CPI} \times 10^6}$，分析其在跨 ISA 比較時的合理性。

---

選項分析

• (a) 錯誤

  • 原因：根據效能鐵律公式 $\text{CPU Execution Time} = \frac{\text{IC} \times \text{CPI}}{\text{Clock Rate}}$，若不限定「指令數（IC）與 CPI 保持不變」（即題目所述 regardless of the instruction count or CPI），則提高時脈速率（Clock Rate）時，可能因為時脈變快導致記憶體存取所需的週期數大幅增加（使 CPI 升高），或是硬體變更導致需要的指令數（IC）增加。當 CPI 或 IC 增加的幅度大於 Clock Rate 提升的幅度時，總執行時間反而會增加。因此「總是下降（will always decrease）」的說法不成立。

• (b) 正確

  • 原因：在 CPI 與時脈週期時間（Clock Cycle Time）維持恆定（constant）的前提下，由公式

1. 本題核心觀念

• 5‑stage RISC‑V pipeline：IF → ID → EX → MEM → WB。
• 分支 (branch) 的控制危險 (control hazard) 在於 分支是否成立、以及分支目標位址 何時可得。
• 分支預測 (branch prediction)：利用「預測不採取 (not‑taken)」或動態預測 (BHT) 於取指階段決定取哪條路徑，減少因分支決策延遲而產生的 flush / 停頓 (pipeline penalty)。
• 在 full forwarding 的情況下，資料危險已被解決，但 控制危險 仍需依靠預測或提前決策的硬體支援。

---

2. 解題過程與判斷

選項	判斷	說明
(a)	正確	若 pipeline 預設 「branch not taken」，當實際分支為 taken 時，已經從 fall‑through (即下一條順序指令) 取出的指令必須在知道分支成立後全部 flush，避免錯誤執行。此 flush 包含在 IF、ID 階段已進入的指令，屬於典型的控制危險處理。
(b)	錯誤	在標準的 RISC‑V 五階段 pipeline 中，分支的條件比較與跳轉目標的計算通常在 EX 階段完成；MEM 階段僅負責資料存取，不影響 分支決策。

核心觀念

本題主要考驗 RISC-V 指令集架構（ISA）格式設計原則與定址模式（Instruction Formats and Addressing Modes），包含以下核心理論重點：

1. 精簡指令集（RISC）之固定長度特性：RISC-V 基礎架構（RV32I/RV64I）採用固定 32 位元（32-bit）指令長度，相較於 x86 變長度（1 ~ 15 位元組）指令，可顯著簡化硬體的「指令擷取（Instruction Fetch, IF）」與「指令解碼（Instruction Decode, ID）」階段邏輯。
2. 固定暫存器欄位位置原則（Fixed Register Source/Destination Location）：RISC-V 為簡化解碼電路，將暫存器指定位元固定於特定位置：$rs1$ 在 bit [19:15]、$rs2$ 在 bit [24:20]、$rd$ 在 bit [11:7]。
3. 二補數立即數範圍計算：$n$ 位元帶符號立即數（Signed Immediate）採用二補數表示法，其數值範圍公式為：
   $-2^{n-1} \le \text{Immediate} \le 2^{n-1} - 1$
4. PC 相對定址模式（PC-Relative Addressing）：目標位址由「程式計數器（Program Counter, PC）」加上分支或跳轉指令中的立即數偏移量計算而得：
   $\text{Target Address} = \text{PC} + \text{Immediate Offset}$

---

解題方法

依據 RISC-V Unprivileged ISA 架構規範與經典計算機組織教科書（Patterson & Hennessy）定義，對每一個選項涉及的指令格式（I-type, S-type, J-type）、編碼欄位配置、數值表示範圍及定址計算方式進行逐一比對與解析。

---

選項分析

• (a) 正確 (TRUE)

  • 分析：RISC-V 的基本指令集（RV32I/RV64I）全數採用固定的 32 位元長度編碼。在多級管線（Pipelining）設計中，固定指令長度使得下一條指令的位址只需簡單計算 $\text{PC} + 4$，且指令欄位格式統一，硬體不需額外解碼變長度指令的邊界與動態長度，大幅簡化了指令擷取（IF）與指令解碼（ID）階段的邏輯電路。相對地，x86 為 CISC 架構，指令長度介於 1 至 15 位元組不等，需要複雜的長度解碼器（Length Decoder）與預擷取緩衝區。

• (b) 錯誤 (FALSE)

  • 分析：在 RISC-V 規範中，jal（Jump and Link）指令屬於 J-type 格式，硬體語法與格式為 jal rd, offset，其作用是將跳轉目標位址寫入 PC，並將返回地址 $PC + 4$ 儲存至指定的目的暫存器 $rd$。雖然在 ABI 軟體慣例中常使用 $x1$（即 $ra$ 暫存器）來儲存返回位址，且偽指令 jal offset 預設會展開為 jal x1, offset，但從 ISA 硬體架構定義而言，jal 支援寫入任意通用暫存器 $rd$（例如可寫入 $x5$ 或寫入 $x0$ 實作無條件跳轉）。

(a) 正確：塊大小 $16\text{B}=2^{4}$，需 $\log_{2}16 = 4$ 位元作為 Byte Offset。

(b) 正確：快取大小 $16\text{KiB}=2^{14}$，塊大小 $2^{4}$，塊數 $2^{14-4}=2^{10}=1024$，直接映射每塊對應唯一索引，故 Index 需 $10$ 位元。

核心觀念

本題考查作業系統（Operating Systems）中**進程排程（Process Scheduling）與上下文切換（Context Switching）**的核心觀念與相關術語定義：

1. 上下文切換（Context Switching）：CPU 從一個進程切換至另一個進程時，保存舊進程狀態並載入新進程狀態的過程與開銷。
2. 排程演算法特性（Scheduling Algorithms）：Round Robin (RR) 與 First-Come, First-Served (FCFS) 的關係及時間區間（Time Quantum, $q$）對排程行為的影響。
3. 處理器親和性（Processor Affinity）：多處理器系統中的 Soft Affinity 與 Hard Affinity 之機制與約束力差別。
4. 進程狀態轉移（Process State Transition）：Ready State 與 Waiting/Blocked State 之定義差異。
5. 排程效能指標（Scheduling Criteria）：Throughput（吞吐量）與 Turnaround Time（週轉時間）的正確定義。

---

解題方法

本題為多重選擇題，需要逐一評估每一個選項敘述的正確性。分析切入點如下：

• 對於定義型敘述（如 (a)、(d)、(e)），對照作業系統經典教材（Silberschatz《Operating System Concepts》）的標準定義進行檢驗。
• 對於演算法極限行為（如 (b)），推導當時間區間 $q \to \infty$ 時，搶佔（Preemption）機制是否失效，進而判定是否退化為 FCFS。
• 對於處理器分配政策（如 (c)），釐清「Soft Affinity」與「Hard Affinity」在系統約束上的強烈程度（Guarantee vs. Attempt）。

---

選項分析

• (a) 正確：上下文切換（Context Switching）是指當 CPU 的執行權由某進程切換給另一個進程時，系統必須先保存舊進程的狀態（如 PCB 中的暫存器數值、程式計數器 PC 等），並載入新進程的狀態。在進行狀態保存與還原的這段時間內，CPU 並未執行任何屬於使用者進程的有效指令，因此上下文切換時間純粹是系統的額外開銷（Pure Overhead）。
• (b) 正確：Round Robin (RR) 演算法依據先到先服務原則排隊，並賦予每個進程固定的時間區間 $q$。當 $q$ 設定得極大（即 $q$ 遠大於所有進程的 CPU 爆發時間 $CPU\ burst\ time$），任何進程在耗盡其時間區間前就會自行完成爆發或進入 I/O 等待，不會發生因時間到期而進行的強制搶佔。

(a) 正確。死結必須同時滿足「互斥、佔有且等待、不可剝奪、循環等待」四個必要條件。

(b) 正確。若在執行前要求程序一次申請並取得全部所需資源，則「佔有且等待」條件不會成立。

核心觀念

本題考查作業系統（Operating Systems）中**虛擬記憶體（Virtual Memory）與頁面置換演算法（Page Replacement Algorithms）**的核心理論與機制，主要涵蓋以下觀念：

1. 最佳頁面置換演算法（OPT）的可行性：基於未來知識（Future Knowledge）的理論上限基準。
2. 貝拉迪異常（Belady's Anomaly）與堆疊演算法（Stack Algorithms）：頁框數增加與缺頁次數關係，以及 LRU 和 FIFO 的演算法特性差異。
3. 工作集模型（Working-Set Model）與顛簸（Thrashing）：多重程式規劃度（Degree of Multiprogramming）過高導致系統效能急遽下降的充要條件。
4. 分頁表項（Page Table Entry, PTE）狀態位元：臟位元（Dirty bit / Modify bit）與保護位元（Protection bits）的功能區隔。
5. 請求分頁（Demand Paging）機制：採用 Lazy Swapper 策略載入頁面的定義。

---

解題方法

本題為多重選擇題，解題切入點依據作業系統權威教材（如 Silberschatz 之 Operating System Concepts）對虛擬記憶體各機制的嚴謹定義，逐一審視各選項敘述的正確性：

• 檢查 OPT 演算法是否需要未來資訊。
• 驗證 LRU 是否屬於堆疊演算法以判斷是否具備 Belady's Anomaly 免疫性。
• 套用工作集模型公式 $\sum WSS_i > D$ 判斷 Thrashing 發生條件。
• 區分 Dirty bit（標記修改）與 Read-Only bit（存取控制）的用途。
• 核對 Demand Paging 的載入時機定義。

---

選項分析

• (a) 正確。最佳頁面置換演算法（Optimal Page Replacement Algorithm, OPT）的淘汰原則是「選擇未來最長時間不會被存取的頁面」。在通用的作業系統中，系統無法預知行程未來的記憶體存取序列（Page-reference string），因此 OPT 在實務上無法實作，僅能作為評估其他頁面置換演算法效能的理論上限基準（Benchmark）。
• (b) 錯誤。貝拉迪異常（Belady's Anomaly）是指「分配給行程的實體頁框（Frames）增加時，缺頁中斷（Page Faults）次數反而增加」的不直覺現象。

核心觀念

本題旨在考驗作業系統中**巨量儲存結構（Mass-Storage Structure）**與 RAID（Redundant Array of Independent Disks）技術的核心定義與運作機制：

1. RAID 層級與特性：包含 RAID 0（Striping）、RAID 1（Mirroring）、RAID 5（Distributed Parity）之容錯能力、最少磁碟需求數與儲存空間利用率。
2. 磁碟格式化層級：物理格式化／低階格式化（Low-Level Formatting / Physical Formatting）於磁碟控制器與底層磁區結構的作用。
3. 磁頭排程演算法（HDD Scheduling）：SSTF（Shortest Seek Time First）演算法的運作邏輯與是否會引發飢餓現象（Starvation）。

---

解題方法

本題為複選觀念題，需依據 Standard Operating System Concepts（Silberschatz 等著）之規範，逐一對各選項敘述進行真偽檢驗：

1. RAID 0 / 1 / 5 規範驗證：
   • 檢視 RAID 0 是否具備 redundancy。
   • 檢視 RAID 1 之空間開銷（Storage cost multiplier）與 redundancy 比例。
   • 檢視 RAID 5 建立所需的最低磁碟數 $N_{\min}$ 及容錯極限。
2. 低階格式化定義驗證：區分低階格式化（劃分 sector、寫入 header/trailer/ECC）與高階格式化（建立檔案系統）。
3. SSTF 性質驗證：依據 greedy 策略分析動態請求序列是否會使遠端磁軌請求陷入無限等待。

---

選項分析

• (a) 正確
  RAID 0 採用**資料條帶化（Data Striping）**技術，將資料切割成區塊後平行分散寫入多台磁碟，極大地提升了讀寫 throughput（效能）。然而 RAID 0 完全不提供任何冗餘機制（No Redundancy），亦無奇偶檢驗碼（Parity）。若陣列中任何一顆磁碟發生實體故障，整組 Array 的資料即毀損且無法復原。

• (b) 正確
  RAID 1 採用**磁碟鏡像（Disk Mirroring）**技術，將同一份資料完整複製並同時寫入兩顆（或兩組）磁碟中。若可用容量為 $C$，則實體所需的總儲存空間為 $2C$，相當於儲存成本翻倍（空間利用率僅為 $50\%$），但提供了 $100\%$ 的資料備份冗餘，可容忍鏡像對中單一磁碟的損壞。

核心觀念

本題考查計算機架構中的 CPU 效能方程式（CPU Performance Equation） 與 加權平均 CPI（Average Cycles Per Instruction） 之計算。

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

1. 加權平均 CPI（$\text{CPI}_{\text{avg}}$）：
   當程式包含多種不同類型的指令時，整體平均每條指令所需的時脈週期數為各類指令比例（Instruction Mix Ratio）與其對應 CPI 的加權平均：
   $\text{CPI}_{\text{avg}} = \sum_{i=1}^{n} (F_i \times \text{CPI}_i)$
   其中 $F_i$ 為第 $i$ 種指令占總指令數的百分比比例，$\text{CPI}_i$ 為第 $i$ 種指令執行所需的時脈週期數。

2. CPU 總執行時間（Total Execution Time, $T_{\text{exec}}$）：
   $\text{Execution Time} = \frac{\text{Instruction Count} \times \text{CPI}_{\text{avg}}}{\text{Clock Frequency}}$
   其中 $\text{Instruction Count}$（簡寫為 $IC$）為指令總數，$\text{Clock Frequency}$（簡寫為 $f$）為 CPU 時脈頻率。

---

解題方法

本題計算可分為三個關鍵步驟推導：

步驟一：計算加權平均 CPI（$\text{CPI}_{\text{avg}}$）

根據題目提供的指令混合比例與對應的 CPI：

• ALU ops：占 $50\%$（$0.50$），$\text{CPI} = 1$
• Loads：占 $20\%$（$0.20$），$\text{CPI} = 5$
• Stores：占 $10\%$（$0.10$），$\text{CPI} = 4$
• Branches：占 $20\%$（$0.20$），$\text{CPI} = 2$

帶入加權平均公式：
$\text{CPI}_{\text{avg}} = (0.50 \times 1) + (0.20 \times 5) + (0.10 \times 4) + (0.20 \times 2)$
$\text{CPI}_{\text{avg}} = 0.5 + 1.0 + 0.4 + 0.4 = 2.3 \text{ cycles/instruction}$

步驟二：確認相關系統參數

• 指令總數 $IC = 10^9 \text{ instructions}$

核心觀念

本題考驗作業系統（Operating Systems）虛擬記憶體管理中**快表（TLB, Translation Look-aside Buffer）與分頁機制（Paging）下的有效記憶體存取時間（Effective Memory Access Time, EMAT）**計算。

關鍵定義與公式：

1. TLB（Translation Look-aside Buffer）：專用於位址轉換的高速硬體快取，用來加速虛擬位址至實體位址（Virtual Address to Physical Address）的轉換。
2. 單層頁表（Single-level Page Table）：頁表存放於主記憶體（Main Memory）中。若 TLB 發生 Miss，CPU 必須先存取一次主記憶體以讀取頁表項目（Page Table Entry, PTE），拿到實體頁框號碼（Physical Page Frame Number）後，才能進行第二次主記憶體存取以獲取目標資料。
3. 順序尋找（Sequential Lookup）：題目特別註明 TLB 搜尋發生於記憶體存取之前（Sequential access），亦即不論命中與否，皆必須先花費 TLB 存取時間 $t_{\text{TLB}}$。
4. 有效記憶體存取時間（EMAT）加權平均通式：
   $\text{EMAT} = \text{Hit Ratio} \times \text{Hit Time} + \text{Miss Ratio} \times \text{Miss Time}$

---

解題方法

根據題意，已知參數如下：

• TLB 命中率（TLB Hit Ratio, $h$）$= 90\% = 0.9$
• TLB 未命中率（TLB Miss Ratio, $1 - h$）$= 1 - 0.9 = 0.1$
• TLB 存取時間（TLB Access Time, $t_{\text{TLB}}$）$= 10\text{ ns}$
• 主記憶體存取時間（Main Memory Access Time, $t_{\text{mem}}$）$= 100\text{ ns}$

關鍵推導步驟：

1. 計算 TLB 命中時的時間（$\text{Time}_{\text{hit}}$）：
   在 TLB 中順序尋找並順利找到頁碼對應關係（$10\text{ ns}$），接著直接存取實體主記憶體取得資料（$100\text{ ns}$）。
   $\text{Time}_{\text{hit}} = t_{\text{TLB}} + t_{\text{mem}} = 10\text{ ns} + 100\text{ ns} = 110\text{ ns}$

2. 計算 TLB 未命中時的時間（$\text{Time}_{\text{miss}}$）：
   先進行 TLB 尋找（$10\text{ ns}$），發生 Miss 後必須先存取一次主記憶體查詢單層頁表（$100\text{ ns}$），獲取實體位址後再存取第二次主記憶體讀取實際資料（$100\text{ ns}$）。
   $\text{Time}_{\text{miss}} = t_{\text{TLB}} + t_{\text{mem}} + t_{\text{mem}} = 10\text{ ns} + 100\text{ ns} + 100\text{ ns} = 210\text{ ns}$