113 年 國立臺灣大學資訊網路與媒體研究所《計算機結構與作業系統》

核心觀念

本題考查計算機結構中**系統功耗管理（Power Management）**的核心理論，涵蓋以下關鍵概念與公式：

1. 動態功耗公式（Dynamic Power Formula）：
   $P_{\text{active}} = \frac{1}{2} \cdot C \cdot V^2 \cdot f$
   其中 $C$ 為負載電容（Capacitance），$V$ 為供給電壓（Supply Voltage），$f$ 為時脈頻率（Clock Frequency）。
2. 邏輯閘延遲與電壓關係：晶體管的電路傳輸延遲與供給電壓成反比。降低電壓會增加電路延遲，從而限制最高可運行的時脈頻率 $f_{\text{max}}$。
3. 記憶體受限（Memory-bound）程式的 DVFS 策略：當程式執行時間的瓶頸在於記憶體存取延遲時，適度調降 CPU 時脈頻率能顯著降低功耗且對整體效能影響極小。
4. 功耗類型與控制技術對應：
   • 動態功耗（Dynamic Power）：主要透過動態電壓與頻率調整（DVFS）進行控制。
   • 漏電功耗（Leakage / Static Power）：主要透過電源閘控（Power Gating）進行控制。
5. 快取快照與一致性（Cache Coherence & Consistency）：Write-back 快取含有 Dirty Data，關閉快取前必須先執行寫回（Flush / Write-back），否則會導致資料遺失與記憶體不一致。

---

解題方法

1. 硬體物理極限分析 (A)：評估晶體管電路延遲、供給電壓與建立時間（Setup Time）之關係，判斷高頻低壓運行的可行性。
2. 動態功耗計算 (B)：利用 $P_{\text{active}} \propto V^2 \cdot f$ 正比關係，代入電壓變化數值推導降壓後的功耗。
3. 系統效能瓶頸分析 (C)：比較 Compute-bound 與 Memory-bound 程式在 CPU 降頻時的效能變化差異。
4. 功耗控制機制釐清 (D)：區分動態功耗與靜態漏電功耗的產生原因及其對應的省電機制（DVFS vs. Power Gating）。
5. 快取運作機制評估 (E)：分析快取寫回（Write-back）策略與系統總能量消耗（Race-to-sleep 原則）。

---

選項分析

• (A) 錯誤
  CMOS 電路的邏輯閘延遲與供給電壓 $V$ 成反比。若降低供給電壓 $V$，晶體管導通速度變慢、訊號傳播延遲增加，會降低處理器所能承受的最大時脈頻率 $f_{\text{max}}$。若在降低電壓的同時強制提高時脈頻率，會引發建立時間違規（Setup Time Violation），導致資料採樣錯誤而使系統崩潰。

• (B) 正確
  主動功耗（Active Power）即動態功耗，公式為 $P_{\text{active}} \propto V^2 \cdot f$。

核心觀念

單週期處理器中，時脈週期由最長指令路徑決定，所有指令都在一個週期內完成。管線處理器的時脈週期則由最慢的管線階段決定；理想情況下，管線填滿後每個週期可完成一條指令。

因此，單一指令的延遲要看它經過幾個週期，處理器的吞吐量則看穩定狀態下每個週期能完成幾條指令。

解題方法

原卷圖中的階段延遲為 IF＝500 ps、ID＝700 ps、EX＝300 ps、MEM＝600 ps、WB＝400 ps；指令比例為 ALU/Logic 40%、Jump/Branch 15%、Load 25%、Store 20%。

單週期處理器的週期時間是五個階段延遲總和：

$$T_{\text{single}}=500+700+300+600+400=2500\text{ ps}$$

理想管線處理器的週期時間是最慢階段的延遲：

$$T_{\text{pipeline}}=\max(500,700,300,600,400)=700\text{ ps}$$

Load 會經過五個階段，因此管線處理器完成一條 Load 需要五個管線週期：

$$L_{\text{load,pipeline}}=5\times700=3500\text{ ps}$$

選項分析

(A) 正確。 單週期處理器的全域時脈週期由最長指令路徑決定，為 2500 ps。

核心觀念

本題旨在考驗對**記憶體階層（Memory Hierarchy）**相關機制的綜合理解，涉及電腦結構中的四大重點議題：

