108 交大資工所考古題詳解｜硬體考點分析

題型與配分

全卷 9 頁、33 題、100 分，不可使用計算機，請使用答案卡作答。

複選題計分與 106、107 年相同。題組為 A（21–24，四小題）、B（25–27）、C（28–30）、D（31–33）。

OS 出現在第 1–9 題與題組 A、B，計組出現在第 10–20 題與題組 C、D。

複選題（1–20，80 分）

• 第 1 題（4%）｜process 與 thread：四個敘述考同 process 的 thread 共享哪些東西、kernel thread 的 PC、many-to-one 模型能否利用多核、many-to-one 模型下是否仍有 race condition
• 第 2 題（4%）｜現代 OS：四個敘述考 process 輸出字元是否需要 system call、process 離開 running 狀態的所有可能原因、microkernel 對通訊開銷的影響、shared memory IPC
• 第 3 題（4%）｜改造過的 readers-writers problem：把標準解法的 if (readcount == 1) wait(wrt) 改成 if (readcount <= Na) wait(wrt)、if (readcount <= Nb) signal(wrt)。要判斷 Na=1、Nb=0 時是否退化成標準解、Na=2、Nb=1 時最多有幾個讀者在等 wrt
• 第 4 題（4%）｜safe state 下哪些變更仍保證安全：增加可用資源、釋放已配置但不再使用的資源、增加某 process 的 Max、增加資源種類。與中央 108 年第 15 題同一個考點
• 第 5 題（4%）｜fork 迴圈的輸出總和：a = 5，迴圈兩次 fork，child process a -= 2 後印出、parent process 直接印出。要判斷「所有輸出數字的總和是否大於 14」「是否至少有一個小於零」「除 main process 外最多只建立兩個額外 process」
• 第 6 題（4%）｜virtual memory：四個敘述考邏輯與實體空間的大小關係、換出頁存在哪裡、頁面被 replace 時是否一定要 write-back、page fault 的處理流程
• 第 7 題（4%）｜disk scheduling：四個敘述考 FCFS 的 starvation、SSTF 的延遲變異、SCAN 在哪一個指標上是最佳、disk scheduling 對 RAM disk 是否有效
• 第 8 題（4%）｜看 ls -l 的輸出判讀：(a) 由目錄 lib/ 的硬連結數推子目錄數 (b) t -> program.c 是哪一種連結 (c) program 對群組成員的執行權限 (d) 配置給 intro.ps 的儲存空間是否剛好等於檔案大小
• 第 9 題（4%）｜page table 設計：四個敘述分別考 inverted page table entry 的內容、hash page table collision linked list 元素的內容、multi-level page table 內層 entry 的內容、層數與 TLB miss penalty 的關係
• 第 10 題（4%）｜CPU 效能：四個敘述考縮短 response time 的方法、不同 ISA 之間能否只比 CPI、CPU 時間的組成、MIPS 指標的公平性
• 第 11 題（4%）｜題目文字併入第 10 題，暫不另列考點
• 第 12 題（4%）｜MIPS 的四大設計原則：四個敘述各舉一個 MIPS 的設計特徵，判斷它對應的原則有沒有配對正確
• 第 13 題（4%）｜計算機算術：四個敘述考 sticky bit 的作用與位元數、restoring 與 non-restoring division 的比較、異號相加是否會 overflow、一段 MIPS 指令能否正確偵測無號數加法 overflow
• 第 14 題（4%）｜strcpy assembly 的 stack frame 與位址欄位：給 11 道指令與位址（96400 起）。(a)(b) 兩種「加上儲存或恢復 $s0 與 $ra」的寫法擇一 (c) ADR1 = beq 的 offset 欄位 (d) ADR2 = j 的 26-bit 位址欄位
• 第 15 題（4%）｜floating point 加法硬體的 control signal 追蹤：1.01111×2⁴ 加 1.10011×2⁶，尾數 5 bits、有 guard bit 與 round bit。要逐一填出 c0–c7 八個 control signal
• 第 16 題（4%）｜single-cycle、multicycle、pipeline 的硬體成本與速度：四個敘述考三種實作的硬體成本、速度、是否需要級間鎖存器、是否有 clock 遷就最慢級的問題
• 第 17 題（4%）｜三種 hazard 的定義：四個敘述考 control hazard 能否避免 stall、算術 overflow 與除以零屬於什麼、「記憶體 hazard」這個分類存不存在、structural hazard 的處理方式
• 第 18 題（4%）｜整數算術 overflow 的 exception handling：四個選項描述處理器遇到 overflow 時的行為。考 MIPS add 的 overflow 語意與 precise exception
• 第 19 題（4%）｜由 tag、index、offset 反推 cache 大小：四個敘述考 direct-mapped 與 set associative cache 能否由欄位大小決定容量、各欄位能不能是 0 bit、同容量下三種對映方式的 tag 大小比較
• 第 20 題（4%）｜cache 與 virtual memory 的共同原理：四個敘述考共同原理的名稱、cache block 在 virtual memory 中的對應物、miss 時 CPU 的行為是否相同、virtual memory 的寫入策略

題組（21–33，20 分）

• 題組 A（21–24，5%）｜RR 平均 turnaround time 的四進位拆解：四個 process 給到達時間與 CPU burst，time quantum = 4。算出平均 turnaround time U 後，把 4U 寫成 U₃×4³ + U₂×4² + U₁×4¹ + U₀，四個小題分別問 U₃、U₂、U₁、U₀。四小題全對才給 5 分
• 題組 B（25–27，5%）｜48-bit 邏輯、32-bit physical address、16 KB 頁
• 第 25 題｜最多幾個 frame
• 第 26 題｜單層 page table 有幾個 entry
• 第 27 題｜page table entry 至少幾個位元（不含控制位元）
• 題組 C（28–30，5%）｜array 索引版與 pointer 版的 MIPS assembly 對照：clear1 用索引、clear2 用 pointer，要填出三組空格（初值、遞增量、迴圈結束的比較對象）
• 題組 D（31–33，5%）｜n+1 道指令無限重複時三種 cache 的 hit rate：n 是 2 的冪，指令與 cache line 都是 32 bits，cache 只有 n 條 line
• 第 31 題｜direct-mapped 的 hit rate
• 第 32 題｜fully associative + LRU 的 hit rate
• 第 33 題｜fully associative + MRU 的 hit rate

作答時要注意的地方

1. 複選題答對一個選項 +1、答錯一個 −2，整題未作答不給分。
2. 題組 A 四小題全對才給 5 分，四個小題分別問平均 turnaround time U 的四進位各位數。
3. 題組 B 三小題分別用到 virtual address 寬度與 physical address 寬度。
4. 題組 D 三小題的條件是 cache 只有 n 條 line、反覆執行 n+1 道指令。

準備方向

• cache replacement algorithm 在循環存取下的行為（題組 D），106 年第 7 題、110 年第 2 題也考 replacement 或 cache。
• 一個數值拆成多位數、每小題問一位的題組設計（108 題組 A）。
• MIPS 的四大設計原則（第 12 題）。
• beq offset 與 j 位址欄位的編碼（第 14 題），106 年第 3 題也考。
• array 版與 pointer 版的 assembly 對照（題組 C）。
• ls -l 的欄位判讀（第 8 題）。