110 中興資工所考古題詳解｜硬體考點分析

題型與配分

全卷 10 頁，不得使用計算機。硬體在資訊概論的 PART I（作業系統與計算機組織），PART II 是資料結構與演算法。

卷面沒有標示倒扣。題組 1、2 以作業系統為主，題組 3 是 virtual memory 與 TLB，題組 4、5 以計算機組織為主，題組 5 的 B、C、D 混有 OS 觀念。

題組 1：排程與 page table（10%）

• 1-A｜哪個 scheduling 演算法是 non-preemptive：Round Robin、First-In First-Out、Multilevel Queue、Multilevel Queue with Feedback
• 1-B｜判斷三句敘述：SRTF 可能造成 starvation、preemptive scheduling 可能造成 starvation、Round Robin 在 response time 上優於 FCFS
• 1-C｜為什麼 multilevel page table 比 single level page table 更受青睞
• 1-D｜P0（到達 0 ms、burst 9 ms）、P1（到達 1 ms、burst 4 ms）、P2（到達 2 ms、burst 9 ms），採 preemptive SJF，scheduling 只在 process 到達或完成時進行，求平均 waiting time

題組 2：process、死結與虛擬記憶體（10%）

• 2-A｜for (i = 0; i < n; i++) fork(); 總共建立幾個 child process
• 2-B｜關於 deadlock prevention 與 deadlock avoidance，哪個敘述不成立
• 2-C｜FIFO page replacement 下增加 page frame 數量，page fault 次數的變化
• 2-D｜關於 virtual memory，哪個敘述是錯的，選項包含 address space 轉換、程式大小可超過 main memory、multiprogramming 程度、context switching 開銷

題組 3：page table、TLB 與記憶體（10%）

• 3-A｜64 MB physical memory、32 位元 virtual address space、頁面 4 KB，page table 的大約大小
• 3-B｜CPU 產生 32 位元 virtual address，頁面 4 KB，TLB 可容納 128 個 page table entry 且為 4-way set associative，TLB tag 的最小大小
• 3-C｜為什麼增加電腦的 RAM 通常能改善效能
• 3-D｜在指令執行 pipeline 中，data TLB 最早可以在什麼時候被存取

題組 4：pipeline 與快取階層（10%）

• 4-A｜pipeline 處理器中哪些敘述不成立：bypassing 能處理所有 RAW hazard、register renaming 能消除所有 WAR hazard、動態 branch prediction 能消除 control hazard 的罰則
• 4-B｜register renaming 在 pipeline 處理器中的用途
• 4-C｜微運算序列 MBR ← PC、MAR ← X、PC ← Y、Memory ← MBR 可能是哪種操作：instruction fetch、operand fetch、conditional branch、initiation of interrupt service
• 4-D｜兩層 cache L1 與 L2 之間哪些條件是必要的：L1 必須 write-through、L2 必須 write-through、L2 的 associativity 必須大於 L1、L2 至少要和 L1 一樣大

題組 5：pipeline 週期數與綜合判斷（10%）

• 5-A｜四級 pipeline IF、ID、EX、WB，IF、ID、WB 各 1 個 clock cycle，ADD 與 SUB 的 EX 為 1 週期、MUL 的 EX 為 3 週期，有 operand forwarding，執行 ADD R2, R1, R0、MUL R4, R3, R2、SUB R6, R5, R4 需要幾個週期
• 5-B｜哪個關於 interrupt 的敘述為真：處理器於執行新指令前檢查 interrupt、loop 指令不可被 interrupt、CPU 要啟用才能處理 interrupt、微處理器只有 level triggered interrupt
• 5-C｜哪個敘述為真：virtual memory 採 write through、NAND Flash 的用途與隨機存取、structural hazard 的定義、同一次資料參考是否可能 TLB hit 而 data cache miss
• 5-D｜哪個敘述為真：programmed I/O 與 DMA 使用的 CPU 資源、mutual exclusion 與 deadlock、context switch 是否在每次 system call 發生、software interrupt 是否與目前 process synchronous

作答時要注意的地方

1. 卷首註明請依序作答，卷面沒有標示倒扣。
2. 1-D 明訂 scheduling 只在 process 到達或完成時進行。
3. 2-A 問的是 child process 的總數。
4. 4-A 三句敘述都用了「所有」或「消除」的字眼，要找出不成立的。
5. 4-D 問的是「必要」的條件。
6. 5-A 的 MUL 在 EX 階段佔 3 個週期。

準備方向

• scheduling：110 第 1-A、1-B、1-D 題，111 第 6-III 題、113 第 1、3 題、114 第 15、16 題、115 第 14 題也有。
• multi-level page table 與 page table 大小：110 第 1-C、3-A 題，111 第 6-I 題、115 第 10 題也有。
• fork 的 process 計數：110 第 2-A 題，112 第 13、21–23 題、113 第 4 題、115 第 13 題也有。
• deadlock prevention 與 avoidance：110 第 2-B 題，113 第 9、10 題、114 第 7、8 題也有。
• Belady 異常：110 第 2-C 題，113 第 5 題、114 第 12 題也有。
• TLB 的 tag 與 effective access time：110 第 3-B、3-D 題，112 第 5 題、115 第 16、17 題也有。
• 增加 RAM 為何改善效能：110 第 3-C 題與 111 第 6-II 題是同一題。
• pipeline 的 hazard 與 register renaming：110 第 4-A、4-B 題，111 第 4-IV 題、112 第 18 題、113 問答第 2 題、115 第 1–4 題也有。
• pipeline 週期數：110 第 5-A 題，111 第 8-II、9-I 題也有。
• interrupt：110 第 5-B 題與 111 第 4-III 題是同一題，選項順序不同。
• 兩層 cache：110 第 4-D 題，111 第 8-I 題、115 第 5 題也有。