1. 快取友善程式設計與區域性（Locality）：程式員在撰寫高效能程式時，即使有現代編譯器輔助，仍需主動考慮時間區域性（Temporal Locality）與空間區域性（Spatial Locality）。
2. 快取缺失分析模型（3C Model）：由 Mark Hill 提出的經典 3C 模型，將單處理器系統中的快取缺失劃分為：
   • 強制性缺失（Compulsory miss）：又稱冷啟動缺失（Cold-start miss），首次存取該記憶體區塊時發生的缺失。
   • 容量缺失（Capacity miss）：因快取容量不足以容納程式執行所需的所有資料而發生的缺失。
   • 衝突缺失（Conflict miss）：在直接對映（Direct-mapped）或組相聯（Set-associative）快取中，因多個區塊競爭同一個快取組（Set）而發生的缺失。
   • 註：在多處理器環境中引入的快取無效化缺失，則被稱為第四個 C——一致性缺失（Coherence miss）。
3. 快取寫入策略（Write Strategy）：
   • 直寫式（Write-through）：每次寫入快取時，同步寫入下層記憶體。
   • 寫回式（Write-back）：寫入時僅更新快取並標記為髒位元（Dirty bit），直到該區塊被替換（Replace/Evict）時才寫回下層記憶體。
4. 虛擬記憶體與快取的定址架構：
   • VIVT（Virtually Indexed, Virtually Tagged）：快取的索引與標籤皆使用虛擬位址，存取快取時完全不需要等待 TLB（Translation Lookaside Buffer）的位址轉譯。
5. 多處理器快取一致性（Cache Coherence）：
   • 在寫無效協定（Write Invalidate Protocol）下，當一個核心寫入共享區塊時，會發出 Invalid 訊號使其他核心快取中的副本失效，後續其他核心再次讀取時便會引發一致性缺失（Coherence miss），甚至產生**偽共享（False sharing）**現象，導致快取缺失次數顯著增加。

---

解題方法

此題為多項選擇題，切入點為逐項對照電腦結構教科書（如 Patterson & Hennessy 的 Computer Organization and Design）中的標準定義與理論機制，比對各語句的觀念是否正確：

1. 檢視編譯器優化的極限與程式員的責任。
2. 比對 3C 模型（Three Cs Model）官方標準的三種分類名稱。
3. 區分 Write-through 與 Write-back 的寫入行為差異。
4. 驗證 VIVT 快取架構的運作原理與避開 TLB 延遲的優點。
5. 分析 Write Invalidate 協定對多執行緒共享記憶體程式在多處理器上執行的影響。

---

選項分析

• (A) 錯誤
  雖然現代編譯器具備一定程度的循環優化能力（例如 Loop Interchange、Loop Tiling/Blocking），但編譯器無法自動修正所有資料結構的記憶體佈局或演算法架構。

核心觀念

本題考驗深度學習加速領域中 FP8（8-bit Floating Point）浮點數格式（包含 E4M3 與 E5M2）的規格、最大數值、最小絕對值推導，以及 Transformer Engine 採用 FP8 進行混合精度訓練（Mixed-Precision Training）的核心觀念。

浮點數表示法的基本公式為：
$V = (-1)^S \times (1 + M) \times 2^{E - B}$

其中：

• $S$ 為符號位元（Sign bit）。
• $E$ 為偏置指數（Biased Exponent），若指數位元數為 $k$，偏置量（Bias）值為 $B = 2^{k-1} - 1$。
• $M$ 為尾數（Mantissa / Fraction）。
• 非規格化數（Subnormal number）時，$E = 0$，公式調整為 $V = (-1)^S \times (0 + M) \times 2^{1 - B}$。

---

解題方法

1. E4M3 與 E5M2 規格分析

• E4M3 格式（1 位元符號 + 4 位元指數 + 3 位元尾數）：

  • 指數偏置量 $B = 2^{4-1} - 1 = 7$。
  • 最大有限數值（Max Value）：在 OCP / NVIDIA FP8 標準中，E4M3 為了提高動態範圍不保留 $\pm\infty$，僅將 $E=\text{1111}_2$ 且 $M=\text{111}_2$ 留作 NaN。其最大數值發生於 $E=\text{1111}_2 (15)$ 且 $M=\text{110}_2$：
    $\text{Max}(E4M3) = \left(1 + \frac{6}{8}\right) \times 2^{15 - 7} = 1.75 \times 2^8 = 448$
    （若依傳統 IEEE 754 規範保留 $E=15$ 給 NaN/$\infty$，最大指數取 $14$ 且 $M=\text{111}_2$，最大值為 $(1 + 7/8) \times 2^{14-7} = 1.875 \times 128 = 240$）。
  • 最小正絕對值（Min Magnitude）：發生於最小非規格化數（$E = 0$ 且 $M = \text{001}_2$）：
    $\text{Min}_{>0}(E4M3) = \left(0 + \frac{1}{8}\right) \times 2^{1 - 7} = 2^{-3} \times 2^{-6} = 2^{-9} = \frac{1}{512} \approx 0.001953$

