112 年 國立中央大學資訊工程學系AI碩士班《作業系統與計算機組織》

核心觀念

本題旨在考驗計算機系統效能評估（Performance Evaluation）的基礎觀念與計算，涵蓋以下四大核心考點：

1. 效能指標定義：區分**吞吐量（Throughput）與響應時間（Response Time / Latency）**的物理意義。
2. CPU 效能方程式（CPU Performance Equation）：理解 CPI（Cycles Per Instruction，每指令平均時脈週期數）的本質為統計平均值，非整數限制。
3. 阿姆達爾定律（Amdahl's Law）：局部最佳化對整體系統執行時間影響的計算公式：
   $T_{\text{new}} = T_{\text{unaffected}} + T_{\text{affected, new}} = T_{\text{old}} \times \left( (1 - f) + \frac{f}{S} \right)$
   其中 $f$ 為可被改善部分佔原時間的比例，$S$ 為該部分的加速倍率。
4. 平行與多執行緒計時（Multi-threading Metrics）：區分 CPU 時間（CPU Time） 與 經過時間（Elapsed Time / Wall-clock Time） 在多核心／多執行緒環境下的差異。

---

解題方法

1. 區分指標與名詞定義：
   • 吞吐量（Throughput）定義為「單位時間內系統完成的工作總量」（例如 $\text{tasks/sec}$）。
   • 系統接收請求後處理完畢所需的物理時間稱為「響應時間（Response Time）」或「執行時間（Execution Time）」。
2. 分析 CPU 效能參數：
   • CPI 為「執行總時脈週期數（Total Clock Cycles）」除以「指令總數（Instruction Count, IC）」。因為是統計平均值，即使 CPU 時脈頻率（Clock Rate）為整數，CPI 仍可為浮點數（小數）。
3. 推導阿姆達爾定律：
   • 設原本系統總執行時間 $T_{\text{old}} = 1.0$。
   • 某元件佔總時間的 $30\%$（即 $f = 0.3$），未改變部分佔 $70\%$（即 $1 - f = 0.7$）。
   • 將該元件執行時間縮減為一半（即加速倍率 $S = 2$），改善後該元件的時間變為 $\frac{0.3}{2} = 0.15$。
   • 新總執行時間 $T_{\text{new}} = 0.7 + 0.15 = 0.85 = 85\% \times T_{\text{old}}$。
4. 檢驗多執行緒環境之時間關係：
   • CPU Time 為所有 CPU 核心執行該程式執行緒所消耗的時間累加和（User CPU Time + System CPU Time）。
   • Elapsed Time 為現實世界經過的牆鐘時間（Wall-clock Time）。

核心觀念

1. Segmentation Fault（記憶體區段錯誤 / SIGSEGV）的定義
   在具備虛擬記憶體管理（MMU / Paging）的作業系統中，當行程（Process）嘗試存取未授權、未分配或違反保護權限（例如試圖寫入唯讀區段）的虛擬記憶體位址時，硬體 MMU 會觸發 Access Violation 異常，作業系統核心隨後傳送 SIGSEGV（Segmentation Violation）訊號給該行程，導致程式異常中斷崩潰。

2. 常見引發 Segmentation Fault 的情境

   • 空指標解引用（NULL Pointer Dereference）：存取位址 $0$（NULL）。
   • 野指標解引用（Wild Pointer Dereference）：存取未初始化、內含隨機記憶體位址的指標。
   • 堆疊溢位（Stack Overflow）：無窮遞迴或過大的區域變數耗盡 Stack 空間，超越位址邊界存取 Guard Page。
   • 越界存取與違規存取：陣列越界、存取已釋放的記憶體（Dangling Pointer）或試圖修改 Code / Text 區段中的常數。

---

解題方法

本題考驗 C 語言指標運算、記憶體配置與作業系統記憶體保護機制。解題切入點在於分析各選項程式碼在執行時對虛擬記憶體空間（Virtual Address Space）產生的影響，並評估是否會觸發非法記憶體存取（SIGSEGV）。

---

選項分析

• A. 錯誤
  行程存取堆積區段（Heap Segment）內合法動態配置的記憶體（如透過 malloc 分配）是標準的正常行為。只有在存取 Heap 範圍外未配置的位址、或存取已被 free() 釋放的記憶體（Dangling Pointer）時才會出錯，而非「存取 Heap 區段本身」就會引發 Segmentation Fault。

• B. 正確
  char* p = NULL; 將指標 p 設定為 NULL（位址為 $0$）。在現代作業系統的虛擬記憶體架構中，位址 $0$ 屬於被特別保護且未映射（Unmapped）的保留頁面。

核心觀念

1. MIPS32 指令格式 (Instruction Formats)：MIPS 架構採用固定長度 32 位元（bits）的指令設計，主要分為三類欄位配置：
   • R-type (Register-type)：opcode (6 bits) | rs (5 bits) | rt (5 bits) | rd (5 bits) | shamt (5 bits) | funct (6 bits)。
   • I-type (Immediate-type)：opcode (6 bits) | rs (5 bits) | rt (5 bits) | immediate/address (16 bits)。
   • J-type (Jump-type)：opcode (6 bits) | target address (26 bits)。
