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

核心觀念

本題考查計算機系統中作業系統（Operating System, OS）、**編譯器（Compiler）與CPU硬體／微架構（Hardware / Microarchitecture）**之間的權責分工與效能優化層級。

在計算機系統分層架構中：

1. 作業系統 (OS)：運作於系統層級（System Level），負責行程／執行緒排程（Process/Thread Scheduling）、虛擬記憶體與頁表管理（Virtual Memory & Page Table Management）、系統呼叫處理、以及檔案與磁碟 I/O 排程（Disk I/O Scheduling）。
2. 編譯器 (Compiler)：運作於軟體轉譯階段，負責高階程式碼的優化與靜態指令排程（Static Instruction Scheduling）。
3. CPU 微架構與記憶體硬體 (Microarchitecture & Memory Hardware)：運作於硬體執行層級，負責動態亂序執行（Dynamic Out-of-Order Execution）、指令層級平行（ILP）、寫入緩衝區（Store/Write Buffer）管理以及記憶體控制器（Memory Controller）對 DRAM 的存取重排。

解題方法

題目明確詢問何者為「作業系統（OS）」提升效能的技術。解題切入點在於區分各項優化技術的執行主體是 OS、編譯器還是硬體：

1. 分析選項 (a)：改變機器指令的執行順序（Instruction Reordering）屬於指令層級優化，主導者為編譯器（靜態分析）與 CPU 執行單元（動態亂序執行），OS 無法介入單一程式內部的低階機器指令排列。
2. 分析選項 (b)：改變快取（Cache）與主記憶體（Main Memory）之間的 Load/Store 存取順序，主導者為 CPU 的記憶體管理硬體（如 Store Buffer、Memory Disambiguation Unit）與記憶體控制器（Memory Controller），屬於硬體記憶體一致性與匯流排優化，非 OS 管轄。

經由權責歸屬分析，(a) 與 (b) 均屬於編譯器或硬體層級的效能技術，非作業系統之技術。

選項分析

• (a) Switching execution order of machine instructions.（調整機器指令的執行順序）：【錯誤】
  • 技術歸屬：編譯器（Compiler）與 CPU 微架構（Hardware）。
  • 詳細說明：調整機器指令執行順序的主要目的是消弭指令暫存器相依性與流水線停頓（Pipeline Hazard/Stall），實現方式包含：
    • 靜態排程（Static Scheduling）：編譯器在編譯期重新排列機器指令。
    • 動態排程（Dynamic Scheduling）：CPU 硬體中的亂序執行單元（Out-of-Order Engine，例如 Tomasulo 演算法）在執行期根據保留站（Reservation Station）狀態與暫存器重命名（Register Renaming）動態重排指令。

核心觀念

本題考查計算機系統架構中作業系統（Operating System, OS）、**計算機結構／硬體（Computer Architecture / Hardware）與編譯器（Compiler）**三者的職責分工以及效能提升技術（Performance-Enhancement Techniques）。

計算機系統的不同層級各自掌管特定的效能優化機制：

1. 作業系統（OS）：負責系統資源的動態排程與管理，如 CPU 多核心負載平衡、虛擬記憶體頁面置換（Page Replacement）、I/O 排程等。
2. 硬體／計算機結構（Hardware / CA）：負責晶片級的硬體加速與快取機制，如快取行置換（Cache Line Replacement）、指令流水線（Instruction Pipelining）、分支預測（Branch Prediction）等。
3. 編譯器（Compiler）：負責程式碼在靜態編譯期的優化，如程序間分析（Inter-procedural Analysis）、函式內聯（Function Inlining）、暫存器配置（Register Allocation）等。

解題方法

本題的解題切入點在於精確判定各技術的「實施主體（Execution Layer）」：

• 作業系統層級：由 OS 核心（Kernel）的排程器或資源管理模組在執行期（Run-time）動態調配資源。
• 硬體層級：由 CPU 內部的數位電路（如 Cache Controller）在執行期自動完成，無需 OS 介入。
• 編譯器層級：由編譯器在編譯期（Compile-time）靜態分析程式碼結構並進行轉譯優化。

逐一評估三個選項的實施主體後，歸屬於作業系統者即為正確選項。

選項分析

• (a) Cache line replacement（快取行置換）：錯誤。
  快取行置換是指當 CPU 的 L1/L2/L3 硬體快取發生未命中（Cache Miss）且對應的快取組（Cache Set）已滿時，由**硬體快取控制器（Hardware Cache Controller）**依據置換演算法（如 LRU、FIFO、Random）決定要替換哪一個快取行。