• E5M2 格式（1 位元符號 + 5 位元指數 + 2 位元尾數）：

  • 指數偏置量 $B = 2^{5-1} - 1 = 15$。
  • 最大有限數值（Max Value）：遵守傳統 IEEE 754 規範，$E=\text{11111}_2 (31)$ 保留給 $\infty$ 與 NaN。最大有限數發生於 $E=\text{11110}_2 (30)$ 且 $M=\text{11}_2$：
    $\text{Max}(E5M2) = \left(1 + \frac{3}{4}\right) \times 2^{30 - 15} = 1.75 \times 2^{15} = 57344$
  • 最小正絕對值（Min Magnitude）：發生於最小非規格化數（$E = 0$ 且 $M = \text{01}_2$）：

參考書等級：大學部教材／期刊綜述

• $175$ B 參數若以 FP8 (1 Byte) 表示，所需記憶體約為 $175$ GB，超過單顆 H100（80 GB），故 (A) 錯。
• LLM 基準測試提供每顆加速卡的吞吐量 (tokens / sec)。

核心觀念

本題考查機器學習基準測試套件（MLPerf Benchmark Suite）的設計原則、AI 硬體加速器（GPU、TPU、專用加速器等）的性能表現評估、半導體先進製程發展，以及機器學習資料集建立過程中所面臨的資料隱私（Data Privacy）挑戰。

1. MLPerf 基準測試套件：由 MLCommons 推出的機器學習標準基準測試，用於衡量 ML 訓練（Training）與推論（Inference）在各式硬體平台上的執行時間（Execution Time）與效能。
2. 混合精度（Mixed Precision）與 FP8 Data Type：在大型語言模型（LLM，如 GPT-3）訓練中，啟用低精度資料型態（如 FP8、BF16）可顯著減少記憶體頻寬需求與運算延遲，進而提升運算效能。
3. AI 晶片與半導體製程：當前主流 MLPerf 測試硬體（如 NVIDIA H100 等）高度依賴台積電（TSMC）的 5 奈米家族（如 TSMC 4N）先進製程。
4. 資料集與隱私權規範：建立具代表性且符合真實場景的 ML Benchmark 需要廣泛的真實資料，但常受限於個人資料保護法規（如 GDPR）與商業隱私風險。

---

解題方法

依據題幹所述背景資訊、MLPerf 官方公佈的效能數據（特別是 2023 年 11 月 Intel Gaudi2 啟用 FP8 精度後的 GPT-3 Benchmark 結果）與電腦結構中關於基準測試設計與晶片製造的常識進行邏輯推導：

1. 比較加速器性能：分析絕對語氣選項（如「GPU 永遠最快」或「Gaudi2 啟用 FP8 後超越 H100」）的真實性。
2. 分析 MLPerf 提交結構與製造技術：評估現有提交結果的硬體架構分布（GPU 為主）與晶片製程技術（台積電 5 奈米製程）。
3. 評估 Benchmark 建立的現實限制：探討機器學習資料集收集時隱私權對建立標準化 Benchmark 的影響。

---

選項分析

• (A) 錯誤
  • 說明：GPU 並非在所有 MLPerf 測試項目中都「絕對（always）」優於 CPU 或其他專用加速器（如 Google TPU、AWS Trainium 等 ASIC）。

本題考查對大型語言模型 (LLM) 在邊緣設備上部署的性能分析、優化策略以及 Roofline 模型應用的理解。題目提供了 TinyChat 的剖析數據和 Roofline 圖。

【題組共用題幹】（此題與 5, 6, 8 題共用部分文章，但 7 題的判斷主要依賴題目中提供的 TinyChat 剖析數據和 Roofline 圖。）

TinyChat 工作負載分析：

• 總執行時間：340ms
• Context Stage：10ms
• Generation Stage：310ms
• Generation Stage 佔總時間的 $310/340 \approx 91.2\%$，是主要瓶頸。

