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

題型與配分

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

第 1 題：十個單選（20%）

• 第 1(1) 題｜保護與存取控制：Android 的 UID 隔離機制、MAC（強制存取控制）對 root 的限制、RBAC 對超級使用者風險的影響、能力式（capability-based）保護的實例
• 第 1(2) 題｜file system 與 mounting，哪個敘述是錯的
• 第 1(3) 題｜檔案配置與空間管理：FAT 的結構、consistency check 能不能完全復原、不可覆寫裝置還需要哪些機制、grouping 與 linked list 在找多個空閒 block 時的效率比較
• 第 1(4) 題｜unified virtual memory 用什麼機制同時 cache process 頁與檔案資料，與 109 第 5(2) 題同一考點，中正 110 第 1(3) 題、112 第 2 題也有
• 第 1(5) 題｜IBM 的 ISAM（索引循序存取法）的索引結構
• 第 1(6) 題｜polling 式 I/O 的主要低效來源
• 第 1(7) 題｜disk scheduling 演算法為何只考慮 seek distance，與中正 110 第 1(5) 題相同
• 第 1(8) 題｜一道指令會修改多個位置時，中途發生 page fault 該如何處理
• 第 1(9) 題｜Windows 的 dispatcher object 進入 signaled 狀態時會發生什麼
• 第 1(10) 題｜關於 Linux spinlock 哪個敘述不正確，與中正 110 第 1(7) 題相同

第 2 題：Solaris 分派表（10%）

卷上給完整的 Solaris time-sharing／interactive dispatch table（priority、time quantum、time quantum expired、return from sleep 四欄）。

• 第 2(1) 題（4%）｜priority 15 與 55 的 time quantum 各是多少毫秒
• 第 2(2) 題（3%）｜priority 35 的 thread 用完整個 time quantum 而未 blocking，新 priority 是多少
• 第 2(3) 題（3%）｜priority 40 的 thread 在 time quantum 用完前因 I/O 而 block，新 priority 是多少

第 3 題：儲存系統的長尾延遲（10%）

題目先解釋什麼是 tail latency（第 99 百分位的延遲可能是平均值的 100 倍），以及它對即時嵌入式系統與企業伺服器的 QoS 影響。

• 第 3(1) 題（5%）｜提出四個可能造成儲存系統 tail latency 的原因，要簡述
• 第 3(2) 題（5%）｜提出兩個解決 tail latency 的方法

第 4 題：分頁、TLB 與 multi-level page table（10%）

• 第 4(1) 題（2%）｜32-bit virtual address、4 KB 頁、最大 physical memory 32 GB，求 process 最多幾個頁與最多幾個 frame
• 第 4(2) 題（2%）｜單層 paging、記憶體存取 100 ns、TLB 存取 20 ns，要求 effective access time < 140 ns，求最小 TLB hit rate
• 第 4(3) 題（3%）｜無 page fault 時有效存取 100 ns、page fault 服務 15 ms、page fault rate 0.0000004，求 effective access time
• 第 4(4) 題（3%）｜64-bit virtual address、8 KB 頁、每個 page table entry 8 bytes、最大 physical memory 64 GB，求需要幾層 page table，交大 114 題組 B 也問 multi-level page table 的層數，參數不同

第 5 題：pipelined datapath（30%）

• 第 5(1) 題（5%）｜卷上給 single-cycle datapath 並標出五級的分界，問要加入什麼硬體資源來在各級之間暫存資料，為什麼
• 第 5(2) 題（12%）｜加上 pipeline register 後，這條 datapath 在處理 load 指令時有一個 bug，請描述並畫圖修正
• 第 5(3) 題（8%）｜各級時間 IF 100／ID 50／EX 100／MEM 200／WB 80 ps，求 load 與 store 指令的延遲（非 pipelining）
• 第 5(4) 題（5%）｜pipelining 後的 clock cycle 是多少，為什麼，理由要寫出來

第 6 題：hazard 處理（20%）

• 第 6(1) 題（5%）｜五級 pipeline 不處理 data hazard 時，在下列程式中插入必要的 NOP：addi x10, x14, 10、sub x13, x10, x14、xor x4, x3, x5
• 第 6(2) 題（5%）｜用程式碼重排（code reordering）緩解，開銷能不能完全消除，為什麼
• 第 6(3) 題（10%）｜Always-Taken 與 Always-Not-Taken 兩種 predictor 對 for (i=0;i<4;i++) x=a+b; 的準確率

作答時要注意的地方

1. 於試題紙上作答不予計分。
2. 第 5(2) 題 12 分，是全卷配分最高的單一小問，並要求畫圖。
3. 第 3 題明訂要簡述，且要求答出四個原因與兩個方法。
4. 第 6(1) 題要插幾個 NOP，要在答案卷註明對 register file 讀寫時序的假設。
5. 第 4(3) 題的 page fault 服務時間以毫秒計、記憶體存取以奈秒計。

準備方向

• pipelined datapath 與 pipeline register（112 第 5 題）。
• TLB effective access time 與 page fault 的 effective access time（112 第 4(2)(3) 題）。
• multi-level page table 的層數：112 第 4(4) 題，交大 114 題組 B（參數不同）。
• 儲存系統的 tail latency（112 第 3 題）。
• branch prediction 的準確率（112 第 6(3) 題）。
• Solaris dispatch table（112 第 2 題）。
• 112 第 1 題的細節題：ISAM、Windows dispatcher object、Android 保護模型、Linux spinlock；ISAM 115 年也考。