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

題型與配分

科目：計算機系統（1103），系所班別「資訊聯招」，考試日期 110 年 2 月 3 日第 3 節（本年起校名為國立陽明交通大學），全卷 100 分、9 頁、33 題。不可使用計算機、請使用答案卡作答。

這一年計分規則有兩處關鍵改動：

1. 答錯一個選項從倒扣 2 分變成倒扣 1 分——單一選項的懲罰減半，把握超過 50% 就值得勾（106–109 是要超過 2/3）。
2. 但倒扣下限從「該題 0 分」放寬成「本科目計算機系統 0 分」——一題可以扣成負分，只是整科不會低於 0。在 106–109 的規則下，一題最多扣到 0；110 年起某一題答錯太多會侵蝕其他題的分數。

整體而言風險是提高而不是降低的。 這個規則沿用到 114 年，115 年才改回「答錯 −2、扣至該題 0 分」。

OS 與計組的比重：OS 50%（第 1–10 題與題組 A、B）、計組 50%（第 11–20 題與題組 C、D）。前十題純 OS、後十題純計組，切得很乾淨。

複選題（1–20，80 分）

作業系統（1–10）

• 第 1 題（4%）｜目錄結構——四個選項橫跨 樹狀、無環圖、一般圖形 三種目錄，分別問 能不能用符號連結共享、會不會出現懸盪指標、參考計數可不可靠、什麼時候才需要垃圾回收。主軸只有一條：目錄圖裡容不容許「環」，三種結構的差異都是從這裡推出來的
• 第 2 題（4%）｜四個頁框的頁面置換：參考串 50, 40, 80, 20, 50, 10, 80, 40，要分別算 LRU 與 Optimal 的頁錯誤數。另外兩個選項問 LRU 會不會出現 Belady's anomaly、要限制輾轉的擴散該用全域置換還是區域置換。後者的方向很容易記反
• 第 3 題（4%）｜索引配置的最大檔案大小：索引區塊與資料區塊都是 1 KB、每個索引條目 4 bytes。先算出「一個索引區塊放得下幾個條目」，單層與兩層再各算一次。另外兩個選項問 鏈結與索引配置有沒有外部碎裂、需要直接存取的應用該用哪一種
• 第 4 題（4%）｜Buddy system 與 Slab 配置——四個選項分別問 「物件事先建好所以能快速滿足請求」是哪一種的特性、一個 slab 內能不能同時有已用與空閒物件、buddy system 會用多大的區塊來滿足一個非 2 的冪的請求、slab 是否完全沒有碎裂。前兩項要小心兩種配置器的特性被對調
• 第 5 題（4%）｜磁碟排程：請求序列 120, 25, 5, 11, 80, 185, 90, 85，磁頭初始在 88 且正往上移動。要判斷 SSTF 與 C-SCAN 的服務順序、SSTF 會不會造成飢餓、C-SCAN 相對 SCAN 改善的是什麼。SSTF 本身看不看方向？題目特地告訴你「正往上移動」，要判斷這個條件對哪個演算法有影響
• 第 6 題（4%）｜系統呼叫——四個選項涵蓋 系統呼叫是不是也走中斷機制、有沒有向量表項、參數太多時的傳遞方式、核心與使用者空間之間的複製能不能卸載給 DMA。最後一項的判斷點是「DMA 連接的是哪兩端」
• 第 7 題（4%）｜執行中的程序遇到各種事件會轉到哪個狀態——四個事件：與自己無關的裝置中斷、時脈中斷、I/O 系統呼叫、非 I/O 的系統呼叫。判準：這個事件是「讓我等別的東西」還是「只是被打斷」
• 第 8 題（4%）｜send／receive 的阻塞與非阻塞組合——四個選項排列出 兩種組合 × receive 早於／晚於 send 兩種時序。判準：非阻塞與阻塞的一方在對方還沒就緒時各會怎麼做
• 第 9 題（4%）｜使用者執行緒與核心執行緒各自擁有哪些堆疊與控制結構——要能分別列出兩者在使用者空間與核心空間裡各有什麼
• 第 10 題（4%）｜現代 OS 調整優先權的常見策略——四個選項分別是 I/O 頻繁的程序、從長時間睡眠醒來的程序、前景程序、用完時間量子的程序 各該往哪個方向調。判準：這個程序是互動型還是 CPU 密集型

