115 成大資工所考古題詳解｜硬體考點分析

題型與配分

全卷 8 頁、100 分，不可使用計算機，於本試題紙上作答者不予計分。

答案必須按題號彙整到答案卷上指定的表格內。

計算機組織（50%）

卷首在配對題之前先給五段參考概念（Reference Concepts），主題分別是：

1. MESI cache coherence
2. pipeline 開銷
3. memory hierarchy 目標（L1 與 L2 各自最佳化什麼）
4. 分支範圍限制（固定長度 ISA 的條件分支 offset）
5. spatial locality（存取步長的影響）

題目說明 Column B 含有干擾項（錯誤敘述），選項數多於 Column A，要為每一項選出最佳配對。

問題 1：Core Mechanisms（25%）

把 Column A 的五個機制配到 Column B 的十一個敘述：

1. Pipelining
2. L2 Cache
3. Cache Block（Line）
4. MESI Protocol
5. PC-relative Addressing

問題 2：Scenario Analysis（25%）

把五個情境配到十一個行為敘述：

1. single-cycle 改成五級 pipeline
2. 用 A[j][i] 跨步存取 2D array
3. Core A 寫入 Shared（S）狀態的資料
4. 分支目標在 1 MB 之外
5. L1 miss 但 L2 hit

作業系統：選擇題（30%，15 題各 2 分）

• 第 1 題｜ECC 能修正錯誤的前提條件
• 第 2 題｜完整的啟動程式（full bootstrap）的特性
• 第 3 題｜IBM 的 ISAM（索引循序存取法）的索引結構，與 112 第 1(5) 題相同
• 第 4 題｜動態儲存配置：first fit、best fit、worst fit 的比較
• 第 5 題｜DMA 式 I/O 的代價與整體效益
• 第 6 題｜interrupt-driven 與 polling 的偵測延遲
• 第 7 題｜無 journaling 的 file system 的 crash consistency 寫入順序
• 第 8 題｜兩層記憶體的頁面遷移政策如何減少來回搬移（ping-pong）
• 第 9 題｜3 個 frame、LRU、參考串 1,2,3,4,1,2,5,1,2,3,4,5，求 page fault 數
• 第 10 題｜huge page（huge pages）的利弊，中央 115 第 6、13 題也考過 huge page
• 第 11 題｜HDD 的 I/O scheduler 與延遲：FCFS、SSTF、SCAN
• 第 12 題｜什麼情況最可能增加 SSD 的 write amplification
• 第 13 題｜三個週期性工作 T1(1/4)、T2(1.5/6)、T3(2/12) 的 schedulability，涉及 EDF 與 RM
• 第 14 題｜priority inversion 與其緩解：priority inheritance 與 priority ceiling
• 第 15 題｜non-coherent cache 下，DMA 寫入完成後 CPU 讀取前該做什麼

作業系統：簡答題（20%）

簡答題 1：建立孤兒 process（8%）

在給定的 C 程式骨架中補完 parent process 與 child process 兩個 block，使 child process 成為孤兒 process。

簡答題 2：LSM-tree（12%）

題目先用一整頁說明 LevelDB 的架構（WAL → MemTable（skip list）→ Immutable MemTable → flush 成 L0 的 SSTable → 逐層 compaction；刪除用 tombstone；讀取由新到舊逐層搜尋），再問三個問題：

• 簡答題 2(a)（4%）｜LSM-tree 的 write amplification 從何而來，要連結到上述維護流程
• 簡答題 2(b)（4%）｜讀取放大從何而來，特別是 L0 為什麼會增加查詢要檢查的檔案數
• 簡答題 2(c)（4%）｜什麼情況下 compaction 會變成瓶頸，造成尾端延遲上升或寫入停滯

作答時要注意的地方

1. 於試題紙上作答不予計分，答案要按題號彙整到答案卷的表格。
2. 計組段的 Column B 選項數多於 Column A，且含干擾項。
3. 簡答題 2 的每個小問都要連結到題目給的那一頁說明。
4. 選擇題第 13 題給了三個工作的週期與執行時間。

準備方向

• MESI、pipeline 開銷、L1 與 L2 的設計目標、PC-relative 分支範圍、spatial locality（115 計組段）。
• LSM-tree 與鍵值儲存：110 第 2 題、115 簡答題 2；write amplification、讀取放大、write stall。
• 儲存系統的現代議題：112 第 3 題的 tail latency，115 的 write amplification、ECC 與 SSD 管理。
• 即時 scheduling 的 EDF 與 RM schedulability（115 選擇題 13）。
• DMA 與 non-coherent cache（115 選擇題 15）。
• crash consistency 的寫入順序（115 選擇題 7）。
• ISAM：112 第 1(5) 題、115 選擇題 3。
• huge page：113 第 4(3) 題、115 選擇題 10。