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

題型與配分

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

計分沿用 110 年的「答錯 −1、扣至整科 0 分」。 單題可以扣成負分，只是整科不低於 0。

題組小題數是十年最多的一年：A（21–24，四小題）、B（25–28，四小題）、C（29–32，四小題）、D（33–35，三小題）共 15 個小題只值 20 分，而且每組全對才給分。

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

複選題（1–20，80 分）

作業系統（1–10）

• 第 1 題（4%）｜fork 巢狀的輸出順序：程式印 A，然後 fork()，子程序隨機睡一段時間後印 B，再 fork()…父程序用 wait(NULL) 等待後印 D、E。要判斷 ABCED／AEBCD／ABDCE／AEBDC 哪些輸出是可能的。關鍵是 wait() 造成的順序約束，要先畫出程序樹再判斷哪些字母之間有先後關係
• 第 2 題（4%）｜單一資源型態的安全狀態：四個執行緒給 Maximum Needs 與 Current Needs，求仍能維持安全狀態的最大 x。其餘選項問 unsafe 與死結的關係、這種單一資源的判斷法與銀行家演算法的關係。unsafe 與死結的關係是跨校高頻考點（中央十年考四次）
• 第 3 題（4%）｜號誌——四個選項涵蓋 兩個程序共用兩個二元號誌會不會死結、用二元號誌實作 mutex 時初值該設多少、對「條件變數」做 signal 但沒人等待時會怎樣、對「號誌」做 signal 但沒人等待時會怎樣。後兩項合起來正是條件變數與號誌最關鍵的差異
• 第 4 題（4%）｜程序狀態——四個選項涵蓋 阻塞式 send() 會讓程序進入哪個狀態、等待自旋鎖時程序在哪個狀態、一直停在 waiting 會不會產生切換開銷、wakeup() 把程序帶到哪個狀態。要想清楚自旋鎖的等待方式，以及被喚醒的程序接下來去哪
• 第 5 題（4%）｜CPU 排程——四個選項涵蓋 非搶占 SJF 與 FCFS 的上下文切換次數比較、SRTF 會不會造成飢餓、時間片用完屬於自願還是非自願切換、處理器親和性算不算負載平衡技術。最後一項要想清楚親和性與負載平衡的關係（中央 114 年第 13 題也考過）
• 第 6 題（4%）｜增強型二次機會演算法的 (reference, modify) 四類——四個選項涵蓋 巡迴時哪一個位元可以清、哪一個不能清、四類的換出優先順序、(0,1) 與 (1,0) 誰先被換出、換出髒頁時要多做什麼。第一項是全題核心：想清楚兩個位元各自的用途，清掉哪一個會出事
• 第 7 題（4%）｜記憶體映射檔案——四個選項涵蓋 mmap() 一開始會不會把整個檔案載入、映射到使用者空間還是核心空間、映射之後 read()／write() 會不會被自動轉譯。第一項要想到 mmap 背後用的是哪一種分頁機制
• 第 8 題（4%）｜四種配置方式讀取第 239 個區塊要讀幾塊：檔案 512 塊，extent 平均 16 塊，目錄已在記憶體中。連續、extent、鏈結、索引四種各算一次。鏈結配置要數清楚「走過幾塊」；索引配置別漏掉讀索引區塊那一次；extent 配置要想清楚 extent 資訊放在哪
• 第 9 題（4%）｜UFS 的 inode 最大檔案大小：4 KB 區塊、2048 個直接區塊、每個間接節點 2048 個條目。四個選項分別問只有直接區塊、加上單層間接、加上雙層間接、加上三層間接時的最大檔案大小。每一層都要逐層累加，不能只算最後一層。是全卷最好拿的 4 分
• 第 10 題（4%）｜Linux 機制——四個選項涵蓋 核心模組會不會被自動卸載、核心如何處理不同的二進位格式（binfmt）、slab 配置器服務的對象是誰、靜態與動態連結在記憶體中各載入幾份。slab 那一項的判斷點是「它配置的是核心物件還是使用者記憶體」