核心觀念

本題考驗作業系統中**死鎖避免（Deadlock Avoidance）**的核心演算法——銀行家演算法（Banker's Algorithm）。

銀行家演算法透過維護以下四個主要資料結構，來判定系統在分配資源後是否仍處於安全狀態（Safe State）：

1. $Available[m]$：長度為 $m$ 的向量，代表目前系統中每種資源的剩餘可用數量。
2. $Max[n][m]$：$n \times m$ 的矩陣，定義每個程序對每種資源的最大需求總量。
3. $Allocation[n][m]$：$n \times m$ 的矩陣，定義目前已分配給每個程序的資源數量。
4. $Need[n][m]$：$n \times m$ 的矩陣，代表每個程序尚需多少資源才能完成執行，計算公式為：
   $Need[i][j] = Max[i][j] - Allocation[i][j]$

資源請求演算法（Resource-Request Algorithm）步驟：

當程序 $P_i$ 提出資源請求 $Request_i$ 時：

1. 若 $Request_i \le Need_i$，進入步驟 2；否則拋出錯誤（請求超出宣告的最大需求）。
2. 若 $Request_i \le Available$，進入步驟 3；否則 $P_i$ 必須等待（系統目前可用資源不足）。
3. 假定試探性分配資源給 $P_i$，並更新系統狀態：
   $Available' = Available - Request_i$
   $Allocation_i' = Allocation_i + Request_i$
   $Need_i' = Need_i - Request_i$
4. 針對更新後的狀態執行安全性演算法（Safety Algorithm）。若系統處於安全狀態（存在至少一組安全序列 Safe Sequence），則正式分配資源；若處於不安全狀態（Unsafe State），則取消試探性分配，令 $P_i$ 等待。

解題方法

步驟一：計算初始剩餘需求矩陣 $Need$

根據公式 $Need = Max - Allocation$，計算各程序的 $Need$ 向量：

• $Need_0 = (3, 2, 6, 0) - (1, 1, 1, 0) = (2, 1, 5, 0)$
• $Need_1 = (2, 2, 3, 2) - (0, 0, 1, 1) = (2, 2, 2, 1)$
• $Need_2 = (5, 3, 2, 3) - (2, 2, 2, 3) = (3, 1, 0, 0)$
• $Need_3 = (3, 3, 4, 3) - (3, 0, 3, 2) = (0, 3, 1, 1)$

初始系統狀態彙整表：

選項分析

(a) A request by P0 of (0,1,1,0), if granted, will make the system unsafe.

1. 合法性檢查：

   • $Request_0 = (0, 1, 1, 0) \le Need_0 = (2, 1, 5, 0)$ （合法）
   • $Request_0 = (0, 1, 1, 0) \le Available = (3, 2, 3, 3)$ （目前可用資源充足）

2. 試探性分配後的新狀態：

   • $Available' = (3, 2, 3, 3) - (0, 1, 1, 0) = (3, 1, 2, 3)$
   • $Allocation_0' = (1, 1, 1, 0) + (0, 1, 1, 0) = (1, 2, 2, 0)$
   • $Need_0' = (2, 1, 5, 0) - (0, 1, 1, 0) = (2, 0, 4, 0)$

3. 安全性演算法檢查：
   持現有 $Available' = (3, 1, 2, 3)$ 比對各程序需求：

   • $Need_0' = (2, 0, 4, 0)$：資源 C 需要 4，目前僅 2 $\Rightarrow$ 無法滿足。

本題核心概念

此題屬於 銀行家演算法（Banker’s algorithm）判斷系統安全性與死結的典型題目。

• 安全狀態：​存在至少一條 安全序列，使得所有程序在逐一取得剩餘資源後皆能完成。
• 不安全狀態：​無法找到此類序列，系統雖未立刻死結，卻有產生死結的風險。
• 死結：​若在不安全狀態下，某些程序已持有資源且其剩餘需求無法被滿足，則系統會卡在等待循環，形成死結。

判斷題目各敘述是否正確的步驟如下：

