108 年 國立臺灣大學資訊工程學系碩士班《計算機結構與作業系統(B)》

核心觀念

本題考查計算機結構中的管線化技術（Pipelining）、指令排程（Instruction Scheduling）與資料相關性（Data Dependency）。

1. 軟體管線化（Software Pipelining）與全域指令排程（Global Instruction Scheduling）：

   • 軟體管線化透過將不同迴圈迭代（Iterations）的指令重排與交錯執行，藉此隱藏長延遲指令（如 Load 指令或浮點數運算）導致的管線空檔。
   • 全域指令排程將排程範圍擴展至多個基本區塊（Basic Blocks）之間，穿越控制分支（Control Branches）以拉大指令間距並尋找更多可平行的獨立指令。
   • 上述編譯器優化技術適用於所有具備管線（Pipelined）架構的處理器，不論是單發射（Single-issue）還是多發射（Multi-issue）處理器均可獲得顯著效能提升。

2. 資料相關性（Data Dependency）與管線停頓（Pipeline Stall）：

   • 資料相關性（如 RAW、WAR、WAW）是程式碼邏輯上的屬性；管線停頓（Stall/Bubble）則是硬體遇到危障（Hazard）且無法及時提供資料時暫停執行的機制。
   • 資料相關性不一定會引發管線停頓。透過硬體的資料轉發／旁路技術（Data Forwarding / Bypassing）或編譯器的指令重排（Instruction Reordering），即可消除或避開停頓。

---

解題方法

針對是非題進行邏輯分析與反例驗證：

• 選項 (a)：評估軟體管線化與全域排程的設計初衷。舉出單發射管線處理器（Single-issue Pipelined Processor）亦能透過這兩種技術隱藏 Load 延遲或分支延遲之反例，即可證明該敘述過於狹隘。
• 選項 (b)：區分「邏輯上的資料相關性」與「物理上的管線停頓」。說明只要硬體支援轉發機制（Forwarding），或是相關指令之間間隔了足夠的獨立指令，就不會產生任何管線停頓。

---

選項分析

選項 (a)

• 題目原文：You must have multi-issue machines to benefit from software-pipelining or global instruction scheduling.
• 分析：錯誤（FALSE）。
  • 軟體管線化（Software Pipelining）：主要目的是打破單次迭代內的資料相關性限制。

a) 大頁面與執行時間

核心觀念

虛擬位址轉換會先查詢 TLB；若 TLB 未命中，處理器必須進行頁表遍歷（page walk），才能取得實體頁框位址。頁面越大，同一容量的 TLB 能涵蓋的記憶體範圍通常越大，因而可能減少 TLB 未命中與頁表遍歷。

解題方法

工作集約為 $2\text{ GiB}$，每次隨機存取 $4$ bytes，且反覆觸及整個工作集。以 $4\text{ KiB}$ 頁面計算，工作集包含：

$$\frac{2\text{ GiB}}{4\text{ KiB}}=524{,}288\text{ 頁}$$

改用 $2\text{ MiB}$ 頁面後，則包含：

$$\frac{2\text{ GiB}}{2\text{ MiB}}=1{,}024\text{ 頁}$$

頁面數大幅減少，使 TLB 較容易涵蓋工作集，降低 TLB 未命中及完成頁表遍歷的頻率。這與題目描述的隨機存取模式相符，主要原因是選項 4。

選項分析

1. 錯誤。 管線氣泡通常與資料相依、分支預測失敗等因素有關；增大頁面不會直接消除這些氣泡。
2. 錯誤。 相鄰快取線預取主要利用空間區域性；題目指定隨機存取整個工作集，不能把效能提升歸因於相鄰快取線預取器效率增加。
3. 錯誤。 大頁面可能讓一段實體記憶體配置得更連續，但隨機存取仍會落在整個工作集不同位置；題目所述的主要效益是減少位址轉換成本，而非降低資料存取延遲。
4. 正確。 大頁面讓每個頁面涵蓋更多位址、頁面總數減少，降低 TLB 未命中及頁表遍歷的頻率。
5. 錯誤。 缺頁率不是此處效能改善的主要來源。題目強調交換空間停用，工作集的反覆存取主要不會因頁面尺寸增加而減少缺頁。

解題技巧

看到「工作集大、隨機存取、改用大頁面」，優先檢查 TLB 覆蓋範圍與頁表遍歷次數。大頁面改善的是位址轉換效率，不會把隨機資料存取變成連續存取。

b) 超純量亂序執行處理器

核心觀念

超純量處理器可在一個時脈週期內發出或執行多條指令。亂序執行會在執行期追蹤指令間的資料相依，讓可先執行的指令提早進行，藉此利用指令層級平行性（ILP）。它可以採用 RISC 或 CISC 指令集，也通常採用管線化設計。

解題方法

核心觀念

本題考查計算機結構中**指令集架構（ISA）的定址模式（Addressing Modes）**設計、**偽指令（Pseudo Instructions）**機制、硬體管線（Pipeline）實作折衷（Trade-offs），以及 EPIC/VLIW 架構（如 Intel Itanium）對定址模式時序的特殊考量。關鍵概念包含：

1. 自動增減定址模式（Auto-increment / Auto-decrement Addressing Modes）：將記憶體載入/儲存（Load/Store）與暫存器位址更新合併於單一指令執行。
2. 硬體管線衝擊與複雜度（Pipeline Hazards & Hardware Complexity）：單一指令多重暫存器寫入埠（Dual Register Write Ports）、精確異常（Precise Exceptions）狀態復原與資料衝突（Data Hazards）。
3. 關鍵路徑與存取時序（Critical Path & Address Latency）：記憶體存取位址發送與 ALU 加法計算在管線時序上的先後相依性。

---

解題方法

針對題目四個子題進行系統化分析與推導：

• (a) 從組譯器（Assembler）與硬體 ISA 的分工視角定義偽指令，說明其對軟體層面（程式簡潔度）與硬體層面（保持簡潔 RISC 核心）的效益。
• (b) 分析自動增減實體指令在動態指令總數（Dynamic Instruction Count）與快取效益上的優勢，並對應高階語言結構（如指標存取 *p++ 與堆疊 push/pop）。
• (c) 從 Itanium 架構（EPIC/VLIW）的關鍵路徑時序（Critical Path Latency）切入，比較 Pre-increment 與 Post-increment 在位址發送時脈週期上的硬體發送延遲。
• (d) 從暫存器檔案寫入埠（Register File Write Ports）、管線衝突（Pipeline Hazards）、亂序執行（Out-of-Order Execution）與精確例外復原（Precise Exception Recovery）四大面向說明硬體缺點。

---

子題詳解與分析

a) 偽指令的定義與優點 [2 pt.]

• 定義：偽指令（Pseudo Instruction）是指組合語言中允許編寫，但硬體 ISA 之中並未直接提供對應機器碼的指令。組譯器（Assembler）在編譯期間會自動將偽指令展開（Expand）或替換為一至多條真實的硬體實體指令（Real/Native Machine Instructions）。
• 優點：
  1. 提升程式可讀性與開發效率：提供高階語言般的簡潔語法（例如清零暫存器 CLR r1 替換為 AND r1, r1, #0；或載入 32 位元大常數 LDR r1, =0x12345678 展開為 MOVWT 序列），減少程式員手寫冗長指令鏈的需求。
  2. 簡化硬體控制邏輯：無需為了滿足多樣化程式語法而過度擴充硬體解碼器與執行單元，維護硬體 ISA 的精簡性（RISC 原則），同時在軟體層面保留開發便利性。
  3. 增強程式碼相容性與可移植性：組譯器可針對不同微架構版本，將同一條偽指令自動最佳化翻譯為最適當的硬體實體指令序列。

b) Pre-increment 與 Post-increment 實體指令的優點與適用高階語言結構 [3 pt.]

• 優點：
  1. 降低動態指令總數（Lower Dynamic Instruction Count）：將「記憶體存取」與「基底暫存器算術更新」整合至單一指令中。原本需兩條指令（如 LDR 加上 ADD）的操作簡化為一條指令完成，縮減程式碼體積（Code Density），降低指令快取（I-Cache）的 Miss Rate 並減輕 Fetch/Decode 單元負擔。
  2. 減少暫存器佔用：無需額外配置暫存器來暫存中間位址。
• 適用的高階語言結構：
  1. 指標與陣列連續存取迴圈（Pointer/Array Iteration Loops）：例如 C/C++ 中的 *p++（Post-increment）與 *++p（Pre-increment），以及 for/while 迴圈遍歷陣列、字串處理或 Buffer 資料搬移。
  2. 堆疊操作（Stack Operations）：函數呼叫時的參數傳遞與暫存器保護。Pre-decrement 對應 Push 操作（先遞減堆疊指標 SP 再寫入記憶體），Post-increment 對應 Pop 操作（先讀取記憶體資料再遞增堆疊指標 SP）。

c) Intel/HP Itanium 僅支援 Post-increment 而不支援 Pre-increment 的原因 [1 pt.]

核心觀念

本題考查計算機結構中**指令集架構（ISA）的定址模式（Addressing Modes）**設計、**偽指令（Pseudo Instructions）**機制、硬體管線（Pipeline）實作折衷（Trade-offs），以及 EPIC/VLIW 架構（如 Intel Itanium）對定址模式時序的特殊考量。關鍵概念包含：

1. 自動增減定址模式（Auto-increment / Auto-decrement Addressing Modes）：將記憶體載入/儲存（Load/Store）與暫存器位址更新合併於單一指令執行。
2. 硬體管線衝擊與複雜度（Pipeline Hazards & Hardware Complexity）：單一指令多重暫存器寫入埠（Dual Register Write Ports）、精確異常（Precise Exceptions）狀態復原與資料衝突（Data Hazards）。
3. 關鍵路徑與存取時序（Critical Path & Address Latency）：記憶體存取位址發送與 ALU 加法計算在管線時序上的先後相依性。

---

解題方法

針對題目四個子題進行系統化分析與推導：

• (a) 從組譯器（Assembler）與硬體 ISA 的分工視角定義偽指令，說明其對軟體層面（程式簡潔度）與硬體層面（保持簡潔 RISC 核心）的效益。
• (b) 分析自動增減實體指令在動態指令總數（Dynamic Instruction Count）與快取效益上的優勢，並對應高階語言結構（如指標存取 *p++ 與堆疊 push/pop）。
• (c) 從 Itanium 架構（EPIC/VLIW）的關鍵路徑時序（Critical Path Latency）切入，比較 Pre-increment 與 Post-increment 在位址發送時脈週期上的硬體發送延遲。
• (d) 從暫存器檔案寫入埠（Register File Write Ports）、管線衝突（Pipeline Hazards）、亂序執行（Out-of-Order Execution）與精確例外復原（Precise Exception Recovery）四大面向說明硬體缺點。

---

子題詳解與分析

a) 偽指令的定義與優點 [2 pt.]

• 定義：偽指令（Pseudo Instruction）是指組合語言中允許編寫，但硬體 ISA 之中並未直接提供對應機器碼的指令。組譯器（Assembler）在編譯期間會自動將偽指令展開（Expand）或替換為一至多條真實的硬體實體指令（Real/Native Machine Instructions）。
• 優點：
  1. 提升程式可讀性與開發效率：提供高階語言般的簡潔語法（例如清零暫存器 CLR r1 替換為 AND r1, r1, #0；或載入 32 位元大常數 LDR r1, =0x12345678 展開為 MOVWT 序列），減少程式員手寫冗長指令鏈的需求。
  2. 簡化硬體控制邏輯：無需為了滿足多樣化程式語法而過度擴充硬體解碼器與執行單元，維護硬體 ISA 的精簡性（RISC 原則），同時在軟體層面保留開發便利性。
  3. 增強程式碼相容性與可移植性：組譯器可針對不同微架構版本，將同一條偽指令自動最佳化翻譯為最適當的硬體實體指令序列。

b) Pre-increment 與 Post-increment 實體指令的優點與適用高階語言結構 [3 pt.]

• 優點：
  1. 降低動態指令總數（Lower Dynamic Instruction Count）：將「記憶體存取」與「基底暫存器算術更新」整合至單一指令中。原本需兩條指令（如 LDR 加上 ADD）的操作簡化為一條指令完成，縮減程式碼體積（Code Density），降低指令快取（I-Cache）的 Miss Rate 並減輕 Fetch/Decode 單元負擔。
  2. 減少暫存器佔用：無需額外配置暫存器來暫存中間位址。
• 適用的高階語言結構：
  1. 指標與陣列連續存取迴圈（Pointer/Array Iteration Loops）：例如 C/C++ 中的 *p++（Post-increment）與 *++p（Pre-increment），以及 for/while 迴圈遍歷陣列、字串處理或 Buffer 資料搬移。
  2. 堆疊操作（Stack Operations）：函數呼叫時的參數傳遞與暫存器保護。Pre-decrement 對應 Push 操作（先遞減堆疊指標 SP 再寫入記憶體），Post-increment 對應 Pop 操作（先讀取記憶體資料再遞增堆疊指標 SP）。

c) Intel/HP Itanium 僅支援 Post-increment 而不支援 Pre-increment 的原因 [1 pt.]

核心觀念

本題考查計算機結構中**指令集架構（ISA）的定址模式（Addressing Modes）**設計、**偽指令（Pseudo Instructions）**機制、硬體管線（Pipeline）實作折衷（Trade-offs），以及 EPIC/VLIW 架構（如 Intel Itanium）對定址模式時序的特殊考量。關鍵概念包含：

1. 自動增減定址模式（Auto-increment / Auto-decrement Addressing Modes）：將記憶體載入/儲存（Load/Store）與暫存器位址更新合併於單一指令執行。
2. 硬體管線衝擊與複雜度（Pipeline Hazards & Hardware Complexity）：單一指令多重暫存器寫入埠（Dual Register Write Ports）、精確異常（Precise Exceptions）狀態復原與資料衝突（Data Hazards）。
3. 關鍵路徑與存取時序（Critical Path & Address Latency）：記憶體存取位址發送與 ALU 加法計算在管線時序上的先後相依性。

---

解題方法

針對題目四個子題進行系統化分析與推導：

• (a) 從組譯器（Assembler）與硬體 ISA 的分工視角定義偽指令，說明其對軟體層面（程式簡潔度）與硬體層面（保持簡潔 RISC 核心）的效益。
• (b) 分析自動增減實體指令在動態指令總數（Dynamic Instruction Count）與快取效益上的優勢，並對應高階語言結構（如指標存取 *p++ 與堆疊 push/pop）。
• (c) 從 Itanium 架構（EPIC/VLIW）的關鍵路徑時序（Critical Path Latency）切入，比較 Pre-increment 與 Post-increment 在位址發送時脈週期上的硬體發送延遲。
• (d) 從暫存器檔案寫入埠（Register File Write Ports）、管線衝突（Pipeline Hazards）、亂序執行（Out-of-Order Execution）與精確例外復原（Precise Exception Recovery）四大面向說明硬體缺點。

---

子題詳解與分析

a) 偽指令的定義與優點 [2 pt.]

• 定義：偽指令（Pseudo Instruction）是指組合語言中允許編寫，但硬體 ISA 之中並未直接提供對應機器碼的指令。組譯器（Assembler）在編譯期間會自動將偽指令展開（Expand）或替換為一至多條真實的硬體實體指令（Real/Native Machine Instructions）。
• 優點：
  1. 提升程式可讀性與開發效率：提供高階語言般的簡潔語法（例如清零暫存器 CLR r1 替換為 AND r1, r1, #0；或載入 32 位元大常數 LDR r1, =0x12345678 展開為 MOVWT 序列），減少程式員手寫冗長指令鏈的需求。
  2. 簡化硬體控制邏輯：無需為了滿足多樣化程式語法而過度擴充硬體解碼器與執行單元，維護硬體 ISA 的精簡性（RISC 原則），同時在軟體層面保留開發便利性。
  3. 增強程式碼相容性與可移植性：組譯器可針對不同微架構版本，將同一條偽指令自動最佳化翻譯為最適當的硬體實體指令序列。

