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

核心觀念

本題考查計算機結構中的 阿姆達爾定律（Amdahl's Law）。

阿姆達爾定律用於評估當系統部分組件進行改善（例如增加處理器數量進行平行運算）時，整體系統所能獲得的加速比（Speedup）。在平行處理情境下，假設程式中包含「可平行化（Parallelizable）」的部份與「必須串行執行（Serial）」的部份。當處理器數量為 $N$，可平行化比例為 $f$（$0 \le f \le 1$）時，整體加速比 $S$ 的公式為：

$S = \frac{1}{(1 - f) + \frac{f}{N}}$

各符號定義如下：

• $S$：改善後獲得的整體加速比（Speedup）。
• $N$：平行執行的處理器（Processor）數量。
• $f$：程式中可被平行執行的比例（Parallelizable fraction）。
• $1 - f$：程式中無法平行化、必須串行執行的比例（Serial fraction）。

解題方法

根據題意，題目給定：

• 處理器數量 $N = 6$
• 目標加速比 $S = 3$

設程式 $P$ 可平行化的最小比例為 $f$，代入阿姆達爾定律公式：

$3 = \frac{1}{(1 - f) + \frac{f}{6}}$

詳細推導與計算步驟如下：

1. 對等式兩邊取倒數，求出改善後的總執行時間比例：
   $(1 - f) + \frac{f}{6} = \frac{1}{3}$

2. 展開並整理含未知數 $f$ 的項：
   $1 - f + \frac{1}{6}f = \frac{1}{3}$
   $1 - \frac{5}{6}f = \frac{1}{3}$

3. 移項求解 $f$：
   $\frac{5}{6}f = 1 - \frac{1}{3}$
   $\frac{5}{6}f = \frac{2}{3}$
   $f = \frac{2}{3} \times \frac{6}{5} = \frac{12}{15} = \frac{4}{5} = 0.8 = 80\%$

求得可平行化的最小百分比為 80%。

選項分析

• a. 75%：錯誤。若 $f = 75\% = 0.75$，代入公式計算加速比

平均存取時間 $T$ 由三段構成

• 直接命中 L1：$1\text{ ns}$
• L1 錯失率 $r_1 = 0.05$（5%），此時必須再存取 L2：$10\text{ ns}$
• L2 錯失率 $r_2$，若再錯失則存取主記憶體 RAM：$100\text{ ns}$

因此

先計算快取的結構

1. 區塊大小
   16 words × 4 bytes/word = 64 bytes = $2^{6}$ bytes → $\text{offset bits}= \log_2 64 = 6$

2. 快取容量
   64 KB = 65536 bytes

3. 組合度
   8‑way set‑associative

4. 組數

→ $\text{index bits}=7$

核心觀念

本題考查計算機結構中**有效每指令週期數（Effective CPI, Effective Cycles Per Instruction）**與快取記憶體（Cache）缺失損失（Miss Penalty）的計算。

在理想快取（Ideal Cache，即完全命中）的情況下，處理器的執行效能由基本 CPI（$\text{CPI}_{\text{base}}$）決定。然而在實際系統中，指令讀取（Instruction Fetch）與資料存取（Data Access / Memory Access）若發生快取缺失（Cache Miss），均會產生額外的記憶體停頓週期（Memory Stall Cycles）。

計算 Effective CPI 的核心公式如下：
$\text{Effective CPI} = \text{CPI}_{\text{base}} + \text{Memory Stall Cycles per Instruction}$

其中，記憶體停頓週期可分為指令快取（I-Cache）停頓與資料快取（D-Cache / Memory Cache）停頓兩部分：
$\text{Memory Stall Cycles per Instruction} = \text{Stall}_{\text{I-cache}} + \text{Stall}_{\text{D-cache}}$
$\text{Stall}_{\text{I-cache}} = \text{Instruction Access Frequency} \times \text{Miss Rate}_{\text{I}} \times \text{Miss Penalty}$
$\text{Stall}_{\text{D-cache}} = \text{Data Access Frequency} \times \text{Miss Rate}_{\text{D}} \times \text{Miss Penalty}$

解題方法

根據題目給定的參數進行整理與計算：