1. 利用目前的資源分配表（已分配、最大需求、可用向量）計算 需求矩陣 $Need = Max - Allocation$。
2. 假設請求已被批准，將請求向量從 可用向量 中扣除，並加入到相應程序的 已分配 中，同時更新 需求矩陣。
3. 用 安全性檢查：
   • 從可用向量開始，找出一個尚未完成且其需求 $\le$ 可用的程序；
   • 若找到，將其已分配資源釋放回可用向量，標記該程序已完成；
   • 重複以上步驟，直至所有程序完成（安全）或無法再找出符合條件的程序（不安全）。
4. 若安全檢查失敗，系統進入 不安全，此時即有可能導致 死結。

(a) 「P1 要求 $(0,1,1,0)$，若批准會使系統 不安全」

步驟

1. 假設目前的 可用向量 為 $Available$，而 $Request_{P1} = (0,1,1,0)$。
2. 若 $Request_{P1} \le Available$，則暫時更新：

3. 以 $Available'$ 為起點執行安全性檢查。若在任一迭代中 沒有 程序的 $Need \le Available'$，則判斷為 不安全。

核心觀念

本題考查計算機結構與作業系統中**多處理器架構（Multiprocessor Architecture）與記憶體架構（Memory Architecture）**的核心概念：

1. 非均勻記憶體存取（Non-Uniform Memory Access, NUMA）：

   • 定義：在多處理器（Multi-socket / Multi-node）系統中，主記憶體（DRAM）被實體分散連接至不同的處理器節點（Node）。處理器存取位於自己節點上的「本地記憶體（Local Memory）」延遲較低、頻寬較高；存取位於其他處理器節點上的「遠端記憶體（Remote Memory）」則需透過跨節點互連網路（Interconnect Network，如 Intel UPI/QPI 或 AMD Infinity Fabric），延遲較高且頻寬較低。這種存取主記憶體時間不一致的現象稱為 NUMA。
   • 成因：傳統對稱多處理器（Symmetric Multiprocessing, SMP）採用均勻記憶體存取（Uniform Memory Access, UMA），所有 CPU 共享單一中央記憶體匯流排。隨著處理器核心數大幅增加，共享匯流排遭遇嚴重頻寬瓶頸（Bus Bottleneck）。為了突破擴充性限制（Scalability），現代多處理器系統將記憶體控制器與實體記憶體分散至各處理器節點，進而產生 NUMA。

2. 記憶體／儲存階層（Memory / Storage Hierarchy）：

   • 定義：利用「區域性原理（Principle of Locality）」（時間區域性與空間區域性），將不同速度與容量的儲存介質依「暫存器 $\rightarrow$ L1/L2/L3 快取 $\rightarrow$ 主記憶體 $\rightarrow$ 輔助儲存器（SSD/HDD）」階層化配置，以兼顧存取速度與成本。
   • 與 NUMA 之關係：單處理器（Single-socket）系統同樣擁有現代儲存階層，但其主記憶體存取屬於 UMA。因此，儲存階層本身並非導致 NUMA 的原因。

3. 快取技術（Cache Technology）：

   • 定義：利用 SRAM 建立高速度、小容量的快取記憶體（Cache），用以彌補 CPU 運算速度與主記憶體存取速度之間的巨大鴻溝（Memory Wall）。
   • 與 NUMA 之關係：快取技術用於降低單一處理器內部的平均記憶體存取時間。在 NUMA 系統中，為了維持多個處理器快取資料的一致性，會結合快取一致性協定（Cache Coherence Protocol），形成 ccNUMA (Cache-Coherent NUMA)。但快取技術本身並非引發 NUMA 的硬體成因。

解題方法

判斷本題選項因果關聯時，應從 NUMA 的硬體層級與根本驅動因素（Root Cause） 切入：

1. 區分 UMA 與 NUMA 的本質差異：
   • NUMA 特指「**主記憶體（Main Memory / DRAM）**層級的存取時間不均勻性」，源自於「多處理器實體拓撲與分散式記憶體控制器配置」。

核心觀念

