115 成大資工所硬體考點分析

題型與配分

科目：計算機組織與系統，系所「電機資訊學院－資訊聯招」，日期 0203、節次 1，全卷 100 分、8 頁。不可使用計算機、於本試題紙上作答者不予計分。

115 年是成大硬體十年裡題型最創新的一年：計組段改成配對題（matching），而且卷首先給五段「Reference Concepts」供你推理，然後明確警告「Column B 含有「干擾項」（錯誤敘述），而且選項數多於 Column A，請為每一項選出最佳配對」。

答案必須按題號彙整到答案卷上指定的表格內——這個規定從 106 年沿用至今。

計算機組織（50%）

卷首給的五段「參考概念」

卷子在配對題之前先給了五段說明，主題分別是：

1. MESI 快取一致性
2. 管線開銷
3. 記憶體階層目標（L1 與 L2 各自最佳化什麼）
4. 分支範圍限制（固定長度 ISA 的條件分支位移）
5. 空間區域性（存取步長的影響）

這五段等於把配對的推理依據交給考生，作答前一定要仔細讀，干擾項就是拿這些概念的「反面」寫成的。

問題 1：Core Mechanisms（25%）

把 Column A 的五個機制配到 Column B 的十一個敘述（含干擾項）：

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

干擾項的辨識方式：Column B 摻了幾個敘述，分別在 「管線改善的是吞吐量還是單指令延遲」、「硬體能不能保證任兩道指令間零資料危障」、「L1 與 L2 誰大誰小」、「快取區塊利用的是連續性還是非連續結構」、「分頁與快取各由誰管理」、「跳躍指令有沒有位元寬度限制」 這幾組觀念上動手腳。先把這幾個方向確認好，干擾項就會自己浮出來

問題 2：Scenario Analysis（25%）

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

1. 單週期改成五級管線
2. 用 A[j][i] 跨步存取二維陣列
3. Core A 寫入 Shared（S）狀態的資料
4. 分支目標在 1 MB 之外
5. L1 失誤但 L2 命中

干擾項的辨識方式：這一組的誘答分別踩在 「管線級數與總執行時間的關係」、「空間區域性受不受存取順序影響」、「MESI 的 Shared 狀態能不能直接寫」、「位移欄位的位元寬度是不是硬性限制」、「L1 與 L2 的速度差」、「快取寫入會不會直達硬碟」 這幾個點上。每一個誘答都是把某個限制或差異說成不存在

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

• 1｜ECC 能修正錯誤的前提條件——要想到「ECC 自己也存在同一個磁區裡」這件事
• 2｜完整的啟動程式（full bootstrap）的特性——關鍵是它存在哪裡，那決定了它會不會被竄改
• 3｜IBM 的 ISAM（索引循序存取法）的兩層索引結構——與 112 年第 1(5) 題一字不差
• 4｜動態儲存配置——要能比較 first fit／best fit／worst fit 在「配置速度」與「空間利用率」上的取捨
• 5｜DMA 式 I/O——要能同時說出它的代價與它的整體效益，兩者並存才是完整答案
• 6｜中斷驅動對輪詢——要會用「週期性取樣」的觀點推出輪詢的平均與最壞偵測延遲
• 7｜無日誌檔案系統的崩潰一致性寫入順序——判準是「崩潰發生在任兩次寫入之間時，磁碟上會不會出現指向垃圾的指標」
• 8｜兩層記憶體的頁面遷移政策，如何減少來回搬移（ping-pong）——可以借用控制系統裡防止震盪的手法去想
• 9｜3 個頁框、LRU、參考串 1,2,3,4,1,2,5,1,2,3,4,5，求頁錯誤數。這是 Belady's anomaly 的經典參考串，但這裡問的是 LRU
• 10｜大頁（huge pages）的利弊——好處在 TLB，代價要能想到不只一項。中央 115 年第 6、13 題也考過大頁
• 11｜HDD 的 I/O 排程器與延遲——要能對 FCFS／SSTF／SCAN 三者同時比較「平均尋道距離」與「公平性／尾端延遲」兩個維度，選項就是拿這兩個維度混搭
• 12｜什麼情況最可能增加 SSD 的寫入放大——要從可用空間、寫入模式、OS 有沒有通知 SSD 哪些區塊已失效這幾個因素去想
• 13｜三個週期性工作 T1(1/4)、T2(1.5/6)、T3(2/12) 的可排程性——要先算出總使用率 U，再分別對照 EDF 與 RM 的條件。RM 的界限公式要背，而且要知道它是充分條件還是充要條件；選項會拿 n→∞ 的極限值來混淆
• 14｜優先權反轉與其緩解——要能比較優先權繼承與優先權天花板兩種協定，各自解決什麼、代價是什麼
• 15｜非一致性快取下，DMA 寫入完成後 CPU 讀取前該做什麼——要想到 DMA 繞過了快取，再推出快取裡的資料可能處於什麼狀態

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

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

要在給定的 C 程式骨架中補完父程序與子程序兩個區塊，使子程序成為孤兒程序。考孤兒程序的定義（與殭屍程序區分），以及孤兒程序最後會被誰收養。要控制好父子程序結束的先後順序。

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

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

• (a) 4%｜LSM-tree 的寫入放大從何而來（要連結到上述維護流程）。要追蹤一筆資料從寫入到最底層之間被寫了幾次
• (b) 4%｜讀取放大從何而來？特別是 L0 為什麼會增加查詢要檢查的檔案數。只答「要查很多層」拿不到分數，要指出 L0 與 L1 之後在結構上的差異
• (c) 4%｜什麼情況下 compaction 會變成瓶頸、造成尾端延遲上升或寫入停滯。要從寫入速率與 compaction 速率的相對關係切入，說明 LevelDB 的保護機制

題目給的那一頁說明就是答題依據，每一小問都要「連結到上述流程」才算答到點上。

這份考卷的難點

1. 計組段的配對題表面上簡單，實際上干擾項設計得很精細。 有些敘述只在「方向」上與正確版本相差一個字。卷首的參考概念已經把這些都講清楚了，關鍵是要真的讀進去。
2. 簡答題 2 的 LSM-tree 佔 12 分，而且要講到具體的結構機制，泛泛之論拿不到分數。
3. 選擇題第 7 題的崩潰一致性順序：要從「崩潰可能發生在任何兩次寫入之間」去推，順序錯了就可能讀到垃圾。
4. 選擇題第 13 題要記住 RM 的利用率界限公式，而且選項刻意拿 n→∞ 的極限值來混淆。

準備建議

• 115 年的計組段是配對題，而且卷首給了參考概念——這代表成大在降低計組段的難度、改為測驗「能不能正確對應概念」。116 年若延續，準備方向應該是把每個機制的一句話定義背熟，而不是練計算
• LSM-tree 是成大近年的招牌題材（110 年第 2 題的鍵值儲存設計、115 年簡答題 2）。要能講出完整的寫入與讀取流程，以及寫入放大、讀取放大、write stall 各自的成因
• 儲存系統的現代議題在 112、115 兩年都佔了不少分數：寫入放大、TRIM、over-provisioning、垃圾回收、長尾延遲。這一塊課本上很少，要另外補
• 即時排程的兩個利用率界限（選擇題 13）：EDF 與 RM 的條件都要背，並知道各自的性質
• DMA 與非一致性快取的維護（選擇題 15）：兩個傳輸方向各要做什麼快取操作
• 崩潰一致性的寫入順序原則（選擇題 7）
• ISAM 在 112、115 兩年都考過同一題（112 第 1(5)、115 選擇題 3）