108 中央資工所硬體考點分析

題型與配分

所別「資工類」，科目：作業系統與計算機組織，全卷 100 分、5 頁、20 題。本科考試禁用計算器。

這是中央硬體十年裡唯一一份「多選不倒扣」的考卷，而且不倒扣的部分佔了 75 分。其他九年的多選一律是「每一選項單獨計分、答錯倒扣 1 分」。在 108 年的規則下，多選題不需要保守作答——這與 106、107、109–115 的策略完全相反。

單選 1–5 有四題是「算出 K 再 mod 5」（第 2、3、4、5 題），而且第 2、5 題還先乘上係數（Round(H)、Round(K×234)）。單選這 25 分才是真正會失血的地方，而且明訂扣到該大題 0 分為止。

OS 與計組的比重：計組 50%（第 2–11 題）、OS 45%（第 1、12–19 題）、計算機網路 5%（第 20 題）。

單選題（1–5，答錯倒扣 2 分）

• 第 1 題（5%）｜多重程式規劃度與 CPU 使用率：6 個程序、每個有 40% 時間在等 I/O，求 CPU 使用率。這是 Tanenbaum 的機率模型，要想清楚「CPU 閒置」對應的是什麼事件、那個事件的機率怎麼算——40% 這個數字代進去的位置最容易放錯
• 第 2 題（5%）｜含記憶體停頓的總週期數：指令 miss rate 2%、資料 miss rate 4%、20% 的指令會存取資料、miss penalty 50 cycles、CPI = 1、共 1111 道指令，求總週期 H 再取 Round(H) mod 5。資料失誤只發生在會存取資料的那 20% 指令上
• 第 3 題（5%）｜四個 IEEE754 數值的 XOR：A = 最大非正規化數、B = 最小正正規化數、C = −2.25、D = 正無窮大。四個 32 位元樣式逐位 XOR 後數出 1 的個數。先正確寫出四個位元樣式是前提，然後可以先兩兩配對再 XOR，比逐位四個一起算快
• 第 4 題（5%）｜2-way 組相聯快取的命中數：16 word 的快取、two-word blocks，對 16 筆字位址跑 LRU 數命中次數。先算出 set 數，再把字位址換成 block 號求 set
• 第 5 題（5%）｜含各種停頓的平均 CPI：load 24%（其中 1/4 後面緊接使用者 → 1 cycle 停頓）、branch 20%（一半預測錯 → 1 cycle）、jump 6%（一律 1 cycle），求 Round(CPI×234) mod 5。乘上 234 就是為了讓小數第二位的誤差也顯示出來，每一項的比例都要乘對

計算機組織考點（6–11）

• 第 6 題（5%）｜快取與控制的綜合判斷——涵蓋 超純量靠硬體還是編譯器達成 ILP、頁表與 TLB 誰是誰的 cache、微程式控制的主要優點、TLB 命中但快取失誤是否可能。頁表與 TLB 的角色常被對調
• 第 7 題（5%）｜單週期對多週期——涵蓋 兩者的時脈率高低、單週期的 CPI、吞吐量比較、多週期的週期由「最慢的指令」還是「最慢的單一級」決定。最後那一項有一個名詞被偷換
• 第 8 題（5%）｜RAW 與 WAW：add $s0,$t0,$t1 → sub $t2,$s0,$t3。逐一檢查兩道指令的目的暫存器與來源暫存器，判斷有哪幾種相依，以及 forwarding 能解決哪一種
• 第 9 題（5%）｜分支指令與預測——涵蓋 MIPS 的 jump 屬於條件分支還是無條件跳躍、branch target buffer 是硬體結構還是編譯器機制、管線長度與分支預測重要性的關係、預測失敗後的處理
• 第 10 題（5%）｜五級管線的性質——涵蓋 理想加速比的上限、為了解控制危障應該把分支判斷提前到哪一級、各級工作量該平衡還是不平衡、分支危障的來源。四個數字／級名全部要逐條核對，不能靠語感
• 第 11 題（5%）｜指令組合對資料路徑各單元的使用率：給 add 30%、addi 20%、beq 25%、lw 15%、sw 10% 的指令組合，問指令記憶體、資料記憶體、sign-extend、MemtoReg 各有多少比例的週期在用。要逐一問「哪幾類指令真的需要這個單元的輸出」，而不是「哪幾類指令的訊號經過它」。這題是把單週期資料路徑的每一條控制線都問一遍，是全卷最需要看懂電路圖的一題

