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

題型與配分

全卷 2 頁、8 大題、100 分，答案寫在答案卷上，卷面沒寫倒扣，沒有選擇題。卷面注意事項是「請依序在答案卷上作答，並標明題號，不必抄題」與「答案必須寫在指定作答區內，否則依規定扣分」。

作業系統考點

• 第 1 題（20%）｜作業系統中的 process 概念：
• 第 1(a) 題（10%）｜畫出 process state diagram，說明一個新的工作／process 從第一次提交到結束，如何在各狀態之間轉換
• 第 1(b) 題（5%）｜用 process state diagram 說明 Readers-Writers 問題中，readers 與 writers 如何在狀態之間移動
• 第 1(c) 題（5%）｜如果問題改成不使用 busy waiting，會有什麼改變
• 第 2 題（20%，4 小題各 5%）｜給 P1 到 P5 的 Burst（10、29、3、7、12 ms）與 Arrival Time（0、1、2、3、4），畫出 Gantt chart 並計算平均 waiting time：(a) SJF (b) FCFS (c) RR，time quantum 10 ms (d) 三層 Multi-level Feedback Queue：Level 1 的 time-slice 為 3 ms，Level 2 為 5 ms 且只在 Level 1 為空時派送，Level 3 為 FCFS 且只在 Level 1 與 2 都為空時派送
• 第 3 題（10%）｜頁面參考序列 1 2 7 3 7 0 8 4 0 4 0 4 3 4 3 6 5 0 2 6 1 2 0（23 個參考），LRU，3 個 frame，一開始 frame 是空的：(a) 5% 逐步列出每個參考之後 frame 裡的頁面 (b) 5% 計算 cache miss ratio（page fault ratio），包含最初的 page fault

計算機組織考點

• 第 4 題（10%，2 小題各 5%）｜程式在 1.5 GHz 的電腦 A 上跑 20 秒，要設計電腦 B 使同一個程式跑 9 秒；clock rate 可以大幅提高，但會使 B 需要 A 的 1.8 倍 clock cycle 數：(a) A 的 CPU clock cycle 數 (b) B 的 CPU clock rate
• 第 5 題（10%，2 小題各 5%）｜轉成十進位：(a) 無號 8 位元二進位數 0001111（卷面只印出 7 個數字） (b) 無號 16 位元十六進位數 04E2
• 第 6 題（10%）｜十進位數 63.25 的 IEEE-754 single precision 十六進位表示
• 第 7 題（10%）｜五級（IF、ID、EXE、MEM、WB）pipeline RISC 處理器，沒有 forwarding，給五道 or 指令：or $r1,$r2,$r3、or $r2,$r1,$r4、or $r1,$r1,$r2、or $r3,$r3,$r4、or $r4,$r5,$r6，問如何加入 NOP 指令消除 hazard
• 第 8 題（10%，2 小題各 5%）｜32 位元位址的 direct-mapped cache，位址欄位為 Tag（位元 31–10）、Index（位元 9–5）、Offset（位元 4–0）。從開機起依序記錄到的位元組位址存取為 0、4、16、132、232、160、1024、30、140、3100、180、2180：(a) cache 有幾個項目 (b) hit rate

作答時要注意的地方

1. 卷面沒寫倒扣，第 1、2 兩大題合計 40 分，題目要求畫圖（process state diagram、四張 Gantt chart）。
2. 第 2(d) 題給了 MLFQ 的層數、time-slice 與派送條件，沒有寫其他規則。
3. 第 3(b) 題要求把最初的 page fault 也算進去。
4. 第 4 題 B 需要 A 的 1.8 倍 clock cycle 數。
5. 第 7 題題目只寫「沒有 forwarding」，沒有說明 register file 是否在同一週期內前半寫、後半讀。
6. 第 8 題的位址存取序列共 12 筆。

準備方向

• process state diagram 與 scheduler：112 第 1(a)(b) 題；106 第七題、107 第 10 題、113 第 1 題、114 第 2 題也有。
• synchronization（busy waiting、critical section、semaphore、鎖）：112 第 1(c) 題；108 第 9 題、113 第 2 題、114 第 7 題也有。
• CPU scheduling：112 第 2 題；106 第九題、107 第 8 題、108 第 8 題、109 第 6 題、110 第 2 題、114 第 5 題、115 第 3 題也有。
• page replacement：112 第 3 題；107 第 7 題、108 第 6 題、109 第 7 題、110 第 5 題也有。
• 效能公式（CPI、clock rate、每秒指令數）：112 第 4 題；106 第二(一)(二)題、107 第 2 題、108 第 2 題、109 第 2(a)(b) 題、110 第 8(2) 題、113 第 7 題、115 第 5 題也有。
• 數字表示（進位、IEEE-754、two's complement）：112 第 5、6 題；106 第一題、107 第 1 題、108 第 1 題、109 第 1 題、110 第 8(1) 題、111 第 5 題、114 第 11 題也有。
• pipeline hazard 與 forwarding：112 第 7 題；106 第四題、107 第 3、5(b) 題、108 第 4 題、109 第 3 題、110 第 7、8(3)(4) 題、111 第 10 題、113 第 6 題、114 第 9 題也有。
• cache：112 第 8 題；106 第三、五題、107 第 4、5(a) 題、108 第 3(c)(d) 題、109 第 4 題、110 第 6、8(5) 題、111 第 11 題、113 第 5 題、114 第 8 題、115 第 9 題也有。