2. 位址計算與定址模式 (Addressing Modes)：
   • 偽直接定址 (Pseudo-Direct Addressing)：J-type 的跳躍目標位址為 $\text{PC}_{31..28} \mathbin{\Vert} (\text{address} \ll 2)$，與暫存器（如堆疊指標 $sp）無關。
3. 位移運算邏輯 (Shift Operations)：
   • 左移 (Shift Left)：邏輯左移（LSL）與算術左移（ASL）在底層二進位操作上完全相同，皆由低位元（LSB）補 $0$。
   • 右移 (Shift Right)：邏輯右移（SRL）由高位元（MSB）補 $0$；算術右移（SRA）由高位元補符號位元（Sign bit）。

---

解題方法

本題考驗對 MIPS32 指令集架構（ISA）編碼格式、定址機制與算術邏輯單元（ALU）運算設計的理解：

1. 分析 I-type 指令欄位配置：計算其包含的暫存器編號欄位數量上限。
2. 剖析 J-type 指令目標位址形成機制：驗證跳躍目標位址是否依賴 Stack Pointer ($sp)。
3. 辨別 jr 指令之編碼類型：區分指令的「控制流程功能」與「二進位機器碼格式」。
4. 檢驗位移運算的邏輯異同：確認算術左移與邏輯左移在二進位補位上的差異性與指令集的必要性。

---

選項分析

• (A) 正確：
  MIPS I-type 指令格式由 opcode (6 bits)、rs (5 bits)、rt (5 bits) 與 immediate/address (16 bits) 組成，總長度為 32 位元。

核心觀念

本題考驗計算機組織中三種核心 CPU 架構（單週期 Single-Cycle、多週期 Multi-Cycle、流水線 Pipeline）的設計原理與效能比較，涵蓋以下關鍵觀念與公式：

1. 回應時間（Response Time / Latency）與吞吐量（Throughput）：
   • 流水線（Pipelining）技術提升的是吞吐量（單位時間內完成的指令數），而非單一指令的回應時間（執行完成該指令所需的時間）。
2. 流水線執行時間公式：
   • 若流水線包含 $k$ 個階段（stages），每個階段週期時間為 $\tau$，執行 $N$ 個無冒險（no hazards/bubbles）的指令所需總時間 $T$ 為：
     $T = [k + (N - 1)] \times \tau$
3. 每指令週期數（CPI, Cycles Per Instruction）與時脈週期時間（Clock Cycle Time, $\tau$）：
   • 單週期 CPU：每個指令均固定在 1 個長週期內完成，$\text{CPI} = 1$。
   • 多週期 CPU：將指令拆分為多個短週期完成，不同指令需要的週期數不同，$\text{CPI} > 1$（通常介於 3～5 之間）。多週期優於單週期的原因在於大幅縮減了時脈週期時間 $\tau$，而非降低 CPI。
4. 流水線深度與冒險（Hazards）：
   • 階段數 $k$ 越深（Deep Pipelining），指令間的資料相關性跨越的階段數越長，分支預測失敗的懲罰（Branch Penalty）也越大，因此效能更容易受到冒險（Hazards）的影響。

---

解題方法

透過計算機效能公式與架構特性逐項推導：

• 時間與吞吐量推導：對 Option B 套用流水線填滿（Fill phase）與穩定產出（Steady phase）的時間總和公式進行精確算術推導。
• CPU 效能公式評估：利用 CPU Time 公式 $\text{CPU Time} = N \times \text{CPI} \times \tau$ 分析單週期與多週期 CPU 的效能差異成因。
• 冒險效應分析：分析加深流水線對資料冒險（Data Hazards）與控制冒險（Control Hazards）所產生的停頓週期（Stall Cycles）影響。

---

選項分析

• A. 錯誤。
  流水線結構無法降低單一指令的回應時間（Response Time / Latency）。相反地，因為各階段延遲需對齊最慢的階段，再加上流水線暫存器（Pipeline Registers）的額外架構開銷（Overhead），單一指令從開始到結束的時間通常會微幅增加或持平。流水線的主要優勢在於重疊執行多個指令，藉此提升整體系統的吞吐量（Throughput）。

核心觀念

本題考查計算機組織與結構中 RISC（Reduced Instruction Set Computer，精簡指令集計算機） 與 CISC（Complex Instruction Set Computer，複雜指令集計算機） 的架構特性差異與效能公式。

根據 CPU 執行時間（CPU Execution Time）公式：
$\text{CPU Execution Time} = \text{IC} \times \text{CPI} \times \text{Clock Cycle Time}$

其中：

• $\text{IC}$（Instruction Count）：執行程式所需要的指令總數。
• $\text{CPI}$（Clock Cycles Per Instruction）：平均每條指令所需的時脈週期數。
• $\text{Clock Cycle Time}$：單一週期時間（即時脈頻率 Clock Rate 的倒數）。

RISC 與 CISC 的設計哲學與架構對比：

