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

題型與配分

全卷 9 頁、35 題、100 分，不可使用計算機，請使用答案卡作答。

計分沿用 110 年的答錯 −1、扣至整科 0 分。

題組為 A（21–24，四小題）、B（25–28，四小題）、C（29–32，四小題）、D（33–35，三小題），共 15 個小題，每組全對才給 5 分。

OS 出現在第 1–10 題與題組 A、B，計組出現在第 11–20 題與題組 C、D。

複選題（1–20，80 分）

作業系統（1–10）

• 第 1 題（4%）｜fork 巢狀的輸出順序：程式印 A，然後 fork()。child process 隨機睡一段時間後印 B，再 fork() 出 grandchild process 印 C，child process wait(NULL) 後印 D；原 parent process 隨機睡一段時間後印 E，再 wait(NULL)。要判斷 ABCED、AEBCD、ABDCE、AEBDC 哪些輸出是可能的
• 第 2 題（4%）｜單一資源型態的 safe state：四個 thread 給 Maximum Needs 與 Current Needs，求仍能維持 safe state 的最大 x。其餘選項問 unsafe 與 deadlock 的關係、這種單一資源的判斷法與 Banker's algorithm 的關係
• 第 3 題（4%）｜semaphore：四個選項涵蓋兩個 process 共用兩個 binary semaphore 會不會 deadlock、用 binary semaphore 實作 mutex 時初值該設多少、對 condition variable 做 signal 但沒人等待時會怎樣、對 semaphore 做 signal 但沒人等待時會怎樣
• 第 4 題（4%）｜process 狀態：四個選項涵蓋 blocking send() 會讓 process 進入哪個狀態、等待 spinlock 時 process 在哪個狀態、一直停在 waiting 會不會產生切換開銷、wakeup() 把 process 帶到哪個狀態
• 第 5 題（4%）｜CPU scheduling：四個選項涵蓋 non-preemptive SJF 與 FCFS 的 context switch 次數比較、SRTF 會不會造成 starvation、time slice 用完屬於自願還是非自願切換、processor affinity 算不算 load balancing 技術（中央 114 年第 13 題也考過）
• 第 6 題（4%）｜增強型二次機會演算法的 (reference, modify) 四類：四個選項涵蓋巡迴時哪一個位元可以清、哪一個不能清、四類的換出優先順序、(0,1) 與 (1,0) 誰先被換出、換出髒頁時要多做什麼
• 第 7 題（4%）｜memory-mapped file：四個選項涵蓋 mmap() 一開始會不會把整個檔案載入、映射到使用者空間還是 kernel space、映射之後 read() 與 write() 會不會被自動轉譯
• 第 8 題（4%）｜四種配置方式讀取第 239 個 block 要讀幾塊：檔案 512 塊，extent 平均 16 塊，目錄已在記憶體中。連續、extent、鏈結、索引四種各算一次
• 第 9 題（4%）｜UFS 的 inode 最大檔案大小：4 KB block、2048 個 direct block、每個間接節點 2048 個 entry。四個選項分別問只有 direct block、加上單層間接、加上雙層間接、加上三層間接時的最大檔案大小
• 第 10 題（4%）｜Linux 機制：四個選項涵蓋 kernel module 會不會被自動卸載、kernel 如何處理不同的二進位格式（binfmt）、slab allocator 服務的對象是誰、靜態與 dynamic linking 在記憶體中各載入幾份

計算機結構（11–20）