計算機結構（11–20）

• 第 11 題（4%）｜CPU 效能——四個選項涵蓋 多核加上負載平衡能不能縮短回應時間、跨 ISA 比較時 CPI 小的是不是一定比較快、CPU 時間由哪三個因子決定、由「比較快但 MIPS 較低」反推是 RISC 還是 CISC。最後一項要從指令數與 MIPS 的關係去推理
• 第 12 題（4%）｜看費氏數列遞迴的 MIPS 組語——四個選項涵蓋 為何只有 32 個暫存器、編譯器的暫存器配置策略、MIPS 為何不提供 blt／bgt、prologue 存的那幾個暫存器是不是每一個都必要。最後一項要真的回去看程式，逐一檢查每個被存起來的暫存器在遞迴呼叫之後還有沒有用到
• 第 13 題（4%）｜MIPS 的浮點與常數載入——四個選項涵蓋 浮點有沒有獨立的暫存器組、lui + ori 組出來的 32 位元常數是多少、浮點加法滿不滿足結合律、給定 PC 時 j 能到達的最高位址。j 的目標位址怎麼組出來要記清楚
• 第 14 題（4%）｜組譯器展開、IEEE754 與 LL/SC——四個選項涵蓋 組譯器為何要把 beq 改寫成 bne + j、最小正單精度非正規化數、sticky bit 有幾位、記錄什麼、ll／sc 這對指令保護的是什麼。第一項要想清楚改寫的真正原因
• 第 15 題（4%）｜乘除法硬體與進位預看——四個選項涵蓋 乘除法合併硬體中各暫存器在乘法時扮演什麼角色、Booth 演算法的效能來源、用 NRDA 與 RDA 做一次除法各需幾次加減（要實際跑一遍）、多層進位預看加法器帶來的好處
• 第 16 題（4%）｜單週期／多週期／管線各自的硬體需求——四個選項涵蓋 時脈訊號能不能拿來控制組合電路、單週期為何至少需要兩個獨立的記憶體單元、哪一種設計的硬體最便宜、管線化需不需要同樣的兩個記憶體單元。主軸是「這一種設計在同一個週期內會同時用到哪些資源」
• 第 17 題（4%）｜看指令格式表與資料路徑做機器碼編碼——四個選項分別要 編碼一道 R-type 指令、編碼一道帶負位移的 sw（負數位移的表示法是最常錯的一項）、判斷 beq 的下一個 PC 怎麼算、列出 sub 的控制訊號值
• 第 18 題（4%）｜管線危障——四個選項涵蓋 結構危障是不是「必須」靠複製硬體來解、單一管線循序取指能保證什麼、真資料相依靠轉送能解決到什麼程度、循序發射與反相依的關係以及迴圈展開為何要重新命名。第一項用了「必須」這種絕對字眼
• 第 19 題（4%）｜記憶體階層——四個選項涵蓋 階層式設計是不是對「任何」應用都比較快、L1 快取該優先最佳化命中時間還是命中率、位址拆出來的三個欄位裡哪些需要真的存在快取列中、AMAT 的式子對不對。第一項的絕對字眼要檢查
• 第 20 題（4%）｜問「哪些敘述不正確」——四個選項涵蓋 快取與虛擬記憶體兩層階層各基於哪幾種區域性、快取控制器與虛擬記憶體管理器各由硬體還是軟體實作、快取失誤時 CPU 會不會切換去跑別的工作。最後一項要比較「快取失誤」與「頁錯誤」的代價量級