1. RISC (精簡指令集)：
   • 指令集特性：指令數量少且功能簡單、僅提供基礎定址模式、採用 Load/Store 架構（僅有 Load 與 Store 能夠存取記憶體）。
   • 指令格式：固定長度（Fixed-length，例如 32-bit）、格式統一（Uniform），使硬體解碼電路極為簡單。
   • 執行效率：設計目標為使絕大多數指令能在單一時脈週期內完成（$\text{CPI} \approx 1$），且因控制邏輯簡單，可採用較高的時脈頻率（較短的 $\text{Clock Cycle Time}$）。
2. CISC (複雜指令集)：
   • 指令集特性：指令數量龐大且功能複雜（單一指令可完成高階語言較複雜的操作）、支援多種定址模式、允許算術指令直接操作記憶體運算元。
   • 指令格式：變長指令格式（Variable-length），解碼器與控制單元極為複雜（常需搭配微程式 Microcode 控碼）。
   • 執行效率：程式所需的總指令數 $\text{IC}$ 較少，但單一指令需要較多時脈週期（$\text{CPI} > 1$），且複雜的控制邏輯限制了時脈頻率的提升。

---

解題方法

針對題目關於 RISC 與 CISC 之描述，依據兩者的設計哲學、硬體實現複雜度、指令格式規範以及現代發展趨勢進行逐項判斷：

1. 比較單一指令的執行時間（$\text{CPI} \times \text{Clock Cycle Time}$）。
2. 檢查指令格式（Instruction Format）是否為固定長度與統一規範。
3. 評估 RISC 於現代計算機體系結構（如 ARM、RISC-V、Apple Silicon 及內部微操作譯碼系統）的應用現況。
4. 比對兩者指令集複雜度（Instruction Set Complexity）的定義。

---

選項分析

• A. 正確。
  RISC 的設計核心在於簡化指令邏輯與控制電路，使處理器得以運作於更高的時脈頻率（較短的

核心觀念

本題旨在考驗計算機組織中「主記憶體與儲存階層」（Memory and Storage Hierarchy）的核心觀念，重點在於區分 RAM（隨機存取記憶體） 與 ROM（唯讀記憶體） 的兩大物理特性：

1. 存取機制與權限（Access Mechanism & Permissions）：讀取（Read）與寫入（Write）操作的能力與限制。
2. 資料保存特性（Data Retention & Volatility）：揮發性（Volatility）與持久性（Persistence / Non-volatility）。

---

解題方法

從計算機硬體定義與記憶體物理特性切入比對：

1. RAM (Random Access Memory)

   • 讀寫特性：支援 CPU 對任意位址進行隨機讀取 (Read) 與隨機寫入 (Write)，存取時間均為 $O(1)$ 常數時間。
   • 電源特性：屬於揮發性記憶體（Volatile Memory），斷電後儲存的電荷或狀態即刻消失，無法作為持久性儲存（Persistent Storage）。

2. ROM (Read-Only Memory)

   • 讀寫特性：學理與硬體標準定義為唯讀記憶體。在 CPU 正常運作的指令週期中，僅支援讀取 (Read) 操作，無法透過一般記憶體寫入指令直接寫入。
   • 電源特性：屬於非揮發性記憶體（Non-volatile Memory），電源切斷後資料仍能長久保留，適合持久保存系統關鍵程式（如 BIOS/UEFI 韌體或 Bootloader）。

綜合上述特性，審視各選項之正確性。

---

選項分析

• A. RAM can be randomly read and written.（正確）
  RAM（隨機存取記憶體）名稱中的 "Random Access" 表示存取任意記憶體位址的時間皆相同，且硬體架構同時支援隨機讀取（Random Read）與隨機寫入（Random Write）兩項基本操作。

核心觀念

本題考查快取記憶體（Cache）架構設計的核心概念與效能指標，主要涵蓋以下觀念：

1. 多階層快取包含政策（Cache Inclusion Policy）：
   • 包含式快取（Inclusive Cache）：頂層快取（靠近 CPU 端，如 L1 快取）的所有資料內容必須同時存在於底層快取（如 L2 快取）中，即滿足 $L_1 \subseteq L_2$ 的子集關係。
   • 互斥式快取（Exclusive Cache）：同一筆資料只會存在於某一層快取中，即 $L_1 \cap L_2 = \emptyset$。
   • 非包含非互斥快取（Non-inclusive Non-exclusive, NINE Cache）：資料可能同時存在或各自獨立存在於不同階層。
2. 快取存取時間與容量之權衡（Trade-off）：
   • 第一階快取（L1 Cache）追求極短的命中時間（Hit Time），以匹配 CPU 高頻時脈。記憶體解碼與訊號傳播延遲隨容量增大而增加，因此 L1 快取的容量通常設計得較小。
3. 平均記憶體存取時間（Average Memory Access Time, AMAT）公式：
   $\text{AMAT} = \text{Hit Time}_{L1} + \text{Miss Rate}_{L1} \times \text{Miss Penalty}_{L1}$
   在多階層快取系統中，$\text{Miss Penalty}_{L1}$ 包含存取 L2 快取的時間（$\text{Hit Time}_{L2}$）以及可能的 L2 缺失懲罰。降低缺失懲罰（Miss Penalty）能有效減少整體 AMAT。
