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

題型與配分

科目：計算機結構與作業系統（B），題號 360、節次 2，全卷 100 分、10 頁——是台大硬體十年來頁數最多的一份。試題隨卷繳回。

這是台大硬體從申論卷轉向選擇卷的第一年。 106–110 全部是手寫申論（110 年是只填答案），111 年起改成全選擇題並沿用至今。

全卷完全不倒扣，而且複選題是「錯誤選項為零分」而不是負分。在這個規則下，所有題目、所有選項都應該作答——空白的期望值一定比猜測差。這與中央硬體的逐選項倒扣是完全相反的邏輯。

配分不平均：複選題從 4 分（第 8、9、10 題）到 10 分（第 19 題）都有，第 18、19 題合計 18 分。答題時要先掃過配分再決定時間分配。

單選題（1–7，35 分）

• 第 1 題（5%）｜看圖做分頁位址轉換：頁面 4 bytes、每個頁表有 4 個條目、實體記憶體 32 bytes。要從邏輯記憶體圖找出變數 g 與 o 的邏輯位址，查頁表換成實體位址。頁面只有 4 bytes 是刻意設計的極小例子，偏移位元很少
• 第 2 題（5%）｜頁內偏移位元數與頁表大小：24-bit 邏輯位址、每個條目 1 byte、每頁 4 KiB。三步驟：由頁面大小得偏移位元數 → 位址位元數減去偏移得頁號位元數 → 頁號數 × 條目大小 = 頁表大小
• 第 3 題（5%）｜open() 失敗時的執行路徑：open(file_name, O_CREAT|O_EXCL|O_WRONLY, mode) 回傳 −1。要在「使用者程式 → 核心記憶體 → 次要儲存」的流程圖上指出走到哪裡就折返。要知道 O_CREAT|O_EXCL 組合在什麼情況下會失敗，以及核心在哪一步就能判斷出來
• 第 4 題（5%）｜由指令數與執行時間反推兩個編譯器的平均 CPI（時脈週期 1 ns）——先把執行時間換算成總週期數，再除以指令數。與 114 年第 11 題是同一個模板
• 第 5 題（5%）｜無 forwarding 的管線完成週期：五級管線、沒有資料轉送、但同一週期可以先寫後讀。程式為 sd x29,12(x16) → ld x29,8(x16) → sub x17,x29,x14 → add x15,x17,x14 → sub x15,x30,x14。要找出所有 RAW 相依，逐拍畫出管線圖才能算出 #3 與 #4 分別在第幾個週期完成。停頓會累積，前面停了後面也跟著延後
• 第 6 題（5%）｜把 RISC-V 組語還原成 C：程式用 slli 做位移、呼叫另一個函式、再用 lui + addi 組出一個 32 位元立即數。關鍵在 addi 的立即數會符號延伸——題目特別提醒這一點，而選項就是拿有沒有處理符號延伸來設計
• 第 7 題（5%）｜兩核心並行執行的所有可能結果：兩個核心各跑「載入 → 加一 → 存回」再「載入另一位址 → 相加 → 存回」，沒有同步保護。要列出 [x2] 與 [x3] 在所有交錯順序下的可能值。這是典型的競爭條件窮舉題，必須把 lost update 的情形考慮進去

複選題（8–19，65 分）