b) Pre-increment 與 Post-increment 實體指令的優點與適用高階語言結構 [3 pt.]

• 優點：
  1. 降低動態指令總數（Lower Dynamic Instruction Count）：將「記憶體存取」與「基底暫存器算術更新」整合至單一指令中。原本需兩條指令（如 LDR 加上 ADD）的操作簡化為一條指令完成，縮減程式碼體積（Code Density），降低指令快取（I-Cache）的 Miss Rate 並減輕 Fetch/Decode 單元負擔。
  2. 減少暫存器佔用：無需額外配置暫存器來暫存中間位址。
• 適用的高階語言結構：
  1. 指標與陣列連續存取迴圈（Pointer/Array Iteration Loops）：例如 C/C++ 中的 *p++（Post-increment）與 *++p（Pre-increment），以及 for/while 迴圈遍歷陣列、字串處理或 Buffer 資料搬移。
  2. 堆疊操作（Stack Operations）：函數呼叫時的參數傳遞與暫存器保護。Pre-decrement 對應 Push 操作（先遞減堆疊指標 SP 再寫入記憶體），Post-increment 對應 Pop 操作（先讀取記憶體資料再遞增堆疊指標 SP）。

c) Intel/HP Itanium 僅支援 Post-increment 而不支援 Pre-increment 的原因 [1 pt.]

核心觀念

本題考查計算機結構中**指令集架構（ISA）的定址模式（Addressing Modes）**設計、**偽指令（Pseudo Instructions）**機制、硬體管線（Pipeline）實作折衷（Trade-offs），以及 EPIC/VLIW 架構（如 Intel Itanium）對定址模式時序的特殊考量。關鍵概念包含：

1. 自動增減定址模式（Auto-increment / Auto-decrement Addressing Modes）：將記憶體載入/儲存（Load/Store）與暫存器位址更新合併於單一指令執行。
2. 硬體管線衝擊與複雜度（Pipeline Hazards & Hardware Complexity）：單一指令多重暫存器寫入埠（Dual Register Write Ports）、精確異常（Precise Exceptions）狀態復原與資料衝突（Data Hazards）。
3. 關鍵路徑與存取時序（Critical Path & Address Latency）：記憶體存取位址發送與 ALU 加法計算在管線時序上的先後相依性。

---

解題方法

針對題目四個子題進行系統化分析與推導：

• (a) 從組譯器（Assembler）與硬體 ISA 的分工視角定義偽指令，說明其對軟體層面（程式簡潔度）與硬體層面（保持簡潔 RISC 核心）的效益。
• (b) 分析自動增減實體指令在動態指令總數（Dynamic Instruction Count）與快取效益上的優勢，並對應高階語言結構（如指標存取 *p++ 與堆疊 push/pop）。
• (c) 從 Itanium 架構（EPIC/VLIW）的關鍵路徑時序（Critical Path Latency）切入，比較 Pre-increment 與 Post-increment 在位址發送時脈週期上的硬體發送延遲。
• (d) 從暫存器檔案寫入埠（Register File Write Ports）、管線衝突（Pipeline Hazards）、亂序執行（Out-of-Order Execution）與精確例外復原（Precise Exception Recovery）四大面向說明硬體缺點。

---

子題詳解與分析

a) 偽指令的定義與優點 [2 pt.]

• 定義：偽指令（Pseudo Instruction）是指組合語言中允許編寫，但硬體 ISA 之中並未直接提供對應機器碼的指令。組譯器（Assembler）在編譯期間會自動將偽指令展開（Expand）或替換為一至多條真實的硬體實體指令（Real/Native Machine Instructions）。
• 優點：
  1. 提升程式可讀性與開發效率：提供高階語言般的簡潔語法（例如清零暫存器 CLR r1 替換為 AND r1, r1, #0；或載入 32 位元大常數 LDR r1, =0x12345678 展開為 MOVWT 序列），減少程式員手寫冗長指令鏈的需求。
  2. 簡化硬體控制邏輯：無需為了滿足多樣化程式語法而過度擴充硬體解碼器與執行單元，維護硬體 ISA 的精簡性（RISC 原則），同時在軟體層面保留開發便利性。
  3. 增強程式碼相容性與可移植性：組譯器可針對不同微架構版本，將同一條偽指令自動最佳化翻譯為最適當的硬體實體指令序列。

b) Pre-increment 與 Post-increment 實體指令的優點與適用高階語言結構 [3 pt.]

• 優點：
  1. 降低動態指令總數（Lower Dynamic Instruction Count）：將「記憶體存取」與「基底暫存器算術更新」整合至單一指令中。原本需兩條指令（如 LDR 加上 ADD）的操作簡化為一條指令完成，縮減程式碼體積（Code Density），降低指令快取（I-Cache）的 Miss Rate 並減輕 Fetch/Decode 單元負擔。
  2. 減少暫存器佔用：無需額外配置暫存器來暫存中間位址。
• 適用的高階語言結構：
  1. 指標與陣列連續存取迴圈（Pointer/Array Iteration Loops）：例如 C/C++ 中的 *p++（Post-increment）與 *++p（Pre-increment），以及 for/while 迴圈遍歷陣列、字串處理或 Buffer 資料搬移。
  2. 堆疊操作（Stack Operations）：函數呼叫時的參數傳遞與暫存器保護。Pre-decrement 對應 Push 操作（先遞減堆疊指標 SP 再寫入記憶體），Post-increment 對應 Pop 操作（先讀取記憶體資料再遞增堆疊指標 SP）。

c) Intel/HP Itanium 僅支援 Post-increment 而不支援 Pre-increment 的原因 [1 pt.]

核心觀念

1. 例外（Exception）與中斷（Interrupt）的區分（依據經典教材 Patterson & Hennessy / CS:APP）：

   • 中斷（Interrupt）：通常指由處理器外部硬體（I/O 裝置、定時器、網路卡等）非同步（Asynchronous）發出的事件，其發生與當前 CPU 正在執行的指令無直接因果關係。
   • 例外（Exception / Trap / Fault / Abort）：由處理器內部目前正在執行的指令所同步（Synchronous）觸發的非正常事件或軟體請求（例如除以零、非法記憶體存取、未定義指令、系統呼叫等）。
   • 註：在 Intel x86 術語中，Interrupt 為廣義統稱，分成 External Interrupt 與 Exception；在 MIPS/RISC-V 體系中，通常統稱 Exception，而外部事件稱為 Interrupt。但無論哪種體系，區分「內部同步事件」與「外部非同步事件」的核心準則完全一致。

2. 精確中斷／例外（Precise Exception）與微處理架構複雜度：

   • 處理例外時，處理器必須保存發生事件當下的機器狀態（Machine State），以維持程式執行的循序性語意（Sequential Semantics）：
     • 引起例外的指令之前的所有指令必須完全執行完畢並寫回結果。
     • 引起例外的指令之後（依程式邏輯順序）的所有指令均不得改變處理器架構狀態（Register File, Memory）。
   • 架構複雜度影響：
     • 若處理器支援循序退休（In-Order Commit），維持精確狀態相對單純。
     • 若處理器引入亂序執行（Out-of-Order）與推測執行（Speculative Execution），指令可能在未確認是否有例外前就亂序完成或在錯誤路徑上執行，需要依賴複雜的 Reorder Buffer（ROB）、暫存器重新命名（Register Renaming）以及狀態回滾（Rollback/Squash）機制來確保精確例外。
     • 記憶體階層架構（如 Data Cache）可能因例外發生後的快取狀態改變或未完成的記憶體存取請求增加硬體回復負擔。

---

解題方法

(a) 事件分類分析

以「觸發源是否為 CPU 內部執行指令（內部同步 $\rightarrow$ Exception）或外部裝置訊號（外部非同步 $\rightarrow$ Interrupt）」為切入點逐一判斷：

• Page fault：
  • 當指令嘗試存取虛擬位址，而分頁表中標記該頁不在實體記憶體（Present bit = 0）時，由 MMU 觸發。屬於內部指令引發的同步錯誤。$\rightarrow$ Exception (Fault)
• TLB miss：
  • 當指令嘗試進行位址轉譯，而在 TLB 中找不到對應項目時觸發。由當前指令存取引發。$\rightarrow$ Exception (在軟體處理 TLB 的架構中為 Exception Handler，在硬體處理中亦視為內部硬體例外事件)
• Floating point arithmetic underflow：
  • 浮點運算指令執行時，計算結果數值過小無法以正規浮點格式表示時產生。由該運算指令本身觸發。$\rightarrow$ Exception (Fault/Trap)
• I/O device request：
  • 由周邊裝置（鍵盤、磁碟控制器、網卡等）向中斷控制器發出的硬體訊號，與當前執行的指令無關。$\rightarrow$ Interrupt (Hardware Interrupt)
• Undefined instruction：
  • 譯碼單元（Decoder）遇到無法辨識或未實作的操作碼（Opcode）時觸發。由該特定指令引起。$\rightarrow$ Exception (Trap/Fault)
• User defined interrupt：
  • 雖然名稱帶有 interrupt，但常指軟體以程式碼或使用者定義的非同步/外部訊號機制；若視為外部可規劃中斷線，屬於 Interrupt；若指軟體產生的事件（如軟體中斷指令），本質為軟體陷阱。然而在標準計算機結構分類中，以其名稱明示之性質（硬體中斷線經由使用者/系統配置引腳觸發）歸類為中斷。$\rightarrow$ Interrupt
• Execution abort：
  • 通常由嚴重的硬體錯誤（如同位檢查錯誤 Parity Error、Machine Check）或無法復原的內部致命錯誤觸發，終止程式執行。在現代處理器（如 ARM/x86）中屬於同步或非同步引發的不可復原例外類型。$\rightarrow$ Exception (Abort)

核心觀念

1. 例外（Exception）與中斷（Interrupt）的區分（依據經典教材 Patterson & Hennessy / CS:APP）：

   • 中斷（Interrupt）：通常指由處理器外部硬體（I/O 裝置、定時器、網路卡等）非同步（Asynchronous）發出的事件，其發生與當前 CPU 正在執行的指令無直接因果關係。
   • 例外（Exception / Trap / Fault / Abort）：由處理器內部目前正在執行的指令所同步（Synchronous）觸發的非正常事件或軟體請求（例如除以零、非法記憶體存取、未定義指令、系統呼叫等）。
   • 註：在 Intel x86 術語中，Interrupt 為廣義統稱，分成 External Interrupt 與 Exception；在 MIPS/RISC-V 體系中，通常統稱 Exception，而外部事件稱為 Interrupt。但無論哪種體系，區分「內部同步事件」與「外部非同步事件」的核心準則完全一致。

2. 精確中斷／例外（Precise Exception）與微處理架構複雜度：

   • 處理例外時，處理器必須保存發生事件當下的機器狀態（Machine State），以維持程式執行的循序性語意（Sequential Semantics）：
     • 引起例外的指令之前的所有指令必須完全執行完畢並寫回結果。
     • 引起例外的指令之後（依程式邏輯順序）的所有指令均不得改變處理器架構狀態（Register File, Memory）。
   • 架構複雜度影響：
     • 若處理器支援循序退休（In-Order Commit），維持精確狀態相對單純。
     • 若處理器引入亂序執行（Out-of-Order）與推測執行（Speculative Execution），指令可能在未確認是否有例外前就亂序完成或在錯誤路徑上執行，需要依賴複雜的 Reorder Buffer（ROB）、暫存器重新命名（Register Renaming）以及狀態回滾（Rollback/Squash）機制來確保精確例外。
     • 記憶體階層架構（如 Data Cache）可能因例外發生後的快取狀態改變或未完成的記憶體存取請求增加硬體回復負擔。

---

解題方法

(a) 事件分類分析

以「觸發源是否為 CPU 內部執行指令（內部同步 $\rightarrow$ Exception）或外部裝置訊號（外部非同步 $\rightarrow$ Interrupt）」為切入點逐一判斷：

• Page fault：
  • 當指令嘗試存取虛擬位址，而分頁表中標記該頁不在實體記憶體（Present bit = 0）時，由 MMU 觸發。屬於內部指令引發的同步錯誤。$\rightarrow$ Exception (Fault)
• TLB miss：
  • 當指令嘗試進行位址轉譯，而在 TLB 中找不到對應項目時觸發。由當前指令存取引發。$\rightarrow$ Exception (在軟體處理 TLB 的架構中為 Exception Handler，在硬體處理中亦視為內部硬體例外事件)
• Floating point arithmetic underflow：
  • 浮點運算指令執行時，計算結果數值過小無法以正規浮點格式表示時產生。由該運算指令本身觸發。$\rightarrow$ Exception (Fault/Trap)
• I/O device request：
  • 由周邊裝置（鍵盤、磁碟控制器、網卡等）向中斷控制器發出的硬體訊號，與當前執行的指令無關。$\rightarrow$ Interrupt (Hardware Interrupt)
• Undefined instruction：
  • 譯碼單元（Decoder）遇到無法辨識或未實作的操作碼（Opcode）時觸發。由該特定指令引起。$\rightarrow$ Exception (Trap/Fault)
• User defined interrupt：
  • 雖然名稱帶有 interrupt，但常指軟體以程式碼或使用者定義的非同步/外部訊號機制；若視為外部可規劃中斷線，屬於 Interrupt；若指軟體產生的事件（如軟體中斷指令），本質為軟體陷阱。然而在標準計算機結構分類中，以其名稱明示之性質（硬體中斷線經由使用者/系統配置引腳觸發）歸類為中斷。$\rightarrow$ Interrupt
• Execution abort：
  • 通常由嚴重的硬體錯誤（如同位檢查錯誤 Parity Error、Machine Check）或無法復原的內部致命錯誤觸發，終止程式執行。在現代處理器（如 ARM/x86）中屬於同步或非同步引發的不可復原例外類型。$\rightarrow$ Exception (Abort)

核心觀念

本題考查處理器中的四種平行性：

縮寫	全名	中文意義	平行的主要對象
ILP	Instruction-Level Parallelism	指令層級平行性	同一執行緒中的多條指令
DLP	Data-Level Parallelism	資料層級平行性	同一操作套用到多筆資料
MLP	Memory-Level Parallelism	記憶體層級平行性	多個記憶體存取同時進行
TLP	Thread-Level Parallelism	執行緒層級平行性	多條執行緒同時執行

四者的差異在於「平行化的單位」不同：

• ILP：同一個程式、同一條執行緒中，找出彼此獨立的指令。
• DLP：同一個運算同時處理多筆資料。
• MLP：同時發出多個尚未完成的記憶體請求，以隱藏記憶體延遲。
• TLP：同時執行多個執行緒，通常需要多核心或硬體多執行緒支援。

---

解題方法

題目分成兩個方向：

1. 硬體／微架構技術：處理器如何在執行時期挖掘平行性。
2. 軟體技術：編譯器或程式設計者如何改寫程式，使可利用的平行性增加。

作答時，每個縮寫至少各提供一項硬體技術與一項軟體技術即可。

---

a) Acronyms 的意義

ILP：Instruction-Level Parallelism