計算機結構（11–20）

• 第 11 題（4%）｜指令集架構——四個選項涵蓋 RISC 的固定格式對管線的好處、大小端的選擇算不算 ISA 的一部分、Open ISA 開放的是規格還是實作、把暫存器欄位固定在同一位置對解碼的簡化（RISC-V 與 MIPS 的差異）。Open ISA 那一項最容易望文生義
• 第 12 題（4%）｜用 1-bit ALU 的控制四元組實作 C 敘述：格式為 (AInvert, BInvert, CarryIn, Operation)，例：C=A+B 給 (0,0,0,2)。要判斷 C=A-B、C=B-A、C=A<B、D=A==B 各該給什麼。A==B 要想 ALU 以外還需要什麼額外電路。與 110 年題組 C 是同一個結構
• 第 13 題（4%）｜DMA 與 I/O——四個選項涵蓋 沒有中斷機制還能不能用 DMA、記憶體映射 I/O 與 DMA 是不是同一件事、DMA 控制器在匯流排上是主控還是從屬、DMA 為什麼會造成快取一致性問題。第三項的判斷點：能自己發起傳輸的裝置在匯流排上扮演什麼角色
• 第 14 題（4%）｜依卷上的英文短文判斷時脈率——四個選項涵蓋 時脈較低的 CPU 有沒有可能比較快、高時脈為何更需要強力的分支預測、big.LITTLE 的兩種核心時脈能不能取平均、加深管線會不會增加單指令延遲。後兩項要留意「能不能相加」「會不會改變」這類說法
• 第 15 題（4%）｜全平行的 CPU——四個選項涵蓋 要充分利用大量核心需要什麼層級的平行、big.LITTLE 裡 big 核與 LITTLE 核各自的設計取向、base 時脈與 turbo 時脈各由什麼決定、各種平行技術分別需要編譯器還是 OS 支援。big.LITTLE 那一項要逐個形容詞核對
• 第 16 題（4%）｜IEEE754 表示——前兩個選項要把 3.125 正規化後求出指數欄位與尾數欄位（指數欄位要加 bias，這是最常見的錯法）；後兩個選項給一個指數小到超出正規化範圍的數，問能不能表示、指數欄位長什麼樣（要想到非正規化數）
• 第 17 題（4%）｜在 ID 級偵測到資料危障時要設哪些訊號才能插入停頓——要同時處理 PC、IF/ID 管線暫存器與送往後面各級的控制訊號。選項裡混了一個處理分支用的訊號當誘答
• 第 18 題（4%）｜切斷資料路徑 A 後哪些程式會出錯：圖上的 A 是某一條 forwarding 路徑。要對四組三道指令的序列判斷相依距離，先確定路徑 A 負責的是哪一個距離的轉送，再看哪些序列依賴它
• 第 19 題（4%）｜七道指令在有 forwarding 與停頓的五級管線上執行：要算 總週期數、停頓次數、第 5 個週期時 EXE 級是哪道指令、第 5 個週期時 ALUSrc 的值。程式裡有 lw 之後緊接使用結果的組合，要特別檢查
• 第 20 題（4%）｜巢狀迴圈的分支預測準確率：外迴圈跑 3 次、內迴圈每次跑 6 次。要分別算 1-bit 與 2-bit 預測器對 branch1（內層） 與 branch2（外層） 的準確率。兩個分支的執行次數與誤判模式完全不同，預測器狀態在外層迴圈之間會延續，要一路追蹤

題組（21–35，20 分）

