109 中正資工所考古題詳解｜硬體考點分析

題型與配分

全卷 5 頁、11 題、100 分。答案寫在試卷（答案卷）作答區內，限用藍色或黑色筆（含鉛筆），試題須隨試卷繳還。入場後 40 分鐘內不得離場。卷面沒有倒扣規定。

第 1 題：十個單選（20%）

• 第 1(1) 題｜log-structured file system 當機時必定發生什麼事
• 第 1(2) 題｜parent 與 child process 先共用同一批頁面、任一方修改時才複製的機制
• 第 1(3) 題｜關於 safe state、unsafe state 與 deadlocked state 的敘述，哪一項為真
• 第 1(4) 題｜file-allocation table（FAT）屬於哪一種配置方式
• 第 1(5) 題｜critical section 問題的解法不必滿足哪一項要求
• 第 1(6) 題｜哪一項工作可以由 user mode 的應用程式直接完成
• 第 1(7) 題｜process 產生合法範圍以外的位址時，立即的結果是什麼
• 第 1(8) 題｜Linux 工作通常用哪個 system call 啟動自己的另一份副本
• 第 1(9) 題｜Multilevel Feedback Queue 之下 CPU 時間如何在各 queue 間分配
• 第 1(10) 題｜page table 項目中的 valid 位元在實作 virtual memory 之後改變了什麼意義

第 2 題至第 11 題

• 第 2 題（5%）｜file system 用 inode，磁碟 block 8 KB，指向 block 的 pointer 4 bytes，有 12 個 direct block 加上單層、雙層與三層 indirect block，問可存放的最大檔案大小
• 第 3 題（13%）｜NAND flash 的 SSD 與 FTL（address translator、garbage collector、wear leveler）。(1) 4%：NAND flash 的兩個先天限制。(2) 6%：garbage collector 與 wear leveler 的功能。(3) 3%：什麼是 over-provisioning space，如何改善 garbage collection 或 wear leveling 的效能
• 第 4 題（6%）｜給五個 process（P0–P4）與四種資源（A–D）的 Allocation 與 Max 表，用 Banker's algorithm 判斷兩種 Available（1,4,1,2）與（2,1,1,3）是否安全，安全的要寫出完成順序，不安全的要說明原因
• 第 5 題（6%）｜demand paging 系統的使用率為 CPU 20%、paging disk 97.7%、其他 I/O 裝置 5%，提出三種提高 CPU 使用率的方法，並簡述理由
• 第 6 題（5%）｜兩台 instruction set 相同的機器 P 與 Q，CPI 分別為 2.0 與 1.0，P 的 clock cycle 250 ps，Q 的 clock rate 2.0 GHz，比較兩者對任何程式的效能
• 第 7 題（5%）｜五級 pipeline 各級延遲為 5、4、6、10、5 ns，沒有 stall，執行 N 道指令的最短時間
• 第 8 題（5%）｜處理器 2.5 GHz，指令 cache 與資料 cache 分開，全部 hit 時 CPI 為 2，miss penalty 20 ns，20% 的指令存取記憶體，指令 cache miss rate 2%、資料 cache miss rate 5%，求實際 CPI
• 第 9 題（10%）｜CNN convolution：3×4 輸入圖、2×2 kernel、2×3 輸出 feature map，輸入與 kernel 參數都用 IEEE 754 single precision，輸入 a 到 l 的值為 0xc0800000，kernel w、x、y、z 的值為 0x40000000，算出輸出 feature map 並用 single precision 格式表示
• 第 10 題（15%）｜(1) 用時序圖畫出 flip-flop 的 setup time、clock-to-q delay 與 hold time。(2) 以 T_setup、T_clk-to-q、T_hold 與 datapath 的 critical path 延遲 T_cp 表示 synchronous circuit 的最小 clock cycle。(3) 用 Amdahl's law 說明為什麼把 datapath 切成 N 級 pipeline 無法達到理想的 N 倍加速
• 第 11 題（10%）｜用最少的 flip-flop（T_setup = 10 ps、T_clk-to-q = 10 ps、T_hold = 30 ps）與 inverter（延遲 50 ps）設計 4 位元移位 register，畫出邏輯圖、標出 critical path，並求最高操作頻率

作答時要注意的地方

1. 全卷沒有倒扣規定，第 1 題每題 2 分。
2. 第 4 題兩組 Available 都要判斷，安全的寫出完成順序，不安全的說明原因。
3. 第 9 題的輸入與 kernel 都以十六進位的 single precision 格式給定。
4. 第 10、11 題要畫時序圖與邏輯圖。

準備方向

• Banker's algorithm（109 第 4 題），110 第 4 題、112 填空第 3 題也有。
• inode 的最大檔案大小（109 第 2 題），107 第 2 題的數據完全相同，110 第 5 題也有。
• 數位邏輯：flip-flop 時序與最小 clock cycle（109 第 10、11 題），106 第 9、10 題、110 第 6 題也有。
• CNN convolution（109 第 9 題），108 第 6、7 題用同一張圖算延遲與週期，106、107 年考 neural network 的延遲與週期數。
• 含 cache miss 的 CPI（109 第 8 題），111 第 3 題、112 填空第 6 題也有 CPU 效能方程式。
• MLFQ 的 CPU 時間分配（109 第 1(9) 題），108 第 1(4) 題、113 第 1(7) 題也有。
• valid 位元（109 第 1(10) 題），107 第 1(9) 題、111 第 1(7) 題也有。
• process 產生非法位址的立即結果（109 第 1(7) 題），107 第 1(2) 題、113 第 1(1) 題也有。
• user mode 能直接做的事（109 第 1(6) 題）在 106 第 1(1) 題，Linux 啟動自己的副本（109 第 1(8) 題）在 107 第 1(6) 題也有。
• Copy-on-write 與 safe state 的觀念（109 第 1(2)(3) 題），115 第 6 題考 copy-on-write，108 第 2 題考 safe state。