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

題型與配分

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

不對稱倒扣連續第三年（106、107、108 都是答對 +1、答錯 −2，扣至該題 0 分）。110 年起才改成答錯 −1，但扣至整科 0 分。

題組 A 有四個小題（21–24）：A（21–24）、B（25–27）、C（28–30）、D（31–33）。題組 A 把一個平均周轉時間拆成四位四進位數字，四個小題全對才給 5 分。

OS 與計組的比重：OS 約 45%（第 1–9 題與題組 A、B）、計組約 55%（第 10–20 題與題組 C、D）。

複選題（1–20，80 分）

• 第 1 題（4%）｜程序與執行緒：四個敘述考同程序的執行緒共享哪些東西、核心執行緒的 PC、多對一模型能否利用多核、多對一模型下是否仍有競爭條件。「所有資料都共享」這種全稱敘述要特別小心
• 第 2 題（4%）｜現代 OS：四個敘述考程序輸出字元是否需要系統呼叫、程序離開 running 狀態的所有可能原因、微核心對通訊開銷的影響、共享記憶體 IPC。第二項用了「只有」兩個字
• 第 3 題（4%）｜改造過的讀者—寫者問題：把標準解法的 if (readcount == 1) wait(wrt) 改成 if (readcount <= Na) wait(wrt)、if (readcount <= Nb) signal(wrt)。要推論 Na=1、Nb=0 時是否退化成標準解、Na=2、Nb=1 時最多有幾個讀者在等 wrt。這是把課本解法參數化再問行為，需要真的模擬
• 第 4 題（4%）｜安全狀態下哪些變更仍保證安全：增加可用資源、釋放已配置但不再使用的資源、增加某程序的 Max、增加資源種類。要逐項想「這個變更會讓銀行家的哪個不等式變鬆或變緊」。與中央 108 年第 15 題是同一個考點
• 第 5 題（4%）｜fork 迴圈的輸出總和：a = 5，迴圈兩次 fork，子程序 a -= 2 後印出、父程序直接印出。要追蹤每個程序的 a 值與印出次數，再判斷「所有輸出數字的總和是否大於 14」「是否至少有一個小於零」「除主程序外最多只建立兩個額外程序」。一定要畫出程序樹，子程序也會繼續執行剩下的迴圈
• 第 6 題（4%）｜虛擬記憶體：四個敘述考邏輯與實體空間的大小關係、換出頁存在哪裡、頁面被置換時是否一定要寫回、頁錯誤的處理流程。第三項考的是 dirty bit 的用途
• 第 7 題（4%）｜磁碟排程：四個敘述考 FCFS 的飢餓、SSTF 的延遲變異、SCAN 在哪一個指標上是最佳、磁碟排程對 RAM disk 是否有效。要分清楚每種演算法「優點在哪個指標」
• 第 8 題（4%）｜看 ls -l 的輸出判讀：(a) 由目錄 lib/ 的硬連結數推子目錄數、(b) t -> program.c 是哪一種連結、(c) program 對群組成員的執行權限、(d) 配置給 intro.ps 的儲存空間是否「剛好」等於檔案大小。(a) 要知道目錄的硬連結數怎麼組成，(d) 要知道檔案系統的配置單位
• 第 9 題（4%）｜頁表設計：四個敘述分別考反轉頁表條目的內容、雜湊頁表碰撞串列元素的內容、多層頁表內層條目的內容、層數與 TLB 失誤罰則的關係
• 第 10 題（4%）｜CPU 效能：四個敘述考縮短回應時間的方法、不同 ISA 之間能否只比 CPI、CPU 時間的組成、MIPS 指標的公平性
• 第 11 題（4%）｜（配分同上，OCR 併入第 10 題敘述）
• 第 12 題（4%）｜MIPS 的四大設計原則：四個敘述各舉一個 MIPS 的設計特徵，要判斷它對應的原則有沒有配對正確。四大原則要一字不差地分清楚，有一項是把特徵配到了錯的原則上
• 第 13 題（4%）｜計算機算術：四個敘述考 sticky bit 的作用與位元數、復原與非復原除法的比較、異號相加是否會溢位、一段 MIPS 指令能否正確偵測無號數加法溢位。最後一項要真的把 nor 與 sltu 的語意代進去推
• 第 14 題（4%）｜strcpy 組語的堆疊框與位址欄位：給 11 道指令與位址（96400 起）。(a)(b) 兩種「加上儲存／恢復 $s0 與 $ra」的寫法擇一——先看程式裡有沒有會覆寫 $ra 的指令、(c) ADR1 = beq 的位移欄位、(d) ADR2 = j 的 26-bit 位址欄位。(c)(d) 兩種編碼的計算基準不同，是最容易算錯的地方
• 第 15 題（4%）｜浮點加法硬體的控制訊號追蹤：1.01111×2⁴ 加 1.10011×2⁶，尾數 5 bits、有 guard bit 與 round bit。要逐一填出 c0–c7 八個控制訊號。要熟悉浮點加法器的四個步驟在資料路徑上對應哪些多工器。這是十年唯一一次直接考浮點加法器的資料流
• 第 16 題（4%）｜單週期／多週期／管線的硬體成本與速度：四個敘述考三種實作的硬體成本、速度、是否需要級間鎖存器、是否有「時脈遷就最慢級」的問題。每一項都要三種實作逐一比較，不要只記一個優缺點
• 第 17 題（4%）｜三種危障的定義：四個敘述考控制危障能否避免停頓、算術溢位與除以零屬於什麼、「記憶體危障」這個分類存不存在、結構危障的處理方式。要以課本的標準分類為準
• 第 18 題（4%）｜整數算術溢位的例外處理：四個選項描述處理器遇到溢位時的行為。考 MIPS add 的溢位語意與精確例外——要想清楚第 i 道指令之前、之後的指令各處於什麼狀態，以及溢位的結果能不能被寫回
• 第 19 題（4%）｜由 tag／index／offset 反推快取大小：四個敘述考直接對映與組相聯快取能否由欄位大小決定容量、各欄位能不能是 0 bit、同容量下三種對映方式的 tag 大小比較。要想到全關聯這個邊界情形
• 第 20 題（4%）｜快取與虛擬記憶體的共同原理：四個敘述考共同原理的名稱、快取區塊在虛擬記憶體中的對應物、失誤時 CPU 的行為是否相同、虛擬記憶體的寫入策略