• 第 11 題（4%）｜ISA：四個選項涵蓋 RISC 的固定格式對 pipeline 的好處、大小端的選擇算不算 ISA 的一部分、Open ISA 開放的是規格還是實作、把 register 欄位固定在同一位置對解碼的簡化（RISC-V 與 MIPS 的差異）
• 第 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 各該給什麼。與 110 年題組 C 是同一個結構
• 第 13 題（4%）｜DMA 與 I/O：四個選項涵蓋沒有 interrupt 機制還能不能用 DMA、memory-mapped I/O 與 DMA 是不是同一件事、DMA 控制器在 bus 上是主控還是從屬、DMA 為什麼會造成 cache coherence 問題
• 第 14 題（4%）｜依卷上的英文短文判斷 clock rate：四個選項涵蓋 clock 較低的 CPU 有沒有可能比較快、高 clock 為何更需要強力的 branch prediction、big.LITTLE 的兩種 core clock 能不能取平均、加深 pipeline 會不會增加單指令延遲
• 第 15 題（4%）｜全平行的 CPU：四個選項涵蓋要充分利用大量 core 需要什麼層級的平行、big.LITTLE 裡 big 核與 LITTLE 核各自的設計取向、base clock 與 turbo clock 各由什麼決定、各種平行技術分別需要編譯器還是 OS 支援
• 第 16 題（4%）｜IEEE754 表示：前兩個選項要把 3.125 normalize 後求出指數欄位與尾數欄位；後兩個選項給一個指數小到超出 normalized 範圍的數，問能不能表示、指數欄位長什麼樣
• 第 17 題（4%）｜在 ID 級偵測到 data hazard 時要設哪些訊號才能插入 stall，選項涉及 PC、IF/ID pipeline register 與送往後面各級的 control signal
• 第 18 題（4%）｜切斷 datapath A 後哪些程式會出錯：圖上的 A 是某一條 forwarding 路徑。要對四組三道指令的序列判斷哪些會出錯
• 第 19 題（4%）｜七道指令在有 forwarding 與 stall 的五級 pipeline 上執行：要算總週期數、stall 次數、第 5 個週期時 EXE 級是哪道指令、第 5 個週期時 ALUSrc 的值
• 第 20 題（4%）｜巢狀迴圈的 branch prediction 準確率：外迴圈跑 3 次、內迴圈每次跑 6 次。要分別算 1-bit 與 2-bit predictor 對 branch1（內層）與 branch2（外層）的準確率

題組（21–35，20 分）

• 題組 A（21–24，5%）｜第一類 readers-writers problem 的 semaphore 填空：程式碼被挖掉八個空格（①–⑧），用 read_count、mutex、rw_mutex 填。四小題分別問 mutex 的初值、① 填什麼、② 填什麼、⑦ 填什麼
• 題組 B（25–28，5%）｜SPARC hash page table 對 ARM 階層 page table 的存取時間：記憶體 100 ns、第二層 cache 10 ns hit rate 90%、第一層 cache 1 ns hit rate 60%、剩下 10% 要查記憶體中的表
• 第 25 題｜最小存取時間
• 第 26 題｜ARM 的最大存取時間（小頁用兩層階層 page table）
• 第 27 題｜SPARC 的最大存取時間（hash linked list 最長 4）
• 第 28 題｜ARM 用 huge page 時的平均存取時間
• 題組 C（29–32，5%）｜自訂 CPU「NYCU」的 cache 效能：2 GHz、lw/sw 佔 25%、理想 CPI 1、main memory 100 ns。公式卷上直接給：real CPI = ideal CPI + 資料存取機率 × 平均停頓週期、平均停頓 = miss rate × miss penalty
• 第 29 題｜direct-mapped L1、miss rate 4% 的 real CPI
• 第 30 題｜改成 4-way 後哪個效果不成立，考 associativity 提高的代價
• 第 31 題｜加上 L2（hit time 8 ns、miss rate 20%）後的 real CPI
• 第 32 題｜關於 TLB 哪個敘述不成立
• 題組 D（33–35，5%）｜MIPS machine code 與程式追蹤：程式從 8800 4000h 開始（106 年是 8000 4000h），$s2 的編號是 18（106 年是 17），其餘與 106 年第 3 題一樣，只把 finish 段的 addi $t0,$t0,100 換成 sll $t0,$t0,2
• 第 33 題｜beq 的 machine code
• 第 34 題｜j 的 machine code
• 第 35 題｜給定兩個 register 初值，求某個 register 的最終值

作答時要注意的地方

1. 題組共 15 個小題，每組全對才給 5 分。題組 B、C 各有四個小題。
2. 複選題答錯 −1，下限是整科 0 分，一題可以扣成負分。
3. 題組 B 是 SPARC hash page table 與 ARM 階層 page table 兩種設計的存取時間，題目有描述機制。
4. 題組 D 與 106 年第 3 題是同一段迴圈，但起始位址、$s2 編號與最後一道指令不同，machine code 要重算。

準備方向

• 106 第 3 題與 111 題組 D 同一段迴圈，換了起始位址、$s2 編號與最後一道指令。
• MIPS machine code 編碼：106 第 3 題、108 第 14 題、110 第 17 題、111 題組 D。
• 1-bit ALU 的控制四元組：110 題組 C、111 第 12 題。
• 讀者—寫者與 producer-consumer 的 semaphore 填空：106 題組 C、107 題組 C、111 題組 A。
• UFS 的 inode 最大檔案大小（111 第 9 題）。
• pipeline stall 時要設的 control signal（111 第 17 題）。