1. 基本 CPI（$\text{CPI}_{\text{base}}$）：$1.5$
2. 指令快取缺失率（$\text{Miss Rate}_{\text{I}}$）：$2\% = 0.02$
3. 記憶體快取缺失率（$\text{Miss Rate}_{\text{D}}$）：$5\% = 0.05$
4. 缺失損失（$\text{Miss Penalty}$）：$80 \text{ cycles}$
5. 存取記憶體的指令比例：$40\% = 0.4$

步驟一：計算指令快取停頓週期（$\text{Stall}_{\text{I-cache}}$）
每一條指令在執行時均必須進行指令擷取（Instruction Fetch），因此指令存取頻率（Instruction Access Frequency）固定為 $1.0$（即 $100\%$）。
$\text{Stall}_{\text{I-cache}} = 1.0 \times 2\% \times 80 = 1.0 \times 0.02 \times 80 = 1.6 \text{ cycles/instruction}$

參考書等級：大學三年級以上，電腦結構/作業系統教材

程式流程

1. x5 ← n（輸入）
2. x6 ← 1、x7 ← 0（迴圈變數）
3. 迴圈條件 bge x6, x5, END：若 x6 ≥ n 則跳至 END，否則執行第 5–6 行。
4. 第 5 行 x6 ← x6 + x7  第 6 行 x7 ← x7 + 1
5. 回到第 4 行重新比較。
6. 迴圈結束時 x7 的值寫入 b（第 8 行）。

數學模型
設迴圈執行了 $k$ 次（$k\ge 0$），則

計算方式

P1 執行週期總數

$C_{\text{P1}} = 2\cdot3 + 2\cdot1 + 1\cdot2 = 10$

指令總數

$I_{\text{P1}} = 2+2+1 = 5$

$\text{CPI}_{\text{P1}} = \frac{C_{\text{P1}}}{I_{\text{P1}}}= \frac{10}{5}=2$

P2 執行週期總數

$C_{\text{P2}} = 1\cdot3 + 4\cdot1 + 3\cdot2 = 13$

指令總數

$I_{\text{P2}} = 1+4+3 = 8$

a. 真 $(2-2^{-52})\times2^{1023}$ 為 double precision 最大有限正數。
b. 真 最小規格化正數為 $2^{-1022}$（指數為 1，Fraction 為 0）。

核心觀念

本題考驗計算機結構中單時脈週期（Single-Cycle）與流水線（Pipelined）資料通道的時脈週期（Clock Cycle Time）、時脈速率（Clock Rate / Frequency）以及**加速比（Speedup）**的計算與邏輯推演。

1. 單時脈週期資料通道 (Unpipelined Single-Cycle Datapath)：
   單一指令必須在同一個時脈週期內完成所有執行階段。因此，最小時脈週期 $T_{\text{single}}$ 取決於所有階段處理時間（Processing Time）的總和：
   $T_{\text{single}} \ge \sum_{i=1}^{k} \tau_i$
2. 流水線資料通道 (Pipelined Datapath)：
   指令被分割為多個階段平行執行。在不考慮流水線暫存器延遲（Pipeline Register Overhead, $\tau_{\text{reg}}$）的理想狀況下，流水線的最小時脈週期 $T_{\text{pipe}}$ 取決於處理時間最長的瓶頸階段（Bottleneck Stage）：
   $T_{\text{pipe}} \ge \max_{1 \le i \le k} (\tau_i)$
3. 時脈速率（Clock Rate）：
   時脈速率為時脈週期的倒數：
   $f = \frac{1}{T}$
   因為時脈週期有下限（$T \ge T_{\text{min}}$），故時脈速率有上限（$f \le f_{\text{max}} = \frac{1}{T_{\text{min}}}$），即時脈速率**至多（at most）**為 $f_{\text{max}}$。
4. 加速比（Speedup）：
   流水線相較於未建置流水線時的性能提升倍數：
   $\text{Speedup} = \frac{T_{\text{single}}}{T_{\text{pipe}}}$

解題方法

Step 1：計算未建立流水線時的時脈週期與最高時脈速率