• 第 8 題（4%）｜wait() 與殭屍／孤兒程序——涵蓋 連鎖終止的定義、殭屍程序的 PID 何時被釋放、沒有子程序時呼叫 wait() 會怎樣、孤兒程序被誰接手。想清楚殭屍程序存在的意義，就能判斷
• 第 9 題（4%）｜執行緒——涵蓋 隱式執行緒把工作交給誰、執行緒池的好處、單核心系統能不能支援並行、Pthread 的兩種取消方式。兩個核心分界：concurrency 與 parallelism 的差別；deferred 與 asynchronous cancellation 的差別。114 年第 9(B) 題再考一次並行與平行之分
• 第 10 題（4%）｜Rate-Monotonic 排程：三個週期性程序（P1 週期 30／burst 10、P2 週期 70／burst 10、P3 週期 100／burst 20）。要算最壞情況周轉時間，並判斷「把 P3 的 burst 增加 X，最壞周轉時間也剛好增加 X」、「改變到達時間，所有最壞周轉時間不變」等敘述。先確定 RMS 怎麼指派優先權，再想清楚低優先權程序的周轉時間會受到什麼影響
• 第 11 題（5%）｜虛擬記憶體——涵蓋 每個程序有沒有自己的虛擬空間、它如何提高並行度、位址空間能不能被共享、以及 分頁機制相當於用「一個」還是「數個」base 暫存器。最後這組是全題的判斷點
• 第 12 題（5%）｜檔案系統的一致性語意——涵蓋 一致性語意到底在規範什麼、UNIX 語意在分散式環境的可行性、session 語意與不可變共享檔案語意的定義。三種語意的定義要能各寫一句，選項就是拿它們互換
• 第 13 題（5%）｜臨界區與同步性質之間的邏輯蘊含方向——涵蓋 資源配置圖的環是不是死結的充要條件、progress 與 bounded waiting 誰蘊含誰、無死結與無飢餓誰蘊含誰。這是全卷最抽象的一題，與中正 110 年第 1(9) 題是同一個考點
• 第 14 題（5%）｜哪些關聯度可以做成 VIPT（頁面 4 KiB、快取 16 KiB、區塊 32 bytes）。要知道 VIPT 避免別名的條件，由那個條件反解關聯度的範圍。與 107 年第 9 題是同一個條件的不同問法
• 第 15 題（5%）｜指令組合與效能最佳化的五個判斷：INT/FP/LS/branch 的 CPI 分別是 1/2/4/2，指令數 12M/15M/50M/13M，時脈 3.2 GHz。第一步一定要先算出各類指令貢獻的週期數與總週期數，五個小判斷都建立在這張表上：移除八成的 INT 指令能省多少、把 LS 的 CPI 降到 1.2 能快幾倍、指令數減半但時脈週期增加 10% 的淨效果、加入一批高 CPI 的系統呼叫指令會慢幾倍、只降 FP 的 CPI 最多能快到什麼程度。最後一項要用 Amdahl's Law 的上限觀念
• 第 16 題（5%）｜Intel SGX 與 TEE——涵蓋 遠端證明（remote attestation）為何必要、enclave 能不能執行特權指令、位於 OS 核心的攻擊者還能對 enclave 做什麼、封存（sealing）金鑰的綁定對象。主軸是「SGX 防得了什麼、防不了什麼」。108 年第 2(c) 題已經考過 TEE，111 年深入到 SGX 的具體機制
• 第 17 題（5%）｜暫存器數量與指令編碼的連動——主線是「暫存器數量改變 ⇒ 暫存器欄位的位元數改變 ⇒ 同一格式裡其他欄位能分到多少位元」。選項分別拿 I-type 的立即數寬度、I-type 指令的數量、移位量欄位、指令總長度、程式碼大小來問。要留意哪些欄位其實與暫存器數無關。與 106 年第 5 題、108 年第 3 題是同一個主題的第三次出現
• 第 18 題（8%）｜推出平均周轉時間的多項式係數：n 個程序，第 i 個在時間 (i−1) 到達、burst 為 (2n−2i+2)。要用可搶占排程最小化平均周轉時間，並把結果寫成 Wn³+Xn²+Yn+Z，然後判斷四個關於係數的等式。先判斷哪一種演算法能最小化平均周轉時間，再推一般式。可以先代 n = 1、2、3 手算，驗證推出的式子對不對
• 第 19 題（10%）｜全卷配分最高的一題——涵蓋 ARM big.LITTLE 的設計目標、用 Amdahl's Law 反推「100 個處理器要達到 90 倍加速時循序部分最多佔幾成」、RISC 是不是「總是」優於 CISC、區塊大小與偽共享（false sharing）的關係、區塊大小對強制失誤的影響。Amdahl 那一項一定要真的算過才知道選項給的比例對不對。偽共享那一項與 110 年第 6 題是同一個觀念

這份考卷的難點

1. 第 18 題要推出一般式的三次多項式。 要先判斷最佳排程、再算出 n 個程序的總周轉時間、除以 n 得到平均，最後展開並驗證四個係數關係。8 分，但花的時間可能抵得上三題。
2. 第 13 題的蘊含方向極容易搞反。 選項把幾組性質的蘊含關係正反各寫了一次，要想清楚死結與飢餓各自的定義，誰涵蓋誰。
3. 第 15 題要做五次獨立的效能計算，而且有幾項都在測試「只優化某一類指令的加速上限」——必須先算出該類指令佔總週期的比例。
4. 第 7 題的競爭條件窮舉沒有捷徑，要老實列出兩個核心指令交錯的所有可能，特別是 lost update 的情形。

準備建議

• 111 年起台大硬體改成全選擇題且完全不倒扣，每一題每一個選項都要作答——複選題答錯只是該選項零分，沒有任何損失。這與中央硬體的逐選項倒扣策略正好相反，兩校一起準備時務必分清楚
• VIPT 的免別名條件在 107 第 9 題、111 第 14 題、115 第 6/7 題三度出現，是台大硬體最穩定的計算考點
• 暫存器數量與指令編碼的取捨（106 第 5 題、108 第 3 題、111 第 17 題）也是三度出現
• Amdahl's Law 的「上限判斷」（第 15、19 題）要練到能反向求解：給定目標加速比，反推可序列化部分的上限
• 偽共享與區塊大小的關係（110 第 6 題、111 第 19 題）：區塊大小對強制失誤與偽共享的影響方向要一起記
• Rate-Monotonic 與最佳排程的手算（第 10、18 題）是 OS 段的固定計算題，110 第 3 題也考過五種排程演算法
• SGX／TEE（108 第 2(c)、111 第 16 題）與 big.LITTLE（108 第 6、111 第 19 題）是台大偏好的產業題，考前要掃過當年度的處理器安全與架構新聞