指令層級平行性是指同一執行緒中，存在多條彼此沒有資料相依性的指令，因此可以同時發射或重疊執行。

例如：

R1 = R2 + R3
R4 = R5 + R6

兩條指令互不依賴，處理器便有機會同時執行。

---

DLP：Data-Level Parallelism

資料層級平行性是指相同的運算可以同時套用在多筆獨立資料上。

例如向量加法：

$$C[i] = A[i] + B[i]$$

對不同的 $i$ 而言，各次運算彼此獨立，因此可以一次處理多個元素。

---

MLP：Memory-Level Parallelism

記憶體層級平行性是指程式中存在多個彼此獨立的記憶體存取，處理器可以在前一個存取尚未完成時，繼續發出其他記憶體請求。

例如：

R1 = Memory[A]
R2 = Memory[B]
R3 = Memory[C]

若三個存取彼此獨立，便可同時等待多個 cache miss 或記憶體請求，以隱藏記憶體延遲。

---

TLP：Thread-Level Parallelism

執行緒層級平行性是指多條執行緒可同時執行。這些執行緒可以執行相同程式的不同資料，也可以執行不同工作。

例如將矩陣的不同列分配給不同執行緒：

$$\text{Thread}_0 \rightarrow \text{第 0 至 99 列}$$ $$\text{Thread}_1 \rightarrow \text{第 100 至 199 列}$$

---

b) 可有效利用各種平行性的硬體／微架構技術

ILP 的硬體技術

Superscalar 多發射處理器

Superscalar 處理器每個 clock cycle 可以發射多條指令。若指令之間沒有相依性，便能在同一週期交給不同功能單元執行。

Out-of-Order Execution 亂序執行

亂序執行會在不違反資料相依性的前提下，先執行已準備好的指令。例如前一條指令因等待記憶體而停頓時，處理器可先執行後方獨立指令。

常搭配：

• Reservation station
• Register renaming
• Reorder buffer
• Dynamic scheduling

這些機制可降低假相依性，並增加同時執行的指令數量。

硬體分支預測與投機執行

分支預測可提前猜測控制流程，先行抓取並執行預測路徑上的指令，避免處理器長時間等待分支結果，進而增加可重疊執行的指令數量。

---

DLP 的硬體技術

SIMD 指令

SIMD 是 Single Instruction, Multiple Data。單一指令同時對多個資料元素執行相同操作。

例如一條向量加法指令可以完成：

$$(C_0,C_1,C_2,C_3) = (A_0,A_1,A_2,A_3) + (B_0,B_1,B_2,B_3)$$

x86 的 SSE、AVX，以及 ARM 的 NEON 都屬於典型 SIMD 技術。

Vector Processor 向量處理器

向量處理器以向量暫存器與向量指令為基礎，使相同運算能連續套用到大量資料元素，適合矩陣、影像、科學計算等工作。

GPU 的大量平行運算單元

GPU 以大量運算核心同時處理資料，特別適合具有規則資料平行性的程式，例如影像處理、矩陣運算與深度學習。

---

MLP 的硬體技術

Non-blocking Cache

Non-blocking cache 允許 cache 正在處理某個 miss 時，繼續接受並處理其他記憶體請求，而不必讓整個 cache 完全停住。

多個 MSHR

MSHR，即 Miss Status Holding Register，用來記錄尚未完成的 cache miss。具有多個 MSHR 時，處理器可以同時追蹤多個 outstanding cache miss。

Out-of-Order Execution

亂序執行可在某個 load 因 cache miss 停頓時，先執行其他獨立的 load 或計算指令，藉此同時產生多個記憶體請求。

多層快取與硬體預取

多層 cache 可降低部分存取的延遲；硬體預取器則能在程式真正使用資料前，提前將資料載入 cache，使記憶體存取與計算重疊進行。

---

TLP 的硬體技術

多核心處理器

多核心處理器可讓不同核心同時執行不同執行緒。這是最直接的 TLP 實作方式。

SMT／Hyper-Threading

Simultaneous Multithreading 可讓同一個處理器核心同時維持多個硬體執行緒。當一條執行緒因 cache miss 或分支停頓時，核心可使用其他執行緒的指令填補執行資源。

多處理器與共享記憶體架構

核心觀念

本題考查處理器中的四種平行性：

縮寫	全名	中文意義	平行的主要對象
ILP	Instruction-Level Parallelism	指令層級平行性	同一執行緒中的多條指令
DLP	Data-Level Parallelism	資料層級平行性	同一操作套用到多筆資料
MLP	Memory-Level Parallelism	記憶體層級平行性	多個記憶體存取同時進行
TLP	Thread-Level Parallelism	執行緒層級平行性	多條執行緒同時執行

四者的差異在於「平行化的單位」不同：

• ILP：同一個程式、同一條執行緒中，找出彼此獨立的指令。
• DLP：同一個運算同時處理多筆資料。
• MLP：同時發出多個尚未完成的記憶體請求，以隱藏記憶體延遲。
• TLP：同時執行多個執行緒，通常需要多核心或硬體多執行緒支援。

---

解題方法

題目分成兩個方向：

1. 硬體／微架構技術：處理器如何在執行時期挖掘平行性。
2. 軟體技術：編譯器或程式設計者如何改寫程式，使可利用的平行性增加。

作答時，每個縮寫至少各提供一項硬體技術與一項軟體技術即可。

---

a) Acronyms 的意義

ILP：Instruction-Level Parallelism

指令層級平行性是指同一執行緒中，存在多條彼此沒有資料相依性的指令，因此可以同時發射或重疊執行。

例如：

R1 = R2 + R3
R4 = R5 + R6

兩條指令互不依賴，處理器便有機會同時執行。

---

DLP：Data-Level Parallelism

資料層級平行性是指相同的運算可以同時套用在多筆獨立資料上。

例如向量加法：

$$C[i] = A[i] + B[i]$$

對不同的 $i$ 而言，各次運算彼此獨立，因此可以一次處理多個元素。

---

MLP：Memory-Level Parallelism

記憶體層級平行性是指程式中存在多個彼此獨立的記憶體存取，處理器可以在前一個存取尚未完成時，繼續發出其他記憶體請求。

例如：

R1 = Memory[A]
R2 = Memory[B]
R3 = Memory[C]

若三個存取彼此獨立，便可同時等待多個 cache miss 或記憶體請求，以隱藏記憶體延遲。

---

TLP：Thread-Level Parallelism

執行緒層級平行性是指多條執行緒可同時執行。這些執行緒可以執行相同程式的不同資料，也可以執行不同工作。

例如將矩陣的不同列分配給不同執行緒：

$$\text{Thread}_0 \rightarrow \text{第 0 至 99 列}$$ $$\text{Thread}_1 \rightarrow \text{第 100 至 199 列}$$

---

b) 可有效利用各種平行性的硬體／微架構技術

ILP 的硬體技術

Superscalar 多發射處理器

Superscalar 處理器每個 clock cycle 可以發射多條指令。若指令之間沒有相依性，便能在同一週期交給不同功能單元執行。

Out-of-Order Execution 亂序執行

亂序執行會在不違反資料相依性的前提下，先執行已準備好的指令。例如前一條指令因等待記憶體而停頓時，處理器可先執行後方獨立指令。

常搭配：

• Reservation station
• Register renaming
• Reorder buffer
• Dynamic scheduling

這些機制可降低假相依性，並增加同時執行的指令數量。

硬體分支預測與投機執行

分支預測可提前猜測控制流程，先行抓取並執行預測路徑上的指令，避免處理器長時間等待分支結果，進而增加可重疊執行的指令數量。

---

DLP 的硬體技術

SIMD 指令

SIMD 是 Single Instruction, Multiple Data。單一指令同時對多個資料元素執行相同操作。

例如一條向量加法指令可以完成：

$$(C_0,C_1,C_2,C_3) = (A_0,A_1,A_2,A_3) + (B_0,B_1,B_2,B_3)$$

x86 的 SSE、AVX，以及 ARM 的 NEON 都屬於典型 SIMD 技術。

Vector Processor 向量處理器

向量處理器以向量暫存器與向量指令為基礎，使相同運算能連續套用到大量資料元素，適合矩陣、影像、科學計算等工作。

GPU 的大量平行運算單元

GPU 以大量運算核心同時處理資料，特別適合具有規則資料平行性的程式，例如影像處理、矩陣運算與深度學習。

---

MLP 的硬體技術

Non-blocking Cache

Non-blocking cache 允許 cache 正在處理某個 miss 時，繼續接受並處理其他記憶體請求，而不必讓整個 cache 完全停住。

多個 MSHR

MSHR，即 Miss Status Holding Register，用來記錄尚未完成的 cache miss。具有多個 MSHR 時，處理器可以同時追蹤多個 outstanding cache miss。

Out-of-Order Execution

亂序執行可在某個 load 因 cache miss 停頓時，先執行其他獨立的 load 或計算指令，藉此同時產生多個記憶體請求。

多層快取與硬體預取

多層 cache 可降低部分存取的延遲；硬體預取器則能在程式真正使用資料前，提前將資料載入 cache，使記憶體存取與計算重疊進行。

---

TLP 的硬體技術

多核心處理器

多核心處理器可讓不同核心同時執行不同執行緒。這是最直接的 TLP 實作方式。

SMT／Hyper-Threading

Simultaneous Multithreading 可讓同一個處理器核心同時維持多個硬體執行緒。當一條執行緒因 cache miss 或分支停頓時，核心可使用其他執行緒的指令填補執行資源。

多處理器與共享記憶體架構

核心觀念

本題考查處理器中的四種平行性：

縮寫	全名	中文意義	平行的主要對象
ILP	Instruction-Level Parallelism	指令層級平行性	同一執行緒中的多條指令
DLP	Data-Level Parallelism	資料層級平行性	同一操作套用到多筆資料
MLP	Memory-Level Parallelism	記憶體層級平行性	多個記憶體存取同時進行
TLP	Thread-Level Parallelism	執行緒層級平行性	多條執行緒同時執行

四者的差異在於「平行化的單位」不同：

• ILP：同一個程式、同一條執行緒中，找出彼此獨立的指令。
• DLP：同一個運算同時處理多筆資料。
• MLP：同時發出多個尚未完成的記憶體請求，以隱藏記憶體延遲。
• TLP：同時執行多個執行緒，通常需要多核心或硬體多執行緒支援。

---

解題方法

題目分成兩個方向：

1. 硬體／微架構技術：處理器如何在執行時期挖掘平行性。
2. 軟體技術：編譯器或程式設計者如何改寫程式，使可利用的平行性增加。

作答時，每個縮寫至少各提供一項硬體技術與一項軟體技術即可。

---

a) Acronyms 的意義

ILP：Instruction-Level Parallelism

指令層級平行性是指同一執行緒中，存在多條彼此沒有資料相依性的指令，因此可以同時發射或重疊執行。

例如：

R1 = R2 + R3
R4 = R5 + R6

兩條指令互不依賴，處理器便有機會同時執行。

---

DLP：Data-Level Parallelism

資料層級平行性是指相同的運算可以同時套用在多筆獨立資料上。

例如向量加法：

$$C[i] = A[i] + B[i]$$

對不同的 $i$ 而言，各次運算彼此獨立，因此可以一次處理多個元素。

---

MLP：Memory-Level Parallelism

記憶體層級平行性是指程式中存在多個彼此獨立的記憶體存取，處理器可以在前一個存取尚未完成時，繼續發出其他記憶體請求。

例如：

R1 = Memory[A]
R2 = Memory[B]
R3 = Memory[C]

若三個存取彼此獨立，便可同時等待多個 cache miss 或記憶體請求，以隱藏記憶體延遲。

---

TLP：Thread-Level Parallelism

執行緒層級平行性是指多條執行緒可同時執行。這些執行緒可以執行相同程式的不同資料，也可以執行不同工作。

例如將矩陣的不同列分配給不同執行緒：

$$\text{Thread}_0 \rightarrow \text{第 0 至 99 列}$$ $$\text{Thread}_1 \rightarrow \text{第 100 至 199 列}$$

---

b) 可有效利用各種平行性的硬體／微架構技術

ILP 的硬體技術

Superscalar 多發射處理器

Superscalar 處理器每個 clock cycle 可以發射多條指令。若指令之間沒有相依性，便能在同一週期交給不同功能單元執行。

Out-of-Order Execution 亂序執行

亂序執行會在不違反資料相依性的前提下，先執行已準備好的指令。例如前一條指令因等待記憶體而停頓時，處理器可先執行後方獨立指令。

常搭配：

• Reservation station
• Register renaming
• Reorder buffer
• Dynamic scheduling

這些機制可降低假相依性，並增加同時執行的指令數量。

硬體分支預測與投機執行

分支預測可提前猜測控制流程，先行抓取並執行預測路徑上的指令，避免處理器長時間等待分支結果，進而增加可重疊執行的指令數量。

---

DLP 的硬體技術

SIMD 指令

SIMD 是 Single Instruction, Multiple Data。單一指令同時對多個資料元素執行相同操作。

例如一條向量加法指令可以完成：

$$(C_0,C_1,C_2,C_3) = (A_0,A_1,A_2,A_3) + (B_0,B_1,B_2,B_3)$$

x86 的 SSE、AVX，以及 ARM 的 NEON 都屬於典型 SIMD 技術。

Vector Processor 向量處理器

向量處理器以向量暫存器與向量指令為基礎，使相同運算能連續套用到大量資料元素，適合矩陣、影像、科學計算等工作。

GPU 的大量平行運算單元

GPU 以大量運算核心同時處理資料，特別適合具有規則資料平行性的程式，例如影像處理、矩陣運算與深度學習。

---

MLP 的硬體技術

Non-blocking Cache

Non-blocking cache 允許 cache 正在處理某個 miss 時，繼續接受並處理其他記憶體請求，而不必讓整個 cache 完全停住。

多個 MSHR

MSHR，即 Miss Status Holding Register，用來記錄尚未完成的 cache miss。具有多個 MSHR 時，處理器可以同時追蹤多個 outstanding cache miss。

Out-of-Order Execution

亂序執行可在某個 load 因 cache miss 停頓時，先執行其他獨立的 load 或計算指令，藉此同時產生多個記憶體請求。

多層快取與硬體預取

多層 cache 可降低部分存取的延遲；硬體預取器則能在程式真正使用資料前，提前將資料載入 cache，使記憶體存取與計算重疊進行。

---

TLP 的硬體技術

多核心處理器

多核心處理器可讓不同核心同時執行不同執行緒。這是最直接的 TLP 實作方式。

SMT／Hyper-Threading

Simultaneous Multithreading 可讓同一個處理器核心同時維持多個硬體執行緒。當一條執行緒因 cache miss 或分支停頓時，核心可使用其他執行緒的指令填補執行資源。

多處理器與共享記憶體架構

核心觀念

本題探討現代行動裝置 SoC（如 ARM big.LITTLE / DynamIQ 架構）的**異質多核心架構（Heterogeneous Multi-Core Architecture）與快取一致性（Cache Coherence）**機制：

1. 異質運算能效平衡（Energy-Performance Trade-off）：
   • Big core（大核）：具備深管線、超純量（Out-of-Order superscalar）執行能力，性能強大但靜態漏電與動態功耗極高。
   • Little core（小核）：採用循序執行（In-Order）或淺管線架構，能源效率高，負責背景常駐服務或輕量運算。
   • 行動裝置受限於熱設計功耗（TDP, Thermal Design Power，通常智慧型手機上限為 $3\text{ W} \sim 5\text{ W}$）以及電池容量限制，多數時間處於輕負載或待機狀態，高運算需求的 Burst 工作階段佔比極低。
