110 中興資工所硬體考點分析

題型與配分

科目名稱：資訊概論，系所「資訊科學與工程學系－甲組」，本科目不得使用計算機，全卷 10 頁。

110 年的 PART I 卷面沒有任何倒扣標示，與 108 年的「答錯 −3」形成強烈對比。中興的計分規則逐年不同，進場一定要先看卷首。

PART I 明訂「請依序作答」。

OS 與計組的比重：第 1、2 題純 OS（20 分）、第 3 題虛擬記憶體與 TLB（10 分）、第 4、5 題純計組（20 分）。

第 1 題：排程（10%，4 個單選）

• A｜哪個排程演算法是非搶占的——要能把常見的排程演算法逐一歸到搶占／非搶占兩類
• B｜哪些敘述為真：三句分別問 SRTF 會不會造成飢餓、可搶占排程會不會造成飢餓、RR 與 FCFS 在回應時間上的比較。判準：長工作在「短者優先」的規則下會不會永遠排不到；以及每種演算法各自最佳化的是哪一個指標。三句要逐一判斷再挑組合
• C｜為什麼多層頁表優於單層頁表——要想清楚多層頁表在什麼情況下能省記憶體
• D｜可搶占 SJF 的平均等待時間：P0(到達 0、burst 9)、P1(到達 1、burst 4)、P2(到達 2、burst 9)。題目明說「排程只在程序到達或完成時進行」，要依此畫甘特圖。每次有新程序到達時，要拿它的 burst 跟目前程序的「剩餘」時間比，而不是跟原始 burst 比

第 2 題：程序、死結與分頁（10%，4 個單選）

• A｜for (i=0; i<n; i++) fork(); 總共建立幾個子程序——每一輪所有現存程序都會分裂一次。注意題目問的是「子程序」還是「程序總數」，兩者差一
• B｜關於死結預防與死結避免哪個「不是」真的——要分清預防與避免各自的做法，選項就是拿這兩者互換
• C｜FIFO 置換下增加頁框數會怎樣——要能說出這個現象的名稱與它只發生在哪一類演算法上
• D｜關於虛擬記憶體哪個是錯的——要特別看它對上下文切換的影響是怎麼描述的：換程序時頁表與 TLB 要做什麼事

第 3 題：頁表、TLB 與記憶體（10%，4 個單選）

• A｜64 MB 實體記憶體、32-bit 虛擬位址、頁面 4 KB 時的頁表大約多大。頁表大小 = 條目數 × 每條目大小；條目數由虛擬位址與頁面大小決定，每條目大小則要由實體頁框號的位元數推出來
• B｜32-bit 虛擬位址、頁面 4 KB、TLB 有 128 個條目且 4-way 時，TLB tag 的最小大小。TLB 也是一種快取，tag 的算法跟組相聯快取一樣：先算 set 數與 index，再從 VPN 扣掉
• C｜為什麼增加 RAM 通常能改善效能——與 111 年第 6(II) 題一字不差
• D｜在指令執行管線中，資料 TLB 最早能在何時被存取——因果關係很直接：得先有虛擬位址才能查 TLB，而位址是在哪一級算出來的？

第 4 題：管線與快取階層（10%，4 個單選）

• A｜哪些敘述在管線處理器中「不成立」：三句分別問 bypassing 能不能處理「所有」RAW 危障、暫存器重新命名能不能消除「所有」WAR 危障、動態分支預測能不能「消除」控制危障的罰則。三句都用了「所有／消除」這種絕對字眼，要逐一檢查有沒有例外，也要注意「減少」與「消除」的差別
• B｜管線處理器中暫存器重新命名的用途——要能說出它解決哪幾種相依、又救不了哪一種
• C｜給一串微操作 MBR ← PC、MAR ← X、PC ← Y、Memory ← MBR，判斷這是什麼操作——逐條翻譯成白話再看整體意圖：PC 被存起來、PC 被換掉，這代表什麼事件正在發生？
• D｜兩層快取 L1 與 L2 中，哪些是必要的：四個候選條件是 L1 必須 write-through、L2 必須 write-through、L2 的關聯度必須大於 L1、L2 至少要和 L1 一樣大。關鍵字是「必要」：要想清楚少了這個條件，兩層快取還能不能正常運作

第 5 題：管線週期數與綜合判斷（10%，4 個單選）

• A｜四級管線（IF/ID/EX/WB），IF、ID、WB 各 1 週期，ADD 與 SUB 的 EX 要 1 週期、MUL 要 3 週期，有運算元轉送。程式：

ADD R2, R1, R0
MUL R4, R3, R2
SUB R6, R5, R4

要逐拍畫出時序圖：多週期的 EX 會佔住該級好幾拍（結構危障），後面的指令還有資料相依要等

• B｜關於中斷哪個敘述為真——與 111 年第 4(III) 題一字不差
• C｜哪個敘述為真——核心觀念：TLB 管位址轉換、快取管資料，兩者是獨立的兩次查詢
• D｜哪個敘述為真——判準是「這個事件由什麼觸發」：同步事件與非同步事件的區分

這份考卷的難點

1. 第 4(C) 題的微操作序列要看出是什麼操作。 要把四步翻譯成白話再看整體，特別注意 PC 被存進記憶體這件事代表什麼。
2. 第 1(D) 題的可搶占 SJF 要正確處理「搶占時機」。 題目明說「排程只在程序到達或完成時進行」，不是每個時間單位都重新比較，而比較的是剩餘時間。
3. 第 5(A) 題的四級管線含多週期 EX。 MUL 會佔用 EX 級好幾拍，加上 SUB 對 MUL 結果的資料相依。要逐拍畫圖。
4. 第 4(A) 題的「Bypassing 能處理所有 RAW」是最經典的陷阱。

準備建議

• 中興的計分規則逐年不同：108 年答錯 −3、110 年無倒扣標示、112 年答錯 −1、113 年不倒扣。進場一定要先看卷首
• 可搶占 SJF 的甘特圖（第 1D 題）要注意「排程只在到達或完成時進行」這個條件
• fork 迴圈的程序數（第 2A 題）：子程序數與程序總數差一。中興、中央、交大都考
• TLB tag 的計算（第 3B 題）：跟組相聯快取的 tag 算法相同
• 中斷的微操作序列（第 4C 題）：要能看懂暫存器傳輸語言
• 三個跨校高頻陷阱在這一年都出現：forwarding 的極限（4A）、Belady's anomaly（2C）、TLB 與快取的命中失誤組合（5C）
• 中興 110 年 PART I 全部是單選、沒有倒扣 ⇒ 每一題都要作答