Roofline 圖分析：

• 圖中有兩條橫線代表 Peak Throughput (FLOPs/s)，分別是 144 TFLOPS (W4A16) 和 1 TFLOPS (W16A16)。這表示不同的數據類型精度會影響峰值吞吐量。
• 圖中有兩條斜線代表 Memory Bandwidth (FLOPs/Byte)。
  • Context Stage: Arithmetic Intensity (AI) >= 165 FLOPs/Byte
  • Generation Stage: AI = 4 FLOPs/Byte (W4A16) 或 AI = 1 FLOPs/Byte (W16A16)
• 圖中顯示了兩個階段的點。Context Stage 的點位於 AI 較高且接近水平線的部分，表示它可能是計算密集型。Generation Stage 的點位於 AI 較低且接近斜線的部分，表示它可能是記憶體密集型。

詳解：
(A) We should include more arithmetic units in the chip design as it will increase the peak throughput and effectively accelerate the LLM.
增加算術單元可以提高峰值吞吐量（Peak Throughput），這對於計算密集型任務有效。然而，Roofline 圖顯示 Generation Stage 的 Arithmetic Intensity 較低 (AI = 4 FLOPs/Byte)，這通常表示該階段是記憶體密集型（memory-bound），而不是計算密集型（compute-bound）。對於記憶體密集型任務，增加算術單元對性能的提升有限，因為瓶頸在於數據從記憶體傳輸到處理器的速度，而不是處理器自身的計算能力。由於 Generation Stage 佔據了 LLM 絕大部分的執行時間，因此單純增加算術單元不太可能「有效地」加速整個 LLM。
因此，(A) 錯誤。

(B) Because the performance of the LLM is mostly memory-bound, increasing the memory bandwidth should improve the performance.
從 Roofline 圖可以看出，Generation Stage 的 Arithmetic Intensity 為 4 FLOPs/Byte。這個值相對較低，且其點位於 Roofline 圖的「斜坡」部分，這表明 Generation Stage 是一個記憶體密集型（memory-bound）的工作負載。

本題考查對大型語言模型訓練系統架構，特別是 NVIDIA DGX GH200 超級電腦的理解，包括記憶體容量、性能、擴展性、軟體優化策略以及快取阻塞（cache blocking）等概念。

【題組共用題幹】（此題與 5, 6, 7 題共用部分文章，但 8 題的判斷主要依賴題目中提供的 DGX GH200 規格和 LLM 訓練假設。）

DGX GH200 規格摘要：

• 32 GH200 Superchips
• 19.5 TB Shared Memory (總記憶體容量)
• 128 petaFLOPS FP8 AI performance (峰值性能)
• GH200 Superchip 包含 Grace CPU 和 Hopper GPU。
  • GPU Memory: 480 GB LPDDR5X (HBM3e)
  • CPU Memory: 624 GB LPDDR5X (Grace CPU)
  • NVLink-C2C interconnect between CPU and GPU for unified, cache-coherent memory.
  • 16x PCIe-5 512GB/s
  • NVLink Network > 25 TB/s

LLM 訓練假設：

• 目標 LLM 有 1 兆（trillion）個參數。
• 每個參數使用 FP8 表示。
• 大部分計算是 FP8 矩陣向量乘法。
• 算術強度（Arithmetic Intensity）為 1 FLOPs/Byte (for FP8)。

詳解：
(A) If we only use the GPU memory to store the input data and parameters, the total GPU memory capacity, 144GB x 32 = 4.6TB, should be enough to run a LLM with 1 trillion parameters, but the performance is limited to 32 x 4900 GB/s * 1 FLOPS = 5 petaFLOPS, which is only 40% of the peak performance of the system.
首先計算總 GPU 記憶體容量：
DGX GH200 有 32 個 GH200 Superchips。每個 GH200 Superchip 有 480 GB HBM3e GPU 記憶體。
總 GPU 記憶體容量 = $480 \text{ GB/chip} \times 32 \text{ chips} = 15360 \text{ GB} = 15.36 \text{ TB}$。
題目中給出的是 144GB x 32 = 4.6TB，這與實際規格不符。144GB 可能是其他型號的 GPU 記憶體，或者是一個錯誤的數字。根據圖表，每個 Hopper GPU 配備 480GB HBM3e。
其次，計算 1 兆參數 LLM 所需記憶體：
1 兆參數 = $10^{12}$ 參數。每個參數 FP8 (1 Byte)。
所需記憶體 = $10^{12} \text{ Bytes} = 1 \text{ TB}$。
$1 \text{ TB}$ 顯然小於 $15.36 \text{ TB}$ (實際 GPU 總記憶體)，也小於題目錯誤計算的 4.6TB。所以從記憶體容量來看，GPU 記憶體是足夠的。

