112 師大資工所硬體考點分析
第 2 題一次要畫四張甘特圖（SJF／FCFS／RR／三層 MLFQ），20 分是全卷最花時間的一題。
題型與配分
科目「計算機系統」，適用系所：資訊工程學系，全卷 2 頁、8 大題、100 分。
| 題號 | 配分 | 歸屬 | 主題 |
|---|---|---|---|
| 1 | 20% | OS | 程序狀態圖、Readers-Writers、busy waiting |
| 2 | 20% | OS | 四種排程的甘特圖與平均等待時間 |
| 3 | 10% | OS | LRU 頁面置換與失誤率 |
| 4 | 10% | 計組 | 時脈週期數與時脈率反推 |
| 5 | 10% | 計組 | 進位轉換 |
| 6 | 10% | 計組 | IEEE-754 單精度 |
| 7 | 10% | 計組 | 無 forwarding 時插入 NOP |
| 8 | 10% | 計組 | 直接對映快取的命中率 |
OS 50 分、計算機組織 50 分，與 111 年一樣精準對半。
沒有倒扣，全卷都是申論與計算題。第 1、2 兩大題合計 40 分都要「畫圖」（程序狀態圖、四張甘特圖）——時間分配上這兩題至少要留一半的時間。
逐題考點
- 第 1 題（20%）｜程序概念
- (a) 10%：畫出程序狀態圖並說明每一條轉換——每一條轉換都要寫一句觸發原因。最常見的錯誤是多畫了課本上不存在的轉換，每條線都要能說出理由
- (b) 5%：用狀態圖說明 Readers-Writers 問題中各程序的狀態移動——要講清楚 reader 與 writer 在存取規則上的差異如何反映在狀態上
- (c) 5%：若改成「不使用忙碌等待」會有什麼改變——要比較兩種等待方式下程序停在哪個狀態，並提到兩者的取捨
- 第 2 題（20%）｜四種排程的甘特圖與平均等待時間——全卷最花時間的一題，佔五分之一的分數
- (a) SJF、(b) FCFS、(c) RR（q = 10ms）、(d) 三層 MLFQ（L1 3ms、L2 5ms、L3 FCFS）
- (a)(b) 兩張圖最好畫，建議先做，穩穩拿 10 分再回頭啃後兩張
- (b) 的資料設計成某個經典現象的教科書範例，跟 (a) 的結果一比就看得出 SJF 的價值
- (d) 的 MLFQ 規則各課本不同（有沒有 priority boost？同層內怎麼排？）⇒ 一定要在答案卷上先把你採用的規則寫出來再畫圖，等於先幫自己定義好評分標準
- 第 3 題（10%）｜LRU 頁面置換（23 個參考、3 個頁框）
- (a) 要「逐步列出每一步的頁框內容」，不能只寫最後的失誤數
- (b) 題目明寫「including the initial/compulsory page faults」 ⇒ 冷啟動的那幾次要算進去，不能扣掉
- 參考串中段有一段交錯重複的頁號，是整串裡最容易數錯的一段
- 第 4 題（10%）｜時脈週期數與時脈率反推
- (a) 由執行時間與時脈率求總週期數、(b) 由「新機需要幾倍週期數」與目標時間求新時脈
- 陷阱：不能直接用時間比去縮放時脈——題目說新機需要 1.8 倍的週期數，這個因子一定要乘進去
- 第 5 題（10%）｜進位轉換
- (a) 無號二進位轉十進位、(b) 無號十六進位轉十進位
- 這題的試卷把「8 位元」印成了 7 個位元——補上前導零與直接讀的結果相同，不影響作答，但考場上看到這種不一致容易慌
- 第 6 題（10%）｜十進位轉 IEEE-754 單精度的十六進位表示
- 四個步驟：轉二進位 → 正規化 → 指數加 bias → 尾數去掉隱含的 1 後補滿
- 單精度與雙精度的欄位寬度與 bias 要能直接寫出來
- 第 7 題（10%）｜無 forwarding 時要插入多少 NOP（五道
or指令） - 先把所有 RAW 相依與它們的距離列出來，再依距離決定各要插幾個
- WAW／WAR 在單一發射的循序管線裡會不會造成危障，想清楚再決定要不要插
- 答案取決於「暫存器檔分不分半週期（前半寫、後半讀）」——兩種假設的 NOP 數不同，務必在答案卷上註明你用哪一種
- 第 8 題（10%）｜直接對映快取的命中率（32 位元位址，給 Tag／Index／Offset 的位元範圍與 12 筆存取）
- (a) 由 Index 的位元數得出條目數；順帶由 Offset 得出區塊大小與總容量
- (b) 要把每一筆位址的 Index 與 Tag 兩欄並排寫出來，衝突一眼就看得到
- 只算前幾筆會覺得這題很簡單，要全部算完才看得出題目的設計
這份考卷的難點
- 第 2 題一次要畫四張甘特圖，其中 MLFQ 那張最長。 20 分、佔全卷五分之一，而且四小題的數字互相獨立，錯一個不會連累其他——但時間一定不夠優雅地做完。建議先做 (a)(b) 兩張簡單的拿 10 分，再回頭啃 (c)(d)。
- 第 2(d) 題的 MLFQ 規則各課本不同。 一定要在答案卷上把假設寫出來，否則閱卷者用不同規則算會判你錯。
- 第 3 題的參考串有 23 個，中間還有一段交錯重複的頁號。 數錯一次，整個 (b) 小題的分母分子都會錯。
- 第 8 題要把 12 筆位址全部拆完。 前半看起來很簡單，後半才是真正的設計。
- 第 5(a) 題的試卷印錯位元數。 補前導零與直接讀的結果相同，不影響答案，但考場上看到這種不一致容易慌。
- 第 7 題的 NOP 數量取決於「暫存器檔分不分半週期」。 兩種假設會得到不同的數量，關鍵是把假設寫清楚。
準備建議
- 四種排程演算法要能在同一組資料上全部跑完（第 2 題）：FCFS、SJF、RR、MLFQ。師大 112、114、115 三年都考排程，其中 112 年一次就要四張圖
- MLFQ 的核心規則要記熟，答題時把規則先寫出來再畫圖，等於先幫自己定義好評分標準
- 護航效應（convoy effect） 值得記成一句話——112 年第 2 題的 (a)(b) 兩小題一比就是活例子
- 頁面置換要算到 20 個以上的參考串不出錯（第 3 題）。師大 110 年考 FIFO+LRU、112 年考 LRU，都要求「逐步列出頁框內容」——不能只寫最後的失誤數
- CPU 時間方程式的各種變形（第 4 題）要熟，這一題的陷阱是「新機需要幾倍的週期數」這個額外因子
- IEEE-754 單精度的格式與偏移量 要背到能反射（第 6 題）。師大 112 年考「十進位 → 十六進位」、114 年考「位元樣式 → 十進位」，兩個方向都要會
- 直接對映快取的 index 衝突（第 8 題）：練習時把 index 與 tag 兩欄並排寫出來，衝突一眼就看得到
- 無 forwarding 時的 NOP 數量（第 7 題）：先列出所有 RAW 相依與距離，再依距離決定；採不採「暫存器檔前半寫後半讀」會得到不同的數量，作答時要註明