已知五個階段的處理時間分別為：
$\tau_{\text{IF}} = 0.5\text{ ns}$、$\tau_{\text{ID}} = 0.35\text{ ns}$、$\tau_{\text{EX}} = 0.25\text{ ns}$、$\tau_{\text{MEM}} = 0.5\text{ ns}$、$\tau_{\text{WB}} = 0.4\text{ ns}$。

單時脈週期的最小週期時間為各階段總延遲：
$T_{\text{single}} = 0.5 + 0.35 + 0.25 + 0.5 + 0.4 = 2.0\text{ ns}$

對應的最高時脈速率 $f_{\text{single, max}}$ 為：
$f_{\text{single, max}} = \frac{1}{T_{\text{single}}} = \frac{1}{2.0\text{ ns}} = 0.5\text{ GHz} = 500\text{ MHz}$
因此，未建立流水線時，時脈速率滿足 $f_{\text{single}} \le 500\text{ MHz}$。

Step 2：計算建立流水線後的時脈週期與最高時脈速率

流水線資料通道的瓶頸階段為 IF 與 MEM（均為 $0.5\text{ ns}$）。
在忽略暫存器延遲的理想條件下，最小時脈週期為：
$T_{\text{pipe}} = \max(0.5, 0.35, 0.25, 0.5, 0.4) = 0.5\text{ ns}$

對應的最高時脈速率 $f_{\text{pipe, max}}$ 為：
$f_{\text{pipe, max}} = \frac{1}{T_{\text{pipe}}} = \frac{1}{0.5\text{ ns}} = 2.0\text{ GHz} = 2000\text{ MHz}$
因此，建立流水線後，時脈速率滿足 $f_{\text{pipe}} \le 2\text{ GHz}$。

先算頁面位元組大小
$16\text{K}=16\times2^{10}=2^{14}$ 位元組 → 頁面位元組偏移需 $14$ 位元。

虛擬位址：$40$ 位元
虛擬頁號位元 = $40-14=26$ 位元 → 虛擬頁面數 $=2^{26}$。
因此

• a. $2^{23}$ 錯
• b. $2^{26}$ 正

階段計算
5 階段流水線，$N$ 條指令的最少週期為
$\text{base}=5+(N-1)=9\;\text{cycles}$

(a) 無 forwarding

• I1 → I2 (load → addi)：需等到 WB 才能在 ID 讀取 → 2 個停頓
• I2 → I4 (addi → addi)：同上 → 2 個停頓
• I3 → I4 (load → addi)：同上 → 2 個停頓

總停頓 $=2+2+2=6$，$\;9+6=15$ cycles。
a ≠ 13 → 錯誤

(b) 有 forwarding

• load‑use 仍需 1 個停頓：I1 → I2、I3 → I4
• I2 → I4 可在 EX 階段直接轉發，無停頓

總停頓 $=1+1=2$，$\;9+2=11$ cycles。
b 為 正確

核心觀念

本題考驗作業系統中 CPU 排程演算法（CPU Scheduling Algorithm） 的特性，特別是 SRTF（Shortest Remaining Time First，最短剩餘時間優先） 演算法及其引起的 飢餓現象（Starvation / Indefinite Blocking）。

1. SRTF（Shortest Remaining Time First）：

   • SRTF 是 SJF（Shortest Job First） 的 搶佔式（Preemptive） 版本。
   • 排程決策點：每當有新程序進入 Ready Queue 或目前執行的程序結束時，CPU 永遠指派給「剩餘 CPU Burst Time 最短」的程序。
   • 若新到達程序的 Burst Time 小於當前執行程序的「剩餘時間」，當前程序會立即被搶佔（Preempted），CPU 轉交給新程序。

2. 飢餓現象（Starvation）：

   • 指某一程序在 Ready Queue 中長期（甚至無限期）無法獲得 CPU 資源執行的狀態。
   • 在 SRTF 中，若系統中持續有短 CPU Burst 的程序源源不絕地到達，其剩餘時間皆小於長程序的剩餘時間，長程序將永遠無法競爭到 CPU，因而陷入 Starvation。

解題方法