1. NUMA（Non-Uniform Memory Access，非均勻記憶體存取架構）：在多處理器（Multiprocessor）或多節點系統中，記憶體被實體分散連接至不同的處理器節點。處理器存取其「本地記憶體（Local Memory）」的延遲與頻寬，顯著優於經由晶片間互連網路（Interconnect Network）存取「遠端記憶體（Remote Memory）」。這種記憶體存取時間隨位址拓撲而異的硬體組織架構稱為 NUMA。
2. 馮紐曼電腦模型（von Neumann Computer Model）：傳統單處理器電腦模型，由運算單元（ALU）、控制單元（Control Unit）、記憶體（Memory）與輸入/輸出（I/O）組成。在該模型中，單一處理器透過單一系統匯流排存取共享記憶體，屬於均勻記憶體存取（UMA, Uniform Memory Access）的概念範疇。
3. 管線化技術（Pipelining）：單一處理器內部的指令級平行（Instruction-Level Parallelism, ILP）微架構技術，將指令執行拆分為多個重疊階段（如 IF, ID, EX, MEM, WB），目的在於提高處理器的指令吞吐量（Throughput）。
4. 編譯器最佳化（Compiler Optimization）：軟體層級的最佳化技術，在編譯時期對原始碼進行語法轉譯、指令重排、循環展開與暫存器分配，以提升機器碼執行效率。

解題方法

本題考察 NUMA 的本質定義及其在計算機系統層級（Level of Abstraction）中的定位。解題切入點為明確劃分計算機系統的結構層級：

• 硬體記憶體拓撲層級：NUMA 與 UMA 屬於多處理器實體記憶體組織與晶片互連拓撲。
• 微架構處理器內部層級：Pipeline 屬於單一 CPU 內部的指令執行平行化技術。
• 軟體/編譯器層級：Compiler Optimization 屬於高階語言轉換至機器碼的軟體優化機制。

經由正確分類與對應，即可精準評估各選項之正確性。

選項分析

• (a) It is intrinsic in von Neumann's computer model.（錯誤）

核心觀念

本題考查分散式系統（Distributed Systems）與容錯計算（Fault-Tolerance Computing）領域中極具代表性的拜占庭將軍問題（Byzantine Generals Problem）。

1. 拜占庭將軍問題的定義：
   由 Leslie Lamport 等人於 1982 年提出，用於抽象化描述分散式系統中存在**任意故障（Arbitrary Faults）或惡意行為（Malicious Behavior）**的節點時，其餘非故障節點（忠誠將軍）如何達成統一共識（Consensus）的決策困境。

2. 學門分類（Domain Categorization）：

   • 容錯計算（Fault-Tolerance Computing）：拜占庭將軍問題探討分散式系統在面對極端故障（拜占庭故障，Byzantine Fault）時的系統容錯邊界與共識協定設計，屬於容錯計算／分散式系統的核心研究議題。
   • 密碼學（Cryptography）：密碼學主要研究資訊安全、密碼編譯、數位簽章與身份驗證等機制。雖然在解決拜占庭將軍問題時，可導入密碼學工具（如數位簽章 Signed Messages）來降低所需的節點總數要求（從 $n \ge 3f + 1$ 降至 $n \ge 2f + 1$），但該問題本身的理論分類屬於容錯計算，而非密碼學。

解題方法

本題之切入點在於區分**「問題本質所屬的研究領域」與「求解過程使用的輔助工具」**：

1. 研判 (a) 選項：

   • 拜占庭將軍問題探討的是分散式系統的共識與容錯機制，而非資料加密、解密或金鑰管理等密碼學的核心範疇。
   • 雖然數位簽章（Digital Signatures）等密碼學技術能用來防範訊息被偽造與篡改，但這僅代表「密碼學技術能輔助解決此問題」，不能將問題本身歸類為密碼學問題。因此 (a) 敘述錯誤。

2. 研判 (b) 選項：

   • 容錯計算旨在研究如何讓系統在部分元件發生故障（包含 Fail-Stop、Fail-Silent 以及最複雜的 Byzantine Fault）時仍能維持整體運作的正確性。

核心觀念

**拜占庭將軍問題（Byzantine Generals' Problem）是由 Leslie Lamport、Robert Shostak 與 Marshall Pease 於 1982 年提出的經典分散式系統（Distributed Systems）**問題。

• 問題定義：在分散式計算環境（Distributed Computing）中，多個獨立節點（將軍）需要透過不可靠的網路通訊對某項決定達成共識（Consensus）。在通訊過程中，可能存在訊息傳遞失敗、系統故障，甚至有惡意節點（叛徒將軍）故意傳送偽造或矛盾的訊息。
• 核心目標：探討在存在任意故障或惡意破壞（即拜占庭容錯，Byzantine Fault Tolerance, BFT）的情況下，分散式系統如何確保忠誠節點仍能達成正確且一致的共識。

解題方法

本題考察作業系統與分散式系統中經典問題與演算法的範疇歸屬。解題切入點為將題目涉及的三個作業系統／計算機系統主題進行正確的分類比對：