然後計算性能限制：
算術強度 (AI) = 1 FLOPs/Byte。這表示工作負載是記憶體密集型（memory-bound）。
性能（Performance）受限於記憶體頻寬。
每個 Hopper GPU 的記憶體頻寬為 4900 GB/s (圖中為 4.9TB/s)。
總記憶體頻寬 = $4900 \text{ GB/s/GPU} \times 32 \text{ GPUs} = 156800 \text{ GB/s} = 156.8 \text{ TB/s}$。
由於 AI = 1 FLOPs/Byte，所以峰值記憶體頻寬下的性能 = $156.8 \text{ TB/s} \times 1 \text{ FLOP/Byte} = 156.8 \text{ TFLOPS}$。
題目中計算的性能是 $32 \times 4900 \text{ GB/s} \times 1 \text{ FLOPs} = 156.8 \text{ TFLOPS} = 0.1568 \text{ PFLOPS}$。
這個值與系統峰值 FP8 AI 性能 128 petaFLOPS 相比，顯然不是 40%。它是遠遠小於峰值性能的。
因此，(A) 錯誤，因為其記憶體容量計算錯誤，且性能計算與峰值性能的比較也錯誤。

(B) It is possible to accelerate the training process for a 1-trillion parameter LLM with 2 sets of DGX GH200, but the scalability should be poor, according to the IEEE Spectrum article shown in a previous question.
使用 2 套 DGX GH200 當然可以加速訓練，因為增加了計算和記憶體資源。

核心觀念

本題涵蓋作業系統的虛擬記憶體、CPU 排程、死結、檔案一致性語意與即時系統，以及資料庫的並行控制。判斷是非時，關鍵在於區分：

• 「通常如此」與「必然如此」。
• 特定演算法的性質與所有演算法的性質。
• 模型本身的定義與作業系統實作時可能使用的硬體輔助。
• 協定保證的性質與協定未保證的性質。

解題方法

每一敘述先找出其隱含的「絕對化」條件。例如「frames 越少，page faults 越多」只有在具備堆疊性質的頁面置換演算法中才成立；若題目未指定演算法，便不能視為普遍真理。

死結與排程題則要區分「系統目前狀態」及「未來資源配置政策」。安全狀態代表存在一條可完成所有工作的安全序列，但不代表系統若任意分配資源，未來永遠不會進入死結。

選項分析

A. The less frames, the more page faults.

錯誤。

頁框數減少時，缺頁次數不一定增加。對具有堆疊性質的演算法，例如 Optimal 與 LRU，較多頁框包含較少頁框時的所有頁面，因此頁框增加不會增加缺頁次數。

但 FIFO 可能發生 Belady’s anomaly：頁框增加後，缺頁次數反而增加。因此，若未指定使用 LRU、Optimal 等堆疊演算法，不能斷言頁框越少就必然有越多缺頁。

B. The less frames, the more page fault rates.

錯誤。

缺頁率定義為：

$$\text{page fault rate} = \frac{\text{page faults}}{\text{memory references}}$$

若比較的是同一段記憶體參考字串，分母固定，缺頁率的變化方向與缺頁次數相同。由於 FIFO 等演算法可能出現 Belady’s anomaly，頁框較少時也不保證缺頁率必然較高。

C. The smaller time quantum for scheduling, the longer average turnaround time.

錯誤。

Round-Robin 的時間片 $q$ 變小，會增加 context switch 的頻率；若 context switch 有成本，確實常使平均 turnaround time 上升。但這不是必然結果。

例如系統只有一個行程時，不論 $q$ 多大，皆不需在行程間切換，turnaround time 不變。不同工作負載下，較小的時間片也可能使短工作較早完成，降低部分行程的 turnaround time。因此不能將此敘述視為普遍定律。

D. Firmware can be executed faster in ROM than in RAM.

錯誤。

ROM 的主要用途是保存開機程式、韌體與不應輕易修改的內容，不是提供較快的執行速度。一般而言，RAM 的讀寫與執行速度通常快於 ROM。

