113 中正資工所考古題詳解｜硬體考點分析

題型與配分

全卷 5 頁、6 題、100 分。答案寫在試卷（答案卷）作答區內，限用藍色或黑色筆（含鉛筆），試題須隨試卷繳還。入場後 40 分鐘內不得離場。卷面沒有倒扣規定。

第 1 題：十五個單選（30%）

• 第 1(1) 題｜現代機器上 process 產生合法範圍以外的位址，立即的結果是什麼
• 第 1(2) 題｜控制器產生 interrupt 時會發生什麼事
• 第 1(3) 題｜Linux 的架構
• 第 1(4) 題｜單處理器系統上常用的哪一種技術，能讓程式設計師在 SMP 系統上利用平行度
• 第 1(5) 題｜FCFS CPU scheduling 最大的問題
• 第 1(6) 題｜Shortest Run Time First scheduling 的問題
• 第 1(7) 題｜Multilevel Feedback Queue 之下 CPU 時間如何在各 queue 間分配
• 第 1(8) 題｜為什麼發展 multi-level page table
• 第 1(9) 題｜在 virtual memory 中找空閒 frame 時，花 CPU 週期避免磁碟存取，哪一項值得
• 第 1(10) 題｜什麼是 buddy system
• 第 1(11) 題｜哪一項不是驗證使用者身分的依據（something you have、see、know、are）
• 第 1(12) 題｜sandbox 模式（sandbox model）指的是什麼
• 第 1(13) 題｜file system 中的 internal fragmentation 是什麼
• 第 1(14) 題｜disk scheduling 中 LOOK 演算法之後又提出其他 seek time 更長的演算法，目的是什麼
• 第 1(15) 題｜Internet 使用的應用層協定

第 2 題至第 6 題

• 第 2 題（10%）｜一段程式：pid = fork(); if (pid == 0) { fork(); thread_create(...); } fork();。(a) 共建立幾個不同的 process。(b) 共建立幾個不同的 thread
• 第 3 題（10%）｜demand paging 記憶體，page table 放在 register 中，換頁時若有空頁或被替換的頁沒被修改要 8 ms，被替換的頁有被修改要 20 ms，記憶體存取時間 100 ns，被替換的頁有 70% 的機率被修改，要使 effective access time 不超過 200 ns，最大可接受的 page fault rate
• 第 4 題（20%）｜十個依序的字組位址（十進位）：18, 121, 26, 123, 168, 169, 126, 68, 85, 89。(a) direct-mapped cache 有 10 個 block、每個 block 只有 1 個字組，對十個位址各自判斷是 hit、compulsory miss、conflict miss 或 capacity miss。(b) 每個 block 有 10 個字組時重做 (a)
• 第 5 題（15%）｜CPU 執行時間 = IC × CPI × clock cycle。N 級 pipeline 的理想 speedup 是 N，但 N = ∞ 時不可能有無限的加速。(a) 說明 pipelining 分別對 CPI 與 clock cycle 的影響（IC 不變）。(b) 列出兩個與 CPI 相關、使 speedup 無法無限的因素。(c) 列出兩個與 clock cycle 相關、使 speedup 無法無限的因素
• 第 6 題（15%）｜一段 MIPS 迴圈（lw $t0, -4($s0)、sw $t0, 996($s0)、addi $s0, $s0, -4、bne $s0, $zero, LOOP、trap，$s0 初始值 400）。(a) 找出在經典五級 pipeline（IF/ID/EXE/MEM/WB）上執行的所有 hazard。(b) 假設沒有任何處理 hazard 的硬體（沒有 interlock、branch predictor、forwarding），不改變指令順序，bne 在 EXE 階段解析，用最少的 NOP 重寫程式以避免 hazard。(c) (b) 的程式要執行幾個週期（到 trap 完成 WB 為止）

作答時要注意的地方

1. 全卷沒有倒扣規定，第 1 題每題 2 分。
2. 第 4 題要對十個位址各自標出 hit 或哪一種 miss，兩種 block size 用同一組位址。
3. 第 6(b) 題不可改變指令順序，bne 在 EXE 階段解析。
4. 第 2 題程式中的 thread_create 用來建立 thread。

準備方向

• 第 1 題十五題裡，非法位址（113 第 1(1) 題）、Linux 架構、SRTF、MLFQ、multi-level page table、找空閒 frame、sandbox 模式，在 108、109 年的單選題都出現過。106、107 年也有：非法位址在 107 第 1(2) 題，控制器產生 interrupt（113 第 1(2) 題）在 106 第 1(2) 題，FCFS 的問題（113 第 1(5) 題）在 107 第 1(3) 題，SRTF 在 107 第 1(4) 題，multi-level page table 在 106 第 1(8) 題。
• cache 3C 分類（113 第 4 題），107 第 8 題、111 第 6 題用同樣的兩種 block size，115 第 1 題改成同一組位址跑三種組態。
• page fault rate 與 effective access time（113 第 3 題），成大 106 第 7 題是同一題。
• fork 與 process 數（113 第 2 題），108 第 4 題也有。
• pipeline 與 CPU 效能方程式（113 第 5 題），111 第 3 題、115 第 3 題也有。
• pipeline hazard 與 NOP（113 第 6 題），111 第 4 題、112 多選第 4、5 題、114 填空第 3 題也有。
• 安全與保護（113 第 1(11)(12) 題），108 第 1(10) 題、111 第 1(10) 題也有。
• disk scheduling（113 第 1(14) 題），110 第 1(5) 題、112 填空第 1 題也有。