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

題型與配分

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

複選題計分與 106–108 年相同。

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

複選題（1–20，80 分）

• 第 1 題（4%）｜現代 OS：三個敘述考 microkernel 的效能代價、shared memory 要用到哪些 system call、DMA 對 interrupt 次數的影響
• 第 2 題（4%）｜process 與 thread：四個敘述考 thread 是否共享 PC、exec() 之後 process ID 的變化、blocking I/O 之後 process 去了哪個 queue、interrupt 能否強制讓 process 離開 CPU
• 第 3 題（4%）｜producer-consumer 的 semaphore 與 critical section 分段：緩衝區 n = 5，程式碼被切成 PA–PE 與 CA–CE 十段。三個敘述考 empty 的初值、同時能有幾個消費者進入 Section CA、單生產單消費時 mutex 是否多餘
• 第 4 題（4%）｜Banker's algorithm 的 safe sequence：五個 process、三種資源，給 Allocation、MAX、Available。要驗證 <P4,P1,P2,P3,P5> 與 <P1,P3,P5,P4,P2> 是不是 safe sequence，並判斷「OS 必須在 process 進入就緒佇列時估計 MAX」
• 第 5 題（4%）｜pthread 與 semaphore：三條 thread 各跑 func，共享的 m 有 mutex 保護、區域的 n 沒有。四個敘述考是否有 race condition、所有輸出數字的總和、"2" 最多被印幾次、哪些變數被共享
• 第 6 題（4%）｜stack 與 heap：四個敘述考兩者的釋放順序限制、每條 thread 各自擁有哪一個
• 第 7 題（4%）｜四顆同容量硬碟要容忍單碟故障，哪些 RAID 等級可以
• 第 8 題（4%）｜page table：四個敘述考每個 process 是否有獨立的 virtual address space、Linux process 的 page table 由誰管理、shared memory 對 page table entry 數的影響、未使用區域的 page table 開銷
• 第 9 題（4%）｜建立檔案並寫入會涉及哪些 file system 操作：取得空閒 i-node、更新目錄 d、取得空閒資料 block 並連結、把 "hello" 寫入資料 block
• 第 10 題（4%）｜HTTPS 的保護範圍：四個敘述考 ISP 能否看出你在瀏覽哪個網站、能否看到頁面內容、從 process 記憶體或磁碟 cache 能否得知頁面內容
• 第 11 題（4%）｜算術與 overflow：四個敘述考 addi 與 lb 是否需要 sign extension、n-bit two's complement 的範圍式、用最高位的 carry-in 與 carry-out 偵測 overflow、大正數加大負數會不會 overflow
• 第 12 題（4%）｜位元組序無關的十六進位資料：56788765、56787856、56655665、55665566 四選，問哪些在大小端下儲存順序相同
• 第 13 題（4%）｜效能與功耗：四個敘述考 pipelining 改善的是什麼、CPI 受哪些因素影響、clock 2.5→2 GHz、電壓 1.2→0.9 V 時功耗降低多少、56% 可平行、8 核能否達到 2 倍加速
• 第 14 題（4%）｜哪些 MIPS 指令不是 R-type：addi、bne、sll、jr 四選
• 第 15 題（4%）｜術語與 floating point：四個敘述考 branch delay slot 與 basic block 的定義、issue slot 的定義、0.3125 × 2³⁰ 能否被 single precision 精確表示、float 轉 double 是否可能損失精度
• 第 16 題（4%）｜看 datapath 圖與 ALU 控制表回答：beq 執行時需要哪些元件，以及 BInvert control signal 的最佳設計應該包含哪些運算
• 第 17 題（4%）｜平行處理器：四個敘述考 vector processor 的取指 bandwidth、vector processor 與 load-use hazard、warehouse-scale computer 的主要維護問題、Omega 網路能否同時完成 P0→P0 與 P1→P4
• 第 18 題（4%）｜問哪些敘述是錯的：四個敘述考 RegWrite control signal 在哪一級使用、需不需要經過 pipeline register、雙重 data hazard 的偵測條件式、load-use hazard 要停幾拍、reservation station 的描述
• 第 19 題（4%）｜記憶體設計：四個敘述考 temporal locality 的例子、direct-mapped cache 中 0xB50 與 0xB54 落在哪個 block（32 block、每 block 32 bytes）、block 太大的壞處、兩層 cache 的有效 CPI（4 GHz、base CPI 1.0、L1 miss rate 2%、L2 3 ns、main memory 75 ns、global miss rate 0.4%）
• 第 20 題（4%）｜提升 throughput 的技術：(a) store 在前、load 在後時是否需要推測 (b)(c)(d) static dual-issue 與 loop unrolling，要填出展開後六個 offset A–F 的值。原程式是位址遞減，與 107 年第 10 題同型

題組（21–33，20 分）

• 題組 A（21–24，5%）｜SRTF 的 waiting time 四進位拆解：五個 process 給到達時間與 burst，用 preemptive 的 shortest-remaining-time-first scheduling，算出 waiting time W 後寫成 W₃×4³ + W₂×4² + W₁×4¹ + W₀，四小題各問一位。與 108 年題組 A 同一個設計（那年是 RR 的 turnaround time）
• 題組 B（25–27，5%）｜判讀 /proc/self/maps：卷上貼出 cat process 的真實記憶體映射表
• 第 25 題｜哪個區間含 cat 的可執行碼
• 第 26 題｜哪個是含 C 函式庫可執行碼的 physical address 範圍
• 第 27 題｜換出頁面時的四個敘述，考有檔案支撐的頁與匿名頁在換出時的差別
• 題組 C（28–30，5%）｜1-bit ALU 串接 32 級的最壞 propagation delay：給各元件延遲（NOT 1、AND 1、OR 1、2-to-1 mux 2、4-to-1 mux 4、full adder 3、overflow 偵測 3）
• 第 28 題｜32-bit NOR 的最壞延遲
• 第 29 題｜32-bit ADD 的最壞延遲
• 第 30 題｜SLT 的最壞延遲
• 題組 D（31–33，5%）｜(7,4) Hamming code 的除錯：碼字為 c1,c2,d1,c3,d2,d3,d4，滿足三條同位方程式；再加一個整體同位位元 c4 後可偵測兩位元錯誤
• 第 31 題｜收到 7-bit 1101100，判斷是否正確或哪一位錯
• 第 32 題｜收到 8-bit 10110101
• 第 33 題｜收到 8-bit 10001011，選項含雙位元錯誤

作答時要注意的地方

1. 複選題答對一個選項 +1、答錯一個 −2，整題未作答不給分。
2. 題組 C 三小題全對才給 5 分。
3. 題組 B 第 26 題問的是 physical address 範圍。
4. 第 12 題問的是儲存順序，以位元組為單位。
5. 第 18 題問的是哪些敘述是錯的。

準備方向

• 把答案拆成四進位四位數的題組：108 題組 A、109 題組 A。
• 1-bit ALU 串接的延遲（109 題組 C），110 題組 C 也考 1-bit ALU。
• Hamming code 的編碼與除錯（109 題組 D）。
• /proc/self/maps 的判讀（109 題組 B）。
• HTTPS 的保護範圍（109 第 10 題）。
• MIPS 指令格式（109 第 14 題）。