要證明 SRTF 會導致 Starvation，必須設計一組程序集合（包含程序名稱、到達時間 Arrival Time, AT、CPU 執行時間 Burst Time, BT），並透過時間軸推導（Gantt Chart 邏輯）展示長程序如何被無限期阻塞。

1. 程序集合設計（Process Set Design）

設程序集合包含一個「長程序 $P_1$」與一連串「短程序序列 $P_2, P_3, P_4, \dots$」：

2. 執行過程與剩餘時間推導（Execution Trace）

• 時間 $t = 0$：

  • Ready Queue 僅有 $P_1$。
  • $P_1$ 開始執行，其剩餘時間 $\text{Remaining Time}(P_1) = 10$。

• 時間 $t = 1$：

  • $P_1$ 已執行 $1$ 個時間單位，剩餘時間 $\text{Remaining Time}(P_1) = 9$。
  • 短程序 $P_2$ 到達（$\text{AT} = 1, \text{BT} = 2$）。
  • 比較剩餘時間：$\text{Remaining Time}(P_2) = 2 < \text{Remaining Time}(P_1) = 9$。
  • 發生搶佔（Preemption）：$P_1$ 被迫切回 Ready Queue，CPU 轉而執行 $P_2$。

• 時間 $t = 3$：

  • $P_2$ 執行完畢（執行區間 $t \in [1, 3]$）。
  • 同時，短程序 $P_3$ 到達（$\text{AT} = 3, \text{BT} = 2$）。
  • 比較剩餘時間：$\text{Remaining Time}(P_3) = 2 < \text{Remaining Time}(P_1) = 9$。
  • CPU 選擇執行 $P_3$。

• 時間 $t = 5$：

  • $P_3$ 執行完畢（執行區間 $t \in [3, 5]$）。
  • 同時，短程序 $P_4$ 到達（$\text{AT} = 5, \text{BT} = 2$）。
  • 比較剩餘時間：$\text{Remaining Time}(P_4) = 2 < \text{Remaining Time}(P_1) = 9$。
  • CPU 選擇執行 $P_4$。

核心觀念

本題考查作業系統中 HRRN (Highest Response Ratio Next) 排程演算法的設計原理與 Starvation（飢餓現象） 的防範機制。

1. HRRN 的優先權定義公式：
   在任何時間點，Process 的優先權（Response Ratio, $R$）定義如下：
   $R = \frac{W + S}{S} = 1 + \frac{W}{S}$

   • $W$：累積等待時間（Accumulated Waiting Time）。
   • $S$：預估或剩餘執行時間（Estimated / Remaining Service Time）。

2. SJF / SRTF 的 Starvation 問題：
   在 Shortest Job First (SJF) 或 Shortest Remaining Time First (SRTF) 排程中，優先權僅取決於 $S$。若系統中持續有短執行時間（Small $S$）的 Process 到達，長執行時間（Large $S$）的 Process 優先權將永遠低於新來的短 Process，導致長 Process 無法獲得 CPU 資源，產生 Starvation。

3. Aging（老化機制）：
   HRRN 透過將等待時間 $W$ 納入優先權分子中，隱式實現了 Aging 機制，使長期等待的 Process 優先權動態提升。

解題方法

說明 HRRN 如何避免 Starvation 的關鍵推導步驟如下：

1. 等待時間 $W$ 的動態成長特性：
   當一個 Process 被放入 Ready Queue 後，只要它未被排程執行，其累積等待時間 $W$ 就會隨著時間 $t$ 線性增加（$\Delta W = \Delta t$）。

2. Response Ratio $R$ 的單調遞增性：
   對於任意給定且有限的剩餘執行時間 $S$（$S > 0$），當 $W \to \infty$ 時：
   $\lim_{W \to \infty} R = \lim_{W \to \infty} \left(1 + \frac{W}{S}\right) = \infty$
   這說明只要 Process 在 Ready Queue 中持續等待，其 Response Ratio $R$ 就會持續上升。