1. 分散式計算（Distributed Computing）：研究多台獨立電腦經由網路協調運作的系統架構，其核心議題包含分散式共識（Consensus）、容錯（Fault Tolerance）、分散式鎖定（Distributed Locks）等。拜占庭將軍問題即為此領域最著名的共識問題模型。
2. 死鎖避免（Deadlock Avoidance）：屬於單機或多進程作業系統中資源管理的範疇，旨在動態分配資源時預先判斷系統是否會進入不安全狀態（Unsafe State），代表性演算法為銀行家演算法（Banker's Algorithm）。
3. 磁碟排程（Disk Scheduling）：屬於作業系統儲存設備（I/O Subsystem）管理的範疇，旨在決定磁碟讀寫頭存取請求的處理順序以最小化尋道時間（Seek Time），代表性演算法包括 FCFS、SSTF、SCAN、C-SCAN 等。

核心觀念

資源配置圖（resource allocation graph）中：

• 資源 → 行程的邊是「配置邊」：該行程已持有一份該資源。
• 行程 → 資源的邊是「請求邊」：該行程正在等待該資源。

資源有多份副本時，圖中有環不一定代表死結，必須實際模擬能否讓所有行程依序完成；若存在一個完成順序（安全序列），狀態就是安全的，也沒有死結。

解題方法：讀圖

各行程的請求：

• $P_0$：持有 $R_0$、$R_1$，請求 $R_2$。
• $P_1$：持有 $R_2$，請求 $R_1$。
• $P_2$：持有 $R_2$，請求 $R_3$。
• $P_3$：沒有持有資源，請求 $R_0$、$R_2$、$R_3$。

依題意，每位哲學家需要「所有與她相連的資源類型」各一份才能完成，因此上表的請求就是她還缺的資源。

模擬完成順序

解題要點

• 死結產生條件：互斥、保持與請求、不可搶占、循環等待。
• 只要破除「循環等待」即可保證不會死結。

(a) 低編號哲學家享有資源分配優先權
若哲學家以編號遞增的順序爭取資源，較高編號者只能在較低編號者已取得全部所需資源後才會取得。此機制消除循環等待 → 不會產生死結。

核心觀念

本題考查計算機結構中的**記憶體階層（Memory Hierarchy）特性，以及編譯器最佳化（Compiler Optimization）**如何結合硬體快取參數調校機器碼效能。

1. 記憶體階層（Memory Hierarchy）：

   • 越靠近 CPU 的記憶體階層，其存取延遲（Latency）越低、頻寬越高、實體與邏輯距離越近，但單位成本越高且容量越小。
   • 階層順序為：$\text{CPU Registers} < \text{L1 Cache} < \text{L2 Cache} < \text{L3 Cache} < \text{Main Memory (DRAM)}$。

2. 編譯器快取感知最佳化（Cache-Aware Compiler Optimization）：

   • 現代編譯器可針對特定目標架構進行快取優化。例如使用**迴圈分塊（Loop Tiling / Loop Blocking）**技術時，編譯器會利用硬體的快取總容量（Total Cache Size）與區塊大小（Cache Line Size）來決定最佳分塊大小（Tile Size），以確保資料能被載入並保留在快取中，大幅提高時間局部性（Temporal Locality）與空間局部性（Spatial Locality）。

解題方法

1. 選項 (a)：從記憶體階層的物理位置、存取時間（Cycles）與邏輯架構分析 L1 快取與 L2 快取相對於 CPU 核心的距離。

核心觀念

本題考查編譯器最佳化技術（Compiler Optimizations）與記憶體階層（Memory Hierarchy）硬體特性之間的互動關係。

核心考點包含：

1. 硬體架構參數（Hardware Architectural Parameters）：如快取列大小（Cache Line Size）、暫存器數量（Register Count）與快取容量（Cache Capacity），為編譯器在編譯期（Compile Time）可獲得並用於調整機器碼（Machine Code）效能的靜態硬體特徵。
2. 動態執行效能指標（Dynamic Execution Metrics）：如快取命中率（Cache Hit Ratio）、每指令週期數（Cycles Per Instruction, CPI）與執行時間，為程式執行後的動態測量結果，非編譯器直接輸入的微架構參數。
3. 記憶體一致性模型（Memory Consistency Model）：如完全儲存排序（Total Store Order, TSO），屬於多核心系統對記憶體寫入順序（Store Buffer）的語意規範，非快取本身的效能調校參數。

