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

題型與配分

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

這一年有幾題和前幾年重複：第 19 題與 107 年第 9 題一字不差（branch prediction 失敗的額外 CPI）、第 17 題與 107 年第 8 題幾乎相同（IEEE754 的四個敘述）、第 7 題與 109 年題組 B 同樣是判讀 cat 的記憶體映射、題組 A 與 112 年題組 A 同一組 RAID 5。

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

複選題（1–20，80 分）

作業系統（1–10）

• 第 1 題（4%）｜paging 的特徵：四個選項涵蓋 paging 是不是為了增加 physical memory、它如何切分 process 的 address space、它對 CPU clock 有沒有影響、它在 process 隔離上的作用
• 第 2 題（4%）｜記憶體管理：四個選項涵蓋 slab allocator 對兩種 fragmentation 的處理、page table 本身是不是存在 PCB 裡、x86-64 的 virtual address 寬度與支援的頁面大小、啟用 MMU 後使用者程式能用哪一種位址
• 第 3 題（4%）｜virtual memory：四個選項涵蓋 page fault 的處理流程、copy-on-write 的共享與複製時機、Linux swap 服務哪一類記憶體、x86 上的 page table traversal 由硬體還是 OS 執行
• 第 4 題（4%）｜process：四個選項涵蓋 PCB 裡放了哪些東西、interrupt 發生時為何必須先保存 context、傳統 UNIX 的 process 樹根是誰、哪些操作必須經過 system call
• 第 5 題（4%）｜Banker's algorithm 判斷 P2 的請求 (1,0,1)：五個 process、三種資源，Available = (3,3,2)。四個選項分別問可用資源夠不夠、核准之後還在不在 safe state、unsafe 與 deadlock 的關係、目前狀態安不安全
• 第 6 題（4%）｜interrupt 處理：四個選項涵蓋 interrupt 的定義、interrupt 是不是只能由硬體產生、interrupt 發生時的控制轉移、interrupt 有沒有 priority
• 第 7 題（4%）｜判讀 /usr/bin/cat 的記憶體映射表：四個選項要從表裡讀出 CPU 架構是 32 還是 64 位元、程式含不含 C 函式庫、放進 malloc() 緩衝區的 shellcode 能不能執行、能不能從映射表看出 child process 數量。與 109 年題組 B 是同一種題型
• 第 8 題（4%）｜Round Robin：四個選項涵蓋 RR 會不會造成 starvation、它能不能讓所有 process 更快完成、縮小 time quantum 對 turnaround time 的影響、它保證的是什麼公平性
• 第 9 題（4%）｜scheduler 與 thread：四個選項涵蓋 thread 切換較快的原因、Linux CFS 如何分配 time quantum、dispatcher 在哪一個模式下執行、新建 thread 與 parent process 共享什麼
• 第 10 題（4%）｜I/O 系統：四個選項涵蓋 bootstrap 存放在哪一種記憶體、開檔時目錄結構可能在哪裡、page cache 用的 DRAM 在斷電後會怎樣、VFS 層的作用

計算機結構（11–20）