3. 新進短 Process 與長期等待長 Process 的優先權對比：

   • 假設系統持續湧入新的極短 Process $P_{\text{new}}$，其剛到達時 $W = 0$，其 Response Ratio 為：
     $R_{\text{new}} = 1 + \frac{0}{S_{\text{new}}} = 1$
   • 設存在一個長期等待的長 Process $P_{\text{long}}$，其 $S_{\text{long}}$ 較大。當其等待時間達到 $W_{\text{long}} > 0$ 時，其 Response Ratio 為：

核心觀念

資料平行化 (Data Parallelism) 是平行計算與計算機結構（Computer Architecture）中的核心概念之一，其重點要點如下：

1. 核心定義：將一份龐大的資料集切分為多個獨立的子集（Subsets），交由多個處理單元（如 CPU 多核心、GPU 運算單元、SIMD 向量暫存器）同時對不同的資料點執行相同的運算邏輯（Single Instruction, Multiple Data, SIMD 或 Single Program, Multiple Data, SPMD）。
2. 與任務平行化 (Task Parallelism) 之對比：
   • 資料平行化 (Data Parallelism)：相同的指令／程式碼，作用於不同的資料區塊上。
   • 任務平行化 (Task Parallelism)：不同的指令／程式碼（獨立任務），同時在不同處理器上執行。
3. 關鍵前提——資料獨立性 (Data Independence)：資料點之間的計算不得存在迴圈攜帶相依性 (Loop-Carried Dependency)。即第 $i$ 個元素的計算結果不能依賴第 $(i-1)$ 個元素的計算結果，否則無法安全地進行平行化。

解題方法

為了在考場上最直觀且完整地示範 Data Parallelism，本題採用最經典且具代表性的向量加法 (Vector Addition)：$C[i] = A[i] + B[i]$ 進行虛擬碼 (Pseudo Code) 設計。

1. 概念推導

• 順序執行 (Sequential)：由單一執行緒從 $i = 0$ 到 $N-1$ 依序計算 $N$ 次，時間複雜度為 $O(N)$。
• 平行執行 (Parallel)：若系統擁有 $P$ 個處理核心／執行緒，可將長度為 $N$ 的陣列均分為 $P$ 個子區塊，每個執行緒獨立且同時處理 $N/P$ 個元素。

2. Data Parallelism Pseudo Code

方法一：高階抽象平行迴圈語法 (parallel_for)

Procedure VectorAddition_DataParallel(A, B, C, N):
    // 輸入：長度為 N 的陣列 A, B
    // 輸出：長度為 N 的陣列 C (C[i] = A[i] + B[i])
    
    // parallel_for 表示所有 iterations 彼此獨立，可由硬體多核心同時執行
    parallel_for i from 0 to N - 1 do
        C[i] <- A[i] + B[i]
    end parallel_for
End Procedure

方法二：顯式多執行緒劃分語法 (SPMD Thread Mapping)

// 假設系統有 P 個執行緒，每個執行緒擁有獨一無二的 thread_id (0 <= thread_id < P)
Procedure VectorAddition_SPMD(A, B, C, N, P, thread_id):
    chunk_size <- N / P
    start_index <- thread_id * chunk_size
    end_index <- min(start_index + chunk_size, N)

    // 各執行緒並行執行此程序，各自處理專屬的資料區塊
    for i from start_index to end_index - 1 do
        C[i] <- A[i] + B[i]
    end for
End Procedure

3. 複雜度分析 (Complexity Analysis)

• 時間複雜度 (Time Complexity)：
  • 順序執行：$O(N)$
  • 平行執行（設核心數為 $P$，且 $P \le N$）：$O\left(\frac{N}{P}\right)$

任務平行（Task Parallelism）指將 相互獨立且無資料相依 的子工作分配至多個執行單元，同時執行，以縮短總執行時間。典型模型為 fork‑join：父任務分裂 (fork) 多個子任務，子任務結束後回收 (join)。若每個子任務執行時間為 $T_i$，平行度為 $P$（可用處理器數），理想總時間為

$T_{\text{total}} = \max_{i=1..P} T_i$

（忽略同步開銷）。

精簡偽碼範例（四個獨立任務）

核心觀念

本題考查作業系統中執行緒模型（Thread Models）的實現機制，特別是多對一模型（Many-to-One Model / User-Level Threads, ULT）。