作業系統考點（12–20）

• 第 12 題（5%）｜硬體沒有特權模式時如何保持掌控——這題在 106 年第 7 題、107 年第 10 題已經連續考過兩次，108 是第三次。中央十年裡重複最多次的一題
• 第 13 題（5%）｜用優先權變化率反推排程演算法：等待時優先權以速率 A 變化、執行時以速率 B 變化，數字越大優先權越高，進入佇列時都是 0。分別問 A < B < 0 與 A > B > 0 對應哪一種排程。要追蹤「新進來的程序」與「已經在跑的程序」的優先權隨時間怎麼變，看誰會超車誰。這是 Silberschatz 的經典習題
• 第 14 題（5%）｜many-to-many 模型下核心執行緒數的影響：使用者執行緒數 > 處理器數，問核心執行緒數在不同情況下的效能。要比較核心執行緒數與處理器數的大小關係
• 第 15 題（5%）｜銀行家演算法下哪些變更保證安全：增加 Available、減少 Available、增加某程序的 Max、減少某程序的 Max、減少程序數。要逐項想「這個變更會讓安全性檢查變容易還是變難」。這題把安全狀態的單調性問得很完整
• 第 16 題（5%）｜三個頁框下比較 LRU／FIFO／Optimal 的頁錯誤數：參考串 20 個頁號要跑三遍。選項把數字與演算法打散配對，等於一題內含三次完整模擬，是全卷最耗時的一題
• 第 17 題（5%）｜兩條執行緒共享什麼——選項列出全域變數、heap、file descriptor、PC。題幹的關鍵字是「不同程序」，要看清楚再作答。這題與 106 年第 8 題正好是一體兩面
• 第 18 題（5%）｜CPU 排程決策發生在哪些狀態轉換上。要分清「觸發排程的時機」與「排程的結果」，另外要檢查每個選項提到的程序狀態在課本裡存不存在
• 第 19 題（5%）｜頁面大小與 Round-Robin——涵蓋 頁面大小對頁表大小與 TLB 失誤率的影響、RR 最佳化的是回應時間還是吞吐量、RR 是否可搶占。前兩項是同一個變因的兩個後果，方向要一起推
• 第 20 題（5%）｜網路協定：ARP、DNS、IPSec、ICMP 四個協定各自的用途。這題與 107 年第 3 題的協定用途判斷互為對照

這份考卷的難點

1. 計分規則與其他年度相反，很多人會用錯策略。 多選 75 分不倒扣；如果照著 107 或 114 的習慣保守作答，等於白白放棄分數。
2. 第 16 題一題要跑三個置換演算法，20 個頁號、3 個頁框，等於手工模擬 60 步。在禁用計算器、還有 19 題要寫的情況下，時間壓力極大。
3. 第 11 題要真的看懂單週期資料路徑的電路。某個單元「有訊號經過」與「輸出真的被用到」是兩回事，背口訣沒用，必須理解每條控制線的意義。
4. 第 3 題的 IEEE754 位元操作要在腦中同時維持四個 32 位元樣式並逐位 XOR，錯一位最後的 mod 5 就完全不同。

準備建議

• 進場第一件事是讀計分規則。 中央硬體十年裡 108 是唯一的「多選不倒扣」，而 106、107 沒寫倒扣下限、109–115 都寫了「扣到該大題 0 分為止」。規則決定策略，看錯規則等於整份卷子的下注方式都錯了
• 「無特權模式如何做安全 OS」已經連三年出現（106 第 7、107 第 10、108 第 12）。這是中央硬體最穩的送分題，三份一起讀就知道它的選項怎麼變化
• Silberschatz 的三個經典習題在這一年全部出現：多重程式規劃度的 CPU 使用率（第 1 題）、優先權變化率反推排程（第 13 題）、銀行家演算法的安全變更（第 15 題）。課本習題要做過才答得出來
• 頁面置換的手工模擬（第 16 題）建議練到 20 個頁號、3 個頁框能在 3 分鐘內跑完三種演算法。中央在 109、112 也各考一次
• 單週期資料路徑的控制訊號表（第 11 題）要能默寫：RegDst／ALUSrc／MemtoReg／RegWrite／MemRead／MemWrite／Branch／ALUOp 在 R-type、lw、sw、beq 四種指令下各是什麼值