題組（21–33，20 分）

• 題組 A（21–23，5%）｜兩層分頁的索引拆解：32-bit 邏輯位址、4 KB 頁、實體記憶體 256 MB、每個頁表條目 4 bytes。
• 第 21 題｜單層頁表時 0xabcdef12 用來索引頁表的值
• 第 22 題｜兩層且外層有 256 個條目時，外層與內層的索引各是多少
• 第 23 題｜每個程序的頁表最多需要多少記憶體——兩層要分開算再相加
• 先切出頁內偏移，剩下的再依外層條目數切成兩段。位址是十六進位，按位元切比按數值除容易
• 題組 B（24–26，5%）｜用 monitor 解餐哲問題：卷上給完整的 DiningPhilosophers monitor 程式。
• 第 24 題｜指出哲學家用餐程式中寫錯的那一行——要逐行對照 monitor 版本的標準寫法，特別注意 test() 裡判斷條件用的是哪一個狀態
• 第 25 題｜test(i) 的目的
• 第 26 題｜test((i+4)%5) 的目的——題目說 index 是逆時針遞增，要先確定 (i+4)%5 指的是哪一位鄰居
• 題組 C（27–29，5%）｜1-bit ALU 的控制訊號：給最低位與最高位兩種 1-bit ALU 的電路圖。
• 第 27 題｜slt 的實現概念：要講清楚最高位 ALU 的哪個輸出接回最低位的 Less 輸入
• 第 28 題｜slt 與 sub 的控制訊號組合
• 第 29 題｜bne、nor、lw、sw 各自的 ALU 控制訊號組合——nor 那一項要先用 De Morgan 律改寫，才對得上 ALU 實際支援的運算
• 題組 D（30–33，5%）｜用符號參數表示各種容量與位元數：記憶體空間 32-bit 位元組定址、主記憶體 2^mm bytes、頁框 2^pf bytes、快取 2^cache bytes、快取區塊 2^cb bytes。要用這些符號寫出程式可用空間、頁框數、快取列數與 tag 位元數。全部用符號推導，不給具體數字

這份考卷的難點

1. 計分規則改動的方向容易誤判。 「答錯只扣 1 分」聽起來變寬鬆，但下限從「該題 0 分」放寬成「整科 0 分」——110 年起多個 −1 會真的從總分扣掉。實質風險是提高的。
2. 題組 B 第 24 題要在一段看似正確的 monitor 程式裡找出唯一寫錯的一行。 只差一個字，而且整段程式其餘都對，沒背過標準寫法很難看出來。
3. 題組 C 的 slt 實現：關鍵是最高位 ALU 的哪個輸出要繞回第 0 位。109 年題組 C 考同一個結構的傳播延遲，110 年改考控制訊號。
4. 第 5 題的磁碟排程給了「磁頭正往上移動」這個條件。 要判斷這個條件對 SSTF 是干擾還是真的會改變答案。

準備建議

• 110–114 年的計分是「答錯 −1、扣至整科 0 分」，115 年改回「答錯 −2、扣至該題 0 分」。進場一定要看清楚當年度寫的是哪一種
• 1-bit ALU 的結構是交大連兩年的重點（109 題組 C 考傳播延遲、110 題組 C 考控制訊號）。AInvert、BInvert、CarryIn、Operation 四個控制訊號在各種運算下的組合要背熟，slt 的接法也要會畫
• 兩層分頁的索引拆解（題組 A）要練到反射
• 餐哲問題的 monitor 解法（題組 B）建議把 Silberschatz 的那段程式背下來，交大直接考「哪一行寫錯」
• Buddy system 的配置規則（第 4 題）：它只配置什麼大小的區塊
• j 指令的跳躍範圍（第 13 題）：目標位址的組成方式與可到達的範圍
• 前十題純 OS、後十題純計組，這個切分從 110 年開始很穩定，分科複習時可以直接對應題號