112 交大資工所硬體考點分析

題型與配分

科目：計算機系統（1103），系所班別「資訊聯招」，考試日期 112 年 2 月 6 日第 3 節，全卷 100 分、9 頁、34 題。不可使用計算機、請用答案卡作答。

這一年的題組明文寫出「各題組下的小題為單選」——以往沒有特別註明。單選比複選好答，但仍是全對才給分，所以難度沒有下降。

計分沿用 110 年起的「答錯 −1、扣至整科 0 分」。

OS 與計組的比重：OS 50%（第 1–10 題與題組 A、B）、計組 50%（第 11–20 題與題組 C、D）。

複選題（1–20，80 分）

作業系統（1–10）

• 第 1 題（4%）｜頁面置換——四個選項涵蓋 Belady's anomaly 在 FIFO 與 LRU 上的可能性、哪一種演算法的頁錯誤數最少、加大 TLB 對置換次數有沒有影響。最後一項要想清楚 TLB 管的是什麼
• 第 2 題（4%）｜64 MB 共享記憶體——四個選項涵蓋 兩個程序必不必須用相同的虛擬位址範圍、一方設成唯讀會不會限制另一方、共享記憶體能不能被換出、實際配置的實體記憶體會不會少於宣告的大小。前兩項的共同判準：虛擬位址與權限記錄在哪裡
• 第 3 題（4%）｜DMA——四個選項涵蓋 DMA 讓「誰」直接存取主記憶體、它會不會拖慢 CPU 密集程式、同步 DMA 完成的兩種方式
• 第 4 題（4%）｜把檔案從 /x/f 搬到 /y/f 哪些步驟不能省。選項有在 y 建立項目、刪除 x 中的項目、重新配置資料區塊、複製內容等。要想清楚同一個檔案系統內「搬移」實際上改的是什麼
• 第 5 題（4%）｜要讓檔案系統產生非連續資料區塊，哪些操作是必要的。要想什麼操作會在磁碟上製造空洞、什麼操作會去填它
• 第 6 題（4%）｜程序——四個選項涵蓋 建立子程序後父程序的兩種選擇、產生太多子程序會耗盡什麼資源、同程序的執行緒能不能在不同核心同時跑、深度遞迴消耗的是 heap 還是 stack
• 第 7 題（4%）｜看甘特圖反推排程演算法：五個程序在 18 ms 內完成。做法是從圖上的切換點反推「這個排程器在那一刻為什麼會做這個決定」，再逐一檢驗 RR、非搶占 SJF、可搶占 SJF 三者能不能產生這張圖。最後一小題再由此推出某個程序的等待時間
• 第 8 題（4%）｜兩條執行緒各累加 10000 次而沒有鎖——四個選項涵蓋 輸出是不是「總是」等於兩者之和、有沒有可能只差一、調換 pthread_join 的順序有沒有用。主軸是競爭條件：累加是不是原子操作、join 能提供什麼保證
• 第 9 題（4%）｜條件變數——四個選項涵蓋 pthread_cond_wait() 是忙碌等待還是睡眠等待、它的參數裡為什麼要帶一個 mutex、pthread_cond_signal() 喚醒幾條執行緒、呼叫 signal 之後呼叫者會不會立刻讓出 CPU
• 第 10 題（4%）｜用不等式判斷死結與安全狀態：m 個資源、4 條執行緒，x_i 是最大需求、y_i 是目前持有。要判斷四個不等式各自能否推出死結或安全。關鍵是分清「總需求超過剩餘資源」與「每一條執行緒的需求都超過剩餘資源」這兩種條件的差別

計算機結構（11–20）

• 第 11 題（4%）｜單週期對五級管線——四個選項涵蓋 兩者的執行時間比較、管線的關鍵路徑是不是「總是」比較短、硬體資源的多寡、兩者的 CPI 高低。CPI 那一項最容易反過來記
• 第 12 題（4%）｜哪些去除危障的技術需要編譯器協助——選項涵蓋 延遲分支、load-use 危障的消除、動態分支預測、forwarding。判準只有一條：這件事是在編譯期決定的，還是執行期由硬體自己做的
• 第 13 題（4%）｜ll／sc 這對指令——四個選項涵蓋 ll 到底有沒有「鎖住」記憶體格、什麼情況會讓 sc 失敗、給的程式片段有沒有 bug（要逐字核對每道指令用到的暫存器）、它與原子交換指令的效率比較
• 第 14 題（4%）｜看簡化的 MIPS 資料路徑圖——四個選項涵蓋 一段程式碼能不能測出某條控制訊號 stuck-at-0 的故障、這個實作會不會有 load-use 危障、指令記憶體與暫存器檔各自需不需要是同步元件。後兩項的判準是「這個元件要不要寫入」
• 第 15 題（4%）｜無 forwarding、無分支預測、分支在 ID 級解析的五級管線：程式是一個迴圈（addi → lw → subi → sw → bne）。要先標出每一組相依的距離，再判斷 哪些 bubble 加上 forwarding 就能消除、哪些不行、$t3 = 100 時 CPI 是否大於 2.5、除了 PC 的加法器外至少還要幾個加法器、加上靜態分支預測器會讓 CPI 變好還是變差。其中有一組是 load-use，要特別看
• 第 16 題（4%）｜快取——四個選項涵蓋 虛擬定址與實體定址快取的速度比較、高關聯度減少的是哪一種失誤、處理器變快之後快取效能是更重要還是更不重要、加大區塊利用的是哪一種區域性
• 第 17 題（4%）｜指令組合的執行時間與加速上限：2 GHz，四類指令各給指令數與 CPI。第一步先算出各類貢獻的週期與總週期，再換算成執行時間。後續小題問 只改善其中一類指令能不能快兩倍（要用 Amdahl 的上限觀念）、綜合改善後的執行時間
• 第 18 題（4%）｜記憶體停頓對 CPI 的影響：給失誤罰則、I-cache 與 D-cache 的失誤率、lw/sw 比例與無停頓 CPI。三個要點：(1) I-cache 與 D-cache 的停頓各要乘上什麼比例；(2)「時脈加倍但記憶體時間不變」時，失誤罰則的「週期數」要重算；(3) 算加速比時分母分子別顛倒——時脈變了，兩邊的週期時間也不同。最後一小題再問只給 I-cache 加 L2 之後的 CPI
• 第 19 題（4%）｜循序走訪 int A[256] 的失誤數與命中率（直接對映、總資料 8192 bytes、區塊 16 bytes）。先算出「一個區塊裝得下幾個 int」，再判斷這些失誤屬於哪一種（陣列大小與快取容量的關係是判準）。最後一小題問 區塊大小加倍後失誤數與失誤率各往哪個方向走
• 第 20 題（4%）｜兩個處理器對 a、b 的讀改寫：P1 做 a++; b++;、P2 做 a=2; b=b+2;，初值皆 0。要分別判斷「有／沒有快取一致性」下 a、b 的可能值。a 與 b 的操作性質不同（一邊是直接賦值、一邊兩方都是讀改寫），要分開窮舉