• 第 11 題（4%）｜新 cache 架構帶來 1.25 倍加速：load 佔執行時間 20%、store 佔 10%，新 cache 讓 load 快 4 倍、store 快 2 倍。要驗證那個 speedup，再判斷這個改善是透過 clock、CPI 還是指令數發生的、以及它降低的是 miss rate 還是 miss penalty
• 第 12 題（4%）｜direct-mapped cache 的高 miss rate 屬於哪一種（tag 26、index 4、offset 2）
• 第 13 題（4%）｜加大 cache block 的影響：四個選項涵蓋它利用的是哪一種 locality、miss penalty 往哪個方向走、tag 的額外開銷怎麼變、miss rate 怎麼變
• 第 14 題（4%）｜改成 2-way 之後的 miss rate，算出 miss 數 ÷ 總存取數。其餘選項再問改用更小的 direct-mapped、或改用 fully associative 之後，miss rate 各往哪個方向走
• 第 15 題（4%）｜AMAT 與 IPC：4 GHz、無 stall CPI 1.4、load/store 佔 30%、hit time 1 cycle、I-cache miss rate 3%、D-cache miss rate 5%、miss penalty 50 ns。選項問 miss penalty 換算成幾個週期、指令存取的 AMAT、每道指令的 stall 週期、IPC
• 第 16 題（4%）｜數值表示：四個選項涵蓋 two's complement 與 IEEE754 各有幾種 0 的表示、兩個異號的 two's complement 相加會不會 overflow、某個 32 位元常數在大小端下存出來的位元組序列是否相同
• 第 17 題（4%）｜IEEE754 的四個敘述：與 107 年第 8 題幾乎完全相同，只換了其中一個數字。涵蓋某個指數極小的數能不能以 normalized 形式表示、最小正 normalized number、最小正 denormalized number
• 第 18 題（4%）｜第 8 個週期時兩個 ALU 輸入從哪來：程式為 add x28,x31,x29 → ld x31,32(x29) → and x30,x29,x31 → sd x5,20(x30) → sub x5,x5,x30 → or x29,x29,x30
• 第 19 題（4%）｜branch prediction 失敗造成的額外 CPI：與 107 年第 9 題一字不差，R-type 50%、beq 25%、lw/sw 25%、預測準確率 20%。問在不同 pipeline stage 修正分支時的額外 CPI
• 第 20 題（4%）｜2-bit predictor 從強烈預測 taken 開始：分支結果序列 N, T, N, N, T。要追蹤 state machine 並算出準確率，再判斷模式重複兩次、三次、一萬次時的整體準確率

題組（21–34，20 分）

• 題組 A（21–24，5%）｜四顆 1 TB 磁碟的 RAID 5（讀寫 throughput 各 100 MB/s）
• 第 21 題｜可儲存的容量
• 第 22 題｜最大讀取 throughput
• 第 23 題｜最多容忍幾顆故障
• 第 24 題｜寫入時最少要動幾顆碟
• 題組 B（25–27，5%）｜multi-level page table 的最少層數：頁面 32 KB、virtual address space 2⁶⁴、page table entry 16 B，題目說只有一個 register 存最上層的 physical address
• 第 25 題｜最少層數
• 第 26 題｜最底層最多有幾頁
• 第 27 題｜multi-level page table 的最上層佔幾頁
• 題組 C（28–30，5%）｜64 KB、4-way、64-byte block 的 L1：32-bit 位址、physical memory 4 GB
• 第 28 題｜block 數
• 第 29 題｜tag 位元數
• 第 30 題｜位址從 32-bit 增加到 64-bit 時哪個欄位會變大
• 題組 D（31–34，5%）｜五級 pipeline 的第 5 個週期狀態：程式為 ld x31,32(x5) → sub x30,x31,x5 → ld x31,20(x30) → add x29,x29,x30 → or x5,x5,x30
• 第 31 題｜第 5 週期時 EXE 級是哪道指令
• 第 32 題｜第 5 週期時 MEM 級是哪道指令
• 第 33 題｜第 5 週期時 WB 級是哪道指令
• 第 34 題｜第 5 週期時 ALUsrc 與 MemToReg 的值

作答時要注意的地方

1. 複選題答錯 −1，下限是整科 0 分。
2. 題組各小題為單選，組內全對才給 5 分。題組 D 四小題共用同一張 pipeline 時序圖。
3. 題組 B 三個小題環環相扣，第 25 題的層數會用到後面兩題。
4. 第 14 題要用到程式讀的位址在 direct-mapped 與 2-way 下的對應。

準備方向

• 重複出題：114 第 19 題 = 107 第 9 題、114 第 17 題 ≈ 107 第 8 題、114 第 7 題 ≈ 109 題組 B、114 題組 A ≈ 112 題組 A。
• branch prediction 失敗的額外 CPI（114 第 19 題）。
• IEEE754 的邊界值：107、114 各考一次。
• multi-level page table 的層數推導（114 題組 B）。
• cache 欄位與位址長度的關係（114 題組 C）。
• /proc/.../maps 的判讀（114 第 7 題）。