在單一核心執行緒（Kernel Thread / Lightweight Process, LWP）之上實現多執行緒程式，代表作業系統核心（Kernel）完全感知不到使用者層級的多執行緒架構，核心僅將整個行程（Process）視為單一執行執行緒。所有的執行緒建立、管理、排程、上下文切換與狀態維護，均由執行緒函式庫（Thread Library，如早期 Java Green Threads 或 GNU Pth）在**使用者空間（User Space）**獨立完成。

解題方法

要完整說明執行緒函式庫如何於單一核心執行緒中實現多執行緒，必須從資料結構與記憶體配置、使用者空間上下文切換、排程與搶佔機制，以及**阻塞系統呼叫的處理（Jacketing / Non-blocking I/O）**四個核心面向說明：

1. 資料結構與記憶體配置（Thread Control Block & Stack）

• 使用者層級 TCB（User-level Thread Control Block）：執行緒函式庫會在使用者空間中維護一個 TCB 結構，用以儲存各個使用者執行緒的狀態（READY、RUNNING、BLOCKED）、執行緒 ID、程式計數器（Program Counter, PC）、堆疊指標（Stack Pointer, SP）及通用暫存器（General-purpose Registers）數值。
• 獨立使用者堆疊（Independent User Stacks）：函式庫會在行程的堆疊區或堆積區（Heap）為每個使用者執行緒分配一塊獨立的記憶體空間作為其專屬的使用者堆疊（User Stack），用於維護區域變數與函式呼叫框架（Stack Frames）。

2. 使用者空間上下文切換（User-Space Context Switch）

當排程器決定切換執行執行緒時，上下文切換完全在使用者空間執行，不需透過系統呼叫（System Call）觸發模式切換（User Mode 到 Kernel Mode）：

1. 保存現有狀態：將當前 CPU 暫存器（PC、SP、通用暫存器等）的值寫入當前執行緒的 TCB 中。
2. 載入目標狀態：將下一個準備執行的執行緒之 TCB 中儲存的暫存器數值寫回 CPU 暫存器。
3. 跳轉執行：更新 SP 至目標執行緒的堆疊，並將 PC 指向其待執行指令位址以恢復執行（實作上常採用 C 語言標準庫的 setjmp() / longjmp() 或 POSIX 的 swapcontext() 機制與組譯碼常式）。

3. 排程與搶佔機制（Scheduling & Preemption）

• 自願讓出（Voluntary Yielding）：執行緒可主動呼叫函式庫提供的 API（如 thread_yield()），觸發函式庫排程器進行上下文切換。
• 非自願搶佔（Preemptive Scheduling）：為了防止單一執行緒因無窮迴圈而獨佔核心執行緒，函式庫利用作業系統提供的時脈訊號（如 POSIX 的 setitimer() 或 SIGALRM 訊號）。當計時器到期，作業系統傳送訊號給該行程，觸發函式庫註冊的訊號處理常式（Signal Handler），由該常式充當使用者排程器強行切換執行緒。

4. 阻塞系統呼叫之包裝與處理（Jacketing / Non-blocking I/O）

• 痛點：若某個使用者執行緒發起傳統阻塞式系統呼叫（如傳統的 blocking read()），作業系統核心會將唯一的核心執行緒掛起（Block），導致該行程內的所有使用者執行緒全部被迫凍結。

核心觀念

1. LFU（Least Frequently Used，最少使用）頁面置換演算法：

   • 為每個在記憶體中的頁面維護一個「存取次數計數器（Access Frequency Counter）」。
   • 當發生頁面錯誤（Page Fault）且實體頁框（Page Frame）已滿時，選擇累積存取次數最少的頁面予以淘汰置換；若有多個頁面次數相同，通常以 FIFO（先先進出）作為平手打破規則（Tie-breaker）。
   • 核心缺點：具有歷史累積效應。在早期被頻繁存取的頁面會累積很高的計數，即使後續程式的工作集（Working Set）轉移且該頁面不再被使用，其高計數仍會使其長期被鎖在記憶體中（成為過時的殭屍頁面），擠占有限的頁框資源。