2. 多叢集快取一致性（Multi-Cluster Cache Coherence）：
   • 當系統分為不同的 CPU Cluster 時，各 Cluster 內部擁有私有的 L1/L2 快取，若多個核心存取相同實體位址的資料，必須維護快取一致性（Data Consistency），避免讀取到過期（Stale）資料。
   • 跨叢集架構通常依賴**一致性互連匯流排（Coherent Interconnect Bus）與監聽濾波器（Snoop Filter / Directory-based protocol）**來維持一致性，並串接共享的末級快取（LLC / L3 Cache）。

---

解題方法

(a) 評估 $B_{2020} = 6$ 與 $L_{2020} = 2$ 的合理性

• 切入點：從行動裝置的「負載型態（Workload Profile）」、「熱設計功耗（TDP）與散熱限制」、「晶片面積與製造成本（Die Area & Cost）」進行綜合評估。
• 分析與推導：
  1. 功耗與散熱限制（Thermal Throttling）：手機無法安裝主動散熱風扇，Passive Cooling 下的持續功耗極限約在 $3\text{ W} \sim 5\text{ W}$。若配置 6 個大核心，同時滿載時必定超出功耗牆，系統會迅速觸發動態電壓頻率調整（DVFS）進行降頻（Throttling），導致 6 個大核心無法發揮預期效能，反而徒增成本與晶片面積。
  2. 智慧型手機工作負載特性：智慧型手機 $80\%$ 以上的時間處於螢幕關閉、背景音訊播放、訊息推播接收或輕量 UI 滑動等低負載狀態。僅有 2 個小核心會導致背景常駐負載過早溢流（Spill over）至大核執行，大幅增加靜態待機耗電量，縮短電池續航。
  3. 實務設計驗證：主流旗艦晶片（如 Snapdragon 855/865 架構）多採用「1 超大核 + 3 大核 + 4 小核」或「2 大核 + 6 小核」的比例，維持充足的小核數量以確保待機省電，絕不會採用「大核遠多於小核（6B + 2L）」的配置。
• 結論：應持反對意見（Object to it）。

(b) 跨叢集快取一致性的成因與實作機制

• Why（成因與必要性）：
  1. 快取私有性與資料不一致問題：CPU_CLUSTERbig 與 CPU_CLUSTERlittle 內部各自擁有私有的 L1 Data Cache（甚至私有 L2 Cache）。
  2. 緒移轉（Thread Migration）與共享資料：在 Global Task Scheduling（GTS / HMP）排程下，作業系統會動態將工作由小核移交給大核（或反之），或跨叢集的執行緒共享記憶體變數。若 Cluster A 寫入變數至私有快取而未同步，Cluster B 讀取時將獲得陳舊（Stale）數據，造成記憶體語意錯誤。
• How（維護快取一致性的具體作法）：
  1. 硬體一致性互連技術（Coherent Interconnect）：
     • 在兩叢集之間設置支援一致性協議的互連匯流排（如 ARM CoreLink CCI-400 / CCI-500 或 CCN / CMN）。
     • 互連架構運行硬體快取一致性協議（如 MOESI 或 MESI 延伸協議）。
  2. Snoop Controller / Snoop Filter（監聽與過濾機制）：

核心觀念

本題探討現代行動裝置 SoC（如 ARM big.LITTLE / DynamIQ 架構）的**異質多核心架構（Heterogeneous Multi-Core Architecture）與快取一致性（Cache Coherence）**機制：

1. 異質運算能效平衡（Energy-Performance Trade-off）：
   • Big core（大核）：具備深管線、超純量（Out-of-Order superscalar）執行能力，性能強大但靜態漏電與動態功耗極高。
   • Little core（小核）：採用循序執行（In-Order）或淺管線架構，能源效率高，負責背景常駐服務或輕量運算。
   • 行動裝置受限於熱設計功耗（TDP, Thermal Design Power，通常智慧型手機上限為 $3\text{ W} \sim 5\text{ W}$）以及電池容量限制，多數時間處於輕負載或待機狀態，高運算需求的 Burst 工作階段佔比極低。
2. 多叢集快取一致性（Multi-Cluster Cache Coherence）：
   • 當系統分為不同的 CPU Cluster 時，各 Cluster 內部擁有私有的 L1/L2 快取，若多個核心存取相同實體位址的資料，必須維護快取一致性（Data Consistency），避免讀取到過期（Stale）資料。
   • 跨叢集架構通常依賴**一致性互連匯流排（Coherent Interconnect Bus）與監聽濾波器（Snoop Filter / Directory-based protocol）**來維持一致性，並串接共享的末級快取（LLC / L3 Cache）。

---

解題方法

(a) 評估 $B_{2020} = 6$ 與 $L_{2020} = 2$ 的合理性

• 切入點：從行動裝置的「負載型態（Workload Profile）」、「熱設計功耗（TDP）與散熱限制」、「晶片面積與製造成本（Die Area & Cost）」進行綜合評估。
• 分析與推導：
  1. 功耗與散熱限制（Thermal Throttling）：手機無法安裝主動散熱風扇，Passive Cooling 下的持續功耗極限約在 $3\text{ W} \sim 5\text{ W}$。若配置 6 個大核心，同時滿載時必定超出功耗牆，系統會迅速觸發動態電壓頻率調整（DVFS）進行降頻（Throttling），導致 6 個大核心無法發揮預期效能，反而徒增成本與晶片面積。
  2. 智慧型手機工作負載特性：智慧型手機 $80\%$ 以上的時間處於螢幕關閉、背景音訊播放、訊息推播接收或輕量 UI 滑動等低負載狀態。僅有 2 個小核心會導致背景常駐負載過早溢流（Spill over）至大核執行，大幅增加靜態待機耗電量，縮短電池續航。
  3. 實務設計驗證：主流旗艦晶片（如 Snapdragon 855/865 架構）多採用「1 超大核 + 3 大核 + 4 小核」或「2 大核 + 6 小核」的比例，維持充足的小核數量以確保待機省電，絕不會採用「大核遠多於小核（6B + 2L）」的配置。
• 結論：應持反對意見（Object to it）。

(b) 跨叢集快取一致性的成因與實作機制

• Why（成因與必要性）：
  1. 快取私有性與資料不一致問題：CPU_CLUSTERbig 與 CPU_CLUSTERlittle 內部各自擁有私有的 L1 Data Cache（甚至私有 L2 Cache）。
  2. 緒移轉（Thread Migration）與共享資料：在 Global Task Scheduling（GTS / HMP）排程下，作業系統會動態將工作由小核移交給大核（或反之），或跨叢集的執行緒共享記憶體變數。若 Cluster A 寫入變數至私有快取而未同步，Cluster B 讀取時將獲得陳舊（Stale）數據，造成記憶體語意錯誤。
• How（維護快取一致性的具體作法）：
  1. 硬體一致性互連技術（Coherent Interconnect）：
     • 在兩叢集之間設置支援一致性協議的互連匯流排（如 ARM CoreLink CCI-400 / CCI-500 或 CCN / CMN）。
     • 互連架構運行硬體快取一致性協議（如 MOESI 或 MESI 延伸協議）。
  2. Snoop Controller / Snoop Filter（監聽與過濾機制）：

本題涵蓋作業系統（Operating Systems）兩大核心考點：權限管理機制（Access Control & UIDs）與多工作業機制（Multi-tasking: Processes vs. Threads）。

1. 使用者識別碼（User Identifiers, UIDs）機制：
   • Unix/Linux 作業系統採用存取控制機制對行程（Process）進行資源存取檢查。
   • 個別行程內部維護三組關鍵 UID 位元：Real UID (RUID)、Effective UID (EUID) 以及 Saved UID (SUID)，用以兼顧身分識別、最小權限原則（Principle of Least Privilege）與動態權限切換。
2. 多行程（Multi-process）與多執行緒（Multi-thread）之架構差異：
   • 記憶體空間：行程擁有獨立的虛擬位址空間（Virtual Address Space）；執行緒共享同一行程之虛擬位址空間。
   • CPU 排程與 Context Switch：行程切換需替換頁表（Page Table Base Register，如 x86 之 CR3）並刷洗／標記 TLB，負擔巨大；執行緒切換僅需保存／恢復暫存器與 Stack Pointer，開銷極低。
   • 資源共享與溝通：行程間需透過 IPC（Inter-Process Communication）與 MMU 保護障壁互動；執行緒間可直接存取全域變數與 Heap，但需仰賴同步機制（Synchronization Primitives）。
3. fork() 系統呼叫與寫入時複製（Copy-on-Write, COW）：
   • fork() 創建子行程時會複製父行程的頁表，使父子行程在初始階段共享相同的物理記憶體頁面（Physical Memory Pages）。
   • 程式碼中所印出的位址為**虛擬位址（Virtual Address）**而非物理位址。
   • 當子行程試圖修改資料時，MMU 會觸發 Page Fault，作業系統隨即執行寫入時複製（COW），配置新的物理頁面給子行程，確保父子行程位址空間之隔離性與獨立性。

---

解題方法

針對本題各子題之切入點與解析步驟如下：

1. 子題 a-1 觀念拆解：
   • 分別定義 RUID、EUID、SUID 的建立時機、主要功能與彼此間的轉換關係。說明三者在權限檢查與 setuid 程式執行時的運作邏輯。
2. 子題 a-2 權限請求切入：
   • 根據 Linux/Unix Kernel 在進行檔案或系統資源存取檢查（access()、open() 等）時的依據，精確指出何者為 Kernel 存取控制（Access Control）的判定標的。
3. 子題 b-1 三維度比較：
   • 從「記憶體使用量（Memory Usages）」、「CPU 排程與切換開銷（CPU Scheduling）」與「資源共享與通訊（Resource Sharing）」三個層面，條理化地對比多行程與多執行緒。
4. 子題 b-2 程式碼執行追蹤與 COW 分析：
   • 追蹤 fork() 後父子行程的分歧執行路徑。分析子行程修改 sharedVariable 對父行程記憶體空間的影響，結合 Copy-on-Write 機制說明 Line 24 的變數數值。
5. 子題 b-3 虛擬位址映射分析：
   • 解析 %p 印出之位址本質（虛擬位址）。說明 fork() 複製頁表後，父子行程在各自的虛擬位址空間中變數配置位址相同的原因。

---

題目詳解

(a) 存取控制與使用者識別碼 (User IDs)

1) Real UID, Effective UID, Saved UID 之性質與差異

在 Unix/Linux 系統中，每個行程（Process）皆維護三組與使用者身份相關的憑證（Credentials）：

• Real UID (RUID，真實使用者識別碼)：
  • 性質：代表開啟該行程的真實使用者身分（即登入系統或啟動該行程的使用者 ID）。
  • 作用：主要用於會計（Accounting）與追蹤行程擁有者。在一般情況下，子行程會繼承父行程的 RUID。只有具備 CAP_SETUID 權限（如 root）的行程才能修改 RUID。
• Effective UID (EUID，有效使用者識別碼)：
  • 性質：作業系統核心（Kernel）在進行任何資源存取檢查（Access Control Check）時所依據的 UID。
  • 作用：決定行程在該瞬間對檔案、裝置、系統呼叫等資源的存取權限。當執行帶有 Set-User-ID (SUID) 權限位元的執行檔（例如 /usr/bin/passwd）時，EUID 會被核心自動變更為該執行檔擁有者（File Owner）的 UID。
• Saved set-user-ID (SUID / Saved UID，保存使用者識別碼)：
  • 性質：在行程執行 execve() 載入新程式時，核心會將變更後的 EUID 複製一份並保存於 SUID 中。
  • 作用：作為高權限行程暫時降權（Temporary Drop of Privilege）後重新恢復權限的備份。行程可藉由 setuid() 系統呼叫將 EUID 在 RUID 與 SUID 之間切換。例如特權行程可先將 EUID 降為普通使用者的 RUID 以安全執行非特權操作，需要存取特權資源時再將 EUID 恢復為 SUID 所保存的高權限 UID。

三者差異對照表：

識別碼類型	決定時機與來源	核心主要用途	可切換範圍（非 root 行程）
Real UID (RUID)	登入或啟動行程時確定	標示行程的所有權者	固定不可變
Effective UID (EUID)	執行時確定（受 setuid bit 影響）	核心檢查存取權限的唯一依據	可切換為 RUID 或 SUID
Saved UID (SUID)	execve() 執行時備份當時的 EUID	保存最高初始權限以備恢復	固定（等於載入時的 EUID）

---

2) 行程需要額外資源存取權限時應變更之識別碼

當一個行程需要額外的權限以存取特定資源時，必須變更 Effective UID (EUID)。

原因說明：
作業系統核心在執行存取控制檢查（Access Control Checks）時，完全根據行程當下的 EUID 與 EGID (Effective Group ID) 進行比對與判定。因此，若行程欲取得額外存取權限（例如存取僅限 root 讀寫的檔案），必須透過 setuid() 或 seteuid() 等系統呼叫，將其 EUID 設定為擁有該資源存取權限的使用者 ID（例如 root 的 UID 0，前提為 SUID 或 RUID 已包含該特權）。

---

(b) 多工作業系統：多行程與多執行緒機制

1) 多行程 (Multi-process) 與多執行緒 (Multi-thread) 比較

從記憶體使用量、CPU 排程與資源共享三個面向比較如下：

1. 記憶體使用量 (Memory Usages)：
   • 多行程 (Multi-process)：每個行程擁有獨立且完整的虛擬位址空間（包含 Text/Code, Data, BSS, Heap, Stack）以及獨立的頁表（Page Table）。記憶體開銷大，空間利用率較低。
   • 多執行緒 (Multi-thread)：同屬一個行程的所有執行緒共享該行程的虛擬位址空間（Code, Data, Heap 與全域變數），每個執行緒僅需擁有私有的 Stack、暫存器集合（Register Set）與 Thread-Local Storage (TLS)。記憶體開銷極小。
2. CPU 排程與上下文切換 (CPU Scheduling & Context Switch)：

本題涵蓋作業系統（Operating Systems）兩大核心考點：權限管理機制（Access Control & UIDs）與多工作業機制（Multi-tasking: Processes vs. Threads）。

1. 使用者識別碼（User Identifiers, UIDs）機制：
   • Unix/Linux 作業系統採用存取控制機制對行程（Process）進行資源存取檢查。
   • 個別行程內部維護三組關鍵 UID 位元：Real UID (RUID)、Effective UID (EUID) 以及 Saved UID (SUID)，用以兼顧身分識別、最小權限原則（Principle of Least Privilege）與動態權限切換。
2. 多行程（Multi-process）與多執行緒（Multi-thread）之架構差異：
   • 記憶體空間：行程擁有獨立的虛擬位址空間（Virtual Address Space）；執行緒共享同一行程之虛擬位址空間。
   • CPU 排程與 Context Switch：行程切換需替換頁表（Page Table Base Register，如 x86 之 CR3）並刷洗／標記 TLB，負擔巨大；執行緒切換僅需保存／恢復暫存器與 Stack Pointer，開銷極低。
   • 資源共享與溝通：行程間需透過 IPC（Inter-Process Communication）與 MMU 保護障壁互動；執行緒間可直接存取全域變數與 Heap，但需仰賴同步機制（Synchronization Primitives）。
3. fork() 系統呼叫與寫入時複製（Copy-on-Write, COW）：
   • fork() 創建子行程時會複製父行程的頁表，使父子行程在初始階段共享相同的物理記憶體頁面（Physical Memory Pages）。
   • 程式碼中所印出的位址為**虛擬位址（Virtual Address）**而非物理位址。
   • 當子行程試圖修改資料時，MMU 會觸發 Page Fault，作業系統隨即執行寫入時複製（COW），配置新的物理頁面給子行程，確保父子行程位址空間之隔離性與獨立性。