解題方法

切入點在於區分「何者為編譯器在編譯期可據以進行代碼調整（Tuning）的硬體架構參數」：

1. 檢視各選項所提及的物理量或模型屬性之本質。
2. 若該項目為靜態微架構參數（如 Cache Line Size），編譯器得以利用其數值實施資料對齊（Data Alignment）、迴圈區塊化（Loop Tiling）等最佳化代碼生成技術，則該敘述正確。
3. 若該項目屬於執行期動態結果（如 Cache Hit Ratio）或概念混淆之模型名稱（如將 TSO 歸為快取參數），則該敘述錯誤。

選項分析

(a) 正確。

• 原因：快取列大小（Cache Line Size）是硬體微架構的靜態參數。編譯器在生成與最佳化機器碼時，會高度依賴快取列大小來進行多種效能調校：
  1. 迴圈區塊化（Loop Tiling / Blocking）：將大矩陣或陣列運算切割為符合快取列大小與快取容量的子區塊，最大化空間局部性（Spatial Locality）。

有效記憶體存取時間 (EMAT) 計算式

其中
$t_{\text{TLB}}=1\;\text{ns}$、$t_{\text{mem}}=26\;\text{ns}$、$t_{\text{disk}}=1\;\text{ms}=10^{6}\;\text{ns}$。
$t_{\text{pt}}$ 為 TLB 未命中時查找頁表的額外記憶體存取時間。

(a) 1‑層頁表

TLB 未命中懲罰：一次頁表存取＝$26\;\text{ns}$。

核心公式

有效記憶體存取時間 (EMAT)

$EMAT = t_{mem}\Bigl[1 + (\text{TLB miss ratio})\times N\Bigr]$

其中
$t_{mem}$ 為一次主記憶體存取時間（包括快取或 DRAM 延遲），
$N$ 為頁表層數（走訪每層需要一次記憶體存取）。

題目所給的 Page‑fault ratio 極小，對 EMAT 影響可忽略（$t_{pf}$ 只會在極少數情況下貢獻），故公式不必加入 page‑fault 項。

(a) 3‑層頁表

• TLB miss ratio = 0.2 % = $2\times10^{-3}$
• $N = 3$

已知 $EMAT = 27.276$ ns，解得

$t_{mem}= \frac{27.276}{1.006}=27.112\text{ ns}$

算式成立 → (a) 為真。

(b) 4‑層頁表

核心觀念

本題考查雲端運算（Cloud Computing）的三大基本服務模型（Service Models）：

1. 基礎設施即服務（Infrastructure as a Service, IaaS）：提供底層運算資源、儲存空間、網路設備與虛擬機器（Virtual Machines, VMs）。使用者需要自行安裝與維護作業系統、中間件（Middleware）及應用程式。
2. 平台即服務（Platform as a Service, PaaS）：提供應用程式開發團隊完備的開發環境（Development Environment）、軟體庫、程式語言執行階段（Runtime）、資料庫管理系統與部署工具。開發者僅需專注於撰寫與管理應用程式程式碼。
3. 軟體即服務（Software as a Service, SaaS）：透過網路向終端使用者提供完整且可直接使用的商業資訊服務與應用軟體（例如 Google Workspace, Microsoft 365, Salesforce）。使用者不需維護任何程式碼或底層基礎設施。

解題方法

區分雲端三大服務模型的關鍵切入點在於服務層級與服務對象：

• 若題目敘述為「底層運算、虛擬機器、儲存與網路資源」，對應 IaaS。
• 若題目敘述為「提供開發團隊應用程式開發環境、Runtime 與部署平台」，對應 PaaS。
• 若題目敘述為「隨選存取套裝軟體或商業資訊服務（Commercial Information Services）」，對應 SaaS。

據此比對選項中服務模型與服務內容的配對是否正確。

選項分析

• (a) 錯誤。
  • 題目原文：IaaS supports on-demand access to commercial information services.

核心觀念

本題考核雲端運算（Cloud Computing）的基本定義、服務模型與系統架構觀念，主要涵蓋以下重點：

1. NIST 雲端服務模型（Service Models）：根據美國國家標準與技術研究院（NIST SP 800-145）定義，雲端服務分為三大層級：
   • IaaS (Infrastructure as a Service)：基礎設施即服務
   • PaaS (Platform as a Service)：平台即服務
   • SaaS (Software as a Service)：軟體即服務