4. 快取關聯性（Associativity）與命中率（Hit Rate）：
   • 全關聯式快取（Fully-Associative Cache）：資料區塊可放置於快取中任一位置，無衝突缺失（Conflict Miss），因此在相同容量與區塊大小下，其命中率通常高於其他映射方式。
   • 直接映射式快取（Direct-Mapped Cache）：資料區塊僅能放置於固定位置，容易產生衝突缺失，命中率通常較低。

---

解題方法

針對題目中快取設計的各項敘述，逐一比對快取組織與效能理論：

1. 對比包含政策的定義：檢驗 Inclusive Cache 是否滿足 $L_1 \subseteq L_2$。
2. 分析 L1 快取的設計考量：驗證 Hit Time 與 Cache Size 的關係。
3. 套用 AMAT 公式進行變數分析：分析降低 Miss Penalty 對整體存取時間的影響。
4. 比較關聯性對 Hit Rate 的影響：分析 Fully-Associative 與 Direct-Mapped 在衝突缺失上的差異。

---

選項分析

核心觀念

本題考驗計算機結構中快取缺失的分類（Types of Cache Misses）以及快取結構特性對快取缺失的影響。

快取缺失主要可分為以下幾類（常稱為 3C 或 4C 效應）：

1. 強制性缺失（Compulsory Miss / Cold-Start Miss）：資料區塊第一次被存取時，因為過去未曾進入快取所產生的缺失。
2. 容量缺失（Capacity Miss）：當程式執行期間所需的資料集（Working Set）大於快取總容量，導致快取無法容納所有資料而發生的缺失。即便使用全相聯快取（Fully Associative Cache），此缺失依然存在。
3. 衝突缺失（Conflict Miss / Collision Miss）：多個資料區塊被對映到快取中相同的組（Set）或位置，當該組空間填滿後，新資料剔除舊資料所產生的缺失。僅發生在直接對映（Direct-Mapped）與組相聯（Set-Associative）快取中。
4. 一致性缺失（Coherence Miss）：在多處理器（Multiprocessor）環境中，因其他處理器更新記憶體資料導致本地快取的快取行（Cache Line）失效（Invalidate）所發生的缺失。

---

解題方法

解題切入點為將題目各選項敘述與上述快取缺失的嚴格定義及快取相聯度（Associativity）進行比對：

1. 預取機制與 Compulsory Miss：預取（Prefetching）會在 CPU 實際提出讀寫請求前，提前將未來的資料讀入快取，因此能將原本 demand access 時產生的首次存取缺失（Compulsory Miss）消除。
2. First-time Access 與 Miss 類型：第一次存取某區塊造成的 Miss 定義上為 Compulsory Miss，而非 Conflict Miss。
3. External Processor Update 與 Miss 類型：其他處理器更新資料造成的 Miss 定義上為 Coherence Miss，而非 Capacity Miss。
4. 相聯度與 Conflict Miss 的關係：在快取總容量與 Block 大小相同的前提下，相聯度 $n$ 越大（組內放置區塊的位置越多），發生衝突的機率越低。因此直接對映快取（$n=1$）的衝突缺失高於 $n>1$ 的 $n$ 路組相聯快取（$n$-way Set-Associative Cache）。

---

選項分析

核心觀念

1. 平均記憶體存取時間 (Average Memory Access Time, AMAT)：
   AMAT 是衡量快取 (Cache) 記憶體系統效能的核心指標，標準計算公式為：
   $\text{AMAT} = \text{Hit Time} + \text{Miss Rate} \times \text{Miss Penalty}$
   當記憶體操作區分讀取 (Read) 與寫入 (Write) 時，總 AMAT 為兩者存取時間之加權平均：
   $\text{AMAT} = f_{\text{read}} \times \text{AMAT}_{\text{read}} + f_{\text{write}} \times \text{AMAT}_{\text{write}}$
   其中 $f_{\text{read}}$ 與 $f_{\text{write}}$ 分別為讀取與寫入請求所佔的比例。

2. 直寫策略 (Write-Through Protocol)：
   在 Write-Through 策略下，每一次寫入操作都必須同步更新主記憶體 (Main Memory)。因此，不論寫入是否命中 Cache，寫入操作均需花費主記憶體的存取時間 $M$。

---

解題方法

1. 整理題目已知條件

• L1 快取 (Cache) 存取時間 $= C\text{ ns}$
• 主記憶體 (Main Memory / L2) 存取時間 $= M\text{ ns}$
• 請求比例：
  • 讀取比例 $f_{\text{read}} = 60\% = 0.6$
  • 寫入比例 $f_{\text{write}} = 100\% - 60\% = 40\% = 0.4$
• 命中率 (Hit Ratio)：
  • 讀取命中率 $= H$ $\implies$ 讀取未命中率 (Miss Rate) $= 1 - H$
  • 寫入命中率 $= 1$

2. 推導讀取操作的平均存取時間 ($\text{AMAT}_{\text{read}}$)

讀取時必先存取 Cache（耗時 $C$）；若未命中（機率為 $1 - H$），則需額外存取主記憶體（懲罰時間為 $M$）：
$\text{AMAT}_{\text{read}} = C + (1 - H) M$