---

解題方法

針對本題各子題之切入點與解析步驟如下：

1. 子題 a-1 觀念拆解：
   • 分別定義 RUID、EUID、SUID 的建立時機、主要功能與彼此間的轉換關係。說明三者在權限檢查與 setuid 程式執行時的運作邏輯。
2. 子題 a-2 權限請求切入：
   • 根據 Linux/Unix Kernel 在進行檔案或系統資源存取檢查（access()、open() 等）時的依據，精確指出何者為 Kernel 存取控制（Access Control）的判定標的。
3. 子題 b-1 三維度比較：
   • 從「記憶體使用量（Memory Usages）」、「CPU 排程與切換開銷（CPU Scheduling）」與「資源共享與通訊（Resource Sharing）」三個層面，條理化地對比多行程與多執行緒。
4. 子題 b-2 程式碼執行追蹤與 COW 分析：
   • 追蹤 fork() 後父子行程的分歧執行路徑。分析子行程修改 sharedVariable 對父行程記憶體空間的影響，結合 Copy-on-Write 機制說明 Line 24 的變數數值。
5. 子題 b-3 虛擬位址映射分析：
   • 解析 %p 印出之位址本質（虛擬位址）。說明 fork() 複製頁表後，父子行程在各自的虛擬位址空間中變數配置位址相同的原因。

---

題目詳解

(a) 存取控制與使用者識別碼 (User IDs)

1) Real UID, Effective UID, Saved UID 之性質與差異

在 Unix/Linux 系統中，每個行程（Process）皆維護三組與使用者身份相關的憑證（Credentials）：

• Real UID (RUID，真實使用者識別碼)：
  • 性質：代表開啟該行程的真實使用者身分（即登入系統或啟動該行程的使用者 ID）。
  • 作用：主要用於會計（Accounting）與追蹤行程擁有者。在一般情況下，子行程會繼承父行程的 RUID。只有具備 CAP_SETUID 權限（如 root）的行程才能修改 RUID。
• Effective UID (EUID，有效使用者識別碼)：
  • 性質：作業系統核心（Kernel）在進行任何資源存取檢查（Access Control Check）時所依據的 UID。
  • 作用：決定行程在該瞬間對檔案、裝置、系統呼叫等資源的存取權限。當執行帶有 Set-User-ID (SUID) 權限位元的執行檔（例如 /usr/bin/passwd）時，EUID 會被核心自動變更為該執行檔擁有者（File Owner）的 UID。
• Saved set-user-ID (SUID / Saved UID，保存使用者識別碼)：
  • 性質：在行程執行 execve() 載入新程式時，核心會將變更後的 EUID 複製一份並保存於 SUID 中。
  • 作用：作為高權限行程暫時降權（Temporary Drop of Privilege）後重新恢復權限的備份。行程可藉由 setuid() 系統呼叫將 EUID 在 RUID 與 SUID 之間切換。例如特權行程可先將 EUID 降為普通使用者的 RUID 以安全執行非特權操作，需要存取特權資源時再將 EUID 恢復為 SUID 所保存的高權限 UID。

三者差異對照表：

識別碼類型	決定時機與來源	核心主要用途	可切換範圍（非 root 行程）
Real UID (RUID)	登入或啟動行程時確定	標示行程的所有權者	固定不可變
Effective UID (EUID)	執行時確定（受 setuid bit 影響）	核心檢查存取權限的唯一依據	可切換為 RUID 或 SUID
Saved UID (SUID)	execve() 執行時備份當時的 EUID	保存最高初始權限以備恢復	固定（等於載入時的 EUID）

---

2) 行程需要額外資源存取權限時應變更之識別碼

當一個行程需要額外的權限以存取特定資源時，必須變更 Effective UID (EUID)。

原因說明：
作業系統核心在執行存取控制檢查（Access Control Checks）時，完全根據行程當下的 EUID 與 EGID (Effective Group ID) 進行比對與判定。因此，若行程欲取得額外存取權限（例如存取僅限 root 讀寫的檔案），必須透過 setuid() 或 seteuid() 等系統呼叫，將其 EUID 設定為擁有該資源存取權限的使用者 ID（例如 root 的 UID 0，前提為 SUID 或 RUID 已包含該特權）。

---

(b) 多工作業系統：多行程與多執行緒機制

1) 多行程 (Multi-process) 與多執行緒 (Multi-thread) 比較

從記憶體使用量、CPU 排程與資源共享三個面向比較如下：

1. 記憶體使用量 (Memory Usages)：
   • 多行程 (Multi-process)：每個行程擁有獨立且完整的虛擬位址空間（包含 Text/Code, Data, BSS, Heap, Stack）以及獨立的頁表（Page Table）。記憶體開銷大，空間利用率較低。
   • 多執行緒 (Multi-thread)：同屬一個行程的所有執行緒共享該行程的虛擬位址空間（Code, Data, Heap 與全域變數），每個執行緒僅需擁有私有的 Stack、暫存器集合（Register Set）與 Thread-Local Storage (TLS)。記憶體開銷極小。
2. CPU 排程與上下文切換 (CPU Scheduling & Context Switch)：

本題涵蓋作業系統（Operating Systems）兩大核心考點：權限管理機制（Access Control & UIDs）與多工作業機制（Multi-tasking: Processes vs. Threads）。

1. 使用者識別碼（User Identifiers, UIDs）機制：
   • Unix/Linux 作業系統採用存取控制機制對行程（Process）進行資源存取檢查。
   • 個別行程內部維護三組關鍵 UID 位元：Real UID (RUID)、Effective UID (EUID) 以及 Saved UID (SUID)，用以兼顧身分識別、最小權限原則（Principle of Least Privilege）與動態權限切換。
2. 多行程（Multi-process）與多執行緒（Multi-thread）之架構差異：
   • 記憶體空間：行程擁有獨立的虛擬位址空間（Virtual Address Space）；執行緒共享同一行程之虛擬位址空間。
   • CPU 排程與 Context Switch：行程切換需替換頁表（Page Table Base Register，如 x86 之 CR3）並刷洗／標記 TLB，負擔巨大；執行緒切換僅需保存／恢復暫存器與 Stack Pointer，開銷極低。
   • 資源共享與溝通：行程間需透過 IPC（Inter-Process Communication）與 MMU 保護障壁互動；執行緒間可直接存取全域變數與 Heap，但需仰賴同步機制（Synchronization Primitives）。
3. fork() 系統呼叫與寫入時複製（Copy-on-Write, COW）：
   • fork() 創建子行程時會複製父行程的頁表，使父子行程在初始階段共享相同的物理記憶體頁面（Physical Memory Pages）。
   • 程式碼中所印出的位址為**虛擬位址（Virtual Address）**而非物理位址。
   • 當子行程試圖修改資料時，MMU 會觸發 Page Fault，作業系統隨即執行寫入時複製（COW），配置新的物理頁面給子行程，確保父子行程位址空間之隔離性與獨立性。

---

解題方法

針對本題各子題之切入點與解析步驟如下：

1. 子題 a-1 觀念拆解：
   • 分別定義 RUID、EUID、SUID 的建立時機、主要功能與彼此間的轉換關係。說明三者在權限檢查與 setuid 程式執行時的運作邏輯。
2. 子題 a-2 權限請求切入：
   • 根據 Linux/Unix Kernel 在進行檔案或系統資源存取檢查（access()、open() 等）時的依據，精確指出何者為 Kernel 存取控制（Access Control）的判定標的。
3. 子題 b-1 三維度比較：
   • 從「記憶體使用量（Memory Usages）」、「CPU 排程與切換開銷（CPU Scheduling）」與「資源共享與通訊（Resource Sharing）」三個層面，條理化地對比多行程與多執行緒。
4. 子題 b-2 程式碼執行追蹤與 COW 分析：
   • 追蹤 fork() 後父子行程的分歧執行路徑。分析子行程修改 sharedVariable 對父行程記憶體空間的影響，結合 Copy-on-Write 機制說明 Line 24 的變數數值。
5. 子題 b-3 虛擬位址映射分析：
   • 解析 %p 印出之位址本質（虛擬位址）。說明 fork() 複製頁表後，父子行程在各自的虛擬位址空間中變數配置位址相同的原因。

---

題目詳解

(a) 存取控制與使用者識別碼 (User IDs)

1) Real UID, Effective UID, Saved UID 之性質與差異

在 Unix/Linux 系統中，每個行程（Process）皆維護三組與使用者身份相關的憑證（Credentials）：

• Real UID (RUID，真實使用者識別碼)：
  • 性質：代表開啟該行程的真實使用者身分（即登入系統或啟動該行程的使用者 ID）。
  • 作用：主要用於會計（Accounting）與追蹤行程擁有者。在一般情況下，子行程會繼承父行程的 RUID。只有具備 CAP_SETUID 權限（如 root）的行程才能修改 RUID。
• Effective UID (EUID，有效使用者識別碼)：
  • 性質：作業系統核心（Kernel）在進行任何資源存取檢查（Access Control Check）時所依據的 UID。
  • 作用：決定行程在該瞬間對檔案、裝置、系統呼叫等資源的存取權限。當執行帶有 Set-User-ID (SUID) 權限位元的執行檔（例如 /usr/bin/passwd）時，EUID 會被核心自動變更為該執行檔擁有者（File Owner）的 UID。
• Saved set-user-ID (SUID / Saved UID，保存使用者識別碼)：
  • 性質：在行程執行 execve() 載入新程式時，核心會將變更後的 EUID 複製一份並保存於 SUID 中。
  • 作用：作為高權限行程暫時降權（Temporary Drop of Privilege）後重新恢復權限的備份。行程可藉由 setuid() 系統呼叫將 EUID 在 RUID 與 SUID 之間切換。例如特權行程可先將 EUID 降為普通使用者的 RUID 以安全執行非特權操作，需要存取特權資源時再將 EUID 恢復為 SUID 所保存的高權限 UID。

三者差異對照表：

識別碼類型	決定時機與來源	核心主要用途	可切換範圍（非 root 行程）
Real UID (RUID)	登入或啟動行程時確定	標示行程的所有權者	固定不可變
Effective UID (EUID)	執行時確定（受 setuid bit 影響）	核心檢查存取權限的唯一依據	可切換為 RUID 或 SUID
Saved UID (SUID)	execve() 執行時備份當時的 EUID	保存最高初始權限以備恢復	固定（等於載入時的 EUID）

---

2) 行程需要額外資源存取權限時應變更之識別碼

當一個行程需要額外的權限以存取特定資源時，必須變更 Effective UID (EUID)。

原因說明：
作業系統核心在執行存取控制檢查（Access Control Checks）時，完全根據行程當下的 EUID 與 EGID (Effective Group ID) 進行比對與判定。因此，若行程欲取得額外存取權限（例如存取僅限 root 讀寫的檔案），必須透過 setuid() 或 seteuid() 等系統呼叫，將其 EUID 設定為擁有該資源存取權限的使用者 ID（例如 root 的 UID 0，前提為 SUID 或 RUID 已包含該特權）。

---

(b) 多工作業系統：多行程與多執行緒機制

1) 多行程 (Multi-process) 與多執行緒 (Multi-thread) 比較

從記憶體使用量、CPU 排程與資源共享三個面向比較如下：

1. 記憶體使用量 (Memory Usages)：
   • 多行程 (Multi-process)：每個行程擁有獨立且完整的虛擬位址空間（包含 Text/Code, Data, BSS, Heap, Stack）以及獨立的頁表（Page Table）。記憶體開銷大，空間利用率較低。
   • 多執行緒 (Multi-thread)：同屬一個行程的所有執行緒共享該行程的虛擬位址空間（Code, Data, Heap 與全域變數），每個執行緒僅需擁有私有的 Stack、暫存器集合（Register Set）與 Thread-Local Storage (TLS)。記憶體開銷極小。
2. CPU 排程與上下文切換 (CPU Scheduling & Context Switch)：

本題涵蓋作業系統（Operating Systems）兩大核心考點：權限管理機制（Access Control & UIDs）與多工作業機制（Multi-tasking: Processes vs. Threads）。

1. 使用者識別碼（User Identifiers, UIDs）機制：
   • Unix/Linux 作業系統採用存取控制機制對行程（Process）進行資源存取檢查。
   • 個別行程內部維護三組關鍵 UID 位元：Real UID (RUID)、Effective UID (EUID) 以及 Saved UID (SUID)，用以兼顧身分識別、最小權限原則（Principle of Least Privilege）與動態權限切換。
2. 多行程（Multi-process）與多執行緒（Multi-thread）之架構差異：
   • 記憶體空間：行程擁有獨立的虛擬位址空間（Virtual Address Space）；執行緒共享同一行程之虛擬位址空間。
   • CPU 排程與 Context Switch：行程切換需替換頁表（Page Table Base Register，如 x86 之 CR3）並刷洗／標記 TLB，負擔巨大；執行緒切換僅需保存／恢復暫存器與 Stack Pointer，開銷極低。
   • 資源共享與溝通：行程間需透過 IPC（Inter-Process Communication）與 MMU 保護障壁互動；執行緒間可直接存取全域變數與 Heap，但需仰賴同步機制（Synchronization Primitives）。
3. fork() 系統呼叫與寫入時複製（Copy-on-Write, COW）：
   • fork() 創建子行程時會複製父行程的頁表，使父子行程在初始階段共享相同的物理記憶體頁面（Physical Memory Pages）。
   • 程式碼中所印出的位址為**虛擬位址（Virtual Address）**而非物理位址。
   • 當子行程試圖修改資料時，MMU 會觸發 Page Fault，作業系統隨即執行寫入時複製（COW），配置新的物理頁面給子行程，確保父子行程位址空間之隔離性與獨立性。

---

解題方法

針對本題各子題之切入點與解析步驟如下：

1. 子題 a-1 觀念拆解：
   • 分別定義 RUID、EUID、SUID 的建立時機、主要功能與彼此間的轉換關係。說明三者在權限檢查與 setuid 程式執行時的運作邏輯。
2. 子題 a-2 權限請求切入：
   • 根據 Linux/Unix Kernel 在進行檔案或系統資源存取檢查（access()、open() 等）時的依據，精確指出何者為 Kernel 存取控制（Access Control）的判定標的。
3. 子題 b-1 三維度比較：
   • 從「記憶體使用量（Memory Usages）」、「CPU 排程與切換開銷（CPU Scheduling）」與「資源共享與通訊（Resource Sharing）」三個層面，條理化地對比多行程與多執行緒。
4. 子題 b-2 程式碼執行追蹤與 COW 分析：
   • 追蹤 fork() 後父子行程的分歧執行路徑。分析子行程修改 sharedVariable 對父行程記憶體空間的影響，結合 Copy-on-Write 機制說明 Line 24 的變數數值。
5. 子題 b-3 虛擬位址映射分析：
   • 解析 %p 印出之位址本質（虛擬位址）。說明 fork() 複製頁表後，父子行程在各自的虛擬位址空間中變數配置位址相同的原因。

---

題目詳解

(a) 存取控制與使用者識別碼 (User IDs)

1) Real UID, Effective UID, Saved UID 之性質與差異

在 Unix/Linux 系統中，每個行程（Process）皆維護三組與使用者身份相關的憑證（Credentials）：