2. 參考位元演算法（Reference-Bit Algorithm / 二次機會演算法 Second-Chance Algorithm）：

   • 為每個頁面設置 1 個參考位元（Reference Bit $R$）。當頁面被載入或被存取時，系統將其設為 $R = 1$。
   • 當發生缺頁需置換時，依據環狀指標（Clock Pointer）依序檢查：若指標指向頁面的 $R = 1$，給予二次機會並將其清零（$R = 0$），指標移至下一個頁框；若遇到 $R = 0$ 的頁面，則直接淘汰該頁面並置換新頁面，最後將指標移至下一位置。
   • 核心優點：參考位元會在搜尋置換目標時被定期清零，能淘汰舊的存取歷史，進而快速反應近期的區域性（Locality of Reference）。

解題方法

要證明 LFU 演算法的表現劣於參考位元演算法，只需設定適當的實體頁框數量（Frame Size $m$），並構造一組特定的頁面參考序列（Page-Reference Sequence $S$），分別推導兩者產生的頁面錯誤（Page Fault）次數。

1. 實驗條件設定

• 實體頁框數：$m = 3$（初始皆為空）。
• 頁面參考序列：$S = \text{A, A, B, C, D, B, C, D}$（總長度 8 次存取）。

2. LFU 演算法推導過程

• 置換規則：選擇累積存取次數最小者淘汰；次數相同時淘汰最早載入者（FIFO）。

• LFU 總缺頁次數：$7$ 次。

3. 參考位元（二次機會）演算法推導過程

• 置換規則：指標初始指向 Frame 0。存取頁面時將該頁面的參考位元 $R$ 設為 $1$。缺頁時若指標指向 $R=1$ 則清零為 $0$ 並前進，直到遇到 $R=0$ 的頁面予以淘汰。

核心觀念

本題考驗多處理器系統（Multiprocessor Systems）中**非均勻記憶體存取（Non-Uniform Memory Access, NUMA）**架構的硬體設計原理以及作業系統（OS）在記憶體管理上的因應機制與功能。

1. UMA vs. NUMA 架構對比：

   • 均勻記憶體存取（Uniform Memory Access, UMA）：所有 CPU 核心透過共享匯流排（Shared Bus）存取集中式實體記憶體，任意 CPU 存取任意記憶體位置的延遲皆相同（Latency 為常數 $t_{\text{UMA}}$）。當 CPU 數量增加時，共享匯流排會成為嚴重的效能瓶頸（Bus Contention）。
   • 非均勻記憶體存取（Non-Uniform Memory Access, NUMA）：實體記憶體被切分並分散建置於各個 CPU 節點（NUMA Node）側。CPU 存取同節點內的記憶體稱為本地存取（Local Access），延遲為 $t_{\text{local}}$；透過跨節點互連網路存取其他節點的記憶體稱為遠端存取（Remote Access），延遲為 $t_{\text{remote}}$。兩者滿足 $t_{\text{remote}} > t_{\text{local}}$，其比值稱為 NUMA Factor（$\text{NUMA Factor} = \frac{t_{\text{remote}}}{t_{\text{local}}} > 1$）。

2. 對稱多處理系統（SMP）與 ccNUMA：

   • 儘管實體記憶體物理上分散，NUMA 系統仍維持 SMP 的核心特性：所有 CPU 共享單一連續的實體位址空間（Single Physical Address Space），並透過硬體層級的快取一致性協定（Cache Coherence Protocol，如 MESI/MOESI 延伸協定）維持資料一致，此架構又稱為 ccNUMA（Cache-Coherent NUMA）。

3. 作業系統 NUMA 感知記憶體管理（NUMA-Aware Memory Management）：

   • OS 核心必須將實體記憶體劃分為多個 NUMA 節點（在 Linux Kernel 中以 pg_data_t 結構抽象化）。
   • OS 記憶體配置器（Memory Allocator）與排程器（Scheduler）必須協同運作，極大化本地存取比例（Locality Optimization），降低跨節點流量。

解題方法

在臺灣大學電機工程研究所（丙組）考試中，解答此類英文申論題時，必須採取「結構化條列式」撰寫，精準命中硬體設計與 OS 記憶體管理兩大面向：