3. 推導寫入操作的平均存取時間 ($\text{AMAT}_{\text{write}}$)

在 Write-Through 策略下，寫入資料必然會寫入主記憶體。檢查 Cache 並同步寫入主記憶體的總時間為：
$\text{AMAT}_{\text{write}} = C + M$

4. 計算總體平均存取時間 ($\text{AMAT}$)

將讀取與寫入依比例加權求和：

核心觀念

本題考驗計算機結構中的**阿姆達爾定律（Amdahl's Law）**與整體效能加速比（Speedup）的計算。

阿姆達爾定律用於評估對系統中特定元件或指令進行局部效能改善後，整體系統所能獲得的效能提升倍數。其標準公式如下：

$S_{\text{overall}} = \frac{1}{(1 - F) + \frac{F}{S_{\text{enhanced}}}}$

其中：

• $F$：可受改善部分占總執行時間的比例（Fraction enhanced）。
• $S_{\text{enhanced}}$：該可改善部分的局部加速比（Speedup of enhanced part）。
• $1 - F$：未受改善（不可改善）部分占總執行時間的比例。

---

解題方法

步驟一：確定各部指令占總執行時間的比例

設舊處理器 $C_1$ 執行該應用程式的總執行時間為 $T_{\text{old}} = 1$。

1. 浮點數（FP）指令：占總執行時間的 60%，即：
   $F_{\text{FP}} = 0.60$
2. 開平方根（Square Root）運算：占浮點數時間的 25%，故占總執行時間的比例為：
   $F_{\text{Sqrt}} = F_{\text{FP}} \times 25\% = 0.60 \times 0.25 = 0.15$

---

步驟二：計算方案一（提升 FP 指令效能 1.5 倍）的整體加速比

若將 FP 指令效能提升至 1.5 倍（即 $S_{\text{FP}} = 1.5$）：
代入阿姆達爾定律計算整體加速比 $S_{\text{overall, FP}}$：

$S_{\text{overall, FP}} = \frac{1}{(1 - 0.60) + \frac{0.60}{1.5}} = \frac{1}{0.40 + 0.40} = \frac{1}{0.80} = 1.25$

---

步驟三：計算方案二（提升開平方根運算效能 8 倍）的整體加速比

若將開平方根運算效能提升至 8 倍（即 $S_{\text{Sqrt}} = 8$）：
代入阿姆達爾定律計算整體加速比 $S_{\text{overall, Sqrt}}$：

$S_{\text{overall, Sqrt}} = \frac{1}{(1 - 0.15) + \frac{0.15}{8}} = \frac{1}{0.85 + 0.01875} = \frac{1}{0.86875} = \frac{160}{139} \approx 1.15108$

---

核心觀念

本題綜合考驗作業系統（Operating System）四大核心模組的基礎理論：

1. 死鎖處理策略（Deadlock Handling Strategies）：區分死鎖避免（Deadlock Avoidance）與死鎖偵測（Deadlock Detection）在機制與執行時機上的本質差異。
2. 記憶體保護機制與頁表（Memory Protection & Page Table）：使用者模式（User Mode）與核心模式（Kernel Mode）的權限劃分，以及頁表項（Page Table Entry, PTE）的保護位元與存取限制。
3. CPU 調度演算法（CPU Scheduling Algorithms）：最短剩餘時間優先（Shortest Remaining Time First, SRTF）演算法的理論特性、實務不可可行性（Implementability）與其副作用。
4. 行程建立機制（Process Creation）：UNIX/Linux 系統中 fork() 系統呼叫運作時，行程識別碼（Process ID, PID）的配置規則與繼承範圍。

---

解題方法

解題時應從作業系統的設計原則與硬體保護機制切入分析：

1. 死鎖防護邏輯：死鎖避免（如 Banker's Algorithm）著重於資源分配當下的動態檢查，確保系統恆維持於安全狀態（Safe State）；死鎖偵測則是允許死鎖發生後再排查並進行復原（Recovery）。兩者屬於不同的死鎖處理層級。
2. 特權存取原則：頁表為控制虛擬記憶體至實體記憶體映射的關鍵資料結構。若允許 User-level Process 直接修改本身的 PTE，行程將能隨意繞過記憶體保護機制，存取其他行程或核心區域。因此，修改 PTE 必須為受保護的特權指令，僅能於 Kernel Mode 下執行。
3. 調度最佳化與實現限制：SRTF 雖可證明能達成最小平均等待時間（Minimum Average Waiting Time），但需要預知行程未來的 CPU Burst Time，實務上無法精確實現，且容易導致長行程發生飢餓現象（Starvation）。
4. PID 全域唯一性：行程建立時，系統必須為每一個行程分配全域唯一的 PID 以供識別與管理。fork() 複製的是父行程的位址空間與狀態，而非 PID 本身。

---

選項分析