• Real UID (RUID，真實使用者識別碼)：
  • 性質：代表開啟該行程的真實使用者身分（即登入系統或啟動該行程的使用者 ID）。
  • 作用：主要用於會計（Accounting）與追蹤行程擁有者。在一般情況下，子行程會繼承父行程的 RUID。只有具備 CAP_SETUID 權限（如 root）的行程才能修改 RUID。
• Effective UID (EUID，有效使用者識別碼)：
  • 性質：作業系統核心（Kernel）在進行任何資源存取檢查（Access Control Check）時所依據的 UID。
  • 作用：決定行程在該瞬間對檔案、裝置、系統呼叫等資源的存取權限。當執行帶有 Set-User-ID (SUID) 權限位元的執行檔（例如 /usr/bin/passwd）時，EUID 會被核心自動變更為該執行檔擁有者（File Owner）的 UID。
• Saved set-user-ID (SUID / Saved UID，保存使用者識別碼)：
  • 性質：在行程執行 execve() 載入新程式時，核心會將變更後的 EUID 複製一份並保存於 SUID 中。
  • 作用：作為高權限行程暫時降權（Temporary Drop of Privilege）後重新恢復權限的備份。行程可藉由 setuid() 系統呼叫將 EUID 在 RUID 與 SUID 之間切換。例如特權行程可先將 EUID 降為普通使用者的 RUID 以安全執行非特權操作，需要存取特權資源時再將 EUID 恢復為 SUID 所保存的高權限 UID。

三者差異對照表：

識別碼類型	決定時機與來源	核心主要用途	可切換範圍（非 root 行程）
Real UID (RUID)	登入或啟動行程時確定	標示行程的所有權者	固定不可變
Effective UID (EUID)	執行時確定（受 setuid bit 影響）	核心檢查存取權限的唯一依據	可切換為 RUID 或 SUID
Saved UID (SUID)	execve() 執行時備份當時的 EUID	保存最高初始權限以備恢復	固定（等於載入時的 EUID）

---

2) 行程需要額外資源存取權限時應變更之識別碼

當一個行程需要額外的權限以存取特定資源時，必須變更 Effective UID (EUID)。

原因說明：
作業系統核心在執行存取控制檢查（Access Control Checks）時，完全根據行程當下的 EUID 與 EGID (Effective Group ID) 進行比對與判定。因此，若行程欲取得額外存取權限（例如存取僅限 root 讀寫的檔案），必須透過 setuid() 或 seteuid() 等系統呼叫，將其 EUID 設定為擁有該資源存取權限的使用者 ID（例如 root 的 UID 0，前提為 SUID 或 RUID 已包含該特權）。

---

(b) 多工作業系統：多行程與多執行緒機制

1) 多行程 (Multi-process) 與多執行緒 (Multi-thread) 比較

從記憶體使用量、CPU 排程與資源共享三個面向比較如下：

1. 記憶體使用量 (Memory Usages)：
   • 多行程 (Multi-process)：每個行程擁有獨立且完整的虛擬位址空間（包含 Text/Code, Data, BSS, Heap, Stack）以及獨立的頁表（Page Table）。記憶體開銷大，空間利用率較低。
   • 多執行緒 (Multi-thread)：同屬一個行程的所有執行緒共享該行程的虛擬位址空間（Code, Data, Heap 與全域變數），每個執行緒僅需擁有私有的 Stack、暫存器集合（Register Set）與 Thread-Local Storage (TLS)。記憶體開銷極小。
2. CPU 排程與上下文切換 (CPU Scheduling & Context Switch)：

本題涵蓋作業系統（Operating Systems）兩大核心考點：權限管理機制（Access Control & UIDs）與多工作業機制（Multi-tasking: Processes vs. Threads）。

1. 使用者識別碼（User Identifiers, UIDs）機制：
   • Unix/Linux 作業系統採用存取控制機制對行程（Process）進行資源存取檢查。
   • 個別行程內部維護三組關鍵 UID 位元：Real UID (RUID)、Effective UID (EUID) 以及 Saved UID (SUID)，用以兼顧身分識別、最小權限原則（Principle of Least Privilege）與動態權限切換。
2. 多行程（Multi-process）與多執行緒（Multi-thread）之架構差異：
   • 記憶體空間：行程擁有獨立的虛擬位址空間（Virtual Address Space）；執行緒共享同一行程之虛擬位址空間。
   • CPU 排程與 Context Switch：行程切換需替換頁表（Page Table Base Register，如 x86 之 CR3）並刷洗／標記 TLB，負擔巨大；執行緒切換僅需保存／恢復暫存器與 Stack Pointer，開銷極低。
   • 資源共享與溝通：行程間需透過 IPC（Inter-Process Communication）與 MMU 保護障壁互動；執行緒間可直接存取全域變數與 Heap，但需仰賴同步機制（Synchronization Primitives）。
3. fork() 系統呼叫與寫入時複製（Copy-on-Write, COW）：
   • fork() 創建子行程時會複製父行程的頁表，使父子行程在初始階段共享相同的物理記憶體頁面（Physical Memory Pages）。
   • 程式碼中所印出的位址為**虛擬位址（Virtual Address）**而非物理位址。
   • 當子行程試圖修改資料時，MMU 會觸發 Page Fault，作業系統隨即執行寫入時複製（COW），配置新的物理頁面給子行程，確保父子行程位址空間之隔離性與獨立性。

---

解題方法

針對本題各子題之切入點與解析步驟如下：

1. 子題 a-1 觀念拆解：
   • 分別定義 RUID、EUID、SUID 的建立時機、主要功能與彼此間的轉換關係。說明三者在權限檢查與 setuid 程式執行時的運作邏輯。
2. 子題 a-2 權限請求切入：
   • 根據 Linux/Unix Kernel 在進行檔案或系統資源存取檢查（access()、open() 等）時的依據，精確指出何者為 Kernel 存取控制（Access Control）的判定標的。
3. 子題 b-1 三維度比較：
   • 從「記憶體使用量（Memory Usages）」、「CPU 排程與切換開銷（CPU Scheduling）」與「資源共享與通訊（Resource Sharing）」三個層面，條理化地對比多行程與多執行緒。
4. 子題 b-2 程式碼執行追蹤與 COW 分析：
   • 追蹤 fork() 後父子行程的分歧執行路徑。分析子行程修改 sharedVariable 對父行程記憶體空間的影響，結合 Copy-on-Write 機制說明 Line 24 的變數數值。
5. 子題 b-3 虛擬位址映射分析：
   • 解析 %p 印出之位址本質（虛擬位址）。說明 fork() 複製頁表後，父子行程在各自的虛擬位址空間中變數配置位址相同的原因。

---

題目詳解

(a) 存取控制與使用者識別碼 (User IDs)

1) Real UID, Effective UID, Saved UID 之性質與差異

在 Unix/Linux 系統中，每個行程（Process）皆維護三組與使用者身份相關的憑證（Credentials）：

• Real UID (RUID，真實使用者識別碼)：
  • 性質：代表開啟該行程的真實使用者身分（即登入系統或啟動該行程的使用者 ID）。
  • 作用：主要用於會計（Accounting）與追蹤行程擁有者。在一般情況下，子行程會繼承父行程的 RUID。只有具備 CAP_SETUID 權限（如 root）的行程才能修改 RUID。
• Effective UID (EUID，有效使用者識別碼)：
  • 性質：作業系統核心（Kernel）在進行任何資源存取檢查（Access Control Check）時所依據的 UID。
  • 作用：決定行程在該瞬間對檔案、裝置、系統呼叫等資源的存取權限。當執行帶有 Set-User-ID (SUID) 權限位元的執行檔（例如 /usr/bin/passwd）時，EUID 會被核心自動變更為該執行檔擁有者（File Owner）的 UID。
• Saved set-user-ID (SUID / Saved UID，保存使用者識別碼)：
  • 性質：在行程執行 execve() 載入新程式時，核心會將變更後的 EUID 複製一份並保存於 SUID 中。
  • 作用：作為高權限行程暫時降權（Temporary Drop of Privilege）後重新恢復權限的備份。行程可藉由 setuid() 系統呼叫將 EUID 在 RUID 與 SUID 之間切換。例如特權行程可先將 EUID 降為普通使用者的 RUID 以安全執行非特權操作，需要存取特權資源時再將 EUID 恢復為 SUID 所保存的高權限 UID。

三者差異對照表：

識別碼類型	決定時機與來源	核心主要用途	可切換範圍（非 root 行程）
Real UID (RUID)	登入或啟動行程時確定	標示行程的所有權者	固定不可變
Effective UID (EUID)	執行時確定（受 setuid bit 影響）	核心檢查存取權限的唯一依據	可切換為 RUID 或 SUID
Saved UID (SUID)	execve() 執行時備份當時的 EUID	保存最高初始權限以備恢復	固定（等於載入時的 EUID）

---

2) 行程需要額外資源存取權限時應變更之識別碼

當一個行程需要額外的權限以存取特定資源時，必須變更 Effective UID (EUID)。

原因說明：
作業系統核心在執行存取控制檢查（Access Control Checks）時，完全根據行程當下的 EUID 與 EGID (Effective Group ID) 進行比對與判定。因此，若行程欲取得額外存取權限（例如存取僅限 root 讀寫的檔案），必須透過 setuid() 或 seteuid() 等系統呼叫，將其 EUID 設定為擁有該資源存取權限的使用者 ID（例如 root 的 UID 0，前提為 SUID 或 RUID 已包含該特權）。

---

(b) 多工作業系統：多行程與多執行緒機制

1) 多行程 (Multi-process) 與多執行緒 (Multi-thread) 比較

從記憶體使用量、CPU 排程與資源共享三個面向比較如下：

1. 記憶體使用量 (Memory Usages)：
   • 多行程 (Multi-process)：每個行程擁有獨立且完整的虛擬位址空間（包含 Text/Code, Data, BSS, Heap, Stack）以及獨立的頁表（Page Table）。記憶體開銷大，空間利用率較低。
   • 多執行緒 (Multi-thread)：同屬一個行程的所有執行緒共享該行程的虛擬位址空間（Code, Data, Heap 與全域變數），每個執行緒僅需擁有私有的 Stack、暫存器集合（Register Set）與 Thread-Local Storage (TLS)。記憶體開銷極小。
2. CPU 排程與上下文切換 (CPU Scheduling & Context Switch)：

本題涵蓋作業系統（Operating Systems）兩大核心考點：權限管理機制（Access Control & UIDs）與多工作業機制（Multi-tasking: Processes vs. Threads）。

1. 使用者識別碼（User Identifiers, UIDs）機制：
   • Unix/Linux 作業系統採用存取控制機制對行程（Process）進行資源存取檢查。
   • 個別行程內部維護三組關鍵 UID 位元：Real UID (RUID)、Effective UID (EUID) 以及 Saved UID (SUID)，用以兼顧身分識別、最小權限原則（Principle of Least Privilege）與動態權限切換。
2. 多行程（Multi-process）與多執行緒（Multi-thread）之架構差異：
   • 記憶體空間：行程擁有獨立的虛擬位址空間（Virtual Address Space）；執行緒共享同一行程之虛擬位址空間。
   • CPU 排程與 Context Switch：行程切換需替換頁表（Page Table Base Register，如 x86 之 CR3）並刷洗／標記 TLB，負擔巨大；執行緒切換僅需保存／恢復暫存器與 Stack Pointer，開銷極低。
   • 資源共享與溝通：行程間需透過 IPC（Inter-Process Communication）與 MMU 保護障壁互動；執行緒間可直接存取全域變數與 Heap，但需仰賴同步機制（Synchronization Primitives）。
3. fork() 系統呼叫與寫入時複製（Copy-on-Write, COW）：
   • fork() 創建子行程時會複製父行程的頁表，使父子行程在初始階段共享相同的物理記憶體頁面（Physical Memory Pages）。
   • 程式碼中所印出的位址為**虛擬位址（Virtual Address）**而非物理位址。
   • 當子行程試圖修改資料時，MMU 會觸發 Page Fault，作業系統隨即執行寫入時複製（COW），配置新的物理頁面給子行程，確保父子行程位址空間之隔離性與獨立性。

---

解題方法

針對本題各子題之切入點與解析步驟如下：

1. 子題 a-1 觀念拆解：
   • 分別定義 RUID、EUID、SUID 的建立時機、主要功能與彼此間的轉換關係。說明三者在權限檢查與 setuid 程式執行時的運作邏輯。
2. 子題 a-2 權限請求切入：
   • 根據 Linux/Unix Kernel 在進行檔案或系統資源存取檢查（access()、open() 等）時的依據，精確指出何者為 Kernel 存取控制（Access Control）的判定標的。
3. 子題 b-1 三維度比較：
   • 從「記憶體使用量（Memory Usages）」、「CPU 排程與切換開銷（CPU Scheduling）」與「資源共享與通訊（Resource Sharing）」三個層面，條理化地對比多行程與多執行緒。
4. 子題 b-2 程式碼執行追蹤與 COW 分析：
   • 追蹤 fork() 後父子行程的分歧執行路徑。分析子行程修改 sharedVariable 對父行程記憶體空間的影響，結合 Copy-on-Write 機制說明 Line 24 的變數數值。
5. 子題 b-3 虛擬位址映射分析：
   • 解析 %p 印出之位址本質（虛擬位址）。說明 fork() 複製頁表後，父子行程在各自的虛擬位址空間中變數配置位址相同的原因。

---

題目詳解

(a) 存取控制與使用者識別碼 (User IDs)

1) Real UID, Effective UID, Saved UID 之性質與差異

在 Unix/Linux 系統中，每個行程（Process）皆維護三組與使用者身份相關的憑證（Credentials）：

• Real UID (RUID，真實使用者識別碼)：
  • 性質：代表開啟該行程的真實使用者身分（即登入系統或啟動該行程的使用者 ID）。
  • 作用：主要用於會計（Accounting）與追蹤行程擁有者。在一般情況下，子行程會繼承父行程的 RUID。只有具備 CAP_SETUID 權限（如 root）的行程才能修改 RUID。
• Effective UID (EUID，有效使用者識別碼)：
  • 性質：作業系統核心（Kernel）在進行任何資源存取檢查（Access Control Check）時所依據的 UID。
  • 作用：決定行程在該瞬間對檔案、裝置、系統呼叫等資源的存取權限。當執行帶有 Set-User-ID (SUID) 權限位元的執行檔（例如 /usr/bin/passwd）時，EUID 會被核心自動變更為該執行檔擁有者（File Owner）的 UID。
• Saved set-user-ID (SUID / Saved UID，保存使用者識別碼)：
  • 性質：在行程執行 execve() 載入新程式時，核心會將變更後的 EUID 複製一份並保存於 SUID 中。
  • 作用：作為高權限行程暫時降權（Temporary Drop of Privilege）後重新恢復權限的備份。行程可藉由 setuid() 系統呼叫將 EUID 在 RUID 與 SUID 之間切換。例如特權行程可先將 EUID 降為普通使用者的 RUID 以安全執行非特權操作，需要存取特權資源時再將 EUID 恢復為 SUID 所保存的高權限 UID。

三者差異對照表：

識別碼類型	決定時機與來源	核心主要用途	可切換範圍（非 root 行程）
Real UID (RUID)	登入或啟動行程時確定	標示行程的所有權者	固定不可變
Effective UID (EUID)	執行時確定（受 setuid bit 影響）	核心檢查存取權限的唯一依據	可切換為 RUID 或 SUID
Saved UID (SUID)	execve() 執行時備份當時的 EUID	保存最高初始權限以備恢復	固定（等於載入時的 EUID）

---

2) 行程需要額外資源存取權限時應變更之識別碼

當一個行程需要額外的權限以存取特定資源時，必須變更 Effective UID (EUID)。