實務上，韌體常先從 ROM 或 Flash 載入 RAM，再由 RAM 執行，以提升效能。

E. Working set model has to be supported by MMU.

錯誤。

Working set model 用來描述某行程在時間窗 $\Delta$ 內實際使用的頁面集合：

$$W(t,\Delta) = \{\text{在 }(t-\Delta,t)\text{ 期間被參考的頁面}\}$$

其核心概念是由作業系統依據頁面參考歷史估計行程所需頁面數量，以避免 thrashing。MMU 可提供頁表、reference bit、dirty bit 等硬體資訊，使作業系統較容易近似 working set；但 working set model 本身不是必須由 MMU 直接實作或支援的機制。

F. A safe state will not go to a deadlocked state.

錯誤。

核心觀念

本題考查「硬體中斷、裝置驅動程式、輸入事件佇列與視窗管理員」之間的分工。

滑鼠移動時，硬體通常會產生一筆輸入資料，例如：

• $x$ 方向位移
• $y$ 方向位移
• 按鍵狀態
• 滑鼠滾輪狀態

基本流程如下：

$$\text{滑鼠硬體} \rightarrow \text{硬體中斷} \rightarrow \text{ISR} \rightarrow \text{滑鼠驅動程式} \rightarrow \text{輸入事件佇列} \rightarrow \text{視窗管理員} \rightarrow \text{重新繪製游標}$$

其中，ISR 與滑鼠驅動程式的職責不同：

• ISR（Interrupt Service Routine）：在硬體中斷發生後立即執行，負責快速處理中斷、讀取或確認硬體狀態。
• 滑鼠驅動程式：負責理解滑鼠資料格式，將原始資料轉換成作業系統可使用的輸入事件，並送入核心輸入系統。
• 視窗管理員：接收輸入事件，更新游標位置與相關視窗狀態，安排畫面重繪。

解題方法

應依照「硬體事件如何一路傳遞到使用者介面」分析，而不是把所有工作都歸給 ISR 或視窗管理員。

1. 滑鼠移動並產生資料

滑鼠偵測到位移後，會將資料寫入滑鼠控制器或裝置本身的緩衝區，並透過硬體中斷通知處理器。

此時中斷的意義是：

「滑鼠有新的輸入資料，請作業系統處理。」

2. ISR 先處理硬體中斷

處理器收到中斷後，執行滑鼠裝置所註冊的 ISR。ISR 通常進行下列工作：

1. 確認中斷來源。
2. 從滑鼠控制器或裝置暫存器讀取原始資料。
3. 清除或確認中斷狀態。
4. 將資料放入核心中的暫存區、環形佇列或輸入緩衝區。
5. 安排後續的驅動程式處理工作。

ISR 必須盡快結束，避免長時間佔用處理器，也避免阻塞其他中斷。因此，完整的資料轉換與事件分派通常不會全部放在 ISR 中。

3. 滑鼠驅動程式處理原始資料

題目特別指出「mouse driver（not ISR）」是在要求說明 ISR 之外的驅動程式工作。

滑鼠驅動程式會：

1. 從 ISR 放入的緩衝區取出資料。
2. 依照滑鼠協定解析資料封包。
3. 將原始位移轉換成作業系統使用的座標變化，例如：

$$(x_{\text{new}}, y_{\text{new}}) = (x_{\text{old}}+\Delta x,\ y_{\text{old}}+\Delta y)$$

4. 判斷按鍵按下、放開、滾輪移動等狀態。
5. 建立標準化的輸入事件。
6. 將事件放入核心輸入佇列，並通知等待輸入的輸入子系統或視窗系統。

驅動程式不負責直接繪製游標，也不應直接操作視窗管理員的畫面繪圖邏輯。它的主要工作是「將硬體資料轉換成作業系統可理解的輸入事件」。

驅動程式會被呼叫嗎？

會，但不是由滑鼠硬體直接呼叫，也通常不是在 ISR 中同步呼叫完整的驅動程式處理流程。

較完整的描述是：

核心觀念

本題考查作業系統（如 Linux Kernel）中常見的資料結構優化技術——侵入式鏈結串列（Intrusive Linked List） 與傳統鏈結串列（Non-intrusive / Traditional Linked List）在記憶體架構 (Memory Hierarchy) 與記憶體管理 (Memory Management) 上的效能差異。

主要涵蓋的核心觀念包括：