• (A) 錯誤
  死鎖避免（Deadlock Avoidance）與死鎖偵測（Deadlock Detection）為兩種獨立的死鎖處理策略：
  • 死鎖避免（Avoidance）：在動態資源分配時，要求行程預先宣告最大資源需求量，系統利用演算法（如銀行家演算法 Banker's Algorithm）確認分配後系統仍處於「安全狀態（Safe State）」才批准分配，從而預先防止死鎖發生。
  • 死鎖偵測（Detection）：系統允許死鎖發生，並定期執行偵測演算法（如資源分配圖 Resource-Allocation Graph 或等待圖 Wait-For Graph）找出死鎖行程，再透過終止行程或剝奪資源進行復原（Recovery）。
    因此，「死鎖偵測」僅能在死鎖發生後進行事後補救，無法達到「避免死鎖發生」的效果。

核心觀念

• Pipe（管道）是 UNIX 系統提供的 半雙工（unidirectional）或 全雙工（bidirectional）通信機制。
• ordinary pipe（匿名管道）由 pipe() 系統呼叫建立，只能在 同一個父子或兄弟程序 之間傳遞 byte‑stream。
• named pipe（FIFO）是以檔名存在於檔案系統中的特殊檔案，允許 不相關程序 打開同一個 FIFO 進行讀寫，仍然是 單向。若要雙向通訊，必須各建立一條 FIFO（或使用 socket、socketpair）。
• 傳輸資料類型：Pipe 本質上是 byte‑oriented（位元組流），不區分文字或二進位，使用者自行決定資料編碼方式。

---

解題方法

1. 先辨識每個選項所描述的概念是否符合 UNIX pipe 的 方向性 與 資料型別。
2. 針對 pipe() 系統呼叫的功能與返回值檢視：int pipe(int fd[2]); 產生兩個檔案描述符 fd[0]（讀端）、fd[1]（寫端），只能 單向 讀寫。
3. 判斷「雙向」需求時的常見作法：
   • 兩條 pipe（或兩條 FIFO）各負責一個方向；
   • 使用 socketpair() 直接提供全雙工 byte 流。
4. 檢驗選項是否提及「可靠」或「同主機」等不屬於 pipe 本身的特性。

---

選項分析

選項	內容	正誤判斷與說明
A	Ordinary pipes are unidirectional, allowing only one-way communication.	正確。匿名管道 (pipe()) 產生的兩個檔案描述符分別為 讀端 與 寫端，只能單向傳遞資料。若要雙向，必須再建立另一條 pipe。

核心觀念
本題考查的是「網路技術」領域的基礎概念與當前趨勢，重點在於：

1. Web 3.0 的定位與目標。
2. Software‑Defined Networking (SDN) 的架構特性。
3. Domain Name System (DNS) 的設計原理（分散、階層式資料庫）。
4. Internet Engineering Task Force (IETF) 的角色與標準制定流程。

了解這四個概念即可判斷各選項的正誤。

---

解題方法
逐條比對選項敘述與正式定義或目前的業界事實：

• 若敘述與官方或學術文獻中描述一致，則為正確。
• 若敘述與實際架構或組織屬性相左，則為錯誤。

本題為多選題，必須對 每一個選項 皆做判斷。

---

選項分析

選項	判斷	理由說明
A. The goal of Web 3.0 is to enable a more decentralized internet.	正確	Web 3.0（亦稱「分散式網路」）的核心願景是將資料、身份認證與服務從中心化平台移向區塊鏈、去中心化存儲（如IPFS）以及 P2P 協議，以降低單點失效與中心化壟斷的風險。學術與產業文件（如 W3C、以太坊白皮書）皆明確指出「去中心化」是 Web 3.0 的主要目標。
B. The architecture of software‑defined networking is decentralized.	錯誤	SDN 的核心概念是將 控制平面（Control Plane） 從 資料平面（Data Plane） 中抽離，並集中於一個或少數幾個 控制器（Controller）。控制器負責全局視圖與路由決策，資料平面則僅執行轉發。此集中式控制模型與「去中心化」相對，故敘述不符。

核心觀念

• 行程（process）狀態圖：常見的狀態包括 new、ready、running、waiting（或 blocked）與 terminated。
  • Ready → Waiting：通常只有在 running 狀態下因 I/O、同步或其他事件被阻塞才會轉入 waiting。
• 頁表（page table）中的參考位（Reference / Accessed bit）：硬體在每次存取該頁時自動設為 1，用以支援 LRU、Clock 等置換演算法。
• 模式位（Mode bit）：CPU 狀態暫存器（如 x86 的 CS、CPSR）中用於區分 kernel mode（特權模式）與 user mode（受限模式），因此能判斷「目前指令正在哪一個模式」執行。
• 有效位（Valid‑Invalid bit）與髒位（Dirty bit）：
  • Valid = 1：此頁已在實體記憶體中，可直接存取。
  • Valid = 0：此頁不在實體記憶體，需要從磁碟載入。
  • Dirty = 1：此頁自載入以來被寫過，置換出時必須寫回磁碟；若 Dirty = 0，則可直接丟棄。

---

解題方法

1. 先釐清題目各選項所涉及的概念（行程狀態、硬體控制位元、CPU 模式位元、頁表置換條件）。
2. 依照操作系統教材與實作規範逐一驗證每個敘述是否符合標準定義。
3. 把每個選項與正確概念對照，判斷「正確」或「錯誤」。