原因說明：
作業系統核心在執行存取控制檢查（Access Control Checks）時，完全根據行程當下的 EUID 與 EGID (Effective Group ID) 進行比對與判定。因此，若行程欲取得額外存取權限（例如存取僅限 root 讀寫的檔案），必須透過 setuid() 或 seteuid() 等系統呼叫，將其 EUID 設定為擁有該資源存取權限的使用者 ID（例如 root 的 UID 0，前提為 SUID 或 RUID 已包含該特權）。

---

(b) 多工作業系統：多行程與多執行緒機制

1) 多行程 (Multi-process) 與多執行緒 (Multi-thread) 比較

從記憶體使用量、CPU 排程與資源共享三個面向比較如下：

1. 記憶體使用量 (Memory Usages)：
   • 多行程 (Multi-process)：每個行程擁有獨立且完整的虛擬位址空間（包含 Text/Code, Data, BSS, Heap, Stack）以及獨立的頁表（Page Table）。記憶體開銷大，空間利用率較低。
   • 多執行緒 (Multi-thread)：同屬一個行程的所有執行緒共享該行程的虛擬位址空間（Code, Data, Heap 與全域變數），每個執行緒僅需擁有私有的 Stack、暫存器集合（Register Set）與 Thread-Local Storage (TLS)。記憶體開銷極小。
2. CPU 排程與上下文切換 (CPU Scheduling & Context Switch)：

核心觀念

本題為分散式系統、作業系統與資料庫交易處理（Transaction Processing）的綜合實務設計題，探討雙十一（光棍節）高併發（High Concurrency）與高寫入吞吐量情境下的系統架構設計。核心觀念涵蓋以下各大考點：

1. 交易排程與營收最佳化：結合貪婪演算法（Greedy Algorithm）與價值導向排程（Value-Based Transaction Scheduling），在資源/庫存有限時最大化整體收益。
2. 分散式時序與定序（Distributed Ordering）：在缺乏全域時鐘（Global Clock）的分散式環境中，利用邏輯時鐘（Lamport Logical Clock / Vector Clock）或入口閘道點集中定序（Sequence Generation），釐清「傳送時間（Sent time）」與「到達時間（Arrived time）」之差異與公平性。
3. 分散式同步與防超賣機制：高併發環境下的分散式鎖定（Distributed Lock）、記憶體快取原子操作（Atomic Cache Operations，如 Redis Lua 腳本/DECR）與庫存預先分區（Inventory Partitioning），避免傳統兩階段提交（2PC）造成的系統瓶頸。
4. 高可靠與高效能檔案系統（Trustful & Efficient Storage）：採用日誌結構檔案系統（Log-Structured File System, LFS）與預寫日誌（Write-Ahead Logging, WAL）的 Append-Only（僅追加）機制，配合補償交易（Compensating Transaction），同時兼顧 ACID 特性與極高磁碟寫入效能。
5. 資安防護與高併發攻擊應對：針對分散式拒絕服務攻擊（DDoS）、搶購機器人（Bot Scalping）、重複提交（Double Spending / Race Condition）與重放攻擊（Replay Attack）的防禦機制（如限流 Token Bucket、冪等性設計 Idempotency Key、HMAC / TLS 數位簽章）。

---

解題方法

(a) 排程演算法與營收最大化 (5 pt.)

• 分析與切入點：
  商品數量有限時，若採用標準的先來先服務（FIFO）排程，可能導致高單價、高利潤或搭配銷售額高的交易因排在後方而無法成交。為使平台營收最大化，問題可抽象化為「有限資源下的背包問題（Knapsack Problem）」或「價值優先排程（Value-Based / Profit-Maximizing Scheduling）」。
• 具體設計：
  1. 單位資源營收排序（Revenue-Density Greedy Scheduling）：
     對每個待處理交易 $T_i$，計算其產生的總利潤（或營業額）$R_i$ 與消耗庫存 $C_i$ 之比值：
     $\text{Priority}(T_i) = \frac{R_i}{C_i}$
     將交易存入優先權隊列（Priority Queue），優先排程 $\text{Priority}(T_i)$ 最高的交易。
  2. 動態批次最佳化（Dynamic Micro-batch Optimization）：
     在極短的微批次（Micro-batch，例如每 $10\text{ ms}$）內，將收集到的交易集合視為 0/1 背包問題，透過動態規劃或分支界限法（Branch and Bound）選出在現有庫存約束下能產生最大總營收 $\sum R_i$ 的交易組合進行 Commit。

(b) 缺乏全域時鐘下的交易先後順序判定 (5 pt.)

• 分析與切入點：
  在分散式網路中，用戶端的實體時鐘（Physical Clock）存在時鐘偏移（Clock Skew）且容易被竄改，因此無法以「用戶端發送時間（Sent Time）」作為絕對公正的先後依據。唯一的公正標準是以伺服器入口端接收到的時間（Arrived Time）或分散式共識與邏輯時鐘為準。
• 具體設計：
  1. 採納原則：保證「先到達（Earlier Arrived）」即「先處理（Earlier Processed）」。
  2. 定序機制：
     • 入口 API 閘道集中定序（Centralized Ingestion Ordering）：交易請求抵達入口 API Gateway 時，由原子遞增序號器（Monotonic Sequence Generator，如 Distributed Snowflake / Redis INCR）即時賦予唯一且嚴格遞增的邏輯時間戳記 $S_{\text{seq}}$。
     • Lamport 邏輯時鐘 / Total Order Broadcast：若採用全分散式架構，利用 Lamport Timestamps 搭配節點 ID 組合為完全序 $(T_{\text{logical}}, \text{NodeID})$，經由共識協定（如 Raft / Paxos Log Index）達成全域一致的交易處理順序。

(c) 高併發分散式同步與防超賣 (5 pt.)

• 分析與切入點：
  若在關聯式資料庫（RDBMS）使用傳統兩階段提交（2PC）或悲觀鎖（Pessimistic Locking，如 SELECT FOR UPDATE），高併發下會導致嚴重的鎖定競爭（Lock Contention）與資料庫死鎖，拉長回應時間。
• 具體設計：
  1. 記憶體內原子扣減與快取層（In-Memory Atomic Operations）：
     將庫存資料載入高效能記憶體快取（如 Redis），利用單執行緒原子操作（如 DECR 或 Lua 腳本）進行庫存預扣。當庫存 $N > 0$ 時扣減成功並允許下單；當 $N = 0$ 時立即拒絕請求，過程完全在記憶體完成，回應時間小於毫秒級。
  2. 庫存預先分區（Inventory Partitioning / Sharding）：
     將熱門商品的 $M$ 件庫存平均拆分至 $K$ 個獨立的資料庫節點/快取節點，每個節點各自管理 $M/K$ 件庫存，節點間互不干擾與競爭，徹底消除單點同步瓶頸。
  3. 非同步訊息隊列解耦（Asynchronous Queueing）：
     快取預扣庫存成功後，將交易發送至分散式訊息隊列（Kafka / RabbitMQ），後端資料庫以穩定的速率非同步消費訊息進行持久化寫入與扣款，確保高併發流量被平滑削峰（Traffic Shaving）。

(d) 可信且高效的交易檔案系統設計 (5 pt.)

• 分析與切入點：
  交易可能因使用者主動取消或系統庫存不足而中途取消。檔案系統必須滿足 ACID 與不可竄改性（Trustful） 以及 高寫入吞吐量（Efficient）。

核心觀念

本題為分散式系統、作業系統與資料庫交易處理（Transaction Processing）的綜合實務設計題，探討雙十一（光棍節）高併發（High Concurrency）與高寫入吞吐量情境下的系統架構設計。核心觀念涵蓋以下各大考點：

1. 交易排程與營收最佳化：結合貪婪演算法（Greedy Algorithm）與價值導向排程（Value-Based Transaction Scheduling），在資源/庫存有限時最大化整體收益。
2. 分散式時序與定序（Distributed Ordering）：在缺乏全域時鐘（Global Clock）的分散式環境中，利用邏輯時鐘（Lamport Logical Clock / Vector Clock）或入口閘道點集中定序（Sequence Generation），釐清「傳送時間（Sent time）」與「到達時間（Arrived time）」之差異與公平性。
3. 分散式同步與防超賣機制：高併發環境下的分散式鎖定（Distributed Lock）、記憶體快取原子操作（Atomic Cache Operations，如 Redis Lua 腳本/DECR）與庫存預先分區（Inventory Partitioning），避免傳統兩階段提交（2PC）造成的系統瓶頸。
4. 高可靠與高效能檔案系統（Trustful & Efficient Storage）：採用日誌結構檔案系統（Log-Structured File System, LFS）與預寫日誌（Write-Ahead Logging, WAL）的 Append-Only（僅追加）機制，配合補償交易（Compensating Transaction），同時兼顧 ACID 特性與極高磁碟寫入效能。
5. 資安防護與高併發攻擊應對：針對分散式拒絕服務攻擊（DDoS）、搶購機器人（Bot Scalping）、重複提交（Double Spending / Race Condition）與重放攻擊（Replay Attack）的防禦機制（如限流 Token Bucket、冪等性設計 Idempotency Key、HMAC / TLS 數位簽章）。

---

解題方法

(a) 排程演算法與營收最大化 (5 pt.)

• 分析與切入點：
  商品數量有限時，若採用標準的先來先服務（FIFO）排程，可能導致高單價、高利潤或搭配銷售額高的交易因排在後方而無法成交。為使平台營收最大化，問題可抽象化為「有限資源下的背包問題（Knapsack Problem）」或「價值優先排程（Value-Based / Profit-Maximizing Scheduling）」。
• 具體設計：
  1. 單位資源營收排序（Revenue-Density Greedy Scheduling）：
     對每個待處理交易 $T_i$，計算其產生的總利潤（或營業額）$R_i$ 與消耗庫存 $C_i$ 之比值：
     $\text{Priority}(T_i) = \frac{R_i}{C_i}$
     將交易存入優先權隊列（Priority Queue），優先排程 $\text{Priority}(T_i)$ 最高的交易。
  2. 動態批次最佳化（Dynamic Micro-batch Optimization）：
     在極短的微批次（Micro-batch，例如每 $10\text{ ms}$）內，將收集到的交易集合視為 0/1 背包問題，透過動態規劃或分支界限法（Branch and Bound）選出在現有庫存約束下能產生最大總營收 $\sum R_i$ 的交易組合進行 Commit。

(b) 缺乏全域時鐘下的交易先後順序判定 (5 pt.)

• 分析與切入點：
  在分散式網路中，用戶端的實體時鐘（Physical Clock）存在時鐘偏移（Clock Skew）且容易被竄改，因此無法以「用戶端發送時間（Sent Time）」作為絕對公正的先後依據。唯一的公正標準是以伺服器入口端接收到的時間（Arrived Time）或分散式共識與邏輯時鐘為準。
• 具體設計：
  1. 採納原則：保證「先到達（Earlier Arrived）」即「先處理（Earlier Processed）」。
  2. 定序機制：
     • 入口 API 閘道集中定序（Centralized Ingestion Ordering）：交易請求抵達入口 API Gateway 時，由原子遞增序號器（Monotonic Sequence Generator，如 Distributed Snowflake / Redis INCR）即時賦予唯一且嚴格遞增的邏輯時間戳記 $S_{\text{seq}}$。
     • Lamport 邏輯時鐘 / Total Order Broadcast：若採用全分散式架構，利用 Lamport Timestamps 搭配節點 ID 組合為完全序 $(T_{\text{logical}}, \text{NodeID})$，經由共識協定（如 Raft / Paxos Log Index）達成全域一致的交易處理順序。

(c) 高併發分散式同步與防超賣 (5 pt.)

• 分析與切入點：
  若在關聯式資料庫（RDBMS）使用傳統兩階段提交（2PC）或悲觀鎖（Pessimistic Locking，如 SELECT FOR UPDATE），高併發下會導致嚴重的鎖定競爭（Lock Contention）與資料庫死鎖，拉長回應時間。
• 具體設計：
  1. 記憶體內原子扣減與快取層（In-Memory Atomic Operations）：
     將庫存資料載入高效能記憶體快取（如 Redis），利用單執行緒原子操作（如 DECR 或 Lua 腳本）進行庫存預扣。當庫存 $N > 0$ 時扣減成功並允許下單；當 $N = 0$ 時立即拒絕請求，過程完全在記憶體完成，回應時間小於毫秒級。
  2. 庫存預先分區（Inventory Partitioning / Sharding）：
     將熱門商品的 $M$ 件庫存平均拆分至 $K$ 個獨立的資料庫節點/快取節點，每個節點各自管理 $M/K$ 件庫存，節點間互不干擾與競爭，徹底消除單點同步瓶頸。
  3. 非同步訊息隊列解耦（Asynchronous Queueing）：
     快取預扣庫存成功後，將交易發送至分散式訊息隊列（Kafka / RabbitMQ），後端資料庫以穩定的速率非同步消費訊息進行持久化寫入與扣款，確保高併發流量被平滑削峰（Traffic Shaving）。

(d) 可信且高效的交易檔案系統設計 (5 pt.)

• 分析與切入點：
  交易可能因使用者主動取消或系統庫存不足而中途取消。檔案系統必須滿足 ACID 與不可竄改性（Trustful） 以及 高寫入吞吐量（Efficient）。

核心觀念

本題為分散式系統、作業系統與資料庫交易處理（Transaction Processing）的綜合實務設計題，探討雙十一（光棍節）高併發（High Concurrency）與高寫入吞吐量情境下的系統架構設計。核心觀念涵蓋以下各大考點：

1. 交易排程與營收最佳化：結合貪婪演算法（Greedy Algorithm）與價值導向排程（Value-Based Transaction Scheduling），在資源/庫存有限時最大化整體收益。
2. 分散式時序與定序（Distributed Ordering）：在缺乏全域時鐘（Global Clock）的分散式環境中，利用邏輯時鐘（Lamport Logical Clock / Vector Clock）或入口閘道點集中定序（Sequence Generation），釐清「傳送時間（Sent time）」與「到達時間（Arrived time）」之差異與公平性。
3. 分散式同步與防超賣機制：高併發環境下的分散式鎖定（Distributed Lock）、記憶體快取原子操作（Atomic Cache Operations，如 Redis Lua 腳本/DECR）與庫存預先分區（Inventory Partitioning），避免傳統兩階段提交（2PC）造成的系統瓶頸。
4. 高可靠與高效能檔案系統（Trustful & Efficient Storage）：採用日誌結構檔案系統（Log-Structured File System, LFS）與預寫日誌（Write-Ahead Logging, WAL）的 Append-Only（僅追加）機制，配合補償交易（Compensating Transaction），同時兼顧 ACID 特性與極高磁碟寫入效能。
5. 資安防護與高併發攻擊應對：針對分散式拒絕服務攻擊（DDoS）、搶購機器人（Bot Scalping）、重複提交（Double Spending / Race Condition）與重放攻擊（Replay Attack）的防禦機制（如限流 Token Bucket、冪等性設計 Idempotency Key、HMAC / TLS 數位簽章）。

---

解題方法

(a) 排程演算法與營收最大化 (5 pt.)

• 分析與切入點：
  商品數量有限時，若採用標準的先來先服務（FIFO）排程，可能導致高單價、高利潤或搭配銷售額高的交易因排在後方而無法成交。為使平台營收最大化，問題可抽象化為「有限資源下的背包問題（Knapsack Problem）」或「價值優先排程（Value-Based / Profit-Maximizing Scheduling）」。