1. 記憶體快取區域性 (Cache Locality)：包括空間區域性 (Spatial Locality) 與時間區域性 (Temporal Locality)，以及對 L1/L2/L3 Cache Miss 和 TLB Miss 的影響。
2. 動態記憶體配置開銷 (Dynamic Memory Allocation Overhead)：減少 malloc / kmalloc 調用次數與堆積中介資料 (Heap Metadata Overhead) 開銷，降低記憶體碎裂化 (Memory Fragmentation)。
3. 指標解引用與間接存取 (Pointer Dereferencing & Indirection)：減少雙重指標追蹤對 CPU 管道 (Pipeline) 與記憶體頻寬的負擔。
4. 結構體位移計算 (container_of 巨集 / offsetof)：以編譯期常數計算 $O(1)$ 時間取得包含容器的起始位址。

---

解題方法

1. 傳統鏈結串列與侵入式鏈結串列的記憶體佈局對比

• 傳統鏈結串列 (Traditional Linked List)：
  鏈結節點（Node）與資料主體（Data Payload）分離。

  struct node {
      void *data;         // 指向實際資料空間的指標
      struct node *next;
      struct node *prev;
  };
  

  • 記憶體配置：插入一個元素需要兩次配置（一次為資料本身，一次為 struct node 包裝節點）。
  • 記憶體位址：node 與 data 位於記憶體中不連續的不同區塊。

• 侵入式鏈結串列 (Intrusive Linked List)：
  指標結構直接嵌入（Embed）於資料結構體內部。

  typedef struct list {
      struct list *next;
      struct list *prev;
  } list_t;
  
  typedef struct item {
      int val;
      list_t links;    // 直接內嵌鏈結指標
  } item_t;
  

  • 記憶體配置：資料與鏈結指標一體成型，插入元素只需一次配置（配置整個 item_t）。
  • 記憶體位址：links 與 val 在記憶體中完全連續（同屬於同一個 item_t 實例）。

2. 記憶體維度的具體優勢推導

1. 顯著提升快取區域性 (Enhanced Cache Locality & Reduced Cache Misses)

   • 在傳統串列中，走訪串列時 CPU 先載入 struct node，接著必須根據 node->data 指標進行第二次記憶體解引用 (Pointer Dereference)。這兩次讀取位在不連續的記憶體位址，極易引發多次 L1/L2 Data Cache Miss 與 TLB Miss。
   • 在侵入式串列中，list_t 與資料欄位（如 val）屬於同一個記憶體區塊。當 CPU 讀取 next / prev 指標時，硬體預取（Prefetching）機制或同一條快取行（Cache Line，通常為 64 Bytes）會同時將相鄰的資料欄位一併載入快取，極大地改進了空間區域性 (Spatial Locality)，減少存取延遲。

2. 消除節點包裝的記憶體開銷與碎片化 (Zero Extra Allocation & No Heap Metadata Overhead)

   • 傳統串列額外配置 struct node 時，記憶體配置器（如 Linux 的 kmalloc / Slab Allocator）會在每個區塊前附加中介資料 (Header Metadata)，且產生碎片 (Fragmentation)。若節點數極多，記憶體浪費非常顯著。
   • 侵入式串列不需任何額外的包裝節點配置，空間開銷僅為結構體本身的 sizeof(list_t)（雙向串列為 2 個指標大小：64-bit 架構下為 $2 \times 8 = 16\text{ bytes}$）。

3. 支援多重串列嵌入且零資料複製 (Multiple List Embedding without Data Duplication)

核心觀念

本題考驗作業系統（Operating System）中**輪轉調度法（Round Robin, RR Scheduling）的搶佔機制、任務狀態轉移（Task State Transition），以及非同步 I/O（Asynchronous I/O）**如何配合實現特定時間間隔的執行與阻塞行為。