---

選項分析

核心觀念

• Copy‑on‑Write (COW)：在 fork 後，父子行程的虛擬記憶頁表先指向相同的實體頁框，且皆設為唯讀。當任何一方第一次寫入時，硬體偵測到寫入例外，作業系統立即為該頁建立新副本，然後讓寫入者指向新頁。
• 具名管道 (named pipe / FIFO)：以檔案系統中的特殊檔案實作的單向或雙向通道，任何具存取權限的行程皆可開啟，並不限定必須是父子關係。
• IPSec：Internet Protocol Security，提供 Authentication Header (AH) 與 Encapsulating Security Payload (ESP) 兩種保護機制，可在 IP 層加密與驗證，常作為 VPN（Virtual Private Network）之底層協定。
• 競爭條件 (race condition)：多執行緒或多行程同時存取共享資源且缺乏同步機制所導致的錯誤。
• 銀行家演算法 (Banker’s algorithm)：用於 死結避免（deadlock avoidance），透過安全性檢查在分配資源前判斷系統是否仍處於安全狀態，與競爭條件的解決無關。

---

解題方法

1. 逐一對照選項文字與上述核心概念。
2. 判斷陳述是否符合概念的正式定義或常見用途。
3. 若概念不相符或屬於其他領域（例如死結 vs. 競爭條件），即判為錯誤。

---

選項分析

核心觀念

• 即時系統（Real‑Time System）：系統必須在限定時間內完成特定工作。
• 硬即時（Hard Real‑Time）：若任何一次截止期限（deadline）被錯過，會導致災難性後果（例如人命危險、設備毀損）。
• 軟即時（Soft Real‑Time）：偶爾錯過截止期限只能造成效能下降或使用者體驗變差，不會造成嚴重損害。
• 判斷依據：錯過期限的後果、系統安全性與可靠性需求。

解題方法

1. 針對每個選項，評估若期限錯過會產生的影響。
2. 若錯過會導致安全危險、設備毀損或法律責任，則屬於硬即時需求。
3. 若錯過僅影響效能、舒適度或服務品質，則屬於軟即時或非即時。

選項分析

選項	系統說明	截止期限錯過的後果	是否屬於硬即時
A. Thermostat in a household	家用恆溫器負責調節室內溫度。	溫度波動會稍微影響舒適度，但不會造成安全或設備損壞。	❌（屬於軟即時或非即時）
B. Control system for a nuclear power plant	核電廠控制系統負責監控反應爐、緊急停機等關鍵參數。

核心觀念

• 排程演算法 (Scheduling algorithm)：作業系統依據某種規則決定哪一個等待中的程序（process）可以取得 CPU。
• 飢餓 (Starvation)：某些程序長時間無法取得資源，因為排程規則總是把資源讓給其他程序。
• 常見的飢餓產生機制：
  • 優先權排程：低優先權的程序可能被高優先權程序不斷剝奪 CPU。
  • 短作業優先 (SJF)：長作業若持續有更短的作業進入，就可能被無限延遲。

解題方法

1. 逐一檢視每個選項的排程策略，判斷該策略是否會因「資源分配不均」而使部分程序永遠得不到 CPU。
2. 若演算法本身具備 公平性 (fairness) 保證，如 FCFS、RR、WFQ，則不會產生飢餓。
3. 若演算法依賴 優先權或作業長度，且未設計防止飢餓的機制（如老化、時間片遞增），則可能導致飢餓。

選項分析

選項	演算法說明	是否會產生飢餓	理由
A. First‑come, first‑served (FCFS)	依到達順序排隊，先到先服務。	❌ 不會	所有程序都按到達時間一次獲得 CPU，沒有偏好或排除機制，必然在其排隊序列中被服務。

核心觀念

• Counting semaphore：在作業系統中屬於 同步原語（synchronisation primitive），其抽象資料型別為 一個非負整數，同時伴隨 兩個原子操作
  • P（wait）：若 semaphore 值 > 0，則減 1；否則阻塞呼叫執行緒。
  • V（signal）：將 semaphore 值加 1，若有等待的執行緒則喚醒其中一個。
• 原子性（atomicity）保證每一次 P 或 V 的執行 不可被其他執行緒在中途中斷，因此在硬體層面上通常以 禁止中斷 (disable interrupts) 或使用硬體鎖 來實作。
• Semaphore 可用來 計數可用資源（例如緩衝區空格、可同時使用的裝置數量）或 實作二元互斥（值只能是 0/1 時即為 mutex）。

---

解題方法
依題目列出的五個敘述，逐一比對上述定義與實作特性，判斷其正確性。

• 若敘述符合 「整數變數」的概念但缺少「只能透過兩個原子操作」的限制，需評估「essentially」是否容許此簡化。
• 若敘述涉及 同時修改、單一操作、無法保護臨界區，則直接與 semaphore 的原子性與用途相矛盾，判為錯誤。
• 原子執行（單一、不可中斷）為 semaphore 最重要的特性，應直接視為正確。

---

選項分析