• 具體設計：
  1. 單位資源營收排序（Revenue-Density Greedy Scheduling）：
     對每個待處理交易 $T_i$，計算其產生的總利潤（或營業額）$R_i$ 與消耗庫存 $C_i$ 之比值：
     $\text{Priority}(T_i) = \frac{R_i}{C_i}$
     將交易存入優先權隊列（Priority Queue），優先排程 $\text{Priority}(T_i)$ 最高的交易。
  2. 動態批次最佳化（Dynamic Micro-batch Optimization）：
     在極短的微批次（Micro-batch，例如每 $10\text{ ms}$）內，將收集到的交易集合視為 0/1 背包問題，透過動態規劃或分支界限法（Branch and Bound）選出在現有庫存約束下能產生最大總營收 $\sum R_i$ 的交易組合進行 Commit。

(b) 缺乏全域時鐘下的交易先後順序判定 (5 pt.)

• 分析與切入點：
  在分散式網路中，用戶端的實體時鐘（Physical Clock）存在時鐘偏移（Clock Skew）且容易被竄改，因此無法以「用戶端發送時間（Sent Time）」作為絕對公正的先後依據。唯一的公正標準是以伺服器入口端接收到的時間（Arrived Time）或分散式共識與邏輯時鐘為準。
• 具體設計：
  1. 採納原則：保證「先到達（Earlier Arrived）」即「先處理（Earlier Processed）」。
  2. 定序機制：
     • 入口 API 閘道集中定序（Centralized Ingestion Ordering）：交易請求抵達入口 API Gateway 時，由原子遞增序號器（Monotonic Sequence Generator，如 Distributed Snowflake / Redis INCR）即時賦予唯一且嚴格遞增的邏輯時間戳記 $S_{\text{seq}}$。
     • Lamport 邏輯時鐘 / Total Order Broadcast：若採用全分散式架構，利用 Lamport Timestamps 搭配節點 ID 組合為完全序 $(T_{\text{logical}}, \text{NodeID})$，經由共識協定（如 Raft / Paxos Log Index）達成全域一致的交易處理順序。

(c) 高併發分散式同步與防超賣 (5 pt.)

• 分析與切入點：
  若在關聯式資料庫（RDBMS）使用傳統兩階段提交（2PC）或悲觀鎖（Pessimistic Locking，如 SELECT FOR UPDATE），高併發下會導致嚴重的鎖定競爭（Lock Contention）與資料庫死鎖，拉長回應時間。
• 具體設計：
  1. 記憶體內原子扣減與快取層（In-Memory Atomic Operations）：
     將庫存資料載入高效能記憶體快取（如 Redis），利用單執行緒原子操作（如 DECR 或 Lua 腳本）進行庫存預扣。當庫存 $N > 0$ 時扣減成功並允許下單；當 $N = 0$ 時立即拒絕請求，過程完全在記憶體完成，回應時間小於毫秒級。
  2. 庫存預先分區（Inventory Partitioning / Sharding）：
     將熱門商品的 $M$ 件庫存平均拆分至 $K$ 個獨立的資料庫節點/快取節點，每個節點各自管理 $M/K$ 件庫存，節點間互不干擾與競爭，徹底消除單點同步瓶頸。
  3. 非同步訊息隊列解耦（Asynchronous Queueing）：
     快取預扣庫存成功後，將交易發送至分散式訊息隊列（Kafka / RabbitMQ），後端資料庫以穩定的速率非同步消費訊息進行持久化寫入與扣款，確保高併發流量被平滑削峰（Traffic Shaving）。

(d) 可信且高效的交易檔案系統設計 (5 pt.)

• 分析與切入點：
  交易可能因使用者主動取消或系統庫存不足而中途取消。檔案系統必須滿足 ACID 與不可竄改性（Trustful） 以及 高寫入吞吐量（Efficient）。

核心觀念

本題為分散式系統、作業系統與資料庫交易處理（Transaction Processing）的綜合實務設計題，探討雙十一（光棍節）高併發（High Concurrency）與高寫入吞吐量情境下的系統架構設計。核心觀念涵蓋以下各大考點：

1. 交易排程與營收最佳化：結合貪婪演算法（Greedy Algorithm）與價值導向排程（Value-Based Transaction Scheduling），在資源/庫存有限時最大化整體收益。
2. 分散式時序與定序（Distributed Ordering）：在缺乏全域時鐘（Global Clock）的分散式環境中，利用邏輯時鐘（Lamport Logical Clock / Vector Clock）或入口閘道點集中定序（Sequence Generation），釐清「傳送時間（Sent time）」與「到達時間（Arrived time）」之差異與公平性。
3. 分散式同步與防超賣機制：高併發環境下的分散式鎖定（Distributed Lock）、記憶體快取原子操作（Atomic Cache Operations，如 Redis Lua 腳本/DECR）與庫存預先分區（Inventory Partitioning），避免傳統兩階段提交（2PC）造成的系統瓶頸。
4. 高可靠與高效能檔案系統（Trustful & Efficient Storage）：採用日誌結構檔案系統（Log-Structured File System, LFS）與預寫日誌（Write-Ahead Logging, WAL）的 Append-Only（僅追加）機制，配合補償交易（Compensating Transaction），同時兼顧 ACID 特性與極高磁碟寫入效能。
5. 資安防護與高併發攻擊應對：針對分散式拒絕服務攻擊（DDoS）、搶購機器人（Bot Scalping）、重複提交（Double Spending / Race Condition）與重放攻擊（Replay Attack）的防禦機制（如限流 Token Bucket、冪等性設計 Idempotency Key、HMAC / TLS 數位簽章）。

---

解題方法

(a) 排程演算法與營收最大化 (5 pt.)

• 分析與切入點：
  商品數量有限時，若採用標準的先來先服務（FIFO）排程，可能導致高單價、高利潤或搭配銷售額高的交易因排在後方而無法成交。為使平台營收最大化，問題可抽象化為「有限資源下的背包問題（Knapsack Problem）」或「價值優先排程（Value-Based / Profit-Maximizing Scheduling）」。
• 具體設計：
  1. 單位資源營收排序（Revenue-Density Greedy Scheduling）：
     對每個待處理交易 $T_i$，計算其產生的總利潤（或營業額）$R_i$ 與消耗庫存 $C_i$ 之比值：
     $\text{Priority}(T_i) = \frac{R_i}{C_i}$
     將交易存入優先權隊列（Priority Queue），優先排程 $\text{Priority}(T_i)$ 最高的交易。
  2. 動態批次最佳化（Dynamic Micro-batch Optimization）：
     在極短的微批次（Micro-batch，例如每 $10\text{ ms}$）內，將收集到的交易集合視為 0/1 背包問題，透過動態規劃或分支界限法（Branch and Bound）選出在現有庫存約束下能產生最大總營收 $\sum R_i$ 的交易組合進行 Commit。

(b) 缺乏全域時鐘下的交易先後順序判定 (5 pt.)

• 分析與切入點：
  在分散式網路中，用戶端的實體時鐘（Physical Clock）存在時鐘偏移（Clock Skew）且容易被竄改，因此無法以「用戶端發送時間（Sent Time）」作為絕對公正的先後依據。唯一的公正標準是以伺服器入口端接收到的時間（Arrived Time）或分散式共識與邏輯時鐘為準。
• 具體設計：
  1. 採納原則：保證「先到達（Earlier Arrived）」即「先處理（Earlier Processed）」。
  2. 定序機制：
     • 入口 API 閘道集中定序（Centralized Ingestion Ordering）：交易請求抵達入口 API Gateway 時，由原子遞增序號器（Monotonic Sequence Generator，如 Distributed Snowflake / Redis INCR）即時賦予唯一且嚴格遞增的邏輯時間戳記 $S_{\text{seq}}$。
     • Lamport 邏輯時鐘 / Total Order Broadcast：若採用全分散式架構，利用 Lamport Timestamps 搭配節點 ID 組合為完全序 $(T_{\text{logical}}, \text{NodeID})$，經由共識協定（如 Raft / Paxos Log Index）達成全域一致的交易處理順序。

(c) 高併發分散式同步與防超賣 (5 pt.)

• 分析與切入點：
  若在關聯式資料庫（RDBMS）使用傳統兩階段提交（2PC）或悲觀鎖（Pessimistic Locking，如 SELECT FOR UPDATE），高併發下會導致嚴重的鎖定競爭（Lock Contention）與資料庫死鎖，拉長回應時間。
• 具體設計：
  1. 記憶體內原子扣減與快取層（In-Memory Atomic Operations）：
     將庫存資料載入高效能記憶體快取（如 Redis），利用單執行緒原子操作（如 DECR 或 Lua 腳本）進行庫存預扣。當庫存 $N > 0$ 時扣減成功並允許下單；當 $N = 0$ 時立即拒絕請求，過程完全在記憶體完成，回應時間小於毫秒級。
  2. 庫存預先分區（Inventory Partitioning / Sharding）：
     將熱門商品的 $M$ 件庫存平均拆分至 $K$ 個獨立的資料庫節點/快取節點，每個節點各自管理 $M/K$ 件庫存，節點間互不干擾與競爭，徹底消除單點同步瓶頸。
  3. 非同步訊息隊列解耦（Asynchronous Queueing）：
     快取預扣庫存成功後，將交易發送至分散式訊息隊列（Kafka / RabbitMQ），後端資料庫以穩定的速率非同步消費訊息進行持久化寫入與扣款，確保高併發流量被平滑削峰（Traffic Shaving）。

(d) 可信且高效的交易檔案系統設計 (5 pt.)

• 分析與切入點：
  交易可能因使用者主動取消或系統庫存不足而中途取消。檔案系統必須滿足 ACID 與不可竄改性（Trustful） 以及 高寫入吞吐量（Efficient）。

核心觀念

本題為分散式系統、作業系統與資料庫交易處理（Transaction Processing）的綜合實務設計題，探討雙十一（光棍節）高併發（High Concurrency）與高寫入吞吐量情境下的系統架構設計。核心觀念涵蓋以下各大考點：

1. 交易排程與營收最佳化：結合貪婪演算法（Greedy Algorithm）與價值導向排程（Value-Based Transaction Scheduling），在資源/庫存有限時最大化整體收益。
2. 分散式時序與定序（Distributed Ordering）：在缺乏全域時鐘（Global Clock）的分散式環境中，利用邏輯時鐘（Lamport Logical Clock / Vector Clock）或入口閘道點集中定序（Sequence Generation），釐清「傳送時間（Sent time）」與「到達時間（Arrived time）」之差異與公平性。
3. 分散式同步與防超賣機制：高併發環境下的分散式鎖定（Distributed Lock）、記憶體快取原子操作（Atomic Cache Operations，如 Redis Lua 腳本/DECR）與庫存預先分區（Inventory Partitioning），避免傳統兩階段提交（2PC）造成的系統瓶頸。
4. 高可靠與高效能檔案系統（Trustful & Efficient Storage）：採用日誌結構檔案系統（Log-Structured File System, LFS）與預寫日誌（Write-Ahead Logging, WAL）的 Append-Only（僅追加）機制，配合補償交易（Compensating Transaction），同時兼顧 ACID 特性與極高磁碟寫入效能。
5. 資安防護與高併發攻擊應對：針對分散式拒絕服務攻擊（DDoS）、搶購機器人（Bot Scalping）、重複提交（Double Spending / Race Condition）與重放攻擊（Replay Attack）的防禦機制（如限流 Token Bucket、冪等性設計 Idempotency Key、HMAC / TLS 數位簽章）。

---

解題方法

(a) 排程演算法與營收最大化 (5 pt.)

• 分析與切入點：
  商品數量有限時，若採用標準的先來先服務（FIFO）排程，可能導致高單價、高利潤或搭配銷售額高的交易因排在後方而無法成交。為使平台營收最大化，問題可抽象化為「有限資源下的背包問題（Knapsack Problem）」或「價值優先排程（Value-Based / Profit-Maximizing Scheduling）」。
• 具體設計：
  1. 單位資源營收排序（Revenue-Density Greedy Scheduling）：
     對每個待處理交易 $T_i$，計算其產生的總利潤（或營業額）$R_i$ 與消耗庫存 $C_i$ 之比值：
     $\text{Priority}(T_i) = \frac{R_i}{C_i}$
     將交易存入優先權隊列（Priority Queue），優先排程 $\text{Priority}(T_i)$ 最高的交易。
  2. 動態批次最佳化（Dynamic Micro-batch Optimization）：
     在極短的微批次（Micro-batch，例如每 $10\text{ ms}$）內，將收集到的交易集合視為 0/1 背包問題，透過動態規劃或分支界限法（Branch and Bound）選出在現有庫存約束下能產生最大總營收 $\sum R_i$ 的交易組合進行 Commit。

(b) 缺乏全域時鐘下的交易先後順序判定 (5 pt.)

• 分析與切入點：
  在分散式網路中，用戶端的實體時鐘（Physical Clock）存在時鐘偏移（Clock Skew）且容易被竄改，因此無法以「用戶端發送時間（Sent Time）」作為絕對公正的先後依據。唯一的公正標準是以伺服器入口端接收到的時間（Arrived Time）或分散式共識與邏輯時鐘為準。
• 具體設計：
  1. 採納原則：保證「先到達（Earlier Arrived）」即「先處理（Earlier Processed）」。
  2. 定序機制：
     • 入口 API 閘道集中定序（Centralized Ingestion Ordering）：交易請求抵達入口 API Gateway 時，由原子遞增序號器（Monotonic Sequence Generator，如 Distributed Snowflake / Redis INCR）即時賦予唯一且嚴格遞增的邏輯時間戳記 $S_{\text{seq}}$。
     • Lamport 邏輯時鐘 / Total Order Broadcast：若採用全分散式架構，利用 Lamport Timestamps 搭配節點 ID 組合為完全序 $(T_{\text{logical}}, \text{NodeID})$，經由共識協定（如 Raft / Paxos Log Index）達成全域一致的交易處理順序。

(c) 高併發分散式同步與防超賣 (5 pt.)

• 分析與切入點：
  若在關聯式資料庫（RDBMS）使用傳統兩階段提交（2PC）或悲觀鎖（Pessimistic Locking，如 SELECT FOR UPDATE），高併發下會導致嚴重的鎖定競爭（Lock Contention）與資料庫死鎖，拉長回應時間。
• 具體設計：
  1. 記憶體內原子扣減與快取層（In-Memory Atomic Operations）：
     將庫存資料載入高效能記憶體快取（如 Redis），利用單執行緒原子操作（如 DECR 或 Lua 腳本）進行庫存預扣。當庫存 $N > 0$ 時扣減成功並允許下單；當 $N = 0$ 時立即拒絕請求，過程完全在記憶體完成，回應時間小於毫秒級。
  2. 庫存預先分區（Inventory Partitioning / Sharding）：
     將熱門商品的 $M$ 件庫存平均拆分至 $K$ 個獨立的資料庫節點/快取節點，每個節點各自管理 $M/K$ 件庫存，節點間互不干擾與競爭，徹底消除單點同步瓶頸。
  3. 非同步訊息隊列解耦（Asynchronous Queueing）：
     快取預扣庫存成功後，將交易發送至分散式訊息隊列（Kafka / RabbitMQ），後端資料庫以穩定的速率非同步消費訊息進行持久化寫入與扣款，確保高併發流量被平滑削峰（Traffic Shaving）。

(d) 可信且高效的交易檔案系統設計 (5 pt.)

• 分析與切入點：
  交易可能因使用者主動取消或系統庫存不足而中途取消。檔案系統必須滿足 ACID 與不可竄改性（Trustful） 以及 高寫入吞吐量（Efficient）。