2. 雲端彈性與自動擴展（Elasticity & Auto-scaling）：雲端環境根據實際工作負載動態配置資源的機制。
3. 虛擬化與容器架構（Virtualization & Containerization）：虛擬機器（VM）、容器（Container）與作業系統行程（Process）及執行緒（Thread）的粒度層級差異。

解題方法

本題為觀念判斷題，解題切入點為逐一比對標準雲端服務定義與作業系統虛擬化層級：

1. 核對 NIST 定義：分析選項 (a) 描述的資源種類（CPU、記憶體、儲存空間）屬於哪一種服務模型（IaaS、PaaS 或 SaaS）。
2. 核對 Auto-scaling 原理：確認自動擴展機制的核心定義是否為根據工作負載（Workload）自動調整資源。
3. 核對 Container 與 Thread 的關係：檢驗 Container 的封裝粒度是否細化至 Thread 層級，評估其合理性。

選項分析

• (a) 錯誤
  根據 NIST SP 800-145 標準定義：
  • IaaS 提供的是最底層的計算資源，如 CPU 週期、記憶體容量、網路與儲存空間（CPU cycles, memory capacities, network storage），使用者能在其上部署作業系統與任意軟體。
  • PaaS 提供的是開發與部署平台（如程式語言執行環境、資料庫、開發工具），主要服務對象才是應用程式開發團隊（application development teams）。

(a) 解析
每個執行緒在讀取前先執行一次寫入：

• Thread 0 執行 A = 1 後才 Print B。
• Thread 1 執行 B = 1 後才 Print A。

因為每個執行緒的指令順序必須依序顯現，且沒有同步機制，唯一能導致兩個輸出皆為 0 的情形是兩條讀取在對方寫入之前完成。
然而在任一執行緒完成自己的寫入後，該變數已變成 1，若另一執行緒在之後才讀取，必會看到 1。

分析要點

• 設 semaphore $S$ 初值 $0$，Wait(S) 於 $S=0$ 時阻塞，Signal(S) 使 $S$ 加 $1$。
• 變數 $A,B$ 初始皆為 $0$。兩執行緒分別執行同一段程式，執行順序可任意交錯，只需符合 semaphore 的阻塞/釋放規則。

(a) 程式

Wait(S)
A = 1
Print B
Signal(S)
B = 1
Wait(S)
Print A
Signal(S)

兩執行緒同時在 Wait(S) 先阻塞，必須先有 Signal(S) 才能前進。第一個 Signal 發生前，$B$ 尚未被寫入，故第一次 Print B 必為 $0$。之後無論交錯如何，Print A 只能在 $A$ 已被設為 $1$ 後執行，故不會產生 $(1,0)$。
結論：敘述 錯誤。

(b) 程式

Signal(S)
A = 1
Wait(S)
Print B
B = 1
Wait(S)
Print A

起始時各執行緒先執行 Signal(S)，$S$ 變為 $1$，隨即 A=1。

核心觀念

1. C 語言動態記憶體管理（Dynamic Memory Allocation）：
   C 語言標準庫中的 malloc() 是在堆疊（Heap）區段進行動態記憶體配置。C 語言採用**手動記憶體管理（Manual Memory Management）**機制，配置後須由程式員手動呼叫 free() 釋放記憶體。

2. 記憶體緊縮（Memory Compaction）與指標有效性：
   記憶體緊縮是指搬移已配置的記憶體區塊以消除外部碎裂（External Fragmentation）。然而，搬移記憶體區塊必須同時更新所有指向該區塊的指標（Pointers）。C 語言原生支援指標算術（Pointer Arithmetic）與直接記憶體位址存取，系統無法追蹤並更新所有指標，因此 C 語言的 malloc() 絕不執行記憶體緊縮。

3. 垃圾回收（Garbage Collection, GC）：
   垃圾回收是高階託管語言（如 Java, C#）自動追蹤並回收不再使用之記憶體的機制。C 語言運行環境並不具備自動垃圾回收器，malloc() 完全不包含垃圾回收機制。

4. 即時系統（Real-Time Systems）與 Deadline Missing：
   在硬即時（Hard Real-Time）作業系統中，任務必須在嚴格的截止時間（Deadline）前完成。在即時系統中禁止或不建議使用 malloc() 的真正原因在於其執行時間具非確定性（Non-deterministic Execution Time）（例如自由鏈表搜尋時間不固定、系統呼叫 brk()/mmap() 觸發分頁配置、分頁錯失 Page Fault 或多執行緒鎖競爭 Lock Contention），而非因為記憶體緊縮或垃圾回收。