選項	判斷	理由
A. is essentially an integer variable	正確	Counting semaphore 的核心是 非負整數，其值代表可用資源數量。題目使用 essentially（本質上）暗示只談抽象概念，未要求必需描述其操作限制，因而與教材中的定義「整數變數」相符。

核心觀念

• Many‑to‑many threading model：使用者層（user‑level）執行緒由程式自行排程到較少的核心層（kernel‑level）執行緒；核心層執行緒再被 OS 排入實體 CPU。
• 執行緒與 CPU 的映射：
  • N < P（核心執行緒＜處理器）→ 無法同時利用全部處理器，會產生 under‑utilisation。
  • N = P→ 理想情況，可讓每個核心執行緒佔一顆 CPU，減少排程與切換開銷。
  • N > P→ oversubscription，必須在核心執行緒之間切換，產生大量 kernel‑level context switch。
• 使用者層執行緒數 M > P：若 M 大於處理器數，必須依賴核心執行緒來提供平行度；核心執行緒不足或過多都會影響效能。
• 效能下界（lower performance implication）：指在最差情況下因資源配置不當而造成的效能損失，包括 CPU 空閒、快取失效、系統呼叫開銷、同步瓶頸等。

---

解題方法

1. 先比較「核心執行緒數 N」與「實體處理器數 P」的關係，判斷是否會產生 under‑utilisation 或 oversubscription。
2. 再觀察 N 與 使用者層執行緒數 M 的關係，判斷 M:N 映射的額外開銷：
   • N << M：大量使用者層執行緒必須共享少數核心執行緒，會產生 user‑level scheduling contention（使用者層排程衝突）與 kernel‑level context switch。
   • N ≈ M：映射較為平衡，額外開銷較小。
   • N >> M：雖然可避免使用者層排程衝突，但會產生 不必要的 kernel threads，導致 kernel‑level context switch 增加且浪費系統資源。
3. 結合上述兩點，針對每個選項列出其 最低效能（最差情況）所可能出現的瓶頸。

---

選項分析

A. Kernel threads < processors

• CPU 利用率：因核心執行緒少於 CPU，最多只能同時執行 N 個執行緒，剩餘 P‑N 顆 CPU 必定閒置。
• 快取與記憶體效能：閒置 CPU 仍會佔用快取線，降低全系統快取命中率。
• 下界效能：$\displaystyle \text{Performance}_{\min} \approx \frac{N}{P}\times \text{理想效能}$。若 N = 1 而 P = 8，最差只會得到 12.5% 的理想吞吐量。
• 結論：嚴重的 under‑utilisation，是最差情況之一。

---

B. Kernel threads = processors

• CPU 利用率：理想上每顆 CPU 可被分配一個核心執行緒，沒有明顯的 idle CPU。
• 映射到使用者層：若 M > P，仍需在 N (=P) 個 kernel threads 上排程 M 個 user threads，會產生 user‑level 排程競爭，但相較於 A、C 的 N < P，CPU 空閒已被最小化。
• 下界效能：受限於 user‑level 排程開銷（如 mutex、condition variable 的 kernel 呼叫），但不會因 CPU 空閒而降低。
• 結論：效能下界主要是 user‑level 排程與同步開銷，而非 CPU 資源不足。

---

C. Kernel threads > processors 且 < user‑level threads (P < N < M)

• CPU 利用率：已達到或超過 P，因此 CPU 能被充分利用。

核心觀念
本題探討在**硬體不提供特權模式（privileged mode）**的情況下，作業系統如何仍能「全程掌控」使用者程式的執行。

• 特權模式：CPU 在硬體層面提供兩種或以上執行等級，特權等級允許執行敏感指令（如 I/O、記憶體保護）而使用者等級則受限。
• 缺乏特權模式的後果：任何程式都能直接執行所有指令，無法靠硬體防止惡意或錯誤的資源存取；作業系統必須以純軟體機制來實現隔離與保護。
• 安全作業系統的必要條件：在每一次指令或系統呼叫執行前，都必須由受信任的控制層（例如解釋器、監控程式）先行檢查，確保不會違背安全策略。

---

解題方法
判斷每個選項是否能提供**「軟體層面持續控制」**的機制：

1. 必須能攔截、檢查、或限制使用者程式的所有行為。
2. 只要該方法本身不依賴硬體特權機制，且能在執行時保持 OS 的控制權，即視為可行。
3. 逐一分析選項，檢視其是否滿足上述條件。

---

選項分析

選項	內容說明	為何符合/不符合「全程控制」
A. software interpretation of all user programs	OS 以解譯器/虛擬機（例如 Java VM、WebAssembly runtime）執行所有使用者程式，所有指令在解譯階段先由 OS 檢查。	✅符合。解譯器本身在受信任的 OS 空間執行，能在每條指令或系統呼叫前加入安全檢查，避免未授權的記憶體或 I/O 存取。即使硬體沒有特權模式，控制權仍由軟體（解譯器）維持。
B. co‑execution with co‑processor to execute all programs	需要另一顆協處理器來代替 CPU 執行使用者程式。若協處理器本身不具備硬體特權保護，仍無法保證 OS 的控制；