題組（21–34，20 分）

• 題組 A（21–23，5%）｜四顆 1 TB 磁碟組成 RAID 5：
• 第 21 題｜最大容量
• 第 22 題｜最多容忍幾顆磁碟故障
• 第 23 題｜最壞情況下寫入單一位元組會牽涉幾顆磁碟——要想到 RAID 5 small write 的「讀改寫」流程
• 題組 B（24–27，5%）｜三個程序 P、Q、R 的訊息傳遞：P 送給 Q、Q 送給 R、R 送給 P，而接收端分別是 R、P、Q——形成一個環。
• 第 24 題｜這是哪一種命名方式
• 第 25 題｜支援這種通訊需要什麼資料結構
• 第 26 題｜哪種條件會造成死結
• 第 27 題｜哪個條件能確保每個程序都在收到訊息後才繼續
• 要能把 send／receive 各自的阻塞與非阻塞版本對應到不同的同步語意，再配合「環」這個結構判斷死結
• 題組 C（28–30，5%）｜從 MIPS 組語反推 C 函式：組語中 move $s1,$a2、move $s0,$a3、兩次 jal func、中間 move $a0,$v0 與 add $a1,$s0,$s1。
• 第 28 題｜由組語推斷 my_call() 有幾個參數——看它用到了哪幾個引數暫存器
• 第 29 題｜函式體是哪一段 C——先把每個 saved register 對應回原本的引數，再看兩次呼叫時 $a0／$a1 各被填進什麼
• 第 30 題｜尾呼叫最佳化能省幾道指令——要找出最後一次 jal 之後做了哪些事，哪些在尾呼叫最佳化下可以省掉
• 題組 D（31–34，5%）｜2-way、四字區塊、LRU 的快取：總資料 32 words、24-bit 位元組位址。
• 第 31 題｜tag 位元數。由區塊大小得 offset、由「區塊數 ÷ 關聯度」得 set 數與 index、位址位元數減掉兩者就是 tag
• 第 32 題｜快取總大小（資料加上每個區塊的 tag 與 valid）
• 第 33 題｜字位址序列 24, 8, 25, 10, 41 的命中與失誤。字位址要先換算成區塊號再取 set，算完之後看看這些位址的分佈有什麼特別之處
• 第 34 題｜其中幾次是強制失誤

這份考卷的難點

1. 題組 D 的位址序列是刻意設計的。 沒有把每個位址的 set 都算出來就直接追蹤，很容易低估失誤數。
2. 第 18 題的加速比方向容易搞反。 時脈加倍後 CPI 會上升，但每個週期的時間也變短了，選項會把分子分母顛倒來設陷阱。
3. 第 13 題的 bug 藏在暫存器名稱裡，只差一個字母，不逐字核對看不出來。
4. 題組 C 要反推兩層巢狀呼叫的參數對應。 四個選項只差運算元的組合方式，對應錯一個就整組錯。

準備建議

• RAID 5 的基本數字（題組 A）：容量、容錯能力、small write 的代價要能直接說出來
• 訊息傳遞的四種組合與環狀通訊的死結（題組 B）
• 從組語反推 C（題組 C）是交大近年新增的題型。要熟悉 MIPS 的呼叫慣例：$a0–$a3 傳參、$v0 回傳、$s0–$s7 是被呼叫者保存、$ra 返回位址
• 快取位址拆解後要檢查「是不是全落在同一組」（題組 D）。交大很愛設計這種「表面上位址分散、實際上全部撞同一組」的序列
• 記憶體停頓的 CPI 計算（第 18 題）要記住：時脈改變時，以週期數計的失誤罰則也會跟著變
• Amdahl 的加速上限判斷（第 17 題）
• 答錯 −1、扣至整科 0 分：把握超過 50% 就值得勾，但仍要記得單題可扣成負分