1. NUMA 的硬體設計原理（Design in SMP）

• 分散式共享記憶體（Distributed Shared Memory）：每個處理器 Socket 擁有獨立的本地記憶體控制器（Local Memory Controller）與直接掛載的 DRAM 通道。
• 點對點互連網路（Point-to-Point Interconnect）：節點之間透過高速互連通道（如 Intel UPI/QPI、AMD Infinity Fabric）連接，用於轉發遠端記憶體讀寫請求與快取一致性訊號。
• 解決 SMP 擴充性瓶頸：消除傳統 UMA 匯流排的單點爭用，使系統記憶體總頻寬（Aggregate Bandwidth）隨著 CPU 節點數增加而呈線性成長。

2. OS 記憶體管理機制與功能（Function in Memory Management）

• 頁面配置策略（Page Allocation Policies）：
  1. 首觸策略（First-Touch Policy，預設）：當行程觸發 Page Fault 時，OS 優先在「當前執行該行程的 CPU 所在之 NUMA 節點」配置實體頁面（Physical Page Frame），從源頭極大化 Local Access。
  2. 交錯配置策略（Interleave Policy）：將連續的虛擬頁面以 Round-Robin 方式輪流配置給各個 NUMA 節點，適用於多執行緒共享且頻寬導向的大型資料集，避免單一節點記憶體頻寬飽和。
  3. 綁定策略（Binding Policy）：限定行程只能從特定的 NUMA 節點配置記憶體。
• NUMA 感知排程與親和性（NUMA-Aware Scheduling & Affinity）：
  • CPU/Memory Affinity：OS 排程器盡量保留執行緒於同一 CPU 節點執行，避免 Thread Migration 導致原本的 Local Access 變成 Remote Access。
• 動態頁面遷移與重平衡（Dynamic Page Migration / AutoNUMA）：
  • 當排程器迫不得以將執行緒遷移至新節點時，OS 核心（如 Linux AutoNUMA）會追蹤頁面的存取頻率（使用 Page Fault 追蹤）。若發現某頁面被遠端 CPU 頻繁存取，OS 會自動將該實體頁面遷移（Migrate）至該 CPU 的本地記憶體節點，或是將執行緒移回資料所在的節點（Task Migration）。

選項分析

本題為問答申論題，答題時應將 NUMA 各項關鍵設計面向與配置策略做對比分析，說明各種設計決策的優缺點與適用場景：

核心觀念

本題考查多執行緒中的 Race Condition（競爭情況）。

當多個執行緒同時存取共享資料，且至少有一個執行緒會修改該資料，而程式結果又取決於執行緒的執行順序時，就會發生競爭情況。

以共享變數 counter 為例，執行：

表面上是一個運算，實際上通常包含三個步驟：

1. 讀取 counter
2. 計算讀取值加一
3. 將結果寫回 counter

這三個步驟不是不可分割的原子操作，因此多個執行緒交錯執行時，可能互相覆蓋更新結果。

解題方法

建立兩個執行緒，讓它們同時對同一個共享變數執行遞增操作。預期結果與實際結果不一致，即可清楚展示競爭情況。

會產生競爭情況的虛擬碼

shared counter = 0

procedure increment():
    repeat 1000 times:
        temp = counter
        temp = temp + 1
        counter = temp

thread T1 runs increment()
thread T2 runs increment()

wait until T1 and T2 finish

print counter

理論上，兩個執行緒各遞增 $1000$ 次，因此預期結果為：

但程式不一定輸出 $2000$。

競爭情況的具體執行順序

假設目前：

兩個執行緒可能依照下列順序執行：

兩個執行緒都完成了一次遞增，但最後結果只有 $1$，其中一次更新被覆蓋。

因此，兩個執行緒各執行 $1000$ 次後，實際結果可能小於 $2000$。實際數值取決於執行緒切換與指令交錯的順序。

臨界區與修正方法

上述程式中，以下區段屬於 Critical Section（臨界區）：

temp = counter
temp = temp + 1
counter = temp

臨界區必須確保同一時間只有一個執行緒進入。可以使用互斥鎖（Mutex）保護共享資料。