題組（21–33，20 分）

• 題組 A（21–24，5%）｜RR 平均周轉時間的四進位拆解：四個程序給到達時間與 CPU burst，時間量子 = 4。算出平均周轉時間 U 後，把 4U 寫成 U₃×4³ + U₂×4² + U₁×4¹ + U₀，四個小題分別問 U₃、U₂、U₁、U₀。四小題全對才 5 分，等於畫錯甘特圖就全失。新到達的程序與剛用完量子的程序誰先進佇列要先確定慣例
• 題組 B（25–27，5%）｜48-bit 邏輯／32-bit 實體位址、16 KB 頁：
• 第 25 題｜最多幾個頁框
• 第 26 題｜單層頁表有幾個條目。算完之後要回頭對選項，選項範圍是這一組的陷阱
• 第 27 題｜頁表條目至少幾個位元（不含控制位元）
• 三小題分別用到虛擬位址寬度與實體位址寬度，別混用
• 題組 C（28–30，5%）｜陣列索引版與指標版的 MIPS 組語對照：clear1 用索引、clear2 用指標，要填出三組空格（初值、遞增量、迴圈結束的比較對象）。兩個版本的遞增量單位不同——一個是索引、一個是位元組位址。這是 Patterson & Hennessy 課本的經典對照範例
• 題組 D（31–33，5%）｜n+1 道指令無限重複時三種快取的命中率：n 是 2 的冪，指令與快取列都是 32 bits，快取只有 n 條列。
• 第 31 題｜直接對映的命中率
• 第 32 題｜全關聯 + LRU 的命中率
• 第 33 題｜全關聯 + MRU 的命中率
• 這組是刻意設計來打破「全關聯 + LRU 一定最好」的直覺。要代一個小的 n 實際跑幾輪，觀察每種策略在穩態下踢掉的是哪一條

這份考卷的難點

1. 題組 D 是全卷設計最好的一題。 大部分人反射性地認為「全關聯 + LRU 一定優於直接對映」，但這個「n+1 個區塊循環走訪、只有 n 條列」的情境正是為了挑戰這個直覺而設計的。沒有代小的 n 實際跑一次就很難答對。
2. 第 8 題要會讀 ls -l 的硬連結數。 目錄的硬連結數怎麼組成，是 UNIX 檔案系統很細的一點，課本常只帶過。
3. 第 14 題要同時做三件事：判斷需不需要存 $ra、算 beq 的位移、算 j 的 26-bit 位址欄位。三個小地方都容易錯。
4. 第 19 題的邊界情形——全關聯快取的位址拆解方式跟另外兩種不一樣，很多人沒想過。

準備建議

• 置換演算法在循環走訪下的病態行為（題組 D）要自己推一次。106 年第 7 題、110 年第 2 題也都在考置換演算法的邊界行為
• 交大的題組幾乎每年都有一組是「把一個數值拆成多位數，四個小題各問一位」（108 題組 A、成大與台大近年也採用）。這種設計等於「全對才給分」的加強版
• MIPS 的四大設計原則要能對號入座：simplicity favors regularity、smaller is faster、make the common case fast、good design demands compromises（第 12 題）
• beq 位移與 j 位址欄位的編碼方式（第 14 題）要練熟。106 年第 3 題也考
• 陣列版與指標版的組語對照（題組 C）直接出自 Patterson & Hennessy，把課本那一節讀熟就能拿滿 5 分
• ls -l 的欄位判讀（第 8 題）：權限、硬連結數、擁有者、群組、大小、時間、檔名，以及第一個字元代表的檔案類型
• 不對稱倒扣：把握低於 2/3 不要勾；但每題至少勾一個（整題未作答不給分）