1. 輪轉調度法（Round Robin Scheduling）：

   • 屬搶佔式（Preemptive）調度演算法，系統定義一個固定的時間斷片（Time Quantum, 記為 $Q$）。本題中 $Q = 1\text{ ms}$。
   • 搶佔條件：若任務屬於完全的 CPU 密集型（CPU-bound），即在 $1\text{ ms}$ 時間斷片內未主動發起阻塞式系統呼叫（Blocking System Call）或讓出 CPU（Yield），則會在執行滿 $1\text{ ms}$ 時精確地被計時中斷（Timer Interrupt）搶佔，並置於就緒佇列（Ready Queue）末端。
   • 恢復執行（Resume）週期：若就緒佇列中共有 $N$ 個 CPU-bound 任務，某任務被搶佔後，需等待其餘 $N-1$ 個任務各執行 $1\text{ ms}$（即等待時間為 $(N-1) \times 1\text{ ms}$），隨後回到佇列頭部並恢復執行。只要任務為無限迴圈且佇列中任務數 $N$ 不變，此「執行 $1\text{ ms} \rightarrow$ 被搶佔 $\rightarrow$ 等待 $(N-1)\text{ ms} \rightarrow$ 恢復執行」的過程將無限期持續重複（Resume indefinitely）。

2. 任務狀態轉移與非同步 I/O：

   • 任務在三態模型中切換：RUNNING（運行）、READY（就緒）、BLOCKED（阻塞）。
   • 傳統同步 I/O（Synchronous I/O）：發起呼叫時會立刻讓任務轉入 BLOCKED 狀態，無法在 I/O 進行的同時進行 CPU 計算。
   • 非同步 I/O（Asynchronous I/O）：發起呼叫（如 POSIX aio_read）後系統立即返回控制權，任務保持在 RUNNING/READY 狀態繼續執行 1 秒的 CPU 運算；待 1 秒運算結束後，任務再透過阻塞等待指令（如 aio_suspend）進入 BLOCKED 狀態 1 秒。

---

解題方法

第一部分：分析搶佔與無限期恢復執行的條件（5 points）

要使輪轉調度器精確地每 $1\text{ ms}$ 搶佔任務，且任務能在搶佔後無限期恢復執行，必須滿足以下三個條件：

1. 時間斷片設定：作業系統調度器的時間斷片設定為 $Q = 1\text{ ms}$。
2. 任務行為屬性：任務必須為無限迴圈的 CPU 密集型任務（CPU-bound Task）。任務在 $1\text{ ms}$ 的執行期間內絕不發起任何阻塞式 I/O、主動讓出（Yield）或終止，確保每次均由計時中斷觸發搶佔。
3. 就緒佇列動態：就緒佇列（Ready Queue）中保持有固定數量 $N$ 個此類 CPU-bound 任務。當任務執行滿 $1\text{ ms}$ 被搶佔移至佇列尾端後，經歷 $(N-1) \times 1\text{ ms}$ 的等待時間即可再次被調度執行（Resume），且此循環因任務不終止而無限期重複。

第二部分：設計 Daemon Task T 的虛擬碼（10 points）

任務 $T$ 的目標為：執行 1 秒 $\rightarrow$ 阻塞 1 秒 $\rightarrow$ 無限循環。

• 執行 1 秒階段：發起非同步 I/O 請求（不阻塞控制權），並透過時間檢查進行 1 秒的 CPU 密集型運算。在 RR 調度器作用下，這 1 秒內任務 $T$ 會被搶佔與調度數次（累積執行時間或經過時間達 1 秒）。
• 阻塞 1 秒階段：1 秒計算完成後，呼叫阻塞指令（如 aio_suspend 或定時器阻塞）等待非同步 I/O / 定時器完成，使作業系統將任務 $T$ 的狀態轉為 BLOCKED，持續 1 秒不佔用 CPU 資源。

---

細節與選項分析

1. 第一小題細節分析：

   • 為何必須強調 CPU-bound？ 若任務在 $1\text{ ms}$ 內發起了同步 I/O，任務會在未滿 $1\text{ ms}$ 時即主動釋放 CPU 進入 BLOCKED 狀態，破壞「精確每 $1\text{ ms}$ 被搶佔」的條件。
   • Resume 的精確時間推導：設就緒佇列中有 $N$ 個任務，忽略上下文切換（Context Switch）時間 $S$。當前任務被搶佔後，前面有 $N-1$ 個任務排隊，每個任務消耗 $1\text{ ms}$，因此恢復執行的等待時間為：
     $T_{\text{wait}} = (N-1) \times 1\text{ ms}$
     若考慮上下文切換開銷 $S$，則等待時間為 $T_{\text{wait}} = (N-1) \times (1\text{ ms} + S)$。

2. 第二小題細節分析：

   • 提示 Asynchronous I/O 的作用：若使用傳統同步 I/O（read() / sleep()），任務呼叫的瞬間就會進入 BLOCKED 狀態，無法達成「先持續執行 1 秒，再阻塞 1 秒」的要求。