• 題組 A（21–24，5%）｜第一類讀者—寫者問題的號誌填空：程式碼被挖掉八個空格（①–⑧），用 read_count、mutex、rw_mutex 填。四小題分別問 mutex 的初值、① 填什麼、② 填什麼、⑦ 填什麼。要清楚 mutex 與 rw_mutex 各自保護的是什麼，以及第一個讀者與最後一個讀者各要做什麼特別的事
• 題組 B（25–28，5%）｜SPARC 雜湊頁表對 ARM 階層頁表的存取時間：記憶體 100 ns、第二層快取 10 ns 命中率 90%、第一層快取 1 ns 命中率 60%、剩下 10% 要查記憶體中的表。先查第一層、再查第二層、最後查記憶體。
• 第 25 題｜最小存取時間
• 第 26 題｜ARM 的最大存取時間（小頁用兩層階層頁表）
• 第 27 題｜SPARC 的最大存取時間（雜湊鏈結串列最長 4）
• 第 28 題｜ARM 用大頁時的平均存取時間
• 別忘了查完頁表之後還要讀資料本身。這組是把課本沒有的「兩種商用 MMU 設計」直接拿來算，是十年唯一一次
• 題組 C（29–32，5%）｜自訂 CPU「NYCU」的快取效能：2 GHz、lw/sw 佔 25%、理想 CPI 1、主記憶體 100 ns。公式卷上直接給：real CPI = ideal CPI + 資料存取機率 × 平均停頓週期、平均停頓 = 失誤率 × 失誤罰則。
• 第 29 題｜直接對映 L1、失誤率 4% 的 real CPI。失誤罰則要先從 ns 換算成週期數
• 第 30 題｜改成 4-way 後哪個效果「不成立」。考關聯度提高的代價
• 第 31 題｜加上 L2（命中時間 8 ns、失誤率 20%）後的 real CPI
• 第 32 題｜關於 TLB 哪個敘述「不成立」。要分清「TLB 失誤」與「頁錯誤」的差別，這個陷阱師大 114 年、中央 115 年也各考過一次
• 題組 D（33–35，5%）｜MIPS 機器碼與程式追蹤：程式從 8800 4000h 開始，內容與 106 年第 3 題幾乎一樣，只把 finish 段的 addi $t0,$t0,100 換成 sll $t0,$t0,2。
• 第 33 題｜beq 的機器碼。offset 的基準是 PC+4，單位是 word
• 第 34 題｜j 的機器碼。要從目標位址算出 26-bit 欄位
• 第 35 題｜給定兩個暫存器初值，求某個暫存器的最終值。要先看出迴圈跑幾輪、每輪累加多少，最後別漏掉迴圈外那道位移指令

這份考卷的難點

1. 題組小題數是十年最多（15 個小題），而且每組全對才給分。 題組 B 的四小題每一題都要重算一次不同情境的存取時間，題組 C 的四小題要算兩次 real CPI 加兩次「哪個不成立」，任何一小題判斷錯就是 5 分歸零。
2. 第 15 題的 big.LITTLE 敘述讀起來很順，但要逐個形容詞核對它放在哪一種核心上。
3. 第 6 題的「兩個位元都清成 0」是很容易勾下去的陷阱，要想清楚 modify bit 被清掉的後果。
4. 題組 B 是課本沒有的內容：SPARC 的雜湊頁表與 ARM 的混合 1/2 層階層頁表。要現場讀懂題目描述的機制再算存取時間。

準備建議

• 題組 D 幾乎是 106 年第 3 題原樣重出（同一段迴圈、同樣問 beq 機器碼、j 機器碼與最終暫存器值），只換了起始位址與最後一道指令。106 年的考古題直接對應 111 年的 5 分
• 交大十年反覆考 MIPS 機器碼編碼（106 第 3 題、108 第 14 題、110 第 17 題、111 題組 D）。beq 的 offset、j 的 26-bit 欄位、R-type 的六個欄位順序都要能手算
• 1-bit ALU 的控制四元組（110 題組 C、111 第 12 題）連兩年考，各種運算的訊號組合要背
• 讀者—寫者與生產者—消費者的號誌填空是交大題組的常客（106 題組 C、107 題組 C、111 題組 A）。把兩段標準程式背下來就能直接拿 5 分
• UFS 的 inode 最大檔案大小（第 9 題）：直接、單間接、雙間接、三間接逐層累加
• 停頓的控制訊號（第 17 題）：插入停頓與處理分支用的訊號不同，別搞混
• 答錯 −1、扣至整科 0 分：把握超過 50% 就值得勾，但要記得一題可以扣成負分