111 台大資工所考古題詳解｜硬體考點分析

題型與配分

全卷 100 分、10 頁，試題隨卷繳回。

106–110 年是手寫申論（110 年是只填答案），111 年起改成全選擇題，沿用到 115 年。

複選題配分從 4 分（第 8、9、10 題）到 10 分（第 19 題）不等，第 18、19 題合計 18 分。

單選題（1–7，35 分）

• 第 1 題（5%）｜看圖做 paging address translation：頁面 4 bytes、每個 page table 有 4 個 entry、physical memory 32 bytes。從邏輯記憶體圖找出變數 g 與 o 的 logical address，查 page table 換成 physical address
• 第 2 題（5%）｜page offset 位元數與 page table 大小：24-bit logical address、每個 entry 1 byte、每頁 4 KiB
• 第 3 題（5%）｜open() 失敗時的執行路徑：open(file_name, O_CREAT|O_EXCL|O_WRONLY, mode) 回傳 −1。在「使用者程式、核心記憶體、次要儲存」的流程圖上指出走到哪裡就折返
• 第 4 題（5%）｜由指令數與執行時間反推兩個編譯器的平均 CPI（clock cycle 1 ns）。114 年第 11 題是同一個模板
• 第 5 題（5%）｜無 forwarding 的 pipeline 完成週期：五級 pipeline、沒有資料 forwarding、同一週期可以先寫後讀。程式為 sd x29,12(x16)、ld x29,8(x16)、sub x17,x29,x14、add x15,x17,x14、sub x15,x30,x14，問 #3 與 #4 分別在第幾個週期完成
• 第 6 題（5%）｜把 RISC-V assembly 還原成 C：程式用 slli 做位移、呼叫另一個函式、再用 lui 加 addi 組出一個 32 位元 immediate。題目特別提醒 addi 的 immediate 會 sign extension
• 第 7 題（5%）｜兩核心並行執行的所有可能結果：兩個 core 各跑「載入、加一、存回」再「載入另一位址、相加、存回」，沒有 synchronization 保護。問 [x2] 與 [x3] 在所有交錯順序下的可能值

複選題（8–19，65 分）

• 第 8 題（4%）｜wait() 與殭屍、孤兒 process：連鎖終止的定義、殭屍 process 的 PID 何時被釋放、沒有 child process 時呼叫 wait() 會怎樣、孤兒 process 被誰接手
• 第 9 題（4%）｜thread：implicit threading 把工作交給誰、thread pool 的好處、單核心系統能不能支援 concurrency、Pthread 的兩種取消方式。114 年第 9(B) 題再考 concurrency 與 parallelism 之分
• 第 10 題（4%）｜Rate-Monotonic scheduling：三個週期性 process（P1 週期 30、burst 10；P2 週期 70、burst 10；P3 週期 100、burst 20）。算最壞情況 turnaround time，並判斷「把 P3 的 burst 增加 X，最壞周轉時間也剛好增加 X」、「改變到達時間，所有最壞周轉時間不變」等敘述
• 第 11 題（5%）｜virtual memory：每個 process 有沒有自己的虛擬空間、它如何提高並行度、address space 能不能被共享、paging 機制相當於用一個還是數個 base register
• 第 12 題（5%）｜file system 的 consistency semantics：consistency semantics 規範什麼、UNIX semantics 在分散式環境的可行性、session semantics 與 immutable shared file semantics 的定義
• 第 13 題（5%）｜critical section 與 synchronization 性質之間的邏輯蘊含方向：resource allocation graph 的 cycle 是不是 deadlock 的充要條件、progress 與 bounded waiting 誰蘊含誰、無 deadlock 與無 starvation 誰蘊含誰。與中正 110 年第 1(9) 題是同一個考點
• 第 14 題（5%）｜哪些 associativity 可以做成 VIPT（頁面 4 KiB、cache 16 KiB、block 32 bytes）。與 107 年第 9 題是同一個條件的不同問法
• 第 15 題（5%）｜指令組合與效能最佳化的五個判斷：INT、FP、LS、branch 的 CPI 分別是 1、2、4、2，指令數 12M、15M、50M、13M，clock 3.2 GHz。五個判斷是移除八成的 INT 指令能省多少、把 LS 的 CPI 降到 1.2 能快幾倍、指令數減半但 clock cycle 增加 10% 的淨效果、加入一批高 CPI 的 system call 指令會慢幾倍、只降 FP 的 CPI 最多能快到什麼程度
• 第 16 題（5%）｜Intel SGX 與 TEE：remote attestation 為何必要、enclave 能不能執行 privileged instruction、位於 OS kernel 的攻擊者還能對 enclave 做什麼、sealing 金鑰的綁定對象。108 年第 2(c) 題已考過 TEE
• 第 17 題（5%）｜register 數量與指令編碼的連動：選項分別拿 I-type 的 immediate 寬度、I-type 指令的數量、移位量欄位、指令總長度、程式碼大小來問。與 106 年第 5 題是同一個主題
• 第 18 題（8%）｜平均 turnaround time 的多項式係數：n 個 process，第 i 個在時間 (i−1) 到達、burst 為 (2n−2i+2)。用 preemptive scheduling 最小化平均 turnaround time，並把結果寫成 Wn³+Xn²+Yn+Z，然後判斷四個關於係數的等式
• 第 19 題（10%）｜ARM big.LITTLE 的設計目標、用 Amdahl's Law 看「100 個處理器要達到 90 倍加速時循序部分最多佔幾成」、RISC 是不是總是優於 CISC、block size 與 false sharing 的關係、block size 對 compulsory miss 的影響。false sharing 那一項與 110 年第 6 題是同一個觀念

作答時要注意的地方

1. 第 18 題 8 分，要寫出一般式並判斷四個係數等式。
2. 第 13 題的選項把幾組性質的蘊含方向正反各寫了一次。
3. 第 15 題五個判斷都建立在各類指令的週期數上。
4. 第 7 題沒有 synchronization 保護，要考慮兩個 core 指令交錯的所有可能。
5. 複選題錯誤選項為零分，不倒扣。

準備方向

• VIPT 的免別名條件在 107 第 9 題、111 第 14 題、114 第 14、15 題都出現。
• register 數量與指令編碼的取捨：106 第 5 題、111 第 17 題，112 第 8(B) 題與 115 第 7(D) 題也問到 register 數量的影響。
• Amdahl's Law 的上限判斷（第 15、19 題），包含給定目標 speedup 反推循序部分的上限。
• false sharing 與 block size 的關係：110 第 6 題、111 第 19 題。
• Rate-Monotonic 與最佳 scheduling 的手算（第 10、18 題）。110 第 3 題也考過五種 scheduling 演算法。
• SGX 與 TEE（108 第 2(c) 題、111 第 16 題）、big.LITTLE（108 第 6 題、111 第 19 題）。