解題方法

本題旨在檢驗考生對 C 語言 malloc() 記憶體管理機制以及即時作業系統（RTOS）中 Deadline Missing 誘因的正確理解。

切入點為分析 malloc() 的底層實作與語言特性：

1. 驗證選項 (a)：檢查 malloc() 是否會進行 Memory Compaction。由於 C 語言允許裸指標（Raw Pointers），搬移記憶體將導致懸空指標（Dangling Pointers），故 malloc() 不進行記憶體緊縮。
2. 驗證選項 (b)：檢查 malloc() 是否具備 Garbage Collection。C 語言為手動記憶體管理，無 GC 機制。
3. 結論：選項 (a) 與 (b) 所陳述的「因果關係」均不成立。

核心觀念

在即時作業系統（Real-Time Operating Systems, RTOS）與計算機結構中，系統的最關鍵要求為可預測性（Predictability）與滿足截止時間（Deadline）。任何會引入非確定性延遲（Non-deterministic Delay）或大幅增加最壞情況執行時間（Worst-Case Execution Time, WCET）的軟硬體機制，都有可能引發任務錯過截止時間（Deadline Missing）。

本題旨在考驗考生是否能精確辨析作業系統（動態記憶體分配 malloc()、虛擬記憶體 Virtual Memory、頁面置換 Page Replacement）與計算機結構（超執行緒 Hyper-Threading、亂序執行 Out-of-Order Execution）中各機制的運作原理及其引發延遲的真正因果關係。

解題方法

解答即時系統相關題目時，切入點為因果邏輯分析（Causation Analysis）：

1. 判斷機制本身是否會造成延遲：檢視題目所述的系統機制是否會引發不可預期的時間開銷。
2. 檢視因果歸因是否正確：選項通常會結合兩個真實存在的計算機專有名詞，但給予錯誤的因果連結。必須確認選項中的「結果」是否確實由指定的「原因」所造成。

選項分析

• (a) 錯誤
  malloc() 確實在即時系統中可能導致任務錯過截止時間，但其原因在於動態記憶體分配演算法的非確定性時間複雜度（如搜尋 Free List 的時間變異）、記憶體碎片化（Fragmentation）、**鎖競爭（Lock Contention）**以及系統呼叫（如 sbrk() / mmap()）的開銷。
  超執行緒（Hyper-Threading / SMT）屬於 CPU 硬體層級的多執行緒共享核心資源技術，並非 malloc() 導致錯過截止時間的根本原因。

核心觀念

本題考查**阿姆達爾定律 (Amdahl's law)**對系統平行化效能極限的評估。
阿姆達爾定律指出，改善系統某一特定部分所獲得的整體加速比，受限於該部分所占的時間比例。

在多處理器或平行運算的背景下，假設 $P$ 為系統中可平行化執行的時間占總執行時間的比例（$0 \le P \le 1$），則不可平行化的序列部分（Sequential fraction）比例為 $1 - P$。
當使用 $N$ 個處理器進行平行加速時，整體加速比（Speedup, $S$）的計算公式為：
$S(N) = \frac{1}{(1 - P) + \frac{P}{N}}$

當處理器數量增加至無限多（即平行化達到理論極限 $N \to \infty$）時，極限加速比 $S_{\text{max}}$ 為：
$S_{\text{max}} = \lim_{N \to \infty} \frac{1}{(1 - P) + \frac{P}{N}} = \frac{1}{1 - P}$

解題方法

利用阿姆達爾定律的極限加速比公式 $S_{\text{max}} = \frac{1}{1 - P}$，將題目給定的平行化比例 $P$ 代入，即可求得該系統平行化所能達到的最大理論加速比（at most），進而判斷各選項的正確性。

1. 當 $P = 30\% = 0.3$ 時，極限加速比為：
   $S_{\text{max}} = \frac{1}{1 - 0.3} = \frac{1}{0.7} = \frac{10}{7}$
2. 當 $P = 60\% = 0.6$ 時，極限加速比為：
   $S_{\text{max}} = \frac{1}{1 - 0.6} = \frac{1}{0.4} = \frac{10}{4} = \frac{5}{2} = 2.5$